Hey Habr!
В In this article, we discussed why it might be necessary to generate random numbers for participants who do not trust each other, what requirements are put forward for such random number generators, and considered two approaches to their implementation.
In this part of the article, we will take a closer look at another approach that uses threshold signatures.
A bit of cryptography
To understand how threshold signatures work, you need to understand a bit of basic cryptography. We will use two concepts: scalars, or simply numbers, which we will denote by lowercase letters (x, y) and points on the elliptic curve, which we will denote by capital letters.
To understand the basics of threshold signatures, you don't need to understand how elliptic curves work, other than a few basic things:
-
Points on an elliptic curve can be added and multiplied by a scalar (we will denote multiplication by a scalar as xG, although the notation Gx also frequently used in the literature). The result of addition and multiplication by a scalar is a point on an elliptic curve.
-
Knowing only the point G and its product with a scalar xG cannot be calculated x.
We will also use the concept of a polynomial p(x) degree k-1. In particular, we will use the following property of polynomials: if we know the value p(x) for any k different x (and we don't have any more information about p(x)), we can calculate p(x) for anyone else x.
Interestingly, for any polynomial p(x) and some point on the curve G, knowing the value p(x)G for any k different meanings x, we can also calculate p(x)G for any x.
This information is enough to dig into the details of how threshold signatures work and how to use them to generate random numbers.
Random number generator on threshold signatures
Let's assume that n participants want to generate a random number, and we want the participation of any k there were enough of them to generate a number, but so that the attackers who control k-1 or fewer participants could not predict or influence the number generated.
Suppose there is such a polynomial p(x) degree k-1 that the first participant knows p (1), the second knows p(2), and so on (nth knows p (n)). We also assume that for some predetermined point G everybody knows p(x)G for all values x. We will call p(i) “private component” i-th participant (because only i-th participant knows it), and p(i)G “public component” ith participant (because all participants know it). Remember, knowledge p(i)G not enough to recover p(i).
Creating such a polynomial so that only i-th participant and no one else knew his private component - this is the most complex and interesting part of the protocol, and we will analyze it below. For now, let's assume that we have such a polynomial, and all participants know their private components.
How can we use such a polynomial to generate a random number? First we need some string that hasn't been used as input to the generator before. In the case of a blockchain, the hash of the last block h is a good candidate for such a string. Let the participants want to generate a random number using h as seed. Participants first convert h to a point on the curve using any predefined function:
H = scalarToPoint(h)
Then each participant i calculates and publishes Hi = p(i)H, what can they do because they know p(i) and H. Disclosure Hi prevents other participants from restoring the private component ith member, and therefore one set of private components can be used from block to block. Thus, the expensive polynomial generation algorithm described below only needs to be performed once.
When k participants were opened Hi = p(i)H, everyone can calculate Hx= p(x)H all x thanks to the property of polynomials that we discussed in the last section. At this moment, all participants calculate H0 = p(0)H, and this is the resulting random number. Note that no one knows p(0), and hence the only way to calculate p(0)H – this is an interpolation p(x)H, which is only possible when k values p(i)H known. Opening any smaller quantity p(i)H does not provide any information about p(0)H.
The generator above has all the properties we want: attackers controlling only k-1 participants, or less, have no information and influence on the conclusion, while any k participants can calculate the resulting number, and any subset of k participants will always come to the same result for the same seed.
There is one problem that we carefully avoided above. For interpolation to work, it is important that the value Hi posted by each participant i it really was the same p(i)H. Since no one but iparticipant does not know p(i), no one but i-th participant cannot verify that Hi actually calculated correctly, and without any cryptographic proof of correctness Hi an attacker can publish any value as Hi, and arbitrarily influence the output of the random number generator:
Different values of H_1 sent by the first participant lead to different resulting H_0
There are at least two ways to prove the correctness Hi, we will consider them after we analyze the generation of the polynomial.
Polynomial generation
In the last section, we assumed that we have such a polynomial p(x) degree k-1 that the participant i know p(i), and no one else has any information about this value. In the next section we will also need that for some predetermined point G everyone knew p(x)G all x.
In this section, we will assume that each participant has some private key locally. xi, such that everyone knows the corresponding public key Xi.
One possible polynomial generation protocol is as follows:
-
Each member i locally creates an arbitrary polynomial pi(x) of degree k-1. They then send each participant j value pi(j) encrypted with the public key Xj. So only i-th и j-th participant know pi(j). Participant i also publicly announces pi(j)G all j from 1 to k inclusive.
-
All participants use some kind of consensus to choose k participants whose polynomials will be used. Since some participants may be offline, we cannot wait until everyone n participants will publish polynomials. The result of this step is a set Z consisting of at least k polynomials created in step (1).
-
Participants make sure that the values they know pi(j) correspond to publicly announced pi(j)G. After this step in Z only polynomials for which privately transmitted pi(j) correspond to publicly announced pi(j)G.
-
Each member j calculates its private component p(j) as a sum pi(j) for all i в Z. Each participant also calculates all values p(x)G as a sum pi(x)G for all i в Z.
Note that p(x) – it is indeed a polynomial of degree k-1, because it is the sum of the individual pi(x), each of which is a polynomial of degree k-1. Then, note that while each participant j know p(j), they have no information about p(x) for x ≠ j. Indeed, in order to calculate this value, they need to know everything pi(x), and as long as the participant j does not know at least one of the selected polynomials, they do not have sufficient information about p(x).
This is the entire polynomial generation process that was needed in the last section. Steps 1, 2 and 4 above have a fairly obvious implementation. But step 3 is not so trivial.
Specifically, we need to be able to prove that encrypted pi(j) indeed correspond to the published pi(j)G. If we can't prove it, the attacker i may send garbage instead pi(j) to participant j, and participant j can't get the real value pi(j), and will not be able to calculate its private component.
There is a cryptographic protocol that allows you to create an additional message pi(j) such that any participant, having some value e, as well as proofi(j) и pi(j)G, can verify locally that e - it's really pi(j), encrypted with the member's key j. Unfortunately, the size of such evidence is incredibly large, and given that it is necessary to publish O(nk) such evidence cannot be used for this purpose.
Instead of proving that pi(j) соответствует pi(j)G we can allocate a very large period of time in the polynomial generation protocol, during which all participants check the received encrypted pi(j), and if the decrypted message does not match the public pi(j)G, they publish a cryptographic proof that the encrypted message they received is incorrect. Prove that the message not соответствует pi(G) much easier than proving that it matches. It should be noted that this requires each participant to appear on the network at least once during the time allocated to create such evidence, and relies on the assumption that if they publish such a proof, it will reach all other participants in the same allotted time.
If a participant did not appear on the network during this period of time, and he really had at least one incorrect component, then this particular participant will not be able to participate in further number generation. The protocol, however, will still function if there is at least k participants who either just received the correct components, or managed to leave a proof of incorrectness in the allotted time.
Correctness proofs for H_i
The last part that remains to be discussed is how to prove the correctness of the published Hi, namely that Hi = p(i)H, without opening p(i).
Recall that the values H, G, p(i)G public and known to all. receive operation p(i) knowing p(i)G и G is called the discrete logarithm, or dlog, and we want to prove that:
dlog(p(i)G, G) = dlog(Hi, H)
without disclosure p(i). There are constructions for such proofs, for example.
With this design, each participant, along with Hi sends a proof of correctness according to the design.
Once a random number has been generated, it often needs to be used by parties other than those who generated it. Such participants, along with the number, must send all Hi and related evidence.
An inquisitive reader may ask: since the final random number is H0, and p(0)G this is public information, why do you need proof for each individual Hi why not send proof of that instead
dlog(p(0)G, G) = dlog(H0, H)
The problem is that you can't create such a proof using the Schnorr Protocol because no one knows the meaning. p (0)required to create a proof, and what's more, the whole random number generator is based on the fact that no one knows this value. Therefore, it is necessary to have all the values Hi and their individual proofs to prove correctness H0.
However, if there were some operation on points on elliptic curves that is semantically similar to multiplication, the proof of correctness H0 would be trivial, we would just make sure that
H0 × G = p(0)G×H
If the selected curve supports , this proof works. In this case H0 is not only the output of a random number generator that can be tested by any participant who knows G,H и p(0)G. H0 is also the signature on the message that was used as a seed, confirming that k и n participants signed this message. Thus, if seed- is the block hash in the blockchain protocol, then H0 is both a multi-signature on a block and a very good random number.
In conclusion
This article is part of a technical blog series . NEAR is a blockchain protocol and decentralized application development platform with a focus on ease of development and ease of use for end users.
The protocol code is open, our implementation is written in Rust, it can be found .
You can see what development under NEAR looks like, and you can experiment in the online IDE .
You can follow all the news in Russian in and , and in English in the official .
See you soon!
Source: habr.com