Module frost_dalek::keygen

A variation of Pedersen's distributed key generation (DKG) protocol.

This implementation uses the typestate design pattern (also called session types) behind the scenes to enforce that more programming errors are discoverable at compile-time. Additionally, secrets generated for commitment openings, secret keys, nonces in zero-knowledge proofs, etc., are zeroed-out in memory when they are dropped out of scope.

Details

Round One

• Step #1: Every participant \(P_i\) samples \(t\) random values \((a_{i0}, \dots, a_{i(t-1)})\) uniformly in \(\mathbb{Z}_q\), and uses these values as coefficients to define a polynomial \(f_i(x) = \sum_{j=0}^{t-1} a_{ij} x^{j}\) of degree \( t-1 \) over \(\mathbb{Z}_q\).

(Yes, I know the steps are out-of-order. These are the step numbers as given in the paper. I do them out-of-order because it saves one scalar multiplication.)

• Step #3: Every participant \(P_i\) computes a public commitment \(C_i = [\phi_{i0}, \dots, \phi_{i(t-1)}]\), where \(\phi_{ij} = g^{a_{ij}}\), \(0 \le j \le t-1\).

• Step #2: Every \(P_i\) computes a proof of knowledge to the corresponding secret key \(a_{i0}\) by calculating a pseudo-Schnorr signature \(\sigma_i = (s, r)\). (In the FROST paper: \(\sigma_i = (\mu_i, c_i)\), but we stick with Schnorr's original notation here.)

• Step #4: Every participant \(P_i\) broadcasts \((C_i\), \(\sigma_i)\) to all other participants.

• Step #5: Upon receiving \((C_l, \sigma_l)\) from participants \(1 \le l \le n\), \(l \ne i\), participant \(P_i\) verifies \(\sigma_l = (s_l, r_l)\), by checking: \(s_l \stackrel{?}{=} \mathcal{H}(l, \Phi, \phi_{l0}, g^{r_l} \cdot \phi_{l0}^{-s_i})\). If any participants' proofs cannot be verified, return their participant indices.

Round Two

• Step #1: Each \(P_i\) securely sends to each other participant \(P_l\) a secret share \((l, f_i(l))\) using their secret polynomial \(f_i(l)\) and keeps \((i, f_i(i))\) for themselves.

• Step #2: Each \(P_i\) verifies their shares by calculating: \(g^{f_l(i)} \stackrel{?}{=} \prod_{k=0}^{n-1} \)\(\phi_{lk}^{i^{k} \mod q}\), aborting if the check fails.

• Step #3: Each \(P_i\) calculates their secret signing key as the product of all the secret polynomial evaluations (including their own): \(a_i = g^{f_i(i)} \cdot \prod_{l=0}^{n-1} g^{f_l(i)}\), as well as calculating the group public key in similar fashion from the commitments from round one: \(A = C_i \cdot \prod_{l=0}^{n-1} C_l\).

Examples

use frost_dalek::DistributedKeyGeneration;
use frost_dalek::Parameters;
use frost_dalek::Participant;

// Set up key shares for a threshold signature scheme which needs at least
// 2-out-of-3 signers.
let params = Parameters { t: 2, n: 3 };

// Alice, Bob, and Carol each generate their secret polynomial coefficients
// and commitments to them, as well as a zero-knowledge proof of a secret key.
let (alice, alice_coeffs) = Participant::new(&params, 1);
let (bob, bob_coeffs) = Participant::new(&params, 2);
let (carol, carol_coeffs) = Participant::new(&params, 3);

// They send these values to each of the other participants (out of scope
// for this library), or otherwise publish them somewhere.
//
// alice.send_to(bob);
// alice.send_to(carol);
// bob.send_to(alice);
// bob.send_to(carol);
// carol.send_to(alice);
// carol.send_to(bob);
//
// NOTE: They should only send the `alice`, `bob`, and `carol` structs, *not*
//       the `alice_coefficients`, etc.
//
// Bob and Carol verify Alice's zero-knowledge proof by doing:

alice.proof_of_secret_key.verify(&alice.index, &alice.public_key().unwrap())?;

// Similarly, Alice and Carol verify Bob's proof:
bob.proof_of_secret_key.verify(&bob.index, &bob.public_key().unwrap())?;

// And, again, Alice and Bob verify Carol's proof:
carol.proof_of_secret_key.verify(&carol.index, &carol.public_key().unwrap())?;

// Alice enters round one of the distributed key generation protocol.
let mut alice_other_participants: Vec<Participant> = vec!(bob.clone(), carol.clone());
let alice_state = DistributedKeyGeneration::<_>::new(&params, &alice.index, &alice_coeffs,
                                                     &mut alice_other_participants).or(Err(()))?;

