Random numbers and decentralized networks: practical applications

Introduction

“The generation of random numbers is too important to leave it to chance”
Robert Cavu, 1970

This article focuses on the practical application of solutions using collective generation of random numbers in an untrusted environment. In short, how and what is used by random in blockchains, and a little about how to distinguish between “good” random and “bad”. The generation of a truly random number is an extremely difficult problem even on a separate computer, and has been studied for a long time 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 indisputable random number makes it possible to effectively solve many of the most important tasks and significantly improve existing schemes. Moreover, gambling and lottery here are not at all the number one goal, as at first it may seem to an inexperienced reader.

Random Number Generation

Computers do not know how to produce random numbers themselves, for this they need outside help. A computer can receive some random value using, for example, mouse movements, the amount of memory used, parasitic currents on the processor pins and many other sources, called entropy sources. These values ​​themselves are not entirely random, as they are in a certain range or have a predictable nature of changes. In order 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 non-uniformly distributed values ​​of the entropy source. The values ​​obtained are called pseudo-random, since they are not truly random, but deterministically derived from entropy. By encrypting the data, any good cryptoalgorithm produces ciphertexts, which should be statistically indistinguishable from a random sequence, so for the production of random data, you can take the source of entropy, which 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’ll add that random number generation even on one 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, load balancing, integrity monitoring, and for many other uses. The security of many protocols depends on the ability to generate a reliable, unpredictable from the outside by random, save it, and not disclose it until the next step of the protocol, otherwise security will be compromised. An attack on a pseudorandom generator is extremely dangerous and threatens all software that uses randomization at once.

All this you need to know 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 the support of smart contracts, it is they who can take full advantage of the opportunities provided by the quality of the indisputable random. Further, for brevity, I will call this technology “ Publicly Verifiable Random Beacons ” or PVRB. Since blockchains are networks, information in which any participant can check, the key part of the name is “Publicly Verifiable”, i.e. Anyone can, with the help of calculations, obtain evidence that the resulting number placed in the blockchain has the following properties:

• The result should have a demonstrably uniform distribution, that is, it is based on provably strong cryptography.
• It is impossible to control any of the bits of the result. As a result, the result cannot be predicted in advance.
• You can not sabotage the generation protocol due to non-participation in the protocol or by overloading the network with attacking messages
• All of the above should be resistant to the collusion of the permissible number of dishonest protocol participants (for example, 1/3 of the participants).

Any possibility of 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 is not an easy task ...

It seems that the most important use for PVRB is various games, lotteries, and in general any kind of gambling on the blockchain. Indeed, this is an important area, but randomness in blockchains has applications and more important. Consider them.

Consensus algorithms

PVRB is crucial for networking consensus. Transactions in blockchains are protected by 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 the order of the 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, it is required to collect signatures from most block manufacturers (hereinafter referred to as BP - block-producers), which requires at least to deliver a block chain to all BP, and to distribute signatures between all BP . As the number of BPs grows, the number of required messages in the network grows exponentially; therefore, consensus algorithms that require finality, such as those used in Hyperledger pBFT consensus, do not work at the desired speed, starting with several dozen BPs, requiring a huge number of connections.

If the network has an undeniable and fair PVRB, then, even in the simplest approximation, you can select one of the block producers on the basis of it and designate it as a “leader” during one round of the protocol. If we have N block producers, of which M: M > 1/2 N are fair, do not censor transactions and do not build forks of a chain in order to conduct a “double spend” attack, then using a uniformly distributed undeniable PVRB will allow you to choose an honest leader. with probability M / 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 malicious BP, and the consensus algorithm relying on the chain length, simply discard the “bad”. This principle of allocating equal time slices to each BP was first used in Graphene (the predecessor of EOS), and allows most blocks to be closed with a single signature, which greatly reduces the 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 the signatures of 2/3 BP. These blocks serve to ensure finality (the impossibility of the appearance of a fork of a chain that begins before the last Last Irreversible Block).

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

