CGGMP21 In Rust, At Last

We're thrilled to share our open-source Rust implementation of threshold ECDSA signatures, built on the CGGMP21 protocol. Here is the Github repository. This implementation has been thoroughly reviewed by Kudelski Security and is ready for real-world use. Dfns already uses this library to secure its own ECDSA signing keys in production, and we're committed to transparency by releasing the code publicly.

We believe our CGGMP21 library is the only audited Rust implementation available under permissive MIT/Apache 2.0 licenses.

If you are looking for other languages or licenses, why not try:

• multi-party-sig written in Go with an Apache-2.0 license
• synedrion written in Rust with an AGPL-3.0 license
• mpc-lib written in C++ with a GPL-3.0 license

You should contact the authors to determine whether the implementations above have been audited, as it’s not always the case. We recommend that you choose the one that best suits your specific needs and licensing requirements.

What is CGGMP21?

The CGGMP21 protocol, named after its creators, stands on the shoulders of earlier groundbreaking work by Rosario Gennaro and Steven Goldfeder. Their paper, "Fast Multiparty Threshold ECDSA with Fast Trustless Setup" (i.e., “GG18”), laid the foundation by:

• Eliminating the need for a trusted party
• Reducing setup vulnerabilities
• Boosting performance

Building on this success, Gennaro and Goldfeder published "One Round Threshold ECDSA with Identifiable Abort" (i.e., “GG20”). This paper:

• Simplified the signing process bringing it down from multiple rounds of communication to just one, significantly improving efficiency and reducing latency.
• Introduced an "abort identification" mechanism that could identify the party responsible if the protocol failed, enhancing overall accountability and security.

CGGMP21 incorporates these advancements, further refining the multiparty threshold ECDSA approach for secure and efficient cryptographic operations, and introduces three novel improvements over the existing protocols:

• Universally Composable Security that guarantees strong security, even when combined with other protocols, making it safe to use alongside existing systems.
• Non-Interactivity that enables 1-round signing (requires some precomputation to be done in advance).
• Proactive Security that enables periodic key share refresh without changing the public key, enhancing long-term protection against potential attacks.

In a "t-out-of-n" threshold signature scheme, n parties distributively generate and share a key, and any t of those parties can jointly run a protocol to sign a message; the scheme remains secure even if up to t-1 of those parties are compromised by an attacker. The CGGMP protocol is a state-of-the-art protocol for threshold ECDSA signatures. The CGGMP21 paper defines protocols for distributed key generation and threshold signing in the "n-ouf-of-n" case, and we have generalized it to the "t-out-of-n" case for arbitrary t.

Dfns have implemented a version of the 4-round CGGMP protocol that supports arbitrary t but does not have identifiable aborts. As described in the CGGMP21 paper, the protocol allows for the generation of presignatures in an offline, preprocessing phase (before any message is specified), after which a signature on any desired message can be produced non-interactively.

This crate implements:

• Threshold (i.e., t-out-of-n) and non-threshold (i.e., n-out-of-n) key generation
• (3+1)-round general threshold and non-threshold signing
• Auxiliary info generation protocol
• Key refresh for non-threshold keys
• HD-wallets support based on slip10 standard (compatible with bip32).
  Requires hd-wallets feature

A self-contained description of the protocols we implemented is available here.

How to use our library

The library is available at crates.io. You can add it to your project by simply writing in Cargo.toml:

1[dependencies]
2cggmp21 = { version = "0.2", features = ["curve-secp256k1"] }

The rest of this article will guide you through the process of running the keygen/signing protocols, mention some caveats, and provide some security advice.

Networking

The most essential part of running an interactive protocol is to define how parties can communicate with each other. Our cggmp21 library is agnostic to the network layer and only requires you to provide two things: a stream of incoming messages and a sink for outgoing messages, i.e.:

1use cggmp21::round_based::{Incoming, Outgoing};
2let incoming: impl Stream<Item = Result<Incoming<Msg>>>;
3let outgoing: impl Sink<Outgoing<Msg>>;

Once you have that, you can construct an MpcParty:

1let delivery = (incoming, outgoing);
2let party = cggmp21::round_based::MpcParty::connected(delivery);

The concrete networking implementation to use will depend heavily on the specific application. Some applications may use libp2p; others may prefer having a central delivery server or a database (like Redis or Postgres); some specific applications may want to communicate over a public blockchain, and so on.

Whatever networking implementation you use, keep in mind that:

• All messages must be authenticated
  Whenever one party receives a message from another, the receiver should cryptographically verify that the message comes from the claimed sender.
• All p2p messages must be encrypted
  Only the designated recipient should be able to read the message

Signer indices

