Wanchain Galaxy Consensus Proof of Stake Technical Deep Dive: Pt. 2

Random Number Generation

By Wanchain’s Research Team — Demmon Guo, Chris Shi and Yu Chen
Translation by Noah Maizels

Deep Dive Series:
Part 1: General Overview
Part 2: Random Number Generation
Part 3: Leader Selection Algorithms
Part 4: Delegation Mechanism
Part 5: Economic Incentives

In part 1 of our technical deep dive series, we introduced the overall framework and process of Galaxy Consensus. In the process of consensus, nodes will form two groups — the RNP (Random Number Proposer) group and the EL (Epoch Leader) group. The former is responsible for the generation of random numbers, and the latter is responsible for processing transactions and proposing blocks. This article will provide an in-depth look at Galaxy Consensus’s random number generation algorithm, its advantages, and its important role in the operation of the consensus protocol.

I. The important role random numbers play in blockchain systems:

Before we start digging deeply into the role of random numbers, we need to understand a concept, that is, “entropy”. Entropy is no stranger to friends in the field of physics. It is a measure of the degree of chaos in a system. In 1948, Claude Elwood Shannon proposed the concept of information entropy to describe the unreliability of sources. In short, entropy is a measure of uncertainty. To give a simple example: “The weather conditions in Beijing tomorrow” may be sunny, cloudy or rainy, the result is uncertain, so the entropy is positive —however, for the statement, “the earth will be destroyed tomorrow”, we know the earth tomorrow will not be destroyed, so the entropy is zero.

So what is the relationship between entropy and blockchain systems? It can be said that entropy is crucial to blockchain systems and is the security guarantee for the operation of the entire system. Taking Bitcoin as an example, it adopts PoW (Proof of Work) as a consensus algorithm. The miners perform countless hash calculations to compete for the right to be the block producer. The identity of the block producer of any height block cannot be predicted in advance. This is the embodiment of entropy in the Bitcoin system. Imagine if the entropy is 0, that is, the block producers of each block are determined in advance or artificially controllable, then there will be attacks such as collusion and forks. Therefore, any blockchain system needs a safe and effective way to introduce entropy into the system. Blockchain systems based on PoW consensus introduce entropy into the system in a natural way due to the randomness of mining. However, for a blockchain system with PoS or DPoS consensus, it is necessary to design a way to introduce entropy. This is where random number generation algorithms come in. It can be said that the random number generation algorithm is one of the main challenges in designing a proof of stake consensus mechanism, and it is also one of the most important criteria for measuring the merits of the consensus mechanism.

II. The requirements of a random number generation algorithm:

Since the random number generation algorithm is so important, what should a good random number generation algorithm look like? From a safety and practical point of view, it should meet the following six characteristics:

1. Decentralized: The process of generating random numbers is decentralized and does not rely on any trusted third parties.

2. Unpredictable: There is no way to predict future random numbers based on historically generated random numbers or other information. This is a basic requirement for randomness.

3. Unbiased: No one can use computing power or latecomer advantage to influence the results of random number generation.

4. Uniformity: The output of random numbers is evenly distributed within its range.

5. Guaranteed Output Delivery: Participants in the random number generation algorithm cannot prevent the random numbers from being generated by violating the algorithm rules, that is, it is guaranteed that there will be a random number output.

6. Publicly Verifiable: A node that does not participate in random number generation can monitor the execution of the protocol after execution, ensuring that the random number is trusted and unbiased.

The above six properties are essential for a random number generation algorithm, and any violation of any of them may lead to serious security holes. According to blockchain security company PeckShield, more than 8 gaming projects on EOS have been hacked for over millions of dollars, seriously threatening the EOS ecosystem, and most of the reasons for successful attacks are related to random number generation vulnerabilities. Taking the EOS.WIN project as an example, we analyze the root cause of its random number algorithm vulnerability.

One of the games supported by EOS.WIN is a number guessing game where a user must guess the random number which will be generated by the system. Obviously, if you can influence the random number generation in the system, you can influence the outcome of the game. The factors that determine the random number generation of the EOS.WIN system are the transaction hash ID, the transaction block height, the transaction block prefix, and the global lottery serial number.

Although the transaction block height and the transaction block prefix are the information of some future block, the implementation process specifies that the latest block information currently synchronized is used, and so this information can be pre-determined. Additionally, the transaction hash ID can be combined through the transaction action, and the block data can be pre-computed. With all this information able to be pre-determined, then the generation of the random number depends only on the global lottery serial number.

The attacker then creates many transactions with errors, causing the transaction status to roll back, and in this way controlling the global lottery serial number, thus controlling the generation of the random number until winning. Obviously, EOS.WIN’s random number generation algorithm does not satisfy the second property (unpredictability) and the fourth property (unbiased) mentioned above, so there is a loophole which is ultimately exploitable by an attacker.

III. Galaxy Consensus random number generation algorithm:

The RNP group in Galaxy Consensus implements a safe and efficient random number generation algorithm by means of commitment, zero-knowledge proof, threshold secret sharing, threshold signatures, elliptic curve-order pairing, etc., and provides data which is the basis for the security of the entire consensus process. In order to be able to illustrate the design of the random number generation algorithm and its subtleties, we compare it to a simple card game:

Card Game Description

Alice and Bob play a game where each of the two secretly choose a playing card to be placed under the table. After their selection, the card is shown on the desktop. If the sum of the face values of the two cards is even, then Alice wins, if it is odd, Bob wins.

This game may seem simple, but it’s not so easy to be fair on the blockchain. There are many problems we need to overcome to prevent Alice or Bob from cheating. We will analyze them one by one:

Problem 1: Alice and Bob can’t change their card selection after making their first choice. Otherwise, they can choose their card according to the other party’s cards. For example, if Alice can change her cards, then Alice can win if she picks a card with the same value as Bob’s, making the sum even.

Solution:

Galaxy Consensus ensures that the above cheating does not occur by using a commitment (CM). A commitment is a cryptographic tool that guarantees that “the evidence is retained” without exposing the original data. The commitment data has a one-to-one correspondence with the original data. Anyone can verify the correspondence between the two.

Going back to our example, Alice and Bob each tear a small corner of their chosen playing card and put it on the table. This small corner will not reveal the information of which card they chose, but the unique tear pattern guarantees that they cannot change their card choice without being discovered. In the Galaxy Consensus protocol, this is the DKG1 (Distributed Key Generation) phase of the Random Beacon. Each RNP node calculates the commitment of its selected data and sends it to the chain for verification.

Problem 2: After Alice and Bob choose their playing cards, they must keep their playing cards secret before the official reveal of the cards, and they cannot let any other party see them. At the same time, when the card is shown, it is necessary to prove that the card is indeed the previously selected card, not a newly selected card.

Solution:

Galaxy Consensus encrypts the original data using a public key encryption algorithm, and then sends the encryption result to the chain to ensure the confidentiality of the data. At the same time, a zero-knowledge proof is used to ensure that the encrypted data of the uplink is fully matched with the commitment. In the Galaxy Consensus protocol, this is the DKG2 phase of the Random Beacon. Each RNP node encrypts the data of other nodes using the other nodes’ public keys and sends it to the chain (S1, S2…SN). At the same time a DLEQ-Proof (discrete log equivalence proof) is also sent on chain, this is used to prove that the encrypted content (S) matches the commitment (CM). After this phase, all nodes can get the data sent by other nodes from the chain and decrypt them locally to plaintext. By way of our previous metaphor of a card game, Alice and Bob lay the torn corners of their cards (CM) out on the table and tape them securely on the table, and then verify (DLEQ) that the cards can be stitched together with the small corners taped to the table to make a complete card (S).

Problem 3: After revealing the card, you need to calculate the points of the two cards. We want to make sure that both Alice and Bob are guaranteed to calculate the same correct result. This problem seems ridiculous, but it is very important. Because a player may be irrational or malicious, and deliberately calculate the wrong number, thus reducing the efficiency of the game.

Solution:

Galaxy Consensus solves Problem 3 by using a distributed key generation algorithm, that is, all RNP nodes generate a common group secret key. The key is never produced completely, but is split into key fragments. Each RNP node has a share of the group secret key. After that, the RNP nodes can synthesize the group key signature, and the hash value of the signature is the final random number output. Since the group key is publicly determined, the group key signature is also uniquely fixed. Going back to our card game example, this is how Alice and Bob can be sure to calculate the same value for their cards’ sum.

Problem 4: At this point, neither Alice nor Bob can terminate the game. That is, once the game starts, it must end normally, and the game cannot be aborted because a player refuses to cooperate with the rules of the game.

Solution:

Galaxy Consensus solves Problem 4 by means of threshold signatures, that is, as long as the participating RNP nodes exceeding the threshold number of participants in the calculation, the group key signature can be synthesized. The refusal of individual RNP nodes to participate in the calculation does not affect the generation of the results. Back to our example of the card game, even if Alice doesn’t want to show up, Bob has the ability to reveal the two cards to complete the game.

The above process corresponds to the SIGN phase of the Random Beacon in the Galaxy Consensus Protocol, in which the RNP nodes cooperate to generate a group key signature and calculate the random number output.

Now let’s sort through the above process:

1. The sum of the points of Alice and Bob playing cards is determined jointly by the both players.

2. The cards chosen and the card sums of each game are independent for each game, so historical game data cannot be used to make predictions about future games.

3. Alice and Bob can’t know each other’s card values in advance, so neither one has an advantage.

4. Alice and Bob can choose any card, so the point distribution is even.

5. Alice and Bob cannot interrupt the game;

6. Any third party can audit the game process, because all data is stored on the chain.

It can be seen from the above analysis that the random number algorithm of Galaxy Consensus satisfies the six properties mentioned above, and is a safe and efficient random number generation algorithm.

Now we have come to the end of our deep dive into the random number generation process Galaxy Consensus, and you hopefully have a better understand of how the process works. In our next article, we will take a deep dive into Galaxy Consensus’s Unique Leader Selection algorithm, so stay tuned!

About Wanchain

Wanchain is the infrastructure connecting the decentralized financial world. Wanchain’s live cross-blockchain solution is EVM-based, includes optional private transactions, and provides a decentralized, permissionless, and secure approach for interoperability. Wanchain has employees globally with teams in Beijing (China), Austin (USA), London (UK), Kuala Lumpur (Malaysia), Paris (France), and Madrid (Spain).

You can find more information about Wanchain on our website. Additionally, you can reach us through Telegram, Discord, Medium, Twitter, and Reddit. You can also sign up for our monthly email newsletter here.