Threshold ECDSA: Research/prototype implementation

[mhluongo]

ECDSA is the primary signature scheme used by many cryptocurrencies, including most Bitcoin variants and Ethereum. ECDSA doesn't support a threshold or aggregate configuration by default (versus newer schemes like BLS and Schnorr).

MPC can be used to make a threshold-supporting variant of ECDSA that's interoperable with the signatures on today's chains (on the libsecp256k1 curve). Goldfeder et al proposed such a construction, and provided an initial implementation and a revision in Java.

Goldfeder's implementation doesn't include a distributed key generation implementation- luckily, we should be able to use our existing work ported to secp256k1.

For our first pass, let's port ThresholdECDSA to Go, plugging in existing Go crypto libraries where possible. In particular, we'll make use of geth's secp265k1 package. We also need something for Pedersen commitments (or we need to write it ourselves) and a Paillier HME implementation (this looks like the most promising).

The outcome we're looking for here is a package that implements the threshold ECDSA protocol, without concern for networking. We'll cover networking and incentives in future work.

[Shadowfiend]

A small comment here, less for research-time and more from an MVP perspective---we do not need DKG, right? This is already useful if a client has to interact to initially ship a private key into the Keep, correct? DKG just provides an extra layer of “hands off” ness?

[mhluongo]

The exciting use-case (sidechain-like bridge between crypocurrencies) needs DKG, as does fully attributable faults- if a third party provides the key we can't slash if a signature we aren't expecting shows up somewhere, as it could have been that third party

[Shadowfiend]

So we don't really think there's strong value/market need for a simple “the contract can autonomously control an existing bitcoin account” functionality?

[mhluongo]

This might have a use without DKG but I'm unsure we'd want to ship without it.

[mhluongo]

So we don't really think there's strong value/market need for a simple “the contract can autonomously control an existing bitcoin account” functionality?

Unclear, but for many uses you could use eg an AWS box there if you don't need fully trustless. It's far less acute.

There are some deadman switch type things I could imagine as well. Another might be Bitcoin fund recovery in case you lost key access

[pdyraga]

This Goldfeder et al paper is better aligned with the code available on GitHub

[mhluongo]

Sorry, good catch!

[pdyraga]

I took another approach to the T-ECDSA paper [GGN 16] and have some thoughts I'd like to share, validate and leave here for others or future me.

• In the [GGN 16] T-ECDSA scheme there are two Pub/Priv keys used and this is not obvious at first: Paillier key and (EC)DSA key.
• Paillier is a transport protocol due to its property of being an additively homomorphic encryption scheme.
• (EC)DSA is what is used for the actual signing.
• The Paillier does not have to be based on EC (Elliptic Curve).
• DSA must be EC-based.
• Our Paillier lib in the current state supports Threshold keys but requires trusted oracle to exist, we need to implement a distributed KeyGen algorithm.
• [GGN 10] recommends algorithm presented in [HMRT 12] for a threshold Paillier KeyGen. Unfortunately, it works only for two parties and we need something better here. The best approach so far has been presented in [DK 01]. It requires n>=2t+1 but it shouldn't be a problem for us - we may take the same approach as we do for DKG and abort KeyGen if a malicious behavior is detected. What's more, the approach described in [DK 01] seems to be nicely aligned with our Paillier library code based on [DJN 10].
• For (EC)DSA key generation, we may probably use our DKG algorithm.
• When generating keys, it's important to use N>q^8, where N is a Paillier modulus and q is a prime order of a cyclic group G generated by an element g in DSA. See remarks at the very end of section 4.3 in [GGN 16].
• We'll need Pedersen commitments for the signature generation (see section 4.3 in [GGN 16]). I could not find any Go library ready for use but the sample Java code for [GGN 16] has Pedersen implemented and we may use it as a reference.

There are two parts we need to implement first and they may be implemented independently:

• Paillier T-KeyGen without a trusted oracle
• Pedersen commitments

Both those parts should be easily testable so we can build T-ECDSA with proven, tested pieces even though the reference Java implementation does not work as expected or I can't make it work as expected.

[GGN 16] Gennaro R., Goldfeder S., Narayanan A. (2016) Threshold-Optimal DSA/ECDSA Signatures and an Application to Bitcoin Wallet Security. In: Manulis M., Sadeghi AR., Schneider S. (eds) Applied Cryptography and Network Security. ACNS 2016. Lecture Notes in Computer Science, vol 9696. Springer, Cham https://eprint.iacr.org/2016/013.pdf

[HMRT 12] Hazay C., Mikkelsen G.L., Rabin T., Toft T. (2012) Efficient RSA Key Generation and Threshold Paillier in the Two-Party Setting. In: Dunkelman O. (eds) Topics in Cryptology – CT-RSA 2012. CT-RSA 2012. Lecture Notes in Computer Science, vol 7178. Springer, Berlin, Heidelberg https://eprint.iacr.org/2011/494.pdf

