Hello, Habr!
In this article, I will discuss the generation of pseudo-random numbers by participants who do not trust each other. As we will see below, implementing a 'good enough' generator is relatively straightforward, but creating a very good one is challenging.
Why is it necessary to generate random numbers for participants who do not trust each other? One application area is decentralized applications. For instance, an application that accepts a bet from a participant and either doubles the amount with a 49% probability, or takes it with a 51% probability, will only work if it can unbiasedly obtain a random number. If a malicious actor can influence the outcome of the random number generator, even slightly increasing their odds of receiving a payout in the application, they can easily drain it.
When we develop a distributed random number generation protocol, we want it to possess three properties:
It must be unbiased. In other words, no participant should have any way to influence the outcome of the random number generator.
It must be unpredictable. In other words, no participant should be able to forecast what number will be generated (or derive any of its properties) before it is generated.
The protocol should be viable, meaning it should be resilient to the scenario where some percentage of participants disconnect from the network or deliberately attempt to halt the protocol.
In this article, we will examine two approaches: RANDAO + VDF and an approach based on erasure codes. In the next part, we will delve deeper into the approach based on threshold signatures.
But first, let’s explore a simple and often-used algorithm that is viable, unpredictable, yet biased.
RANDAO
RANDAO is a very simple and, consequently, a fairly commonly used method for obtaining randomness. All participants in the network first locally select a pseudo-random number, then each participant sends a hash of their chosen number. Next, participants take turns revealing their chosen numbers and perform an XOR operation on the revealed numbers, with the result of this operation becoming the output of the protocol.
The step of publishing hashes before revealing the numbers is necessary so that the attacker cannot choose their number after seeing the numbers of other participants. This would allow them to unilaterally determine the output of the random number generator.
Throughout the protocol, participants need to come to a consensus twice: when to start revealing the chosen numbers, thus stopping the acceptance of hashes, and when to finish accepting the chosen numbers and compute the resulting random number. Making such decisions among participants who do not trust each other is a complex task in itself, and we will return to it in future articles. For this article, we will assume that such a consensus algorithm is available to us.
What properties described above does RANDAO have? It is unpredictable, has the same viability as the underlying consensus protocol, but it is biased. Specifically, an attacker can observe the network, and after other participants reveal their numbers, they can compute their XOR and decide whether to reveal their own number to influence the outcome. While this does not allow an attacker to unilaterally determine the output of the random number generator, it still gives them 1 bit of influence. If attackers control multiple participants, the number of bits they control will equal the number of participants under their control.
The influence of attackers can be significantly reduced by requiring participants to reveal numbers sequentially. In this case, an attacker can only influence the outcome if they reveal last. While the influence is much smaller, the algorithm is still biased.
RANDAO + VDF
One option to make RANDAO unbiased is as follows: after all numbers are revealed and the XOR is calculated, its result is fed into a function that takes a long time to compute but allows checking the correctness of the computation very quickly.
(vdf_output, vdf_proof) = VDF_compute(input) // this is very slow
correct = VDF_verify(input, vdf_output, vdf_proof) // this is very fastThis function is called a Verifiable Delay Function, or VDF. If computing the final result takes longer than the reveal phase, a malicious actor will not be able to predict the effect of revealing or hiding their number, and thus, will lose the ability to influence the outcome.
Designing efficient VDFs is extremely challenging. Recently, several breakthroughs have been made, for example, and which have made VDFs more practically applicable, and Ethereum 2.0 plans to use RANDAO with VDF as a source of randomness in the long term. Besides the fact that this approach is unpredictable and unbiased, it has the additional advantage of being viable if at least two participants are available in the network (provided that the consensus protocol used is functional with such a small number of participants).
The biggest challenge of this approach is configuring VDFs so that even a participant with very expensive specialized equipment cannot compute the VDF before the reveal phase ends. Ideally, the algorithm should have a significant margin, say, 10x. The illustration below shows an attack by a participant with specialized ASIC equipment, allowing them to run the VDF faster than the time allocated for revealing the RANDAO confirmation. Such a participant can still compute the final result using or not using their number, and then, based on the calculations, decide whether to reveal it or not.
For the aforementioned family of VDFs, the performance of specialized ASICs can be over 100 times greater than that of standard equipment. Thus, if the reveal phase lasts for 10 seconds, the VDF computed on such an ASIC should take more than 100 seconds to have a tenfold safety margin; therefore, the same VDF computed on standard equipment should take 100 x 100 seconds = ~ 3 hours.
The Ethereum Foundation plans to address this issue by creating its own public, free ASICs. Once this occurs, all other protocols may also benefit from this technology, but until then, the RANDAO + VDF approach will not be as viable for protocols that cannot invest in developing their own ASICs.
Many articles, videos, and other information about VDF are collected on .
We use erasure codes
In this section, we will examine the protocol for generating random numbers that utilizes . It can withstand up to ⅓ of adversaries while remaining viable, and can tolerate the existence of up to ⅔ of adversaries before they can predict or influence the outcome.
The main idea of the protocol is as follows. For simplicity, let's assume it has exactly 100 participants. Let's also assume that all participants have some private key locally, and the public keys of all participants are known to everyone:
Each participant locally generates a long string, splits it into 67 parts, creates erasure codes to obtain 100 shares, such that any 67 are sufficient to reconstruct the string, assigns each of the 100 shares to one of the participants, and encrypts them using the public key of the same participant. Then all encoded shares are published.
Participants use some consensus mechanism to reach an agreement on the encoded sets from specific 67 participants.
Once consensus is reached, each participant takes the encoded shares from each of the 67 sets, encrypted with their public key, decrypts all such shares, and publishes all such decrypted shares.
Once 67 participants have completed step (3), all agreed sets can be fully decoded and reconstructed due to the properties of erasure codes, and the final number can be obtained as the XOR of the initial strings from which participants began in (1).
It can be shown that this protocol is unbiased and unpredictable. The resulting random number is defined after reaching consensus, but it is unknown to anyone until ⅔ of the participants decode the parts encrypted with their public key. Thus, the random number is defined before the information necessary for its recovery is published.
What happens if at step (1) one of the participants sends encoded shares to the other participants that do not represent a valid erasure code of some string? Without additional modifications, different participants will either be unable to recover the string at all or will recover different strings, leading to different participants receiving different random numbers. To prevent this, the following can be done: each participant, in addition to the encoded shares, also computes of all such shares, and sends each participant both the encoded share itself and the Merkle tree root, along with a proof of inclusion of the share in the Merkle tree. During consensus at step (2), the participants agree not just on sets of shares, but on specific roots of such trees (if some participant deviated from the protocol and sent different Merkle tree roots to different participants, and two such roots are shown during consensus, their share will not be included in the resulting set). As a result of the consensus, we will have 67 encoded strings and their corresponding Merkle tree roots such that there are at least 67 participants (not necessarily the same ones who proposed the corresponding strings), each of whom has a message with a share of the erasure code, and proof of inclusion of their share in the corresponding Merkle tree.
When at step (4) a participant decodes 67 shares for some string and attempts to recover the original string, one of the following scenarios is possible:
The string is successfully recovered, and if it is then encoded with erasure codes again, and the Merkle tree for the locally computed shares is calculated, the root matches the one on which consensus was reached.
The string is successfully recovered, but the locally calculated root does not correspond to the one on which consensus was reached.
The string cannot be recovered.
It is easy to show that if at least one participant encounters case (1), then all participants will encounter case (1), and conversely, if at least one participant encounters case (2) or (3), then all participants will encounter case (2) or (3). Thus, for each line in the set, either all participants will successfully reconstruct it, or all participants will be unable to reconstruct it. The resulting random number is the XOR of only those lines that participants were able to restore.
Threshold Signatures
Another approach to randomness involves the use of what are known as BLS threshold signatures. A random number generator based on threshold signatures has the same guarantees as the aforementioned erasure code-based algorithm but has significantly lower asymptotic messaging overhead for each generated number.
BLS signatures are a construct that allows several participants to create a single common signature for a message. Such signatures are often used to save space and bandwidth by eliminating the need to transmit multiple signatures.
A common application for BLS signatures in blockchain protocols, aside from random number generation, is block signing in BFT protocols. For instance, 100 participants create blocks, and a block is considered final if 67 of them sign it. They can present their parts of the BLS signature and use some consensus algorithm to agree on 67 of them, and then combine them into a single BLS signature. Any 67 (or more) parts can be used to create the final signature, which will depend on which specific 67 signatures were combined, and therefore may vary; however, despite the different selections of 67 participants resulting in different signatures, any such signature will be a valid signature for the block. The remaining participants only need to receive and verify one signature per block over the network instead of 67, which significantly reduces the load on the network.
It turns out that if the private keys used by the participants are generated in a certain way, then regardless of which 67 signatures (or more, but not less) are aggregated, the resulting signature will be the same. This can be used as a source of randomness: participants first agree on a message that they will sign (this can be an output from RANDAO or simply the hash of the last block, it doesn't really matter, as long as it changes every time and is agreed upon), and create a BLS signature for it. The generation output will be unpredictable until 67 participants provide their shares, after which the output is predetermined and cannot depend on any participant's actions.
This approach to randomness is viable if at least ⅔ of the participants are online and following the protocol, and it remains fair and unpredictable as long as at least ⅓ of the participants adhere to the protocol. It is important to note that an attacker who controls more than ⅓ but less than ⅔ of the participants can halt the protocol but cannot predict or influence its output.
Threshold signatures themselves are a very interesting topic. In the second part of the article, we will delve into how they work and how exactly participants' keys need to be generated for threshold signatures to be used as a random number generator.
In conclusion
This article is the first in a series of technical articles in the blog . NEAR is a blockchain protocol and platform for developing decentralized applications with a focus on ease of development and usability for end users.
The protocol code is open, and our implementation is written in Rust, which can be found at .
You can see what development looks like on NEAR and experiment in the online IDE .
You can follow all the news in Russian in the and in , and in English in the official .
See you soon!
Source: habr.com