The most prominent representative of such algorithms: Ouroboros from the Cardano team, which, as announced, has mathematically demonstrable 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 “equality” of BP (according to the size of their balance sheets). The honesty of the PVRB ensures that malicious BP cannot control the schedule of time slots, and therefore cannot manipulate the chain, preparing and analyzing the forks of the chain in advance, and to choose the fork it is enough just to rely on the length of the chain without using the tricky BP and “utility” “Weight” of its blocks.

In general, in all cases when you need to select a random participant in a decentralized network, PVRB is almost always the best choice, and not a deterministic variant based on, for example, a block hash. Without PVRB, the ability to influence the choice of a 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, to ensure a more significant stake in the decision. Using PVRB discredits these types of attacks.

Scaling and load balancing

PVRB can bring serious benefits also in tasks to reduce the load, scale payments. For a start, it makes sense to read Rivest's article “Electronic Lottery Tickets as Micropayments”. The general point is that instead of making 100 payments of 1c from the payer to the payee, you can play an honest lottery game with a prize of $ 1 = 100c, where the payer sends one of his 100 “lottery tickets” to each bank for each payment to 1c. One of these tickets wins the bank $ 1, 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 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. But the main requirement, of course, is the fairness of the lottery, and PVRB is absolutely necessary for it.

The selection of a random participant is also extremely important for sharding protocols, the purpose of which is to scale the block chain horizontally, allowing different BPs to process only their own transaction scope. This is an extremely difficult task, especially in matters of security when combining shards. Honestly choosing a random BP to assign those responsible for a particular shard, as in the consensus algorithms, is also a PVRB task. In centralized systems, shards are assigned by the balancer, it simply calculates the hash from the request and sends it to the necessary performer. In blockchains, the ability to influence this assignment can lead to an attack on consensus. For example, the contents of transactions can be controlled by an attacker, he can control which transactions fall into the shard he controls and manipulate the chain of blocks in it. Discussion of the problem of using random numbers for sharding problems in Ethereum can be read here.
Sharding is one of the most ambitious and serious tasks in the blockchain field; its solution will allow building 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 difficult to overestimate. Explicit use of online casinos, and implicit in calculating the effects of a player’s actions - all these are extremely difficult problems for decentralized networks, where there is no possibility of relying on the central source of randomness. But, random choice can solve many economic problems and help build simpler and more efficient protocols. Suppose in our protocol there are disputes about the payment of some kind of low-cost services, and these disputes occur quite rarely. 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, the customer wins with a 60% probability, and the seller wins with a 40% probability. This, from the first point of view, absurd approach allows you to automatically solve disputes with an exactly predictable share of winnings / losses that suits both parties without the participation of a third party and wasting time. Moreover, the ratio of probabilities 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 probability of resolving the dispute towards customer-orientation, for example 70/30 or 80/20, and vice versa, if disputes take 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 penalize bad ones. They often encounter security problems, the defenses against which contradict each other. What is protected from the attack of “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, created to to make a big steak work unprofitable, 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. Such probabilistic commissions are implemented very simply, if the blockchain has a reliable source of randomization and does not require any complicated calculations, making life difficult for whales and sybils.
At the same time, it is necessary to continue to remember that control over a single bit in this random house allows you to deceive, reducing and doubling the likelihood, so fair PVRB is the most important component of such protocols.

Where to find the right random?

In theory, fair random selection in decentralized networks allows for provable security of almost any protocol against collusion. The justification is quite simple - if the network agrees on one bit 0 or 1, and less than half of the participants 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 honest random will choose 51 out of 100 participants in 51% of cases. But this is in theory, because in real networks, to ensure this level of security, as in the articles, many messages between hosts are required, complex multi-pass cryptography, and any complication of the protocol immediately adds new attack vectors.
That is why we still don’t see proven persistent PVRB in blockchains, which would have already used enough time to pass tests with real applications, multiple audits, loads, and of course, real attacks, without which it is difficult to call a product truly safe.

Nevertheless, there are several promising approaches at once, they differ in many details, and one of them will exactly solve the problem. With modern computing resources, cryptographic theory is able to quite cleverly turn into practical applications. In the future, we will be happy to tell you about the implementation of PVRB: 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. Random is not involved in many teams, and the experience of each of them is extremely important for everyone else. We hope that our information will allow the rest of the teams to move faster, taking into account the experience of predecessors.