A prerequisite for flow encryption in Penumbra is some distributed key
generation algorithm. Our threshold encryption
scheme uses ElGamal and operates over the
decaf377 group, thus we must choose
a DKG which operates over
decaf377 outputs a
decaf377 public key.
The DKG must be run by all validators at the start of every epoch. Ideally, the
DKG should be able to run in over a single block, such that there is no delay
between the start of the epoch and when users can delegate in the staking
system or trade on ZSwap. As such, for optimal UX and simplicity of
implementation, the optimal DKG for our scheme should have minimal round
complexity. Each round of communication can occur in the
vote extension phase. Since Tendermint votes already impose an
communication complexity for each block, minimal communication complexity is
not important for our DKG.
In addition to minimal round complexity, our DKG must be verifiable: participants (validators) must be able to verify that counterparty participants (other validators) are contributing to the DKG honestly, without the use of a trusted dealer. This can be achieved using something similar to Feldman’s Verifiable Secret Sharing protocol, where each participant shares a commitment to their share which is visible to all other participants. In addition, our DKG must be able to tolerate rogue-key attacks: that is, it must tolerate the instance where a validator maliciously chooses their share based on the value of the other validator’s shares in order to cancel out other validator’s keyshares and gain unilateral control over the resulting DKG key. One way this can be prevented is by each validator producing a proof of knowledge of their secret share.
An additional property that our DKG should have is that of robustness. The DKG should be able to tolerate a byzantine threshold of validators intentionally refusing to participate in the DKG round, or intentionally contributing malformed shares during DKG execution, without requiring a full restart of the DKG protocol. This is due to DoS concerns: with a naive, non-robust implementation, a single malicious validator could potentially indefinitely delay the beginning of an epoch by refusing to participate in DKG or by contributing invalid shares.
Gurkan, Jovanovic, Maller, Meiklejohn, Stern, and Tomescu present a survey of DKG instantiations with their communication complexity, public verifiablity, round complexity, prover, and verifier costs:
Note that PV, public verifiability, is slightly different than our requirement of verifiability: public verifiability means that any non-participating observer must be able to verify the correct execution of the DKG.
Of the schemes listed, Fouque-Stern has the lowest round complexity, however
the scheme uses Pallier which is not compatible with our encryption scheme.
The scheme described in that paper uses pairings, and thus is also not
compatible with our scheme. In addition,
O(n*log*n) communication complexity
is not important for our scheme, since our vote extensions already require
In addition to these schemes, ETHDKG is in use by Anoma and Osmosis in Ferveo. However, this scheme is also not applicable to our threshold encryption scheme as it is based on pairings rather than a discrete log DKG.
Komlo and Goldberg introduced FROST: Flexible Round-Optimized Schnorr
Threshold Signatures. FROST contains a DKG which is a slightly modified
version of Pedersen’s DKG, modified to protect against rogue-key attacks. FROST
DKG operates on any prime order group where Decisional Diffie-Hellman is
difficult, and thus is compatible with
FROST DKG fulfills the requirement of verifiability and security under rogue-key attacks. FROST DKG achieves this by slightly modifying Pedersen’s DKG to include a proof of knowledge of each participant’s secret in the first round of communication.
FROST DKG trades off simplicity and efficiency in favor of robustness. A
single participant can cause the DKG to abort by contributing an invalid share
or by refusing to produce a key share. Gennaro, Jarecki, Krawczyk, and Tal
Rabin presented an alternative instantiation of Pedersen’s DKG, which
can tolerate up to
n-t invalid or missing shares. This is accomplished by
adding an additional complaint round, where participants can publish evidence
of a participant’s invalid contribution and disqualify them from the DKG. A
similar strategy could be added to FROST DKG to adapt it to be robust.
By including an additional round for relaying complaints from each participant to each counterparty, the round complexity of our DKG rises to 3 rounds.
A prerequisite for implementing any DKG scheme in Penumbra is ABCI++, the extension to Tendermint which adds additional hooks to the Tendermint state machine interface, most importantly vote extensions.
Implementing FROST DKG with ABCI++ can be done naively by placing each round of communication in the Vote Extensions phase of ABCI++. This gives an upper bound on the delay between the start of a new epoch and the completion of the DKG as 3 blocks: 1 block per vote extension communication round.
This could potentially be pipelined by including each participant’s commitments for the next epoch (the commitments from FROST) in the block data at one of the last blocks of the previous epoch. Round 2 of FROST could occur during the vote extensions phase of the epoch transition block.
NOTE: FROST requires private communication channels for round 2, thus we
must assign validators encryption keys, perform key agreement, and encrypt
round 2 communications before placing them in the vote extension. This can be
accomplished using ECDH with
decaf377, and an AEAD cipher (though
authentication is not strictly required, since vote extensions are signed).
 concrete robust FROST implementation