zengo-x / multi-party-ecdsa Goto Github PK

Run with: seq 50 | xargs -Iz cargo test:

---- test_two_party_keygen stdout ----
thread 'test_two_party_keygen' panicked at 'assertion failed: party_two::PaillierPublic::verify_range_proof(&party_two_paillier, &challenge,
                                              &encrypted_pairs, &proof)', tests/keygen_integ_test.rs:53:5
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
stack backtrace:
   0: std::sys::unix::backtrace::tracing::imp::unwind_backtrace
             at libstd/sys/unix/backtrace/tracing/gcc_s.rs:49
   1: std::sys_common::backtrace::print
             at libstd/sys_common/backtrace.rs:71
             at libstd/sys_common/backtrace.rs:59
   2: std::panicking::default_hook::{{closure}}
             at libstd/panicking.rs:211
   3: std::panicking::default_hook
             at libstd/panicking.rs:221
   4: <std::panicking::begin_panic::PanicPayload<A> as core::panic::BoxMeUp>::get
             at libstd/panicking.rs:475
   5: secp256k1_sha256_transform
             at /Users/travis/build/rust-lang/rust/src/libstd/panicking.rs:409
   6: keygen_integ_test::test_two_party_keygen
             at tests/keygen_integ_test.rs:53
   7: keygen_integ_test::__test::TESTS::{{closure}}
             at tests/keygen_integ_test.rs:8
   8: core::ops::function::FnOnce::call_once
             at /Users/travis/build/rust-lang/rust/src/libcore/ops/function.rs:223
   9: <F as alloc::boxed::FnBox<A>>::call_box
             at libtest/lib.rs:1454
             at /Users/travis/build/rust-lang/rust/src/libcore/ops/function.rs:223
             at /Users/travis/build/rust-lang/rust/src/liballoc/boxed.rs:640
  10: panic_unwind::dwarf::eh::read_encoded_pointer
             at libpanic_unwind/lib.rs:106


failures:
    test_two_party_keygen

test result: FAILED. 0 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out

Create utility functions for Elliptic curve and Big number manipulation relying on a basic Point (x,y).

Secure Two-party Threshold ECDSA from ECDSA Assumptions (https://eprint.iacr.org/2018/499.pdf) is a work done by Doerner et al. The PoC code is provided in https://gitlab.com/neucrypt/mpecdsa . The code is provided under the Three-clause BSD License. For initial support we should:

• switch to secp256k1 lib (the original code currently using its own elliptic curve implementation).
• switch to cryptographic-utils (https://github.com/KZen-networks/cryptography-utils) instead of what they use for simple cryptographic protocols and arithmetic.
• delete communication layer (so that later we can add our own)
• code review for secure programming
• code optimizations

Add unit tests for Modulo trait: https://github.com/KZen-networks/multi-party-ecdsa/blob/master/src/arithmetic/big_gmp.rs#L32.

rust-paillier has been updated from n to nn. This change should effect the benchmark of keygen.

First Step
take the hash of the public key to be a token.
save to local storage (cache):

1. id for token
2. next for next function for this token

place a test at the beginning of every function for party_one,party_two such that only if :

1. the token id is registered in the storage
2. the function that is being called is next

Then execute the function and update next, otherwise abort.

After the last function of the protocol has been called - clean the id from storage

Second Step
make a token that will connect between key generation and signing so that the signing parties in case they run Key Generation multiple times will know which private key to use for signing.
suggestion: use the local public keys (H(secret_share * G)) to identify keys. This should be saved to permanent storage.

ZenGo-X/curv#58

ZenGo-X/curv#51

I would like to start a thread about how to properly unit test two party ECDSA.
Each function should be tested independently. It is obvious on how to inject edge cases as well as dummy values, the question here is how to unit test that values returned are expected (without any interaction with the other party (E.g. the client).

Thoughts?

Suggesting that you might relicense this project under MIT or BSD or Public Domain.

Many cryptographic libraries are licensed as such (e.g., secp256k1, libsnark, nacl, etc).

This makes it easier to include them in a diverse set of projects, and is more likely to get attention from outside contributors.

GPL is a fine license and has many benefits, so I understand the desire to use it, but for crypto libraries something more permissive is probably appropriate.

Setup travis for CI and automatic unit test. See: https://github.com/dwyl/learn-travis.

Lindell's Key Generation [1] protocol could be adapted to support {2,3}-threshold Signing if we implement the functionality F_rand from [2] for generating shares of random values non-interactively.

1. each party i chooses a random number r_i and sends it to party i+1.

• The full private key will be r_1 * r_2 * r_3
  The roles of the Prover (party1 in Lindell's protocol) and the Verifier (party2 in Lindell's protocol) and their corresponding secret shares will be defined according to the following rules:
  rule 1: Each party will play the Prover for the party that received its r_i and will play the Verifier for the party that sent to it r_(i-1)
  rule 2: The private share of the Prover will always be r_i * r_(i-1) and the Verifier private key will always be r_(i+1)

2. Each party i calculates alpha_i = r_(i-1)*G - r_i*G and send it to the other two parties
3. Each party checks that sum(alpha_i) = 0, and aborts otherwise
4. Every two parties do the following (designation of prover/verifier is according to rule1) :

• The Prover party P_(i-1) defines x_1 = r_(i-1)*r_(i-2) and sends Q_1 = x_1*G to the Verifier, indexed i.
• The Verifier V_i checks that Q_1 = r_(i-1) * [alpha_(i-1) + r_(i-1)*G], and aborts otherwise
• The Verifier V_i defines x_2 = r_i and send Q_2 =x_2 * G to the Prover
• The prover P_(i-1) checks that Q_2 = alpha_(i-2) + r_(i-1)*G, and aborts otherwise

5. The Prover and Verifier engage with Lindell's Key Generation protocol as Party1 and Party2 respectively.

Lindell's signing protocol stays the same.
Note: numbering in this protocol is circular, for example for P_1 and V_2 we get x_1 = r_1*r_3 and alpha_1 = r_3*G - r_1*G.

[1] Y. Lindell. Fast Secure Two-Party ECDSA Signing - CRYPTO 2017 (Proceedings, Part II), volume 10402 of LNCS, pages 613–644. Springer,
2017
[2] Y. Lindell, A. Nof. A Framework for Constructing Fast MPC over Arithmetic Circuits with Malicious Adversaries and an Honest-Majority. pages 259-276. CCS 2017

Two-Party ECDSA from Hash Proof Systems and
Efficient Instantiations (https://eprint.iacr.org/2019/503.pdf, Crypto19') is similar to Lindell17 but provides tight security and maybe performance improvement.
It is required to implement the paper and evaluate it in comparison to Lindell17.

After writing benches which execute signing many times, here is what I see:

thread 'main' panicked at 'assertion failed: party_one::verify(&ec_context, &signature, &pubkey, &message).is_ok()', benches/two_party_ecdsa/lindell_2017/signing.rs:68:13
stack backtrace:
   0: std::sys::unix::backtrace::tracing::imp::unwind_backtrace
   1: std::sys_common::backtrace::print
   2: std::panicking::default_hook::{{closure}}
   3: std::panicking::default_hook
   4: std::panicking::rust_panic_with_hook
   5: std::panicking::begin_panic
   6: bencher::Bencher::iter
   7: bencher::Bencher::auto_bench
   8: bencher::run_tests_console
   9: signing::main
  10: std::rt::lang_start::{{closure}}
  11: std::panicking::try::do_call
  12: __rust_maybe_catch_panic
  13: std::rt::lang_start_internal
  14: main

https://github.com/zkcrypto/ff contain Traits and utilities for working with finite fields.
Before using it let's test how it can fits in our design. i.e. use it instead of mod_mul or mod_sub

Write the discrete log proof to be used by both client and server.

Add proper unit testing for: https://github.com/KZen-networks/multi-party-ecdsa/blob/master/src/cryptographic_primitives/commitments/hash_commitment.rs#L23.

follow the multi-party-ecdsa demo, when keygen use gg18_keygen_client, the output file keys.store, that is a json file.
what's the mean of all fields ? especially how to generate the pubkey based on keys.store file ?

https://eprint.iacr.org/2017/552.pdf section 4.3 is new. The bottom line is to change the dlog zero knowledge proof of knowledge in the signing protocol to proof of ec-ddh membership

https://github.com/zkcrypto/group
depends on #18

would allow us to abstract for many elliptic curves

Issue stub to integrate changes required to run on Android

Currently recid is implemented and returned only in two_party_ecdsa signature, but there is no way to receive it after signing using multi_party_ecdsa protocol.

Identifiable Abort in Threshold Signatures (IATS) - problem statement

Informally, IATS is a way for honest parties to either output a valid signature or to agree on the set of parties that behaved maliciously in the computation.
Formally, there are various security properties that allow for different levels of “accountability” in MPC . Taken from https://eprint.iacr.org/2016/611.pdf here is an example of Openability and Auditability properties and how they can be dressed on top of MPC ideal functionality. In our case we are mainly concerned with Identifiable Abort or better Public Verifiability which allows honest parties to prove to a third party (did not participate in the computation) that a given party behaved in a malicious way. (https://eprint.iacr.org/2016/187.pdf section 8)

Few other papers that are dealing with “Accountability” properties of MPC are:
https://eprint.iacr.org/2014/075.pdf,
https://link.springer.com/chapter/10.1007/978-3-319-49175-2_8 ,
https://eprint.iacr.org/2015/058.pdf ,
https://eprint.iacr.org/2018/942
A related properties are those of fairness and guaranteed output delivery in MPC.

The motivation is very simple. We wish to allow honest signers of a threshold signature to fight against Denial of Service by a small set of malicious parties that deliberately fails the computation time after time. In other words we want to preserve Liveness as long as there are less than threshold malicious parties participating. This can be translated to a “Blame” phase in protocol that rely on threshold signing. It is most critical in a n-out-of-n setting where all parties must be honest in order for the signature to be valid. An attacker can fail the signing each time and there will be no tool for the n parties to prove learn which one of them is the attacker.

https://github.com/binance-chain/tss-lib implements GG18.
We would like to add benchmarks and comparison to tss-lib key generation and signing run locally between different t and n parameters.

Benchmark code for this library exists: https://github.com/KZen-networks/multi-party-ecdsa/tree/master/benches/multi_party_ecdsa/gg18

implement Setup, Lock, Rel from Anonymous Multi-Hop Locks for Blockchain
Scalability and Interoperability based on lindell 2p ecdsa

The new library for zero knowledge proof based on paillier cryptosystem is in: https://github.com/KZen-networks/zk-paillier and the code should use this library at all places where currently rust-paillier is used directly

Let's take KeyGenBroadcastMessage1 in gg2018 as an example. It can be improved since:

1. Broadcast has no more information except that we should broadcast this kind of message, but we may also broadcast other messages, thus, the Broadcast should not be used here.

2. Actually it's Commit, Decommit = Com(pk, M, R) in the paper, it can be simply called KeyGenCommit

Currently we have only keyGen benches:

• we need to update keygen benchs (currently there are compilation errors)
• we need to add signing benchs

Write SecondMsgClientProofVerification of party 1, it can be inspired by the following code that we wrote in the past. Also make sure to document that properly (or create a follow up issue).

pub struct SecondMsgClientProofVerification {
    pk_commitment_blind_factor: BigUint,
    zk_pok_blind_factor: BigUint,

    pk: PublicKey,
    pk_t_rand_commitment : PublicKey,
    challenge_response : BigUint,
}

impl SecondMsgClientProofVerification {
    pub fn create(s: &Secp256k1,
                  client_pk_t_rand_commitment: &PublicKey,
                  client_challenge_response: &BigUint,
                  client_pk: &PublicKey) -> Result<(), &'static str>
    {
        //TODO: change. challenge is not a commitment, it is a hash function.
        let challenge = MPCUtils::get_commitment(
            vec![
                &client_pk_t_rand_commitment.to_point().x,
                &s.get_base_point().x,
                &client_pk.to_point().x],
            &Secp256k1::get_q());

        let mut client_pk_challenge = client_pk.clone();
        assert!(client_pk_challenge.mul_assign(&s, &SecretKey::from_big_uint(s, &challenge)).is_ok());

        let mut pk_verifier = PublicKey::to_key(&s, &s.get_base_point());
        assert!(pk_verifier.mul_assign(
            s, &SecretKey::from_big_uint(s, client_challenge_response)).is_ok());

        assert!(pk_verifier.combine(&s, &client_pk_challenge).is_ok());

        if pk_verifier == *client_pk_t_rand_commitment {
            Ok(())
        } else {
            Err("Error during the zero knowledge proof of knowledge of the client private key!")
        }

        // TODO: use local in-memory hash to output SecondMsgClientProofVerification
    }
}

To reproduce, in: multi-party-ecdsa/src/cryptographic_primitives/commitments/hash_commitment.rs, you can add a for loop in the test itself:

    #[test]
    fn test_bit_length_create_commitment() {
        for _ in 1..100 {
            let message = BigInt::sample(SECURITY_BITS);
            let (commitment, blind_factor) = HashCommitment::create_commitment(&message);
            //test commitment length  - works because SHA256 output length the same as sec_bits
            assert_eq!(commitment.to_str_radix(16).len(), SECURITY_BITS / 4);
            assert_eq!(blind_factor.to_str_radix(16).len(), SECURITY_BITS / 4);
        }
    }

---- cryptographic_primitives::commitments::hash_commitment::tests::test_bit_length_create_commitment stdout ----
	thread 'cryptographic_primitives::commitments::hash_commitment::tests::test_bit_length_create_commitment' panicked at 'assertion failed: `(left == right)`
  left: `63`,
 right: `64`', src/cryptographic_primitives/commitments/hash_commitment.rs:69:13
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
stack backtrace:

They have the same interface. Just need to change to use line

Consumers of the app probably want to use a single protocol.
They should be able to choose which one and build only for him.
Currently there's a single feature to enable CCLST19 on top of GG18 and L17

Run with: seq 50 | xargs -Iz cargo test:

failures:

---- protocols::two_party_ecdsa::lindell_2017::test::tests::test_d_log_proof_party_two_party_one stdout ----
thread 'protocols::two_party_ecdsa::lindell_2017::test::tests::test_d_log_proof_party_two_party_one' panicked at 'assertion failed: party_two_seco
nd_message.d_log_proof_result.is_ok()', src/protocols/two_party_ecdsa/lindell_2017/test.rs:26:9
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
stack backtrace:
   0: std::sys::unix::backtrace::tracing::imp::unwind_backtrace
             at libstd/sys/unix/backtrace/tracing/gcc_s.rs:49
   1: std::sys_common::backtrace::print
             at libstd/sys_common/backtrace.rs:71
             at libstd/sys_common/backtrace.rs:59
   2: std::panicking::default_hook::{{closure}}
             at libstd/panicking.rs:211
   3: std::panicking::default_hook
             at libstd/panicking.rs:221
   4: <std::panicking::begin_panic::PanicPayload<A> as core::panic::BoxMeUp>::get
             at libstd/panicking.rs:475
   5: secp256k1_sha256_transform
             at /Users/travis/build/rust-lang/rust/src/libstd/panicking.rs:409
   6: multi_party_ecdsa::protocols::two_party_ecdsa::lindell_2017::test::tests::test_d_log_proof_party_two_party_one
             at src/protocols/two_party_ecdsa/lindell_2017/test.rs:26
   7: multi_party_ecdsa::__test::TESTS::{{closure}}
             at src/protocols/two_party_ecdsa/lindell_2017/test.rs:9
   8: core::ops::function::FnOnce::call_once
             at /Users/travis/build/rust-lang/rust/src/libcore/ops/function.rs:223
   9: <F as alloc::boxed::FnBox<A>>::call_box
             at libtest/lib.rs:1454
             at /Users/travis/build/rust-lang/rust/src/libcore/ops/function.rs:223
             at /Users/travis/build/rust-lang/rust/src/liballoc/boxed.rs:640
  10: panic_unwind::dwarf::eh::read_encoded_pointer
             at libpanic_unwind/lib.rs:106


failures:
    protocols::two_party_ecdsa::lindell_2017::test::tests::test_d_log_proof_party_two_party_one

test result: FAILED. 0 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out

there's a redundancy where the same code for ECDH is found in curv:
https://github.com/KZen-networks/curv/blob/master/src/cryptographic_primitives/twoparty/dh_key_exchange.rs
and is alos used by 2p-ecdsa for key generation and ephemeral key generation.
The only difference is that in 2p-ecdsa, party 1 must choose x1 < q/3 (for q curve order) for the range proof later to work. this can be done by generating x1 in this lib such that the condition holds and call curv ECDH with predefined randomness.

based on protocol 3.2 in https://eprint.iacr.org/2017/552.pdf :

• steps 1,2,3 are identical to Key Generation protocol but with ephemeral secret keys
• steps 4,5 require use of Paillier cryptosystem. Using the same ek and dk from Key Generation protocol. We can use https://github.com/mortendahl/rust-paillier for Paillier.

The purpose of this task is to build a proof of concept for running this code on iOS.
Nice to have: simple benches that we will be able to compare with benches running on a machine.

Success criteria:

• Ability to call locally at least one function of 2-party ECDSA on iOS
• Documentation on how to run
• Simple benches (execution time for functions of your choice)

Write Rust doc for Lindell 2017 2P-ECDSA (https://doc.rust-lang.org/book/first-edition/documentation.html). Mention in the doc papers, math formula and plain english description.

See: https://github.com/KZen-networks/multi-party-ecdsa/blob/master/src/protocols/two_party_ecdsa/lindell_2017/party_one.rs#L51

In the multi-party ECDSA case, in mta.rs, in impl MessageA the range proofs are not
included for Alice, and in impl MessageB, instead it is only computing a proof of
knowledge of a discrete logarithm of bG instead of proving that b is in the
appropriate range as per page 8 of GG18, where it says Bob should be proving in ZK
that b < K

The rational why we might want to have the range proof is in GG18 on page 9,
basically it would allow a malicious party to make the threshold signature fail
verification and let them go unblamed.

Motivation to drop the range proofs is discussed in Section 5 (page 19) of the paper but we think that it should be optional.

example: https://github.com/KZen-networks/multi-party-ecdsa/blob/master/src/protocols/multi_party_ecdsa/gg_2018/party_i.rs#L202

Should be replaced with an Err returned to the caller

This issue is dependent of #5. Code has been added to https://github.com/mortendahl/rust-paillier in order to do this. Need to be use in 2 party ECDSA.

Hi. I am using 0.2.8 version of multi-party-ecdsa.
In particular, I have used {1,3} party scheme.
I have recently faced with the following error during signature generation process:

DEBUG: number: 1, uuid: "0x2c658b237993db261cb073e6d9d985ea0383441380cc1fd47f55993e2d35ef18"
DEBUG: ["round0"] party 2 => party 1
DEBUG: ["round1"] party 2 => party 1
DEBUG: ["round2"] party 2 => party 1
DEBUG: ["round3"] party 2 => party 1
DEBUG: ["round4"] party 2 => party 1
DEBUG: ["round5"] party 2 => party 1
DEBUG: ["round6"] party 2 => party 1
DEBUG: ["round7"] party 2 => party 1
DEBUG: ["round8"] party 2 => party 1
DEBUG: ["round9"] party 2 => party 1
DEBUG: party 1 Output Signature: 

R: SecretKey(782b3aef10b775721336204d593683bdf2bd57b2cbd43e7e05073f3db5507dbb)
s: SecretKey(28c35476586b15d1dba7ab8c7cef8a1ab6c333cbf8a3aae06df7d3edb3aad1f9) 


DEBUG: thread 'main' panicked at 'called `Result::unwrap()` on an `Err` value: InvalidPublicKey', src/libcore/result.rs:1165:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace.

Signatures generation was restarted several times, but this did not help, the same error appeared every time.
Unfortunately, I was not able to reproduce this issue with more verbose logging.

we changed range proof ni api [1]. we need to apply this change here as well.

[1] https://github.com/mortendahl/rust-paillier/blob/changes_to_range_proof_ni/src/proof/range_proof_ni.rs

usize in Rust is for something related with memory address offset, not for counting number.

Ref: https://users.rust-lang.org/t/i32-vs-isize-u32-vs-usize/22657/2

Tezos is currently using https://github.com/project-everest/hacl-star.

We need to add support for ed25519 (likely be in https://github.com/KZen-networks/cryptography-utils) to support Tezos for 2 party ECDSA.

While running protocols::two_party_ecdsa::cclst_2019::test::tests::test_two_party_sign or protocols::two_party_ecdsa::cclst_2019::test::tests::test_full_key_gen is always working and passing. Trying to just cargo test --features=cclst returns a PARI error. Each time a different one:

It can sometimes work, while other times the following errors are received:

  ***   the PARI stack overflows !
  current stack size: 10000000 (9.537 Mbytes)
  [hint] set 'parisizemax' to a non-zero value in your GPRC

  ***   ***   Error in the PARI system. End of program.
  unknown type 31.  ***   Error in the PARI system. End of program

  ***   
the PARI stack overflows !
  current stack size: 10000000 (9.537 Mbytes)
  [hint] set 'parisizemax' to a non-zero value in your GPRC
  ***   Error in the PARI system. End of program.

  ***   unknown type 26.  ***   Error in the PARI system. End of program.

Might be connected topari_init in class_groups lib

Rust-paillier https://github.com/mortendahl/rust-paillier contains zk proofs that we need for 2-party ECDSA.

Those proof are currently in a dev branch, if not "mergeable" in master, fork this repo in KZen-networks and merge dev in master.

Currently the code is tailored for secp256k1_lib. To enable use of other EC libs we abstract the EC from the code, see https://github.com/KZen-networks/multi-party-ed25519 for example.
Please use https://github.com/KZen-networks/cryptography-utils/tree/rewrite_ec_abstract/src/elliptic to refactor the code for multiple ECs

ld: library not found for -lgmp
clang: error: linker command failed with exit code 1

rustc --version
rustc 1.36.0-nightly (a9ec99f42 2019-05-13)

Add De/Serialization for structures that are exposed to the server.

partial list:

1. minimize binary size
2. separate programs for Prover/Verifier for two parties use case