How to use threshold signatures to generate random beacons?

Author: ALEXANDER SKIDANOV

Translation & Proofreading: IAN LIU & A Jian

Source: Ethereum enthusiasts

Looking back at 2015, the DFinity project proposed a random beacon scheme that excited the entire community-using BLS threshold signatures to generate random output, while ensuring the output is unbiased and unpredictable. However, today, until 2020, it is still difficult to construct unbiased and unpredictable random beacons, and few projects are still being studied.

• Swiss Crypto Valley Association Chairman: Central bank digital currency is the next stage in the development of decentralized finance
• Perspectives | Why Should You Hold Bitcoin?
• Babbitt Column | Pan Chao: Automated Market Maker DEX Economics

In fact, threshold signature is only one of the feasible methods for constructing random beacons. We published an overview article earlier, introducing other possible solutions, including one that this article will focus on. Other details-what is a random beacon? What is unbiasedness and unpredictability? What else can you do besides threshold signatures-these questions can be answered in the overview above.

After several design iterations, we finally proposed a solution similar to DFinity, which is also a great opportunity for us to further understand the random beacons.

In this paper, we will describe a series of protocols for generating random numbers with threshold signatures.

Cryptography basics

In order to better understand the random beacons mentioned in this article, we need to have some basic cryptography knowledge. First, we must distinguish between two concepts: 1. In this article, lowercase letters (such as x, y) are used to represent scalars, or ordinary constants; 2. Capital letters are used to represent points on an elliptic curve (elliptic curve point).

We don't need to know the elliptic curve points thoroughly, just grasp the following two points:

1. Elliptic curve points can be added or multiplied by scalars (this is represented by xG in this article, and Gx is also very common), and then another elliptic curve point is obtained.

2. Even if you know the values ​​of G and xG, it is impossible to calculate the value of x.

In this article, we will also use the k-1 order polynomial p (x); for p (x), you do n’t have to think too much, just treat it as an equation, and: as long as you know that there are The value of p (x) under x, you can deduce the value of p (x) for all x.

By analogy, for the same function p (x) and the base point G, if you know the value of p (x) G substituted into k different x values, you can derive the p (x) G values ​​corresponding to all x .

As long as you understand these properties of elliptic curve points, you can understand the working principle of random beacons in depth.

Random beacon

Hypothesis 1: There are n participants in the system, and at least k of them are required to generate random numbers. Even if you control the k-1 of them, you cannot predict the output of random beacons and cannot manipulate the results.

Hypothesis 2: Now there is a k-1 degree polynomial p (x), participant 1 knows the value of p (1), participant 2 knows the value of p (2), …, participant n knows the value of p (n) Value; everyone agreed to use G as the base point of the elliptic curve, and all participants knew that p (x) G was substituted into all values ​​of x. We consider p (i) as the "private share (not public, only the participant knows)" of participant i, and p (i) G is its "public share" (all participants know this value) ( Recalling the previous article, we said that p (i) cannot be derived from p (i) G, so only participant i knows the value of p (i))

The most difficult part of designing a random beacon is to find such a polynomial so that each participant can know their private share, but cannot know the private share of others-this is also called distributed secret Key Generation (DKG). DKG will be discussed in the next chapter. Now let's assume that there is such a polynomial, and everyone knows their private shares.

We then discuss how to use this set of assumptions to generate a random beacon in a blockchain protocol? Suppose the network generates a block, and the block hash is h. Now that the participants want to use h as a seed to generate random numbers, first use the agreed function to convert h to a point on an elliptic curve:

H = scalarToPoint (h)

For participant i, since he knows p (i) and H, he can calculate H_i = p (i) H by himself. The public announcement of H_i does not cause the private share p (i) of participant i to be exposed, so the same private share can be reused in each block, so DKG only needs to do it once.

According to the third feature mentioned above, when at least k participants announce their respective H_i = p (i) H, others will know what H_x = p (x) H is after substituting any of x. . Then all participants can calculate H_0 = p (0) H locally and use the hash value of this result as the output of the random beacon; please note that because no participant knows p (0), the only way to get p The method of (0) H is to perform an interpolation calculation on p (x) H. To complete the interpolation calculation, we need to know at least k values ​​of p (i) H. If there are fewer than k people posted, no one else can infer the value of p (0) H.

A beacon built on this technology continues these features we need: if an attacker only controls less than k-1 participants, he cannot manipulate the output of the random beacon; the other k participants can calculate the final output , A subset of them, or more participants, can all get the same output.

We also ignore one thing. In order to calculate p (0) H using interpolation, it must be guaranteed that H_i disclosed by participant i is really equal to p (i) H. However, since participant i does not know what p (i) is, other than participant i, there is no way to directly verify whether the H_i published by participant i is indeed equal to p (i) H; if a cryptographic certificate is not required for H_i , The attacker can directly claim the value of a certain H_i, while others have no way to distinguish the authenticity.

There are at least two cryptographic proof methods that can be used to determine the authenticity of H_i. We will introduce after talking about DKG.

Distributed Key Generation (DKG)