[DK 01] Damgård I., Koprowski M. (2001) Practical Threshold RSA Signatures without a Trusted Dealer. In: Pfitzmann B. (eds) Advances in Cryptology — EUROCRYPT 2001. EUROCRYPT 2001. Lecture Notes in Computer Science, vol 2045. Springer, Berlin, Heidelberg https://www.iacr.org/archive/eurocrypt2001/20450151.pdf

[DJN 10] Ivan Damgard, Mads Jurik, Jesper Buus Nielsen, (2010) A Generalization of Paillier’s Public-Key System with Applications to Electronic Voting Aarhus University, Dept. of Computer Science, BRICS http://cs.au.dk/~stm/local-cache/paillier.pdf

[Shadowfiend]

Paillier is a transport protocol

What exactly do we mean by this? Just that it is used as a container for underlying data that needs to be mutated in encrypted fashion?

When generating keys, it's important to use N>q^8, where N is a Paillier modulus and q is a prime order of a cyclic group G generated by an element g in DSA.

This is when generating ECDSA keys?

[pdyraga]

What exactly do we mean by this? Just that it is used as a container for underlying data that needs to be mutated in encrypted fashion?

Yep. At least this is my (current) understanding. If you look at [GGN 16], section 4.3 Signature generation, you'll see a lot of operations like or and this is actually combining encrypted data thanks to that homomorphic property of Paillier.

I don't see any use for Paillier there other than encrypting, combining and decrypting some information between rounds.

This is when generating ECDSA keys?

Yes, but we must also pick N big enough during Paillier key generation to make N>q^8 possible later.

[Shadowfiend]

Yep.

Got it. I would call it an envelope… Mostly because “transport protocol” means networking to me. But the analogy holds, so either way.

We must pick N big enough during Paillier key generation

That's a different N, right?

[pdyraga]

Got it. I would call it an envelope… Mostly because “transport protocol” means networking to me. But the analogy holds, so either way.

Oh, right. An envelope is a much better name here. :100:

That's a different N, right?

Correct. N is from Paillier. We construct Paillier key by choosing two big primes meeting some requirements, say a and b to do not confuse with naming used in [GGN 16]. Then, N=ab.

The DSA key pair is (x,y = g^x) with y public and x shared among the players. The public DSA parameter include a cyclic group G of prime order q generated by an element g, a hash function defined from arbitrary strings into Z_q and another hash function defined from G to Z_q.

The idea in [GGN 16] is to generate a public key E for an additively (mod N) homomorphic encryption scheme E (it's just Paillier in our case), together with the secret key D in shared form among the players. Then a value x (DSA) is generated and encrypted with E, with the value E(x) made public. Note that this is an implicit threshold secret sharing of x, since the decryption key D is shared among the players.

In order for the protocol to be correct, all the Paillier homomorphic operations over the ciphertexts (which are modulo N) must not conflict with the operations modulo q of the DSA. That's why they suggest to choose N > q^8.

[pdyraga]

Speaking about the right N and q...

We want to have Elliptic Curve DSA, not just a standard DSA. In EC-DSA, G is a group of points on the curve of cartinality q.

According to this post sicp256k1 cardinality is ... 115792089237316195423570985008687907852837564279074904382605163141518161494337 (10^77)

And we must have N > q^8.

[Shadowfiend]

I'm sorry, at some point I just stopped seeing numbers ;)

Is this still feasible?

[mhluongo]

Is this still feasible?

It sounds like it.

Great approach so far @pdyraga- instead of high-level shared test vectors we do ground-up components and test vectors to verify correctness. It's a slower approach but can save us from the shared curves and I expect will yield higher-quality code.

[pdyraga]

In their paper, they claim they integrated with Bitcoin successfully so I think it's feasible. Unfortunately, we don't have a full sample working. I am a bit concerned about number ranges and prime generators but with small steps, I think we can do it. At some point, we'll probably need to confirm some parts with our academic advisor.

Impossible is nothing 😉

[mhluongo]

At some point, we'll probably need to confirm some parts with our academic advisor.

Keep a running log of questions. We can get any help from Vlad as we go, but it'd also be handy to know what you ran into and solved as breadcrumbs for eg the auditors.

[mhluongo]

For (EC)DSA key generation, we may probably use our DKG algorithm.

I'm skeptical of this- I'd like to have attributable abort DKG here, as we'll be able to efficicently punish cheaters (unlike our beacon DKG). It's fine if we start with JF but remember that we'll need a different protocol before any of this goes near production.

I suppose I should open an issue 😁

[Shadowfiend]

Attributable abort may not be a core req for the beacon, but if we improve it to include attributable abort we could use it for both, right?

[pdyraga]

What would you say about closing this issue? The prototype is done, we successfully signed a testnet BTC transaction.

The remaining work has been identified and is listed here: https://github.com/keep-network/keep-core/projects/7

[Shadowfiend]

Down to transition tracking this to the project 👍