Wanchain Galaxy Consensus Exploration 02 – Random Number Generation Algorithm

In the previous article , we introduced the overall framework and process of the galaxy consensus. In the process of consensus, the nodes will form two large constellations – the RNP constellation and the EL constellation. The former is responsible for the generation of random numbers, and the latter is responsible for packing transactions to propose blocks. This article will provide an in-depth introduction to the galaxy consensus random number generation algorithm and its advantages and important role in the operation of the consensus protocol.

First, the important role of random numbers for blockchain systems

(Image taken from the network, invaded)

• 2019 blockchain technology trend analysis and outlook blue book
• Does Buffett still have enough bitcoin? I have already written annoyed.
• Inventory: A-share blockchain concept stocks are over 70% profit, less than the overall performance of listed companies

Before we officially talk about 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 the 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; "the earth will be destroyed tomorrow", we know the earth tomorrow Will not destroy, this is the result of the determination, so the entropy is zero.

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

Second, the measurement of the advantages and disadvantages of the 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. Distributed: The process of generating random numbers is decentralized and cannot be relied upon or done with trusted third parties.
2. Unpredictable: Unable to predict future random numbers based on historically generated random numbers or other information. This is a basic requirement for "random".
3. Unbiased: No one can use the computing power or the latecomer advantage to target the results of random numbers.
4. Uniformity: The output random number is evenly distributed within its range.
5. Guaranteed Output Delivery: Participants in the random number generation algorithm cannot pass the algorithm in such a way that the random number cannot be output, that is, there will be random number output.
6. Publicly Verifiable: A node that does not participate in random number generation can monitor the execution of the protocol in a post-test manner, verifying that the random number is trusted and unbiased.

The above six properties are essential for the 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 quiz projects on EOS have been hacked and profited millions of dollars, seriously threatening the normal ecological order of EOS, 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 to guess the number, that is, the user enters a number and presses it up or down, and then the system randomly generates a number. If the user presses the size, it is regarded as winning and gaining. Obviously, if you can control the number randomly generated by the system, you can control 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. The transaction block height and the transaction block prefix are some block information in the future, but the implementation process specifies that the latest block information currently synchronized is used, and thus is determined; at the same time, the transaction hash ID can be combined through the transaction. The block information is pre-computed. Then the generation of the random number depends only on the global lottery number. The attacker uses the constant creation of the wrong transaction, causing the transaction status to roll back, controlling the global lottery serial number, and thus controlling the generation of the random number until winning. Obviously, EOS.WIN 's random number generation algorithm does not satisfy the above-mentioned second property (unpredictability) and the fourth property (unbiased), so there is a loophole that is ultimately attacked by the attacker.

 

Third, the galaxy consensus random number generation algorithm

 

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

Card game

Alice and Bob play card games, and the two secretly choose a playing card to be placed under the table. After the selection, the card is illuminated on the desktop. If the sum of the points of the two cards is even, then Alice wins; otherwise, Bob wins.

This game seems simple, but it's not easy to be fair on the blockchain. There are many ways to prevent Alice or Bob from cheating. We will analyze it step by step:

Question 1 : Alice and Bob can't change the cards after they are selected. Otherwise, they can decide the number of cards according to the number of points on the other cards to win. For example, if Alice can change the playing cards, then Alice can win as long as the playing cards and Bob's playing cards have the same parity, then the points and the total number are even.

The galaxy consensus guarantees that the above cheating will not occur by using a "commitment" . "Commitment" is a cryptographic tool that guarantees that "evidence is retained" on the basis of not exposing the original data. It is one-to-one correspondence with plaintext. Anyone can verify whether the correspondence between the two is true. .

Combined with our example image understanding, Alice and Bob tear a small corner of their chosen playing card and put it on the table. This small corner will not reveal the poker points, and only the other part that is torn can be stitched into one. Complete playing cards. In the Galaxy Consensus Agreement, this is the DKG1 phase of the Random Beacon. Each RNP node calculates the commitment of its selected data and sends it to the chain for verification.

Question 2 : After Alice and Bob choose the playing cards, they must keep their playing cards secret before the official opening of the cards, and they cannot let the 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 the newly selected card.

The galaxy consensus encrypts the original data by public key encryption algorithm , and then sends the encryption result to the chain to ensure the confidentiality of the data. At the same time, the zero-knowledge proof is used to ensure that the encrypted data of the uplink is fully matched with the promise. In combination with our example image understanding, Alice and Bob take the torn corner cards out of the table and buckle them on the table, and both verify that the cards buckled on the table can be stitched together with the small corners previously placed on the table. A complete card. In the Galaxy Consensus Agreement, this is the DKG2 phase of Random Beacon. Each RNP node encrypts the data of other nodes to the other node and sends it to the chain. At the same time, it is sent to the chain with DLEQ-Proof. Prove that the encrypted content matches the promised CM. After this phase, all nodes can get the data sent by other nodes from the chain and decrypt them locally to plaintext.

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

Question 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.

The galaxy consensus solves the problem 3 by using a distributed key generation algorithm, that is, all RNP nodes generate a common group secret key by interaction, and the key does not appear completely, but is split into key fragments. Each RNP node has a group secret key. After that, the RNP node 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. Combined with our example image understanding, Alice and Bob will calculate the common points.

The galaxy consensus solves the problem 4 by means of threshold signature , that is, as long as the RNP node exceeding the threshold number participates 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. Combined with our example image understanding, even if Alice doesn't want to show up, Bob has the ability to show 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 by the two; 2. The points and sums of each game are independent, there is no interdependent relationship, so the history game The data has no predictive effect; 3. Alice and Bob can't know each other's poker points in advance, so there is no late advantage to the sum of the left and right points; 4. Alice and Bob can choose any card, so the point distribution is even. ; 5. Alice and Bob can not interrupt the game; 6. Any third party can audit the game process, because all data is stored in the chain.

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

This interpretation of the random number generation algorithm for the galaxy consensus ends, I believe you have a deeper understanding. Next time we will interpret the galaxy consensus ULS algorithm, so stay tuned.

We will continue to update Blocking; if you have any questions or suggestions, please contact us!