Expand description
Distributed Key Generation (DKG) and Resharing protocol for the BLS12-381 curve.
This crate implements a Distributed Key Generation (DKG) and Resharing protocol for the BLS12-381 curve. Unlike many other constructions, this scheme only requires participants to publicly post shares during a “forced reveal” (when a given dealer does not distribute a share required for a party to recover their secret). Outside of this reveal, all shares are communicated directly between a dealer and recipient over an encrypted channel (which can be instantiated with https://docs.rs/commonware-p2p).
The DKG is based on the “Joint-Feldman” construction from “Secure Distributed Key Generation for Discrete-Log Based Cryptosystems” (GJKR99) and resharing is based on the construction provided in “Redistributing secret shares to new access structures and its applications” (Desmedt97).
§Protocol
The protocol has two types of participants: the arbiter and contributors. The arbiter serves as an orchestrator that collects commitments, acks, complaints, and reveals from contributors and replicates them to other contributors. The arbiter can be implemented as a standalone process or by some consensus protocol. Contributors are the participants that deal shares and commitments to other contributors in the protocol.
Because the target use case for this protocol is a blockchain, the protocol is designed
to maintain a 2f + 1 threshold over 3f + 1 participants across any reshare (including reshares
with a changing contributor set) where 2f + 1 contributors are online and honest (although
the threshold can be arbitrarily configured). To achieve this, the protocol sacrifices
responsiveness and instead relies on “timeouts” that all online and honest contributors
are expected to communicate within. To provide a “feeling” of responsiveness, the protocol
can be implemented with block height-based timeouts over an optimistically responsive protocol.
Whether or not the protocol succeeds in a given round (i.e. 2f + 1 participants are not
online and honest), all contributors that do not adhere to the protocol will be identified
and returned. If the protocol succeeds, the contributions of any contributors that did not
adhere to the protocol are excluded (and still returned). It is expected that the set of
contributors would punish/exclude “bad” contributors prior to a future round.
§Arbiter
§[Phase 0] Step 0: Collect Commitments
In the first phase, the arbiter collects randomly generated commitments from all contributors.
If the arbiter is instantiated with a polynomial (from a previous DKG/Reshare), it will enforce all
generated commitments are consistent with said polynomial. The arbiter, lastly, enforces that the
degree of each commitment is threshold - 1.
Any contributors that do not submit a commitment before the timeout or submit an invalid commitment are disqualified.
If there are not at least threshold valid commitments (or previous.degree + 1 commitments in
resharing), the arbiter will abort the protocol.
§[Phase 0] Step 1: Distribute Valid Commitments
After the Phase 0 timeout, the arbiter sends all valid commitments to all qualified contributors (this can be implemented as a read operation on a blockchain and does not actually need to be a network message).
§[Phase 1] Step 2: Collect Acks and Complaints
After distributing valid commitments, the arbiter will listen for acks and complaints from qualified contributors. An “ack” is a message indicating that a given contributor has received a valid share from a dealer (does not include encrypted or plaintext share material). A “complaint” is a signed share from a given dealer that is invalid (signing is external to this implementation). If the complaint is valid, the dealer that sent it is disqualified. If the complaint is invalid (it is a valid share), the recipient is disqualified. Because all shares must be signed by the contributor that generates them and this signature is over the plaintext share, there is no need to have a “justification” phase where said contributor must “defend” itself.
Any commitments without at least threshold - 1 acks (dealers don’t need to ack their own
commitment) are disqualified. Contributors that are missing more than (threshold - 1)/2 shares
(on commitments with at least threshold - 1 acks) are disqualified (revealing this many shares
could allow an adversary to reconstruct the secret).
If there are not at least threshold valid commitments (or previous.degree + 1 commitments in
resharing), the arbiter will abort the protocol.
§[Phase 1] Step 3 (Optional): Request Reveals
After the Phase 1 timeout, the arbiter will send a request to contributors of any commitments with
at least threshold - 1 acks for qualified contributors that have not yet sent an ack for
said commitment.
If there are no such requests, the arbiter will proceed directly to step 5 (without waiting for a timeout).
If there are such requests, the arbiter will proceed to step 4.
§[Phase 2] Step 4 (Optional): Collect Reveals
Collect reveals that match any requests from Step 3. If a valid reveal for a commitment is not sent before the timeout or the reveal is invalid, the arbiter will disqualify the commitment.
§[Phase 2] Step 5: Finalize Commitments and Distribute Reveals
After Step 2 (or 4), the arbiter will forward all commitments with at least threshold - 1 acks to
all qualified contributors (and any accompanying reveals). The arbtier will then recover the
new group polynomial using all valid commitments, if a DKG, or the first threshold commitments
(sorted by participant identity), if a reshare.
§Contributor
§[Phase 0] Step 0 (Optional): Generate Shares and Commitment
If a contributor is joining a pre-existing group (and is not a dealer), it proceeds to Step 2.
Otherwise, it generates shares and a commitment. If it is a DKG, the commitment is a random polynomial
with degree of threshold - 1. If it is a reshare, the commitment must be consistent with the previous
group polynomial. The contributor generates the shares and commitment for Step 1 and sends the commitment
to the arbiter.
§[Phase 0] Step 1 (Optional): Distribute Shares
After receiving qualified commitments from the arbiter, the contributor (if qualified) will distribute shares to all other contributors (ordered by participant identity).
§[Phase 1] Step 2: Submit Acks/Complaints
After receiving a share from a qualified contributor, the contributor will send an “ack” to the arbiter if the share is valid (confirmed against commitment) or a “complaint” if the share is invalid.
The contributor will not send an “ack” for its own share (if it is a qualified contributor).
§[Phase 2] Step 3 (Optional): Respond to Reveal Requests
If a contributor receives a “request” from the arbiter to reveal a share, it will do so. Even if it knows it sent said share to said contributor, it is possible that this contributor is malicious and chose not to “ack” it (this should not be a penalty for the contributor that must reveal).
§[Phase 2] Step 4 (Optional): Collect Reveals, Recover Group Polynomial, and Derive Share
If the round is successful, the arbiter will forward the valid commitments and any reveals required to construct shares for the new group polynomial (which shares the same constant term if it is a reshare). Like above, the contributor will recover the group polynomial. Unlike above, the contributor will also recover its new share of the secret (rather than just adding all shares together).
§Example
For a complete example of how to instantiate this crate, checkout commonware-vrf.
Modules§
- Orchestrator of the DKG/Resharing procedure.
- Participants in a DKG/Resharing procedure that hold a share of the secret.
- Stateless operations useful in a DKG/Resharing procedure.
- Utilities for a DKG/Resharing procedure.