Random Numbers and Decentralized Networks: Practical Application

In this article we will focus on solutions using collective random number generation scheme in an untrusted environment and their practical application. In short, how and why randomness is used in blockchains, and a few words about how to distinguish between "good" and "bad" randomness. Cryptographers have been studying generation of a truly random number for a long time and it is extremely difficult to reach it even on a separate computer. Let alone decentralized networks, where random number generation is even more complex and important.

In the networks where participants do not trust each other, the possibility to generate an indisputable random number allows to effectively solve numerous important problems and significantly improve the existing schemes. Moreover, games, gambling and lotteries are not number one goal at all, as it might seem at first to an inexperienced reader.

Computers are unable to generate random numbers themselves, they need external help. A computer can receive some random value from different sources called entropy sources: for example, mouse movements, the amount of memory used, parasitic currents at processor pins and many others. These values are not entirely random as they have a certain range or predictable mechanics of changes. In order to turn such numbers into a statistically random ones within a given range, crypto-transformations are applied to them. As a result, we 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 crypto algorithm produces ciphertexts that statistically should not differ from a random sequence. So, to produce random data, you can take the source of entropy that ensures good non-repeatability and unpredictability of values even in small ranges, the rest of the work on confusion and diffusion of bits in the resulting value will be handled by the encryption algorithm.

In the end of this short training I must say that random number generation even on a separate device is one of data security pillars, as generated pseudo-random numbers are used for establishing secure connections in various networks, generating cryptographic keys, load balancing, integrity monitoring, and many others. Security of many protocols depends on the ability to generate a reliable, externally unpredictable randomness, save it and not to disclose it until the next protocol step, otherwise security will be compromised. An attack on a pseudorandom generator is extremely dangerous and threatens most of modern cryptographic software.

You must know this if you took a basic course in cryptography, so let's continue speaking about randomness in decentralized networks.

First of all, I will talk about blockchains that support smart contracts since they can fully benefit from the opportunities of high-quality indisputable randomness. These algorithms are called "Publicly Verifiable Random Beacons", and, for the sake of brevity, I will further call them PVRB. Since blockchains are networks where any participant can check the data, the key part of the name is "Publicly Verifiable", i.e. via calculations anyone can obtain evidence that the resulting random number in the blockchain has the following properties:

• The result should be drawn from a provably uniform distribution, i.e. based on well-known and strong cryptography.
  
  
• It is impossible to control any single bit of result. Consequently, the result cannot be predicted in advance.
  
  
• It is difficult to 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 an acceptable number of dishonest protocol participants, for example, 1/3 of the participants.
  

Any chance of a conspiring minor group of dishonest participants to produce a controlled even/odd random number is a security flaw. Any possibility for such group to stop random number generation is a security flaw. Well, there are many important problems in this area, and this is by far an easy task...

It seems that the most important applications for PVRB are games, lotteries, and any kind of blockchain-based gambling. Indeed, this is an important area, but blockchain randomness is used in other, more important spheres. Let's have a look at them.

PVRB plays an important role in network consensus organization. Transactions in blockchains are protected by the sender's signature, and the only way to "attack a transaction" is to include or exclude it from the block (or several blocks) in different moments of time. So, the main function of the consensus algorithm is establishing the order of transactions and blocks including them. Also, an essential feature of blockchains in reality is finality - the ability of a network to agree that the chain up to the finalized block is final and will never be excluded in case 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 producers (hereinafter referred to as BPs) that at least involves delivering a chain of blocks to all BPs and distributing signatures between all BPs. As the number of BPs grows, the volume of required network messages grows exponentially; therefore, consensus algorithms requiring finality, such as those used in Hyperledger, already do not work in case of several dozen BPs, since a huge number of interactions is required.

If the network has an undeniable and fair PVRB, then you can select one of BPs and appoint him a "leader" for one protocol round. If we have an N number of BPs where M: M > 1/2 N are honest: they do not censor transactions and do not build chain forks to perform a "double spend" attack, then using a uniformly distributed undeniable PVRB will allow you to choose a honest leader with probability rate equal to M / N (M / N> 1/2). If each leader is assigned a time slot during which he can produce a block and validate a chain, and with these slots being equal, the block chain of honest BPs will be longer than the chain formed by malicious BPs, and the consensus algorithm relying on the chain length will simply discard the "bad" one. This principle of allocating equal time slots to each BP was first used in Graphene (EOS predecessor) and allows to approve most blocks with a single signature, that greatly reduces the network load and ensures high consensus speed and stability. However, in EOS, it is necessary to use special blocks (Last Irreversible Block), which are confirmed by 2/3 + 1 of BP signatures. These blocks serve to ensure finality (the impossibility of a chain fork that begins prior to the last Last Irreversible Block).