Our library uses indices to uniquely refer to particular signers sharing a key. Each index i is an unsigned integer u16 with 0 ≤ i < n where n (sometimes called num_signers in our code) is the total number of parties.

All signers should have the same view about each others' indices. For instance, if Signer A holds index 2, then all other signers must agree that i=2 corresponds to Signer A.

Assuming some sort of PKI (which would anyway likely be used to ensure secure communication, as described above), each signer has a public key that uniquely identifies that signer. It is then possible to assign unique indices to the signers by lexicographically sorting the signers' public keys, and letting the index of a signer be the position of that signer's public key in the sorted list.

Execution ID

Execution of our protocols requires all participants to agree on a unique execution ID (aka session identifier) that is assumed never to repeat. This string provides context separation between different executions of the protocol to ensure that an adversary cannot replay messages from one execution to another.

Auxiliary-data generation

In the usual flow, signers run a protocol for auxiliary-data generation before running distributed key generation. This protocol sets up certain parameters (in particular, Paillier moduli) for each of the signers) that will be used during the signing protocols. This protocol can be run as follows:

1// Prime generation can take a while
2let pregenerated_primes = cggmp21::PregeneratedPrimes::generate(&mut OsRng);
3
4let eid = cggmp21::ExecutionId::new(b"execution id, unique per protocol execution");
5let i = /* signer index, same as at keygen */;
6let n = /* amount of signers */;
7
8let aux_info = cggmp21::aux_info_gen(eid, i, n, pregenerated_primes)
9    .start(&mut OsRng, party)
10    .await?;

The auxiliary-data generation protocol is computationally heavy as it requires the generation of safe primes and involves several zero-knowledge (ZK) proofs.

Distributed Key Generation (DKG)

The DKG protocol involves all signers who will co-share a key. All signers need to agree on some basic parameters including the participants' indices, the execution ID, and the threshold value (i.e., t). The protocol can be executed as:

1use cggmp21::supported_curves::Secp256k1;
2
3// Networking is described above
4let delivery = (incoming, outgoing);
5let party = cggmp21::round_based::MpcParty::connected(delivery);
6
7let eid = cggmp21::ExecutionId::new(b"execution id, unique per protocol execution");
8let i = /* signer index (0 ≤ i < n) */;
9let n = /* amount of signers taking part in key generation */;
10let t = /* threshold */;
11
12let incomplete_key_share = cggmp21::keygen::<Secp256k1>(eid, i, n)
13    .set_threshold(t)
14    .start(&mut OsRng, party)
15    .await?;

The above produces an incomplete key share. An incomplete key share can be saved on disk by serializing using serde crate. Treat this material appropriately as it contains sensitive information.

Assuming auxiliary-data generation has already been done (see above), you can "complete" the key share using:

1let key_share = cggmp21::KeyShare::from_parts((incomplete_key_share, aux_info))?;

On reusability of the auxiliary data

The CGGMP21 paper assumes that new auxiliary data is generated for each secret key that is shared. However, examination of the proof shows that this is not necessary, and a fixed group of signers can use the same auxiliary data for the secure sharing/usage of multiple keys.

Signing

Once signers have a set of "completed" key shares, they can sign or generate presignatures. In either case, exactly the threshold number (i.e., t) of signers must take part in the protocol. As in the DKG protocol, each signer needs to be assigned a unique index, now in the range from 0 to t-1. But the signers also need to know which index each signer occupied at the time of keygen.

In the example below, we show how to do a full signing:

1let eid = cggmp21::ExecutionId::new(b"execution id, unique per protocol execution");
2
3let i = /* signer index (0 ≤ i < min_signers) */;
4let parties_indexes_at_keygen: [u16; MIN_SIGNERS] =
5    /* parties_indexes_at_keygen[i] is index which i-th party occupied at keygen */;
6let key_share = /* completed key share */;
7
8let data_to_sign = cggmp21::DataToSign::digest::<Sha256>(b"data to be signed");
9
10let signature = cggmp21::signing(eid, i, &parties_indexes_at_keygen, &key_share)
11    .sign(&mut OsRng, party, data_to_sign)
12    .await?;

Alternatively, you can generate a presignature and use it to sign data determined later:

• Use SigningBuilder::generate_presignature to run the presignature generation protocol.
• Once a signing request is received, each signer issues a partial signature using Presignature::issue_partial_signature.
• A threshold number of partial signatures can be combined using PartialSignature::combine to obtain a full signature.

Never reuse presignatures! If you use the same presignature to sign two different messages, the private key may be leaked.

Intellectual property

Our implementation of CGGMP21 is available and free to use, double licensed under MIT and Apache 2.0. We welcome your feedback.

References

• UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts
• Fast Multiparty Threshold ECDSA with Fast Trustless Setup
• One Round Threshold ECDSA with Identifiable Abort