Introduction
"Random Number Generation Is Too Important to Leave to Chance"
Robert Cavulo, 1970
This article focuses on the practical application of solutions that use collective random number generation in an untrusted environment. In short, it addresses how and why randomness is used in blockchains and also discusses how to distinguish 'good' randomness from 'bad'. Generating genuinely random numbers is a highly challenging problem even on a single computer, and has been studied by cryptographers for a long time. In decentralized networks, the generation of random numbers is even more complex and critical.
In networks where participants do not trust one another, the ability to generate undisputed random numbers allows for the effective resolution of many crucial tasks and significantly enhances existing schemes. Moreover, gambling and lotteries are by no means the primary goal, as might initially seem to an uninitiated reader.
Random Number Generation
Computers cannot generate random numbers on their own; they require external assistance for this. A computer can acquire some random value by using, for example, mouse movements, the amount of memory used, parasitic currents on processor contacts, and many other sources known as entropy sources. These values themselves are not entirely random, as they exist within a specific range or exhibit predictable patterns of change. To convert such numbers into truly random numbers within a specified range, cryptographic transformations are applied to obtain uniformly distributed pseudo-random values from the unevenly distributed values of the entropy source. The resultant values are called pseudo-random because they are not truly random; they are deterministically produced from entropy. Any good cryptographic algorithm, when encrypting data, produces ciphertexts that should statistically be indistinguishable from random sequences, meaning that for generating randomness, one can use an entropy source that ensures only good uniqueness and unpredictability of values, even within small ranges, while the rest of the work of dispersing and shuffling bits in the resulting value will be handled by the encryption algorithm.
To conclude this brief primer, I would like to add that the generation of random numbers, even on a single device, is one of the cornerstones of ensuring the security of our data. The generated pseudo-random numbers are used to establish secure connections in various networks, for generating cryptographic keys, for load balancing, integrity checks, and numerous other applications. The security of many protocols depends on the ability to generate reliable, unpredictable randomness from external sources, to preserve it, and not to disclose it until the next step of the protocol, otherwise the security will be jeopardized. An attack on the pseudo-random number generator is extremely dangerous and endangers all software that relies on random number generation.
All of this is something you should know if you've taken a basic course in cryptography, so let's continue with decentralized networks.
Randomness in Blockchains
First of all, I will talk about blockchains that support smart contracts; they can fully utilize the capabilities provided by quality undeniable randomness. For brevity, I will refer to this technology as “Publicly Verifiable Random Beacons” or PVRB. Since blockchains are networks where any participant can verify information, a key part of the name is “Publicly Verifiable,” meaning that anyone can compute evidence that the resulting number stored in the blockchain possesses the following properties:
- The result must have provably uniform distribution, i.e., it is based on provably secure cryptography.
- It is impossible to control any of the bits of the result. As a consequence, the result cannot be predicted in advance.
- The protocol for generating randomness cannot be sabotaged by not participating in the protocol or by overwhelming the network with attacking messages.
- All of the above must be resistant to collusion among an acceptable number of dishonest participants in the protocol (for example, 1/3 of participants).
Any possibility for a colluding minor group of participants to produce even controlled odd/even randomness is a security flaw. Any possibility for a group to stop the issuance of randomness is also a security flaw. In general, there are many issues, and this task is not easy…
It seems that the most important application for PVRB is various games, lotteries, and any type of gambling on the blockchain. Indeed, this is an important direction, but randomness in blockchains has even more significant applications. Let's consider them.
Consensus Algorithms
PVRB plays a crucial role in organizing network consensus. Transactions in blockchains are secured by digital signatures, which means that a 'transaction attack' is essentially the inclusion/exclusion of a transaction in a block (or multiple blocks). The main task of the consensus algorithm is to agree on the order of these transactions and the sequence of blocks that include these transactions. Additionally, a necessary property of real blockchains is finality — the ability of the network to agree that the chain up to the finalized block is definitive and will never be excluded due to the emergence of a new fork. Typically, to determine that a block is valid and, importantly, final, it requires collecting signatures from the majority of block producers (henceforth BP — block producers). This requires at least delivering the chain of blocks to all BPs and distributing signatures among all BPs. As the number of BPs increases, the number of necessary messages in the network grows exponentially, which is why consensus algorithms requiring finality, such as those used in pBFT consensus in Hyperledger, do not operate at the needed speed once there are just a few dozen BPs, demanding an enormous number of connections.
If there is an undisputed and honest PVRB in the network, then even in the simplest approximation, it is possible to select one of the block producers based on it and appoint them as the 'leader' for 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 create chain forks with the intention of executing a 'double spend' attack, then using a uniformly distributed undisputed PVRB will allow selecting an honest leader with a probability of M / N (M / N > 1/2)If each leader is assigned their own time interval during which they can produce a block and validate the chain, and these intervals are equal in duration, the chain of honest BPs will be longer than the chain formed by malicious BPs, and the consensus algorithm relying on the length of the chain will simply discard the 'bad' one. This principle of assigning equal time quanta to each BP was first applied in Graphene (the predecessor of EOS), allowing most blocks to be closed with a single signature, significantly reducing network load and enabling this consensus to operate extremely quickly and stably. However, EOS networks currently have to use special blocks (Last Irreversible Block), which are confirmed by the signatures of 2/3 BPs. These blocks serve to ensure finality (the impossibility of a fork appearing that starts before the last Last Irreversible Block).
Moreover, in real implementations, the protocol scheme is more complex — voting for proposed blocks occurs in several stages to maintain network operation in case of block misses and network issues, but even taking this into account, consensus algorithms using PVRB require significantly fewer messages between BPs, making them faster than traditional PBFT or its various modifications.
The most prominent representative of such algorithms is: from the Cardano team, which is claimed to have mathematically proven resilience against collusion among BPs.
In Ouroboros, PVRB is used to determine the so-called 'BP schedule' — a timetable according to which each BP is assigned a time slot for publishing a block. A significant advantage of using PVRB is complete 'equality' among BPs (according to the sizes of their balances). The honesty of PVRB ensures that malicious BPs cannot control the scheduling of time slots and therefore cannot manipulate the chain by preemptively preparing and analyzing chain forks; instead, to select a fork, one can rely simply on the length of the chain, without resorting to clever methods of calculating the 'utility' of BPs and the 'weight' of their 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 compared to deterministic options based on, for example, block hashes. Without PVRB, the ability to influence participant selection leads to attacks, in which an attacker can choose the next corrupted participant or several at once by selecting from multiple future options, ensuring a greater share in decision-making. Using PVRB mitigates these types of attacks.
Scaling and Load Balancing
PVRB can also provide significant benefits in tasks aimed at reducing load and scaling payments. To begin with, it makes sense to familiarize oneself with Rivest's “Electronic Lottery Tickets as Micropayments.” The gist is that instead of making 100 payments of 1c from the payer to the recipient, one can play a fair lottery with a prize of $1 = 100c, where the payer, with each payment of 1c, transfers the bank one of their 100 “lottery tickets.” One of these tickets wins the bank $1, and it is this ticket that the recipient can record on the blockchain. The most important thing is that the remaining 99 tickets are exchanged between the recipient and the payer without any external involvement, through a private channel and at any desired speed. A good description of a protocol based on this scheme in the Emercoin network can be read .
This scheme has several issues; for instance, the recipient may stop serving the payer immediately after receiving the winning ticket, but for many specific applications, such as per-minute billing or electronic subscriptions to services, these can be overlooked. The main requirement, of course, is the honesty of the conducted lottery, and PVRB is essential for its execution.
The selection of a random participant is crucial for sharding protocols, which aim for horizontal scaling of the blockchain, allowing different BPs to process only their scope of transactions. This is an extremely complex task, especially regarding security when merging shards. A fair selection of a random BP to assign responsibility for a specific shard, similar to consensus algorithms, is also a task for PVRB. In centralized systems, shards are assigned by a load balancer, which simply computes a hash from the request and sends it to the appropriate executor. In blockchains, the ability to influence this assignment can lead to consensus attacks. For example, the content of transactions can be controlled by an attacker, who can manage which transactions enter their controlled shard and manipulate the blockchain within it. You can read about the problem of using random numbers for sharding tasks in Ethereum.
Sharding is one of the most ambitious and serious tasks in the blockchain space; solving it will enable the creation of decentralized networks with fantastic performance and volume. PVRB is just one of the important blocks needed to address this challenge.
Games, economic protocols, arbitration
The role of random numbers in the gaming industry is hard to overestimate. Their explicit use in online casinos, as well as their implicit use in calculating the effects of a player's actions, presents extremely complex challenges for decentralized networks, where reliance on a central source of randomness is not an option. However, random selection can also address many economic issues and help build simpler and more efficient protocols. Let's assume that our protocol involves disputes over the payment for certain inexpensive services, and these disputes occur infrequently. In this case, if there is an indisputable PVRB, clients and vendors can agree to resolve disputes randomly, but with a specified probability. For example, there might be a 60% chance that the client wins and a 40% chance that the vendor does. This initially absurd approach allows for automatic resolution of disputes with a precisely predictable win/loss ratio that satisfies both parties, without the involvement of a third party and unnecessary time wasted. Moreover, the probability ratios can be dynamic and depend on certain global variables. For instance, if a company is doing well, with a low number of disputes and high profitability, it might automatically shift the probability of dispute resolution towards client orientation, say 70/30 or 80/20, and conversely, if disputes are costly and fraudulent or unreasonable, the probability can be shifted in the opposite direction.
A large number of interesting decentralized protocols, such as token curated registries, prediction markets, bonding curves, and many others, represent economic games where good behavior is rewarded and bad behavior is penalized. They often face security issues, the defenses against which can contradict each other. What is protected against attacks from 'whales' with billions of tokens ('big stake') is vulnerable to attacks from thousands of accounts with small balances ('sybil stake'), and the measures taken against one type of attack, such as nonlinear fees designed to make it unprofitable for large stakes to operate, are typically undermined by another attack. Since this is an economic game, the corresponding statistical weights can be calculated in advance, and fees can simply be replaced with randomized ones that conform to the appropriate distribution. Such probabilistic fees can be implemented quite simply if there is a reliable source of randomness in the blockchain and do not require any complex computations, complicating life for both whales and sybils.
At the same time, it is essential to remember that control over a single bit in this randomness allows for manipulation, effectively doubling or halving probabilities, so an honest PVRB is a crucial component of such protocols.
Where to find the right randomness?
In theory, honest random selection in decentralized networks can provide provable security for almost any protocol against collusion. The justification is quite simple: if the network agrees on a single bit being 0 or 1, and less than half of the participants are dishonest, then, with a sufficient number of iterations, the network will reliably reach consensus on that bit with a fixed probability. This is simply because honest random selection will choose 51 out of 100 participants in 51% of cases. But this is in theory, as in real networks, to achieve such a level of security as mentioned in the articles, numerous messages between hosts are required, complex multi-step cryptography, and any complication of the protocol immediately adds new attack vectors.
That is why we do not yet see a proven resilient PVRB in blockchains that has been used long enough to withstand real-world applications, multiple audits, loads, and, of course, real attacks, without which it is hard to call a product truly secure.
However, there are several promising approaches, each differing in many details, and one of them will certainly solve the problem. With today's computing resources, cryptographic theory is capable of smoothly transforming into practical applications. In the future, we will gladly discuss implementations of PVRB: there are currently a few, each with its own set of important characteristics and features in implementation, and each backed by a good idea. Not many teams are working with randomness, and the experience of each is extremely valuable for all the others. We hope our information will enable other teams to advance more quickly, considering the experiences of predecessors.
Source: habr.com
