Introduction
"Random number generation is too important to be left to chance"
Robert Caviu, 1970
This article focuses on the practical application of solutions that use collective random number generation in an untrusted environment. In short, how and why random is used in blockchains, and a little about how to distinguish “good” random from “bad”. Generating a truly random number is an extremely difficult problem, even on a single computer, and has long been studied by cryptographers. Well, in decentralized networks, the generation of random numbers is even more complex and important.
It is in networks where participants do not trust each other that the ability to generate an undeniable random number allows you to effectively solve many critical problems and significantly improve existing schemes. Moreover, gambling and lotteries are not at all the number one goal here, as it may seem to an inexperienced reader at first.
Random number generation
Computers cannot produce random numbers themselves, they need outside help to do so. A computer can generate some random value using, for example, mouse movements, the amount of memory used, parasitic currents on processor pins, and a variety of other sources called entropy sources. These values themselves are not completely random, as they are in a certain range or have a predictable pattern of change. To turn such numbers into a truly random number in a given range, crypto transformations are applied to them in order to obtain uniformly distributed pseudo-random values from the unevenly distributed values of the entropy source. The resulting values are called pseudo-random, since they are not truly random, but deterministically produced from entropy. Any good cryptoalgorithm, when encrypting data, produces ciphertexts that should be statistically indistinguishable from a random sequence, so for the production of randomness one can take an entropy source that provides only good non-repeatability and unpredictability of values even in small ranges, the rest of the work on scattering and mixing bits in the resulting value will be taken over by the encryption algorithm.
To complete a brief educational program, I will add that the generation of random numbers even on the same device is one of the pillars of ensuring the security of our data, the generated pseudo-random numbers are used to establish secure connections in various networks, to generate cryptographic keys, for load balancing, integrity control, and for many more applications. The security of many protocols depends on being able to generate a reliable, externally unpredictable random, keep it, and not reveal it until the next step of the protocol, otherwise the security will be compromised. An attack on a pseudo-random value generator is extremely dangerous and immediately jeopardizes all software that uses randomness generation.
You should know all this if you took a basic course in cryptography, so let's continue about decentralized networks.
Random in blockchains
First of all, I will talk about blockchains with support for smart contracts, they are the ones who can take full advantage of the opportunities provided by high-quality undeniable randomness. Hereafter, for brevity, I will refer to this technology as “Publicly Verifiable Random Beaconsor PVRB. Since blockchains are networks in which information can be verified by any participant, the key part of the name is “Publicly Verifiable”, i.e. anyone can use calculations to prove that the resulting number placed on the blockchain has the following properties:
- The result must have a provably uniform distribution, i.e. based on provably secure cryptography.
- None of the result bits can be controlled. As a consequence, the outcome cannot be predicted in advance.
- You cannot sabotage the generation protocol by not participating in the protocol or by overloading the network with attacking messages
- All of the above must be resistant to collusion by the allowable number of dishonest participants in the protocol (for example, 1/3 of the participants).
Any possibility for a conspiring minor group of participants to produce even a controlled even/odd random is a security hole. Any possibility for the group to stop the randomization is a security hole. In general, there are many problems, and this task is not easy ...
It seems that the most important application for PVRB is various games, lotteries, and in general any form of gambling on the blockchain. Indeed, this is an important direction, but randomness in blockchains has more important applications. Let's consider them.
Consensus algorithms
PVRB is of great importance for organizing network consensus. Transactions in blockchains are protected by an electronic signature, so a “transaction attack” is always the inclusion / exclusion of a transaction in a block (or several blocks). And the main task of the consensus algorithm is to agree on the order of these transactions and on the order of the blocks that these transactions include. Also, a necessary property for real blockchains is finality - the ability of the network to agree that the chain to the finalized block is final, and will never be excluded due to the appearance of a new fork. Usually, in order to agree that the block is valid and, most importantly, final, it is required to collect signatures from most block producers (hereinafter BP - block-producers), which requires at least delivering the block chain to all BPs, and distributing signatures between all BPs . With an increase in the number of BPs, the number of necessary messages in the network grows exponentially, therefore, consensus algorithms that require finality, used for example in Hyperledger's pBFT consensus, do not work at the required speed, starting from a few dozen BPs, requiring a huge number of connections.
If the network has an undeniable and honest PVRB, then, even in the simplest approximation, one of the block producers can be selected based on it and appointed as the “leader” during one round of the protocol. If we have N block producers, of which M: M > 1/2 N are honest, do not censor transactions, and do not fork the chain in order to carry out a “double spend” attack, then using an evenly distributed undeniable PVRB will allow choosing an honest leader with a probability M / N (M / N > 1/2). If each leader is assigned its own time interval during which he can produce a block and validate the chain, and these intervals are equal in time, then the chain of blocks of honest BPs will be longer than the chain formed by malicious BPs, and the consensus algorithm, relying on the length of the chain, simply discard the "bad". This principle of allocating equal time slices to each BP was first applied in Graphene (the predecessor of EOS), and allows most blocks to be closed with one signature, which greatly reduces network load and allows this consensus to work extremely quickly and steadily. However, the EOS network now has to use special blocks (Last Irreversible Block), which are confirmed by 2/3 BP signatures. These blocks serve to ensure finality (the impossibility of a fork of the chain starting before the last Last Irreversible Block).
Also, in real implementations, the protocol scheme is more complicated - voting for proposed blocks is carried out in several stages to keep the network running in case of missing blocks and problems with the network, but even taking this into account, consensus algorithms using PVRB require significantly fewer messages between BPs, which allows you to make them faster than traditional PVFT, or its various modifications.
The brightest representative of such algorithms: from the Cardano team, which is claimed to have mathematically provable resistance to BP collusion.
In Ouroboros, PVRB is used to define the so-called "BP schedule" - a schedule according to which each BP is assigned its own time slot for publishing a block. The big advantage of using PVRB is that BPs are completely “equal” (according to the size of their balance sheets). The integrity of PVRB ensures that malicious BPs cannot control the timeslot schedule and therefore cannot manipulate the chain by preparing and analyzing forks of the chain in advance, and to choose a fork, it is enough to rely simply on the length of the chain, without operating with tricky ways to calculate the “utility” of BP and "weight" of its blocks.
In general, in all cases where a random participant needs to be selected in a decentralized network, PVRB is almost always the best choice, and not a deterministic option based on, for example, a block hash. Without PVRB, the ability to influence the choice of a participant leads to attacks in which an attacker can choose from several futures, choose the next corrupt participant or several at once, in order to provide a more significant share in the decision. The use of PVRB discredits these types of attacks.
Scaling and load balancing
PVRB can also be of great benefit in reducing the load and scaling payments. To begin with, it makes sense to familiarize yourself with Rivest “Electronic Lottery Tickets as Micropayments”. The general gist is that instead of making 100 payments of 1c from the payer to the recipient, you can play an honest lottery with a prize of $ 1 = 100c, where the payer, for each payment of 1c, transfers one of his 100 “lottery tickets” to the bank. One of these tickets wins $1 to the bank, and it is this ticket that the recipient can record in the blockchain. Most importantly, the remaining 99 tickets are transferred between the recipient and the payer without any external participation, through a private channel and at any desired speed. A good description of the protocol based on this scheme in the Emercoin network can be read .
This scheme has several problems, for example, the recipient may stop serving the payer immediately after receiving the winning ticket, but for many special applications, such as per-minute billing or electronic subscriptions to services, they can be neglected. The main requirement, of course, is the honesty of the lottery, and PVRB is absolutely necessary for its implementation.
The choice of a random participant is also extremely important for sharding protocols, the purpose of which is horizontal scaling of the block chain, allowing different BPs to process only their own scope of transactions. This is an extremely difficult task, especially in terms of security when merging shards. The fair selection of a random BP in order to assign its responsibility for a particular shard, as in consensus algorithms, is also the task of PVRB. In centralized systems, shards are assigned by the balancer, it simply calculates the hash from the request and sends it to the required executor. In blockchains, the ability to influence this assignment can lead to an attack on the consensus. For example, the content of transactions can be controlled by the attacker, he can control which transactions fall into the shard he controls and manipulate the block chain in it. A discussion of the problem of using random numbers for sharding tasks in Ethereum can be read
Sharding is one of the most ambitious and serious challenges in the field of blockchain, its solution will allow building decentralized networks of fantastic performance and volume. PVRB is just one of the important blocks for its solution.
Games, economic protocols, arbitration
The role of random numbers in the gaming industry is difficult to overestimate. Explicit use in online casinos, and implicit when calculating the effects of a particular player action - all these are extremely difficult problems for decentralized networks, where there is no way to rely on a central source of randomness. But, random choice can also solve many economic problems and help build simpler and more efficient protocols. Suppose in our protocol there are disputes about payment for some inexpensive services, and these disputes occur quite rarely. In this case, if there is an undisputed PVRB, customers and sellers can agree on a random resolution of disputes, but with a given probability. For example, with a probability of 60%, the client wins, and with a probability of 40%, the seller wins. This, from the first point of view, absurd approach allows you to automatically resolve disputes with a precisely predictable share of wins / losses, which suits both parties without any participation of a third party and unnecessary waste of time. Moreover, the ratio of probabilities can be dynamic and depend on some global variables. For example, if the company is doing well, has a low number of disputes and high profitability, the company can automatically shift the probability of dispute resolution towards customer-oriented, for example 70/30 or 80/20, and vice versa if disputes are costly and are fraudulent or inadequate, you can shift the probability in the other direction.
A large number of interesting decentralized protocols such as token currated registries, prediction markets, bonding curves and many others are economic games in which good behavior is rewarded and bad behavior is penalized. They often have security problems, protection against which contradict each other. What is protected from attack by “whales” with billions of tokens (“big stake”) is vulnerable to attacks by thousands of accounts with small balances (“sybil stake”), and measures taken against a single attack, such as non-linear commissions designed to to make big stake work unprofitable, are usually discredited by another attack. Since we are talking about an economic game, the corresponding statistical weights can be calculated in advance, and simply replace the commissions with randomized ones with the appropriate distribution. Such probabilistic commissions are extremely easy to implement if there is a reliable source of randomness in the blockchain and do not require any complex calculations, making life difficult for both whales and sybils.
That being said, keep in mind that controlling a single bit in this randomness allows you to cheat by doubling and doubling the odds, so fair PVRB is an essential part of such protocols.
Where can I find the correct random?
In theory, fair random choice in decentralized networks allows almost any protocol to be provably secure from collusion. The rationale is quite simple - if the network agrees on one bit 0 or 1, and among the participants less than half are dishonest, then, with a sufficient number of iterations, the network is guaranteed to come to a consensus on this bit with a fixed probability. Simply because an honest random will choose 51 out of 100 participants 51% of the time. But this is in theory, because. in real networks, to ensure such a level of security as in the articles, a lot of messages between hosts, complex multi-way cryptography are required, and any complication of the protocol immediately adds new attack vectors.
That is why we do not yet see a proven persistent PVRB in blockchains, which would have been used for enough time to be tested by real applications, multiple audits, loads, and of course, real attacks, without which it is difficult to call a product truly secure.
Nevertheless, there are several promising approaches at once, they differ in many details, and one of them will definitely solve the problem. With today's computing resources, cryptographic theory is quite capable of being translated into practical applications. In the future, we will be happy to talk about PVRB implementations: there are several of them now, each has its own set of important properties and features in the implementation, and there is a good idea behind each. There are not many teams involved in randomness, and the experience of each of them is extremely important for everyone else. We hope that our information will allow other teams to move faster, taking into account the experience of their predecessors.
Source: habr.com