The DKG protocol used in Flow random beacon is a discrete-logarithm-based DKG, used to provide keys for a BLS-based threshold signature scheme. The specific instance used in Flow is Joint Feldman (Pedersen).

The purpose of such a DKG is to generate and share a secret BLS private key over all participants of the protocol.

The implementation is configured to use the elliptic curve BLS 12-381, over an extension field F(p^2). This means public keys are points in E(F(p^2)) while private keys are scalars in Zr, where r is the order of the E(F(p^2)) subgroup.

This document does not enter into the details of Joint Feldman, it only describes the high level steps of the protocol, and the API of the Flow DKG implementation.

Set up:

• Joint-Feldman DKG is run by the $n$ nodes of the random beacon committee $P_1..P_n$. In the current Flow architecture, the random beacon committee is formed by all consensus nodes.
• One DKG instance of the protocol is run at the end of each epoch $E_k$ by the random beacon committee elected for $E_{k+1}$, to generate the set of keys to be used in $E_{k+1}$.
• The protocol is parametrized by a threshold value $t$ that must be the same as the threshold value used in the threshold signature scheme in Hotstuff. In Flow, $t$ is set to $floor((n-1)/{2})$
• For the protocol to succeed, it requires at least $t+1$ honest participating node.
• Each node $P_i$ is assigned a public index $i$, the index must be the same as the threshold signature index used by the threshold signature scheme in Hotstuff.

The protocol overview :

1. The protocol starts at a specific block height before the end of $E_k$, let's call it $h_0$. All nodes $P_i$ start the first phase of the protocol "synchronously".

2. In the first phase, every node $P_i$ uses a local secret seed to generate a bunch of data locally, and shares it with the other $P_j$ under two different forms:

   • One direct message to be sent to each $P_j$ through a confidential channel (which means an encrypted message). There are $n^2$ direct messages sent in total.
   • One message to be broadcasted to all other $P_j$ using a broadcasting channel such that it is guaranteed that all $P_j$ 's receive the same broadcasted message. If such a channel fails to guarantee this property, the DKG protocol is broken. There are $n$ messages broadcasted in total.
   • Both channels must provide authentication.
   • All messages must include an instance ID $k$ related to $E_k$ to avoid message replay attacks. It is not decided yet if this should be included in the crypto library or during the protocol integration.

3. The first phase ends at a block height $h_1$. The duration between $h_0$ and $h_1$ must be large enough to allow the confidential channels and the broadcasting channels to relay all messages to the nodes.

4. The second phase starts also at $h_0$. In the happy path (all nodes in phase 1 have behaved correctly/honestly), there are no messages sent during this phase. In the unhappy path (some nodes sent wrong data or no data at all in phase 1), there will be some messages broadcasted using the same broadcasting channel. There will be about $(n^2)/4$ broadcasted messages in the worst case. This phase ends at a block height $h_2$, that must be far enough from $h_1$.

5. The third (last) phase starts at $h_2$. Same as phase 2, there are no messages sent in the happy path. In the unhappy paths, there will be as many broadcasted messages in this phase as in phase 2 ($(n^2)/4$ in the worst case). $h_3$ is the end of this phase and the end of the protocol.

6. At $h_3$, every node $P_i$ can use all the received data through all the channels to get to a conclusion:

   • DKG has succeeded: all honest nodes are able to retrieve the same distributed keys. Byzantine nodes either retrieve wrong data, or are disqualified from the protocol because of a wrong behaviour. In both cases, this does not impact the threshold signature in the next epoch.
   • DKG has failed: there were less than $t+1$ honest nodes and this is not enough to have valid keys to run the threshold signature in the next epoch.

7. In the case where DKG has succeeded, every honest node is able to compute locally two types of data:

   • a private data : the random beacon private key to be used in the threshold signature
   • a public data :

     • all the public keys corresponding to the random beacon private keys of all nodes.

     • the group public key, which is the public key corresponding to the secret private key that the DKG has generated and shared.

       $h_0$                                      $h_1$                                      $h_2$                                     $h_3$
       

   

   DKG Phases and deadlines

The protocol from a node-perspective:

From a perspective of one particular honest node, the protocol should look simpler, here is what the node should do to participate in a instance of DKG:

• Anytime before $h_0$: Create an instance of Joint-Feldman DKG using: