Random Numbers and Decentralized Networks: A Practical Application

Introduction

“Random number generation is too important to be left to chance”
Robert Caviu, 1970

This article is devoted to the practical application of solutions using the collective generation of random numbers in an untrusted environment. In short - how and why the 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 separate computer, and has long been studied by cryptographers. Well, in decentralized networks, random number generation 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 can effectively solve many important problems and significantly improve existing schemes. Moreover, gambling and lotteries here are not at all the number one goal, as an inexperienced reader may seem at first.

Random number generation

Computers do not know how to produce random numbers themselves, for this they need outside help. A computer can get some random value using, for example, mouse movements, the amount of memory used, spurious currents on the processor contacts and many other sources called sources of entropy. These values ​​themselves are not entirely random, as they are in a certain range or have a predictable nature of changes. To turn such numbers into a truly random number in a given range, cryptographic transformations are applied to them in order to obtain uniformly distributed pseudorandom values ​​from the unevenly distributed values ​​of the source of entropy. The obtained values ​​are called pseudo-random, since they are not truly random, but are deterministically derived from entropy. Any good cryptographic algorithm

To complete the short educational program, I’ll add that the generation of random numbers even on one device is one of the pillars of ensuring the security of our data, the generated pseudorandom numbers are used to establish secure connections in various networks, to generate cryptographic keys, to balance the load, to control integrity, and for many more uses. The security of many protocols depends on the ability to generate reliable, unpredictable random data from outside, save it, and not open it until the next step of the protocol, otherwise security will be compromised. An attack on a pseudo-random value generator is extremely dangerous and threatens all software that uses random generation at once.

You should know all this if you have taken a basic cryptography course, so let's continue with decentralized networks.

Blockchain Random

First of all, I will talk about blockchains with support for smart contracts, it is they who can fully use the opportunities provided by a quality undeniable random. Further, for brevity, I will call this technology “ Publicly Verifiable Random Beacons ” or PVRB. Since blockchains are networks in which any participant can verify information, the key part of the name is “Publicly Verifiable”, i.e. anyone with the help of calculations can get proof that the resulting number, placed on the blockchain, has the following properties:

• The result should have a provably uniform distribution, i.e. based on provably strong cryptography.
• It is not possible to control any of the bits of the result. As a result, the result cannot be predicted in advance.
• You cannot sabotage the generation protocol by not participating in the protocol or by overloading the network with attack messages
• All of the above should be resistant to collusion of the allowable number of dishonest participants in the protocol (for example, 1/3 of the participants).

Any opportunity for a conspiring minor group of participants to produce even a controlled even / odd random is a security hole. Any opportunity for the group to stop issuing a random house 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 generally any kind of gambling on the blockchain. Indeed, this is an important direction, but the random house in blockchains has applications and more important. Consider them.

Consensus algorithms

PVRB is crucial for networking consensus. Transactions in blockchains are protected by an electronic signature, therefore, “attack on a transaction” is always the inclusion / exclusion of a transaction in a block (or in several blocks). And the main task of the consensus algorithm is to agree on the order of these transactions and on the order of blocks that include these transactions. 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 a block is valid and, most importantly, final, you need to collect signatures from most block producers (hereinafter BP - block-producers), which requires at least delivering a chain of blocks to all BP, and distribute signatures between all BP. As the number of BPs grows, the number of required messages on the network exponentially grows; therefore, consensus algorithms that require finality, such as those used in Hyperledger's pBFT consensus, do not work at the right speed, starting from several dozen BPs, requiring a huge number of connections.

