New randomness beacon

[abacabadabacaba]

The new randomness beacon (RNG) was implemented in February 2020 and is still not used. Also, the description of the RNG was not published anywhere, so I decided to write it.

The RNG implements a protocol that allows the participants to jointly generate a random number such that it cannot be predicted in advance or biased in any way so long as the fraction of malicious participants is 1/3 or less. The protocol has two stages:

1. Key generation: during this stage, the participants jointly generate a key for a threshold verifiable random function (VRF). This only needs to be performed when the set of participants changes, which in general happens once per epoch.
2. VRF evaluation: the participants jointly evaluate the VRF using the height of the current block as an argument. The result is the generated random number.

Notation

The scheme is based on a group 𝔾 of prime order. The elements of the group are called points, and the integers modulo the group's order are called scalars. A generator of the group is denoted by G.

The scheme uses a hash function, denoted by ℋ. When used without a subscript, the codomain of ℋ is assumed to be the set of all byte sequence of the same length as the encoding of a scalar. Two other hash functions are used: ℋ_s and ℋ_p. The codomains of those functions are the sets of all scalars and points, respectively.

In this scheme, there are n participants (validators). All participants are equal, so in reality validators with higher stake can take the role of multiple participants. At least k participants need to collude to reveal the key, so the value k is chosen to be about 2/3 n. The participants are numbered by the natural numbers 1, 2, …, n.

Each participant has a public key V_i, which is a point (i is the index of the participant). The corresponding scalar is v_i, so that V_i = v_iG. During key generation, each participant generates a polynomial p_i over the scalars of degree at most k − 1. Later, a shared polynomial p is constructed with the same properties. While the coefficient of those polynomials are private, the corresponding points P_i(x) = p_i(x)G and P(x) = p(x)G are public and can be used to verify the private values.

Threshold VRF scheme

In this scheme, the private key is a scalar a, and the public key is the group element A = aG. The output of the VRF on the value x is aℋ_p(x).

No participant has the private key. Instead, the key is distributed using Shamir's secret sharing scheme. That is, there is a random polynomial p, such that the value p(0) is the private key, and i-th participant has the value p(i). To compute the output, each participant computes and reveals p(i)ℋ_p(x), from which the value p(0)ℋ_p(x) can be derived using polynomial interpolation.

Key generation

During the key generation phase, each participant chooses a random polynomial p_i of degree at most k − 1. They publish the values P_i(j) for 1 ≤ j ≤ k, and also encrypt each of the values p_i(j) for 1 ≤ j ≤ n using j-th participant's public key.

To prove that they generated the polynomials themselves and not derived them from the polynomials generated by other participants, the participants provide a proof of knowledge of the values p_i(j). For that, they generate a random scalar r and publish the values R = rG and s = r − ℋ_s(D, 1)p_i(1) − ℋ_s(D, 2)p_i(2) − … − ℋ_s(D, k)p_i(k), where D consists of the participant's public key, the values P_i(j) for 1 ≤ j ≤ k, and R. To verify the proof, one needs to check that R = sG + ℋ_s(D, 1)P_i(1) + ℋ_s(D, 2)P_i(2) + … + ℋ_s(D, k)P_i(k).

To encrypt the value p_i(j) to a public key V_j, the participant computes a shared secret S = p_i(j)V_j, then computes and publishes the value E = ℋ(S) xor p_i(j). To decrypt, the recipient computes S = v_jP_i(j) and p_i(j) = E xor ℋ(S). Unfortunately, the correctness of the encryption cannot be publicly verified, so the receipient must either confirm the encryption's correctness or show a proof that it is incorrect. To prove that the encryption is not correct, the recipient publishes the value S and a proof of correctness of that value. To generate this proof, the participant generates a random scalar r and publishes c = ℋ_s(V_j, P_i(j), S, rG, rP_i(j)) and s = r − cv_j. To verify, one needs to check chat c = ℋ_s(V_j, P_i(j), S, sG + cV_j, sP_i(j) + cS).

If at least one of the encrypted values is shown to be incorrect, the participant which generated it is slashed and all values produced by that participant are discarded. When enough polynomials have been distributed this way among at least k participants, they can compute the shared polynomial p as the sum of the individual participant's polynomials that were selected. Each participant knows the value of that polynomial at one point, and all participants know the entire polynomial multiplied by G. The value p(0) is the shared private key, and the value P(0) is the shared public key.

VRF evaluation

The generated random value is the result of evaluating the VRF on the value x, which can be just the block height. First, the value is hashed to the point X = ℋ_p(x). Then, it needs to be multiplied by the shared private key p(0). To do this, each participant publishes the share S_i = p(i)X and a proof of correctness, which is computed in the usual manner: the participant generates a random scalar r, then computes and publishes c = ℋ_s(P(i), S_i, rG, rX) and s = r − cp(i). To verify, one needs to check that c = ℋ_s(P(i), S_i, sG + cP(i), sX + cS_i).

After at least k shares are collected, the final value can be recovered using polynomial interpolation.

Implementation details

Because this scheme is not currently used, these details are subject to change.

In this implementation, the group 𝔾 is the ristretto255 group. Unlike Curve25519, this group's order is actually a prime, which is important for the security of the scheme. The points and the scalar are encoded in the usual way. The hash function ℋ is BLAKE2b with 32-byte output, ℋ_s is the same but taken modulo the group order, and ℋ_p is BLAKE2b with 64-byte output converted to a group element using Ristretto-flavored Elligator map.

When generating the proof for the polynomial, a different hash function is used: ℋ(D) is computed and used as a key for ChaCha20/20 (with zero nonce), and the first 32k bytes of the key stream are interpreted as k scalars (by taking each 32 bytes modulo group size).

[ilblackdragon]

Thanks for writing this out! Also for less technical explanation - https://near.org/blog/randomness-threshold-signatures/

Should the technical specification be converted into NEP and scheduled for implementation (integration of existing code in this case)?