Context:

• Distributed Key Generation [DKG] is the setup phase of the random beacon. It is run among the n next-epoch participants during the epoch setup phase.
• The DKG is a protocol that allows the n participants (enumerated for simplicity i ∈ {0,1, ... n-1}) to generate an implicit private key SK and its corresponding public key PK , and to divide it into n key shares, each share is a key pair (sk_i, pk_i) with regards to a threshold parameter t (see parameter t below). The private group key SK remains unknown to any subgroup of up-to t participants. The generated keys can be used by a threshold signature scheme parametrized t.

An epoch smart contract gathers the final DKG results from each node (specifically, the public key shares pk_i and the public group key PK) The overall Epoch setup succeeds if enough nodes end up computing the same results. How much is “enough” ?

DKG native threshold

In Flow, DKG is used to set up the keys of a threshold signature scheme. The DKG parameter t is therefore set to be equal to the parameter t used by the threshold signature scheme and the overall random beacon design.

For details please see Threshold Signatures.

Notation:

• $C$ is the set of all epoch participants with $|C|=n$ ,
• $H$ denotes the honest subset and $M$ is the malicious subset, i.e. $C = H \\cup M$ and $M \\cap H = \\emptyset$ . The number of malicious participants is $m = |M|$ .

Flow protocol chose t to be floor((n-1)/2) to maximize the number of malicious participants m (as defined above) the beacon can handle. That value is referred to informally as “50%” although it’s not precisely equal to half.

For the overall DKG and the epoch setup phase to succeed, it’s required that at least t+1 nodes agree on the same result (by submitting the same result to the epoch contract). This is the native required success threshold t_native = t+1 (informally 50% +1). Note that this is a threshold expressed in number of nodes, not in staked value. We make the assumption that all honest nodes (online and behaving per the protocol rules) succeed DKG.

Hotstuff

Hotstuff is run among the same DKG participants $C$ (in mature Flow, DKG participants are only a subset of Hotstuff participants). Hotstuff makes the assumption that malicious nodes $M \\sub C$ (or nodes controlled by a malicious adversary) do not reach 1/3 of the total staked value (not in number of nodes!).

We can distinguish two ways to model the adversary:

• (A) static: a static adversary controls the same nodes (and stake) during the entire epoch and the epoch setup. In that case, the nodes $H$ that are honest during the epoch setup are also the same honest $H$ nodes during all blocks of the epoch.
• (B) dynamic/adaptive: a more powerful adversary can control different nodes at different times, but at any given time, the staked valued controlled by the adversary is less than 1/3. We define the point of “times” as the block rounds. We consider the DKG protocol as the initial block 0. Although DKG takes longer time than a block round, we consider it as a single point of time for simplicity. For this model we define the honest and malicious subsets for a single block $B$ as $H^{B}$ and $M^{B}$ respectively.

To make the analysis simpler, we will assume all participants have staked equally, so that the remaining reasoning only focuses on number of nodes. In this case, Hotstuff’s requirement about 1/3 stake is simplified to:

• (A) $|M|<1/3\\cdot|C|$ (which also means $|H|>2/3\\cdot|C|$ )