Also, in real use cases the protocol scheme is more complex - voting for the proposed blocks involves several stages in order to support the network in case of missing blocks and network issues; but even with this in mind, consensus algorithms using PVRB require significantly fewer messages between BPs allowing to make them faster than the traditional PBFT or its various modifications.

The most prominent example of such algorithms is: Ouroboros by Cardano team, that was announced to have mathematically provable resistance to BP collusion.

In Ouroboros, PVRB is used to define the so-called "BP schedule", according to which each BP is assigned a time slot for block publishing. The big advantage of PVRB is a complete BP "equality" (according to their balance sizes). PVRB fairness guarantees that malicious BPs cannot control the schedule of time slots, and therefore cannot manipulate the chain, preparing and analyzing chain forks in advance. To choose a fork it is enough to rely on the chain length without tricky calculations of BP "utility" or "weight" of its blocks.

In general, in case you need to select a random participant in a decentralized network, PVRB is usually better than, for instance, a deterministic variant based on a block hash. Without PVRB, the ability to influence the participant's choice leads to attacks, when out of several available options, the attacker chooses the next corrupt participant or some of them at once to ensure a more significant stake in the decision making. PVRB discredits these types of attacks.

PVRB can be of help in terms of load reduction and payment scaling. For starters, I advise reading the article "Electronic Lottery Tickets as Micropayments" by Rivest. The message is that instead of handling 100 micropayments worth 1 cent each from the payer to the recipient, you can play an honest lottery game with a prize of $1 = 100 cents, where the buyer sends one of his 100 "lottery tickets" to the bank for each payment worth 1 cent. One of these tickets wins $1 for the bank, and the recipient can record this ticket in the blockchain. Most importantly, the remaining 99 tickets are transferred between the recipient and the buyer without any external participants, through a private channel and at any desired speed. A good description of the protocol based on this scheme in the Emercoin network is available here.

This scheme has several problems (for instance, the recipient may stop serving the buyer immediately after receiving a winning ticket) but they can be neglected for special applications, such as per-minute charges or electronic subscriptions to services. However, lottery fairness is still the main requirement, and PVRB is crucial to fulfill it.

Selecting a random participant is also extremely important for sharding protocols that aim to scale the chain of blocks horizontally, allowing different BPs to process only their own transaction scope. This is an extremely cumbersome task, especially in terms of shard combining security. As in consensus algorithms, choosing a random BP to assign him responsible for a particular shard is also a PVRB task. In centralized systems, shards are assigned by the balancer: it simply calculates the request hash and sends it to the necessary performer. In blockchains, the ability to influence this assignment can lead to a consensus attack. For example, the attacker can control the contents of transactions, monitor which transactions fall into the shard and manipulate its chain of blocks. Discussion on using random numbers for sharding in Ethereum is available here.

Sharding is one of the most ambitious and serious tasks in blockchain; its solution will allow building decentralized networks with fantastic performance and volume. PVRB is just one of the important blocks to solve it.

The role of random numbers in the gaming industry is difficult to overestimate. They are explicitly used in online casinos and implicitly - for calculating the effects of a player's actions. These are extremely complex issues for decentralized networks as they cannot rely on the central source of randomness. However, random choice can solve many economic problems and help build simpler and more efficient protocols. Suppose that there are disputes about the some low-cost services payment in our protocol, 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. At first sight, this absurd approach allows to automatically solve disputes with a fully predictable share of winnings / losses that suits both parties without third party involvement and wasting 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 probability of resolving the dispute in favour of a customer, for example, 70/30 or 80/20, and vice versa, if disputes take a lot of money and are fraudulent or inadequate, probability can be shifted in the other direction.

A large number of interesting decentralized protocols, such as token-curated registries, prediction markets, bonding curves, and many others, are economic games that favour good behavior and penalize misbehaviour. They often have security flaws and the defense methods are contradictory. What is protected from the attack of "whales" with billions of tokens ("big stake") may be vulnerable to attacks of thousands of accounts with small balances ("sybil stake"). Measures that are taken against a single attack, such as non-linear commissions created to make a big steak unprofitable, are usually discredited by another attack. Since this is an economic game, the corresponding statistic weights can be calculated in advance, and you can simply replace regular commissions with the random ones with the appropriate distribution. Such probabilistic commissions are implemented very simply: if the blockchain has a reliable source of random generation and no complicated calculations, making life difficult for "whales" and sybils, are required.

At the same time, bear in mind that control over a single random bit allows for fraud, reducing and doubling probability rate. Therefore, fair PVRB is the most important component of such protocols.