// Alice then collects the secret shares which they send to the other participants:
let alice_their_secret_shares = alice_state.their_secret_shares()?;
// send_to_bob(alice_their_secret_shares[0]);
// send_to_carol(alice_their_secret_shares[1]);

// Bob enters round one of the distributed key generation protocol.
let mut bob_other_participants: Vec<Participant> = vec!(alice.clone(), carol.clone());
let bob_state = DistributedKeyGeneration::<_>::new(&params, &bob.index, &bob_coeffs,
                                                   &mut bob_other_participants).or(Err(()))?;

// Bob then collects the secret shares which they send to the other participants:
let bob_their_secret_shares = bob_state.their_secret_shares()?;
// send_to_alice(bob_their_secret_shares[0]);
// send_to_carol(bob_their_secret_shares[1]);

// Carol enters round one of the distributed key generation protocol.
let mut carol_other_participants: Vec<Participant> = vec!(alice.clone(), bob.clone());
let carol_state = DistributedKeyGeneration::<_>::new(&params, &carol.index, &carol_coeffs,
                                                     &mut carol_other_participants).or(Err(()))?;

// Carol then collects the secret shares which they send to the other participants:
let carol_their_secret_shares = carol_state.their_secret_shares()?;
// send_to_alice(carol_their_secret_shares[0]);
// send_to_bob(carol_their_secret_shares[1]);

// Each participant now has a vector of secret shares given to them by the other participants:
let alice_my_secret_shares = vec!(bob_their_secret_shares[0].clone(),
                                  carol_their_secret_shares[0].clone());
let bob_my_secret_shares = vec!(alice_their_secret_shares[0].clone(),
                                carol_their_secret_shares[1].clone());
let carol_my_secret_shares = vec!(alice_their_secret_shares[1].clone(),
                                  bob_their_secret_shares[1].clone());

// The participants then use these secret shares from the other participants to advance to
// round two of the distributed key generation protocol.
let alice_state = alice_state.to_round_two(alice_my_secret_shares)?;
let bob_state = bob_state.to_round_two(bob_my_secret_shares)?;
let carol_state = carol_state.to_round_two(carol_my_secret_shares)?;

// Each participant can now derive their long-lived secret keys and the group's
// public key.
let (alice_group_key, alice_secret_key) = alice_state.finish(alice.public_key().unwrap())?;
let (bob_group_key, bob_secret_key) = bob_state.finish(bob.public_key().unwrap())?;
let (carol_group_key, carol_secret_key) = carol_state.finish(carol.public_key().unwrap())?;

// They should all derive the same group public key.
assert!(alice_group_key == bob_group_key);
assert!(carol_group_key == bob_group_key);

// Alice, Bob, and Carol can now create partial threshold signatures over an agreed upon
// message with their respective secret keys, which they can then give to a
// [`SignatureAggregator`] to create a 2-out-of-3 threshold signature.

Structs

Coefficients	A struct for holding a shard of the shared secret, in order to ensure that the shard is overwritten with zeroes when it falls out of scope.
DealtParticipant	A participant created by a trusted dealer.
DistributedKeyGeneration	State machine structures for holding intermediate values during a distributed key generation protocol run, to prevent misuse.
GroupKey	A public key, used to verify a signature made by a threshold of a group of participants.
IndividualPublicKey	A public verification share for a participant.
Participant	A participant in a threshold signing.
RoundOne	Every participant in the distributed key generation has sent a vector of commitments and a zero-knowledge proof of a secret key to every other participant in the protocol. During round one, each participant checks the zero-knowledge proofs of secret keys of all other participants.
RoundTwo	During round two each participant verifies their secret shares they received from each other participant.
SecretKey	A secret key, used by one participant in a threshold signature scheme, to sign a message.
SecretShare	A secret share calculated by evaluating a polynomial with secret coefficients for some indeterminant.
VerifiableSecretSharingCommitment	A commitment to the dealer's secret polynomial coefficients for Feldman's verifiable secret sharing scheme.

Traits

DkgState	Marker trait to designate valid rounds in the distributed key generation protocol's state machine. It is implemented using the sealed trait design pattern pattern to prevent external types from implementing further valid states.
Round1	Marker trait to designate valid variants of RoundOne in the distributed key generation protocol's state machine. It is implemented using the sealed trait design pattern pattern to prevent external types from implementing further valid states.
Round2	Marker trait to designate valid variants of RoundTwo in the distributed key generation protocol's state machine. It is implemented using the sealed trait design pattern pattern to prevent external types from implementing further valid states.