Multi-party Random Number Generation On Distributed Networks

November 30, 2018
- BY GINAR

People have been fascinated by the concept of randomness since the early days of history. We have never stopped figuring out rules by which things operate. As in our nature, we want to refuse to assume that anything occurs in a random manner. We observe things, look for patterns, make predictions. Gradually, people started to realize that randomness plays important roles in daily activities. As a result, randomness finds numerous applications in a variety of areas from gaming, art to simulation, statistics, and cryptography. Although randomness seems very naturally obvious, creating randomness is actually surprisingly challenging. The degree of randomness required varies according to which application it is used for. Weaker forms of randomness can be used in simple applications (like randomly selecting a music track from the list) whereas many cryptographic applications require a higher degree of apparent randomness. Plenty of methods, both arithmetical and physical, have been proposed and implemented.

Traditionally, a random number generator (RNG) is a computational algorithm or a physical device that generates unpredictable sequences of bits. Most of the conventional RNGs use local sources of randomness and are designed for single-client uses. Whilst some of us can choose to trust these sources, it has been shown that locally available randomness can be subverted. As many applications today require a common public randomness between parties, these RNGs seem not to be a good option. In addition, the lack of an easy cost-effective way to verify their outcome pushes them away from many applications operating on distributed networks.

Introduced in 2009, the Blockchain Technology is increasingly rising its popularity and getting more and more attention from researchers. More applications have been built upon this technology. As a result, the so-called Distributed Random Number Generation has inevitably become a vital field of study. The most common type is the multi-party random number generation. This article will clarify what a multi-party RNG is and how it is different from a conventional RNG. Since most of the conventional RNGs are centralized, if not specified, we will use the terms conventional and centralized interchangeably.

Distributed-Random-Number-Generation-1

What is multi-party random number generation?

Multi-party random number generation is a mechanism to build a single value from the contributions of multiple parties. Each party’s contribution altering the final value in such a way that no one has any advantage over others in knowing how their contribution will shape the final value. In contrast to the centralized approach where the random numbers are generated from a single source, this approach collects random sources from all over the network to combine them into a final random number.

To better understand this term, let’s take a look at the example of an online game between two or more parties betting on the outcome of a game. In this case, if any party knows the numbers before it is revealed, the game is no longer considered fair. Therefore, it is essentially important to have the outcome of the game generated by a fair random number generator. Centralized RNGs somehow can be applied to this game but it lacks a way to audit the result. Moreover, the parties have to place trust to a third party and if this party is malicious, the outcome is no longer fair. One simple approach is to let every party contribute a number of their choice, then by XORing these numbers to get the final result. This naive approach obviously has some drawbacks but it enables to remove a third-party element.  All parties can directly influence the random number which increases accountability in the outcome.

In general, if designed properly, not only do multi-party RNGs meet the stringent requirements of an RNG, but they also achieve some interesting properties that make it possible for many applications. Following are some of the properties that set them apart from centralized RNGs.

No trusted third-party

The main disadvantage of using a centralized RNG is that trust is required in the provider not to abuse its power and to faithfully provide its services. Moreover, there is a risk that an attacker gains control over the provider, which enables the attacker to compromise the service. Therefore, we do not know if the RNG has been manipulated or not. In such a case, it is likely that the generated numbers are not random. A multi-party RNG offers a mechanism to reach an agreement between many parties on a random value despite the presence of malicious parties. Hence, a multi-party RNG, instead of relying on a particular party, distributes the trust to every party. From the answers to the following questions, one can easily see how distributed RNGs, in general, remove the need to trust any third party.

  • What is more likely to happen: one party is malicious, or 51 out of 100 parties are malicious at the same time?
  • Which of the following do you trust the most: a single party, or a network of 100 parties?

Fairness

In applications such as lotteries or slot-and-slot, there is a need for an agreement between many parties on a random number and no one should have an advantage over others to predict the random number. If we employ a centralized RNG in these applications, not only do we have to trust another third-party but there is also a chance that someone can bribe the third party to get the number he can benefit from. Therefore, we would strongly need to construct an RNG that requires no trusted parties. This is when the multi-party random number generation comes in. A multi-party RNG allows every party to contribute to the generation of the common value by submitting his own number. Moreover, any party in the network is not able to see others’ contributed value before the random number is settled. As a result, no one can determine the outcome until the generation process is completed. Fairness is guaranteed since everyone has the same probability of guessing the correct generated numbers based on public information and indeed, this probability is negligible.

Availability

Availability (also known as liveness) means the RNG successfully generates random numbers despite malicious nodes. It is obvious that a system with many computers is less likely to fail accidentally than a system with only one computer. A distributed network helps deal with the problem of Single Point of Failure (SPOF – the term used in a network to describe a single node that brings the whole network down if itself fails). Since there are many nodes, as long as the portion of malicious nodes (with respect to the algorithm used) is kept at a reasonable value, it is guaranteed that the network still operates and produces outcomes. Multi-party RNGs make availability possible since if one or more parties are malicious (the number of malicious parties is dependent on the algorithm used in each RNG), the RNGs still guarantee to produce an outcome that has not been manipulated.

Universal Verifiability

Universal verifiability is the ability to let any third party check the correctness of the outcomes. This property does not reside in the nature of multi-party RNGs. However, since a multi-party RNG requires contributions from many sources, verifiability is required to ensure that the generation process has not been circumvented. Conventional RNGs can only prove that they use a random method but are not able to provide any technique to audit the outcome after it is generated – meaning that the final result may have been manipulated. Thus, these RNGs may be prone to insider fraud. This places heavy trust in the service provider. Distributed solutions, in general, use a distributed ledger to record all data of every step of generating random numbers. Thus, they bring transparency in the generation process to everyone. With this information, everyone can easily check if there is any manipulation happening during the generation process.

Manipulation-resistance

It is necessary to ensure that everyone trusts the outcome of an RNG. It is obvious that a system of one node is more likely to be manipulated than a system consisting a thousand of nodes.

Distributed networks are less likely to fail accidentally since they rely on many components. As aforementioned, the process of generating random numbers in a multi-party RNG is transparent and verifiable, any attempt to manipulate the results will be detected. Moreover, it would require collusion between a specific majority amount of parties (for example, 51% for most of the dRNGs) for tampering to occur. Therefore, tamper-proof is achieved in almost all dRNGs (with some assumptions on the portion of honest parties).

Conclusion

Distributed systems introduce many challenges to the generation of random numbers that are unique to its own. The challenging task is to find a method to generate trustworthy random values among a set of mutually distrusting parties over a distributed network. In this article, we have given a brief introduction into the so-called multi-party random number generation. We have also analyzed how it is different from the traditional approach through some of the properties including fairness, availability, tamper-proof, etc. As centralized RNGs have many drawbacks, multi-party RNGs stand to be an outstanding choice. However, research on this topic is minimal. There are a few protocols that have been proposed but they only have achieved some of the aforementioned properties. In the subsequent articles, we will present our solution – GINAR.

GINAR RNG

GINAR is a multi-party RNG that guarantees to provide fair, transparent random numbers at an impressive speed and volume for businesses wanting to leverage unpredictable, tamper-resistant and verifiable digits. Stay tuned!

Feature Posts