If the network has an undeniable and honest PVRB, then, even in the simplest approximation, it is possible to select one of the block producers on the basis of it and appoint it the “leader” for one round of the protocol. If we have Nblock producers of which we M: M > 1/2 Nare honest, do not censor transactions and do not build fork chains in order to conduct a “double spend” attack, then using a uniformly distributed indisputable PVRB will allow choosing an honest leader with probabilityM / N (M / N > 1/2). If each leader is assigned his 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 honest BP blocks will be longer than the chain formed by the malicious BP, 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 a single signature, which greatly reduces network load and allows this consensus to work extremely quickly and steadily. However, EOS networks now have to use special blocks (Last Irreversible Block), which are confirmed by 2/3 BP signatures. These blocks are used to ensure finality (the impossibility of a fork chain,

Also, in real implementations, the protocol scheme is more complicated - voting for the proposed blocks is carried out in several stages in order to maintain the network in case of missing blocks and network problems, but even with this in mind, PVRB consensus algorithms require significantly fewer messages between BPs, which allows you to make them faster than traditional PBFT, or its various modifications.

The most striking representative of such algorithms: Ouroboros from the Cardano team, which, as announced, has mathematically provable resistance to collusion among BP.

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 the complete “equal rights” of BP (according to the size of their balances). Honesty PVRB ensures that malicious BPs cannot control the schedule of time slots, and therefore cannot manipulate the chain by preparing and analyzing the chain forks in advance, and to select a fork, you can simply rely on the length of the chain without using tricky ways to calculate the “usefulness” of BP and “Weights” of its blocks.

In general, in all cases when a random participant needs to be selected in a decentralized network, PVRB is almost always the best choice, rather than a deterministic option based on, for example, a block hash. Without PVRB, the ability to influence the choice of the participant leads to the appearance of attacks in which the attacker can, choosing from several options for the future, choose the next corrupt participant or several at once, in order to provide a more significant share in the decision. Using PVRB discredits these types of attacks.

Scaling and load balancing

PVRB can also be of great benefit in tasks to reduce workload and scale payments. For starters, it makes sense to read Rivest’s article “Electronic Lottery Tickets as Micropayments”. The general essence 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 transfers one of his 100 “lottery tickets” to the bank for each payment in 1c. One of these tickets wins the bank $ 1, and it is this ticket that the recipient can fix on 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 found here .

This scheme has several problems, for example, the recipient may stop serving the payer immediately after receiving a 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 holding.

The choice of a random participant is also extremely important for sharding protocols, the purpose of which is to horizontally scale the chain of blocks, allowing different BPs to process only their scope of transactions. This is an extremely difficult task, especially when it comes to security when merging shards. The honest choice of a random BP in order to assign it to those responsible for a particular shard, as in consensus algorithms, is also a PVRB task. In centralized systems, shards are assigned by the balancer, he simply calculates the hash from the request and sends it to the necessary executor. On blockchains, the ability to influence this assignment can lead to an attack on consensus. For example, the contents of transactions can be controlled by the attacker, he can control which transactions fall into the shard he controls and manipulate the chain of blocks in it.here
Sharding is one of the most ambitious and serious tasks in the field of blockchain, its solution will allow to build decentralized networks of fantastic performance and volume. PVRB is just one of the important blocks to solve it.

Games, economic protocols, arbitration

The role of random numbers in the gaming industry is hard to overestimate. Explicit use in online casinos, and implicit in calculating the effects of a player’s action, are all extremely difficult problems for decentralized networks, where there is no way to rely on a central source of randomness. But, a random choice can solve many economic problems and help build simpler and more efficient protocols. Suppose in our protocol there are disputes about paying for some inexpensive services, and these disputes are quite rare. In this case, if there is an undeniable 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. Such, from the first point of view, absurd, the approach allows you to automatically solve disputes with an accurately predictable share of wins / losses, which suits both parties without any third-party participation and unnecessary waste of time. Moreover, the probability ratio can be dynamic and depend on some global variables. For example, if a company is doing well, there is a low number of disputes and high profitability, the company can automatically shift the likelihood of a dispute resolving toward client-oriented, for example 70/30 or 80/20, and vice versa, if disputes take up a lot of money and are fraudulent or inadequate, you can shift the probability in the other direction. the probability ratio can be dynamic and depend on some global variables. For example, if a company is doing well, there is a low number of disputes and high profitability, the company can automatically shift the likelihood of a dispute resolving toward client-oriented, for example 70/30 or 80/20, and vice versa, if disputes take up a lot of money and are fraudulent or inadequate, you can shift the probability in the other direction. the probability ratio can be dynamic and depend on some global variables. For example, if a company is doing well, there is a low number of disputes and high profitability, the company can automatically shift the likelihood of a dispute resolving toward client-oriented, for example 70/30 or 80/20, and vice versa, if disputes take up a lot of money 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 that reward good behavior and fine bad ones. They often encounter security problems, the protection against which contradict each other. What is protected from an 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 one attack, such as non-linear commissions created to to make a large steak work disadvantageous, they are usually discredited by another attack. Since this is an economic game, the corresponding statistical weights can be calculated in advance, and simply replace the commissions with randomized ones with the appropriate distribution.
It is necessary to continue to remember that control over a single bit in this randomization allows you to cheat, reducing and doubling the probabilities, so honest PVRB is the most important component of such protocols.

Where to find the correct random?

In theory, honest random choices in decentralized networks provide the provable security of almost any protocol against 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. Just because an honest random will choose 51 out of 100 participants in 51% of cases. But this is in theory, because in real networks, to ensure such a level of security as in articles, it requires a lot of messages between hosts, complex multi-pass cryptography, and any complication of the protocol immediately adds new attack vectors.
That is why we do not yet see in the blockchains a proven PVRB that would have been used enough time to be tested by real applications, multiple audits, loads, and of course, real attacks, without which it is difficult to call the product truly safe.

Nevertheless, there are several promising approaches at once, they differ in many details, and some of them will definitely solve the problem. With modern computational resources, cryptographic theory is able to quite skillfully turn into practical applications. In the future, we will be happy to talk about the implementation of PVRB: there are several of them now, each has its own set of important properties and features in implementation, and each one has a good idea. There are not many teams involved in the random, 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.