Module hbbft::sync_key_gen

A synchronous algorithm for dealerless distributed key generation.

This protocol is meant to run in a completely synchronous setting where each node handles all messages in the same order. It can e.g. exchange messages as transactions on top of HoneyBadger, or it can run "on-chain", i.e. committing its messages to a blockchain.

Its messages are encrypted where necessary, so they can be publicly broadcast.

When the protocol completes, every node receives a secret key share suitable for threshold signatures and encryption. The secret master key is not known by anyone. The protocol succeeds if up to t nodes are faulty, where t is the threshold parameter. The number of nodes must be at least 2 t + 1.

Usage

Before beginning the threshold key generation process, each validator needs to generate a regular (non-threshold) key pair and multicast its public key. SyncKeyGen::new returns the instance itself and a Part message, containing a contribution to the new threshold keys. It needs to be sent to all nodes. SyncKeyGen::handle_part in turn produces an Ack message, which is also multicast.

All nodes must handle the exact same set of Part and Ack messages. In this sense the algorithm is synchronous: If Alice's Ack was handled by Bob but not by Carol, Bob and Carol could receive different public key sets, and secret key shares that don't match. One way to ensure this is to commit the messages to a public ledger before handling them, e.g. by feeding them to a preexisting instance of Honey Badger. The messages will then appear in the same order for everyone.

To complete the process, call SyncKeyGen::generate. It produces your secret key share and the public key set.

While not asynchronous, the algorithm is fault tolerant: It is not necessary to handle a Part and all Ack messages from every validator. A Part is complete if it received at least 2 t + 1 valid Acks. Only complete Parts are used for key generation in the end, and as long as at least one complete Part is from a correct node, the new key set is secure. You can use SyncKeyGen::is_ready to check whether at least t + 1 Parts are complete. So all nodes can call generate as soon as is_ready returns true.

Alternatively, you can use any stronger criterion, too, as long as all validators call generate at the same point, i.e. after handling the same set of messages. SyncKeyGen::count_complete returns the number of complete Part messages. And SyncKeyGen::is_node_ready can be used to check whether a particluar node's Part is complete.

The Part and Ack messages alone contain all the information needed for anyone to compute the public key set, and for anyone owning one of the participating secret keys to compute their own secret key share. In particular:

• Observer nodes can also use SyncKeyGen. For observers, no Part and Ack messages will be created and they do not need to send anything. On completion, they will only receive the public key set, but no secret key share.
• If a participant crashed and lost its SyncKeyGen instance, but still has its original key pair, and if the key generation messages were committed to some public ledger, it can create a new SyncKeyGen, handle all the messages in order, and compute its secret key share.

Example

use std::collections::BTreeMap;

use threshold_crypto::{PublicKey, SecretKey, SignatureShare};
use hbbft::sync_key_gen::{AckOutcome, PartOutcome, SyncKeyGen};

// Use the OS random number generator for any randomness:
let mut rng = rand::OsRng::new().expect("Could not open OS random number generator.");

// Two out of four shares will suffice to sign or encrypt something.
let (threshold, node_num) = (1, 4);

// Generate individual key pairs for encryption. These are not suitable for threshold schemes.
let sec_keys: Vec<SecretKey> = (0..node_num).map(|_| rand::random()).collect();
let pub_keys: BTreeMap<usize, PublicKey> = sec_keys
    .iter()
    .map(SecretKey::public_key)
    .enumerate()
    .collect();

// Create the `SyncKeyGen` instances. The constructor also outputs the part that needs to
// be sent to all other participants, so we save the parts together with their sender ID.
let mut nodes = BTreeMap::new();
let mut parts = Vec::new();
for (id, sk) in sec_keys.into_iter().enumerate() {
    let (sync_key_gen, opt_part) = SyncKeyGen::new(
        id,
        sk,
        pub_keys.clone(),
        threshold,
        &mut rng,
).unwrap_or_else(|_| panic!("Failed to create `SyncKeyGen` instance for node #{}", id));
    nodes.insert(id, sync_key_gen);
    parts.push((id, opt_part.unwrap())); // Would be `None` for observer nodes.
}

