The document describes both Joint-Feldman and Gennaro et al. DKG protocols, but the protocol implemented in Flow is Joint-Feldman.
Context:
Flow requires a source of randomness for several sub protocols. For each Epoch, the generation process outputs a sequence of pseudo-randoms that are deterministic, unpredictable till the random is revealed, agreed upon by all nodes, and verifiable by anyone against the commitment.
Protocol overview:
Since the protocol is heavy to be run by all security nodes, a relatively smaller group runs the protocol. The members of the group are self-assigned before the Epoch starts and are in charge of generating the randoms until the next Epoch. The protocol starts by running a Distributed Key Generation (DKG) to generate a common secret key for the group S. A threshold signature (TS) is run every time a random is needed afterwards. The signature output using the generated secret key is the new random R_n for block view n : Initially R_n was proposed to be
R_n = hash(sign(S, R_n-1)) , it was later updated to R_n = hash(sign(S, B_n-1)) where B_n is the block hash of view n .
Both (DKG) and (TS) are run using a BLS signature setup (cyclic groups G1 and G2 with hard CDH and easy DDH, generators g1 and g2..). we’ll use the multiplicative notation for G1 and G2.
In both protocols, the threshold t is fixed to floor((n-1)/2) to maximize the number of malicious nodes the group can handle. Malicious nodes of a number up to the threshold t are not able to uncover the value of the secret key S nor prevent the generation of S. Below is a (very) brief description of (DKG) and (TS).
Distributed Key Generation:
DKG is based on VSS (Verifiable Secret Sharing). The purpose of Feldman VSS is to generate a secret key S and to distribute secret shares S_i over n participants P_1 .. P_n, such that t+1 shares S_i can construct S but up to t shares don’t reveal any information about S.
In a very similar way to Shamir Secret Sharing (SSS), a trusted dealer generates a polynomial P of degree t : P(x) = a_0 + a_1*x + … + a_t*x^t.
The secret S is set to a_0 = P(0), and for all i in {1..n}, S_i = P(i).
Unlike SSS, a verification vector [A_j, j = 0..t] is computed and published such that A_j = g^a_j Each S_i is secretly shared with P_i. Each participant P_i is able to verify their share S_i using [A_j]:g^S_i = A_0^(i^0) * A_1^(i^1) * ….. * A_t^(i^t). The public key in this case is A_0 = g^S .
Feldman VSS is a modification of VSS where a dealer can be disqualified or not depending on the correctness of the distributed shares (we omit the details in this doc).
Feldman VSS is centralized. Although the secret shares are verifiable, S is generated solely by the dealer. The joint-Feldman protocol allows a decentralized key generation and distribution by running n parallel instance of Feldman VSS, each with a participant P_i as a dealer. For each participant P_i, the secret share S_i is the sum of the n shares: its own and the n-1 received from the n-1 other dealers. The secret key S is the sum of the n secret keys generated by the ndealers. The public key g^S is the product of all the n A_0 verification coefficients. This was only the happy path description where all participants acted honestly (the unhappy path requires the disqualification addition in the protocol from Feldman VSS).
The DKG protocol [GJKR] is very similar to the joint-Feldman protocol. A second round of interaction is added to commit on the secret shares and solve the last actor problem in the joint-Fedlman protocol (where the public key can be chosen by the last actor) : Every dealer generates two polynomials P and P’ and shares s_i=P(i) and s’_i=P’(i) to each participant P_i. The verification vector [A_j, j=0..t] from joint-Feldman is replaced by [C_j, j=0..t] where C_j = g^a_j * h^a’_j , where a_j and a’_j are the coefficients of P and P’, and h is an element of G1 . The shares s_i and s’_i are verified thanks to [C_j, j=0..t]. This first phase commits the overall secret S, without the public key g^S being computed by any party. The public key is computed in a second interaction round. This time the vector [A_j, j=0..t] is published. The share s_i can be verified thanks to the vector [Aj]. Any dealer who changes the value of the committed s_j can be uncovered at this step. The rest of the protocol is similar to joint-Feldman protocol where the public key is retrieved. ( again, this was only the happy path when all participants acted honestly )
Threshold Signature:
Let’s assume we’re given n participants, each has a private key S_i and a public key y_i = g^S_i . A group private key S has been generated but only t+1 participants can reconstruct its value. A public key y = g^S is known to all participants. Note that this setup can be done through a DKG (the ones described above), or any other key generation process.
S of a known message M. The Threshold signature can only be found if at least t+1 participants sign the message M using their private keys S_i. The signature is independent of the subgroup that signs the message M.- each participant P_i computes and publishes the BLS v_i = Sign(S_i, M )v_i using their public keys y_i- any pary that received t+1 valid signatures is able to reconstruct the signature V = v_0^l_0 * .. * v_t^l_t where l_i are the Lagrange coefficients i at point 0.Performance: