Skip to content

Latest commit

 

History

History
182 lines (123 loc) · 10.2 KB

0005-kzen-two-party-ecdsa.adoc

File metadata and controls

182 lines (123 loc) · 10.2 KB
Raw

Kzen Two Party ECDSA Review

Table of Contents

  • Authors(s): Lloyd Fournier

  • Date: 2019-05-10

Issue: #897

Context

In order to do an atomic swap with Scriptless Scripts using the ECDSA protocol described in [Sanchez18a] we need to have an implementation of [Lindell17]. The point of this spike is to review [Lindell17] and KZen’s rust implementation [kzen_mp_ecdsa].

Outcome Summary

KZen’s [kzen_mp_ecdsa] should work for us. The code itself is easily good enough for the PoC implementation of [Sanchez18a]. Most of the proofs we need are in their own modules and exposed in a straightforward way. The protocols are implemented pretty strictly to how they are described in the papers which is nice.

Protocol Overview

[Lindell17] describes a two-party protocol to (i) generate a joint public key and (ii) jointly create ECDSA signatures under that public key. The technical term for this is key aggregation. Lindell summarizes his paper in the following video.

Signature schemes with aggregated keys are a nice thing to have. They look exactly like normal signatures but are produced by multiple parties instead of one. Practically, this means you do not need to lock Bitcoin to multiple public keys and check the signature with OP_CHECKMULTISIG; you can just lock it to a joint public key using a normal P2WSH output (i.e. use OP_CHECKSIG). There is no way to tell the difference between a single user P2WSH output and a P2WSH output from a joint public key.

Since ECDSA signatures do not have a nice algebraic structure it is very difficult to do key aggregation. Using Schnorr you can quite literally just add each party’s share of the signature together. The method we have to use in ECDSA is to move the operations to produce the s component of the signature into a Paillier group rather than doing them simply modulo the Secp256k1 curve order. Once you are in Paillier land things become much easier but it comes at a cost of boatloads of messages and complexity during the key generation and exchange phase. It is so complicated that it is amazing that anyone actually bothered to come up with this. For us it may be very useful. Even though Bitcoin is likely to get Schnorr signatures eventually, Ethereum probably will not switch anytime soon.

The hard bit is doing the setup phase which involves quite a few proofs. Some of them are in the above crate but some of them are imported from elsewhere. We start with going through these.

Key Generation

Generating the joint public key

To produce signatures under a joint public key you first need to generate it fairly. Because of rogue key attacks, you can not just have one party send their public key and the other send one back.

The technique used in the paper (and followed by the implementation) is to do a coin tossing protocol to determine the joint public key. This ensures that the public key is totally random and cannot be biased by the party that chooses their key afterwards. The ability to simulate a random coin toss gives the key generation very strong security guarantees.

The protocol is roughly as follows, where x1 is P1’s (resp. P2) private key and X1 = gx1 is her public key.

  • P1 → P2: Hash(X1, schnorr_nizk(X1))

  • P2 → P1: X2, schnorr_nizk(X2)

  • P1 → P2: X1, schnorr_nizk(X1) (i.e. opens the commitment from 1)

  • Both parties calculate the joint public key X = X1x2 = X2x1 (i.e. Diffie-Hellman)

Implementation notes

The implementation commits by sending two hashes, one for the key and one for the NIZK.

Proving Paillier modulus is well formed

In order to use Paillier encryption, P1 needs to generate a RSA type modulus N = pq where p and q are large primes. P1 needs to prove that she generated N properly (I do not actually know what the risk is to P2 if she does not generate N properly).

The proof mentioned in the original paper is [Hazay11]. But in a more recent paper on multi-party ECDSA, [Lindell18] (section 6.2.3) modifies the proof from [Goldberg18] to do the job. Roughly speaking, the strategy is to prove that N is square free and to show that ƒ(x) = xN (mod N) is a permutation which proves that N is form N = pq.

Implementation notes

Since it is a public coin protocol, you can make a non-interactive version of the proof using the Fiat-Shamir transformation. They implemented a non-interactive version of it here: https://github.com/KZen-networks/zk-paillier/blob/a7f3907fb2b3464f12b55e3ad2f50405db54f36a/src/zkproofs/correct_key_ni.rs (which uses the interactive proof module but supplies the challenge as a hash of the initial commitment).

Proving a Paillier encryption is a private key of a EC public key

To do the signing protocol, we need P2 to have P1’s encrypted private key. In order for P2 to know that he is signing under their joint public key, he has to know that this encrypted private key is the right one (without learning what the private key is).

The proof is described in [Lindell17] (section 6). It is a little tricky to get your head around. Here is a high level and very rough intuition to how it works (it would be better to read the paper):

P2 takes the P1’s encrypted private key ckey and multiplies and adds random stuff to it (using Paillier operations). This creates a new encrypted private key c′. P2 has no idea about the value of this new private key he has just created but he can figure out the corresponding public key because he knows P1’s public key can do the operations on it that he did to ckey to get c′. P2 sends c′ to P1 (think of it as his challenge to P1).

P1 sets α = PaillierDecrypt(c′) and figures out the public key gα.

If P1 can produce gα such that it equals the public key P2 calculated then ckey must encrypt P1’s private key.

Implementation notes

This proof is not in its own module but the code for it hangs around with the rest of the protocol:

It looks like this protocol cannot be made non-interactive. It requires four rounds of communication.

Range proof

In order for the previous proof to actually prove the statement you have to couple it with a range proof which proves that the encrypted private key is in the curve order (i.e. is a valid private key). The poof chosen was originally from [Boudot00] but I found it was easier to understand in [Lindell17] anyway (see Appendix A).

The proof uses the cut and choose technique, so it is quite large. It is tricky to understand, but does not use any wonky math. You just have to follow what happens closely.

Implementation notes

To prove that the private key lies within the curve order P1 first has to choose their private key so that it is in Zq/3 rather than Zq. Without this the proof will not be complete.

This is implemented here:

Messages

Here is my early sketch of how many messages you need:

  1. P1 → P2: Hash(X1, schnorr_nizk(X1))

  2. P2 → P1: X2, schnorr_nizk(X2)

  3. P1 → P2:

    1. Opens commitment from (1)

    2. Paillier modulus N

    3. Proof N was generated properly

    4. ckey = PaillierEncrypt(x1)

    5. Range proof for c encrypts a valid private key

  4. P2 → P1: Challenge for c being Paillier encryption of x1.

  5. P1 → P2: Committed response to challenge from (4)

  6. P2 → P1: Reveal challenge from (4)

  7. P1 → P2: Open committed response from (5)

Signing

Assuming the keygen phase went well both parties know the following:

  1. P1 knows: x1 , X, N,p,q | N = pq,

  2. P2 knows: x2, X, N, ckey = PaillierEncrypt(x1, N)

Now they want to sign a message m.

Since ECDSA signatures are in the form (r,s), they need to agree on the r value before they can produce the s value. To do this, they do the same coin flipping protocol as in Generating the joint public key (3 rounds).

Then P2 sends back c3 which is produced by performing homomorphic operations with P1's encrypted private key ckey and his own private data. Note, When P2 creates c3 there is a random rho factor (ρ * q) added to c3 to prevent P1 from learning anything from it before doing a modular reduction to the curve order (q).

P1 then decrypts c3 and does a modular reduction to the curve order (this transforms it from a scalar in the Paillier group to a scalar in the elliptic curve group). From this, P1 can produce s and therefore a valid (r,s) ECDSA signature on m.

Messages

The messages are depicted nicely in Section 3.3, Figure 1 of [Lindell17].

References