// All nodes now handle the parts and send the resulting `Ack` messages.
let mut acks = Vec::new();
for (sender_id, part) in parts {
    for (&id, node) in &mut nodes {
        match node
            .handle_part(&sender_id, part.clone(), &mut rng)
            .expect("Failed to handle Part")
        {
            PartOutcome::Valid(Some(ack)) => acks.push((id, ack)),
            PartOutcome::Invalid(fault) => panic!("Invalid Part: {:?}", fault),
            PartOutcome::Valid(None) => {
                panic!("We are not an observer, so we should send Ack.")
            }
        }
    }
}

// Finally, we handle all the `Ack`s.
for (sender_id, ack) in acks {
    for node in nodes.values_mut() {
        match node.handle_ack(&sender_id, ack.clone()).expect("Failed to handle Ack") {
            AckOutcome::Valid => (),
            AckOutcome::Invalid(fault) => panic!("Invalid Ack: {:?}", fault),
        }
    }
}

// We have all the information and can generate the key sets.
// Generate the public key set; which is identical for all nodes.
let pub_key_set = nodes[&0].generate().expect("Failed to create `PublicKeySet` from node #0").0;
let mut secret_key_shares = BTreeMap::new();
for (&id, node) in &mut nodes {
    assert!(node.is_ready());
    let (pks, opt_sks) = node.generate().unwrap_or_else(|_|
        panic!("Failed to create `PublicKeySet` and `SecretKeyShare` for node #{}", id)
    );
    assert_eq!(pks, pub_key_set); // All nodes now know the public keys and public key shares.
    let sks = opt_sks.expect("Not an observer node: We receive a secret key share.");
    secret_key_shares.insert(id, sks);
}

// Two out of four nodes can now sign a message. Each share can be verified individually.
let msg = "Nodes 0 and 1 does not agree with this.";
let mut sig_shares: BTreeMap<usize, SignatureShare> = BTreeMap::new();
for (&id, sks) in &secret_key_shares {
    if id != 0 && id != 1 {
        let sig_share = sks.sign(msg);
        let pks = pub_key_set.public_key_share(id);
        assert!(pks.verify(&sig_share, msg));
        sig_shares.insert(id, sig_share);
    }
}

// Two signatures are over the threshold. They are enough to produce a signature that matches
// the public master key.
let sig = pub_key_set
    .combine_signatures(&sig_shares)
    .expect("The shares can be combined.");
assert!(pub_key_set.public_key().verify(&sig, msg));

How it works

The algorithm is based on ideas from Distributed Key Generation in the Wild and A robust threshold elliptic curve digital signature providing a new verifiable secret sharing scheme.

In a trusted dealer scenario, the following steps occur:

1. Dealer generates a BivarPoly of degree t and publishes the BivarCommitment which is used to publicly verify the polynomial's values.
2. Dealer sends row m > 0 to node number m.
3. Node m, in turn, sends value number s to node number s.
4. This process continues until 2 t + 1 nodes confirm they have received a valid row. If there are at most t faulty nodes, we know that at least t + 1 correct nodes sent on an entry of every other node's column to that node.
5. This means every node can reconstruct its column, and the value at 0 of its column.
6. These values all lie on a univariate polynomial of degree t and can be used as secret keys.

In our dealerless environment, at least t + 1 nodes each generate a polynomial using the method above. The sum of the secret keys we received from each node is then used as our secret key. No single node knows the secret master key.

Structs

Ack	A confirmation that we have received and verified a validator's part. It must be sent to all participating nodes and handled by all of them, including ourselves.
Part	A submission by a validator for the key generation. It must to be sent to all participating nodes and handled by all of them, including the one that produced it.
SyncKeyGen	A synchronous algorithm for dealerless distributed key generation.

Enums

AckFault	An error in an Ack message sent by a faulty node.
AckOutcome	The outcome of handling and verifying an Ack message.
Error	A local error while handling an Ack or Part message, that was not caused by that message being invalid.
PartFault	An error in a Part message sent by a faulty node.
PartOutcome	The outcome of handling and verifying a Part message.