According to the introduction of random beacons in the previous chapter, we need n participants to use a k-1 polynomial p (x) together, so that each participant i knows its own p (i) and others cannot. Next, all participants need to know: given G, all the values ​​of p (x) g for x.

In this section, we assume that everyone has their own private key x_i, and everyone else knows the public key X_i corresponding to x_i.

One way to run DKG is as follows:

1. Each participant i runs the calculation of k-1 order polynomial p_i (x) locally. Then use the public key X_j to encrypt each p_i (j) (j ≠ i) and send it to the corresponding participant j. In this way, only participant j can decrypt p_i (j); participant i also needs to publish all p_i (j) G, j ∈ 1 ~ k.

2. All participants must agree on a set consisting of at least k polynomials. Because some participants may be offline, they cannot wait until n validators have made such a commitment before proceeding; as long as at least k validators have made a "receive at least k such polynomial" commitment, they will Some form of consensus algorithm (eg, Tendermint) can be used to reach a consensus on a subset Z of the polynomials they receive (Z contains at least k polynomials).

3. All participants jointly verify whether the encrypted p_i (j) corresponds to the public p_i (j) G and remove the unqualified polynomial from Z.

4. For each polynomial p_i (x) in the set Z, each participant j calculates the sum of p_i (j) as a private share p (j); similarly, for each p_i (x) in the set Z G, participants can calculate the sum of p_i (x) G as the public share p (x) G.

Because p (x) is the sum of each independent p_i (x), and each p_i (x) is a k-1 order polynomial, you need to observe whether p (x) is also a k-1 order polynomial. The second thing to note is that each participant j only knows the value of p (j), but not the other values ​​of p (x) (x ≠ j). In fact, in order to know the value of p (x), TA needs to know all p_i (x). As long as the value of at least one promised polynomial is unknown, TA cannot know p (x).

The above steps constitute a complete DKG process. Steps 1, 2, and 4 are relatively intuitive, but step 3 is more complicated.

To explain the third step in detail-we need to find a way to prove that each encrypted p_i (j) has a corresponding relationship with the public p_i (j) G. Without this verification, attacker i can send a random message to participant j instead of sending the correct encrypted p_i (j), preventing participant j from further calculating his own private share.

Although there are ways to make cryptographic proof of the correctness of the form of the encrypted share. However, such proof data is too large, and to publish such a proof to the entire network, the time complexity may be as high as O (nk), and the size of the proof is a serious bottleneck.

In the NEAR protocol, we do not prove the relationship between p_i (j) and the public p_i (j) G, but give each participant sufficient time in the DKG process (that is, reach consensus on the polynomial set Z, and finally Aggregate the private shares, the time interval between the two events), to prove that "the p_i (j) they receive is not the same as the publicly broadcasted p_i (j) G". The agreement assumes that each participant will go online at least once during the window period (about half a day), and the challenges they submit can enter the blockchain. For block producers, both of these assumptions are reasonable, because to be a block producer, generally, the entire epoch must be online; if most block producers plot to not receive this message, in fact The entire system is already insecure, and attackers have better ways to attack the entire system (rather than just rejecting challenge messages).

If a block producer receives an invalid public share and does not promptly challenge the DKG process, the miner will not be able to participate in random number generation during this period. Please note that as long as the other k honest participants can correctly calculate the shares (by not receiving any invalid shares, or challenging all invalid shares in a timely manner), the agreement will still function normally.

prove

One last question remains: How can we prove that the H_i we have announced is equal to p (i) H on the premise of not disclosing p (i)?

Recall that each participant knows the values ​​of H, G, and p (i) G. The operation of back pushing p (i) given p (i) G and G is called the discrete logarithm problem, which is also simply called dlog. Then what each participant wants to do is to be able to prove to others that dlog (p (i) G, G) = dlog (H_i, H) without revealing p (i). There is indeed such a method to construct the above proof, one of them is the Schnorr protocol; through the Schnorr protocol, participants can attach a proof of the correctness of H_i when publishing H_i.

Recall that the output of the random beacon chain is the interpolated value of H_0. For people who are not involved in generating random beacon output, what information is needed in addition to H_0 to verify the correctness of this value? Because everyone can add G_0 to their own calculations, just prove that dlog (G_0, G) = dlog (H_0, H). But because of the nature of the beacon, we cannot know p (0), and we cannot generate such a proof through the Schnorr protocol. So if you want to prove the correctness of H_0 to others, you must keep all H_i values ​​and their corresponding proofs.

However, the good news is that if some calculations are similar to elliptic curve point multiplication, you only need to verify that H_0 × G = G_0 × H to prove that H_0 is correct.

This proof is feasible if the selected elliptic curve supports elliptic curve pairings. In this case, anyone who knows G, H, and G_0 can verify H_0 (the output of a random beacon); and H_0 can also be considered as a collective multi-signature to prove the correctness of block n with at least k bits of participation Inspection certification.

Currently we have not used elliptic curve pairing in NEAR, but we may use it in the future and then use the tips discussed above to replace the single signature method we currently use. On the other hand, DFinity uses BLS signatures, which can be implemented by pairing operations.

Original link: https://nearprotocol.com/blog/randomness-threshold-signatures/

We will continue to update Blocking; if you have any questions or suggestions, please contact us!