Wanchain Galaxy Consensus Exploration 03 – Blocker Selection Algorithm

In the previous article, we introduced the overall architecture and flow of the galaxy consensus and the random number generation algorithm . 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. In the previous article, a detailed and visual introduction has been made. The latter is responsible for packaging. The transaction proposes a block, and the core difficulty of this work is to solve the problem of the choice of the blocker. This article will introduce the process principle and important role of the blocker selection in the EL star group.

1. The importance of reasonable choice of the blocker

In our first article, the two core issues to be addressed in the blockchain consensus protocol are Leader selection and Chain selection, regardless of the consensus agreement. Reasonable choice of the blocker is a top priority. One of the key functions of the design of the random number generation algorithm to introduce entropy is to use it for the choice of the blocker.

Reasonable choice of the blocker is crucial to the security and activity of the guarantee chain. A good block selector algorithm is the cornerstone of the consensus health operation. Let us first talk about the significance of the choice of the block to the security of the chain. The extension of the chain is essentially the continuous connection of the block, and it is these blockers who complete the package and propose the block. On the one hand, they decide which transactions are written into the block. Furthermore, the uplink confirmation, on the other hand, also determines the development direction of the chain by selecting the parent block of access. In the environment where the consensus nodes are good and evil in the network, a good block selector algorithm is to ensure that the honest node can Get more out of the block, and then lead the chain. Of course, different consensus protocols are different under different security assumptions, and the design of the block selector algorithm is different.

• Babitian MatPool operates NEO node, 2019 must be the first year of Staking economy
• Poloniex crazy to clear the token: Who is the next one to be fired?
• Depth | BitMEX Research Report: Incentives and Investment Value of BTC Lightning Network

• Proof of Work (PoW): 50% or more

Under this security assumption, PoW uses the hash operation method to select the blocker, that is, the node uses a large number of hash trials to find random data to solve the problem, that is, mining, in the process, the result of the hash function is not available. Predictive, any node does not have an advantage in hash trials, it is a purely computational competition, and more than 50% of the security calculations ensure that most of the blockers are honest nodes, thus ensuring the security of the chain.

• Security assumption for class BFT protocol: 2/3 or more node security

Under this security assumption, the BFT-like protocol usually adopts the method of taking the initiative or the probability selection to select the blocker. No matter which method is adopted, the honest node can guarantee the majority of the block-out rights, and the nodes in the consensus network must be required. Vote on the proposed block, only the block that has won more than 2/3 of the vote is the final legal block, thus ensuring the security of the chain.

• Proof of Rights (PoS) security assumption: more than 50% of the security

Under this security assumption, the PoS protocol randomly selects the blockers according to the proportion of node equity holdings, and the key to this choice is the security of randomness, ensuring the security of the random source to ensure a large number of blocks. In the process of selection, the honest node can obtain the majority of the block right, and then lead the development of the chain, ensuring the security of the chain.

The above introduces the design method of the common consensus protocol under the different security assumptions, and of course there are special mixed modes, which will not be discussed in detail here. It can be seen from the above that reasonable block selector selection is extremely important for the security of the guarantee chain. We can use a simple reverse example to intuitively understand that if a bite coin is found, a malicious node finds the mining. Tuen Mun has obtained more than half of the right to block, so he can arbitrarily reconstruct the chain to achieve double-flower attack, any transaction will no longer be trusted, this will be a devastating blow to the Bitcoin ecosystem. .

Let us briefly talk about the importance of the choice of the block to ensure the activity of the chain . The definition of activity is discussed in different interpretation articles. In short, the chain can be extended and developed continuously, and effective legal transactions can be confirmed after a period of time. The blockers are responsible for the development of the chain. Obviously they are the main body of the chain activity. There are many consensus models (such as Snow White) that have in-depth research and exploration on how to ensure chain activity. In general, to ensure chain activity, two problems need to be solved: First, to ensure the activity of the blocker, if the selected blocker is active, actively participate in the consensus process, but not offline or dormant, which leads to a large number of The lack of blocks affects the normal development of the chain; the second is to ensure data consistency between nodes, honest nodes must be able to receive valid legal transactions, and honestly package them into the block to confirm. Together with the above discussion of safety, the chain's activity can be guaranteed. The activity of the blocker is guaranteed by the choice of the blocker. This choice is a generalized concept, which is not necessarily narrowly defined in the specific selection algorithm, but is considered in the overall design concept. Wanchain The galaxy consensus has focused on this and has been properly addressed through the new definition of the concept of equity, the design of the entrustment mechanism, and the incentives for reward and punishment mechanisms. We will not elaborate on this, and the subsequent interpretation will explain it in detail.

2. Several problems to be considered in the block selector algorithm

The importance of the blocker selection algorithm is introduced above. Which questions should be considered when designing a blocker selection algorithm, or which properties are the measure for evaluating the quality of a blocker selection algorithm?

1) Fairness: The block right is distributed according to the consensus node qualification. For example, the higher the power in PoW, the greater the chance of obtaining the block right, and the greater the amount of equity held in PoS, the greater the chance of obtaining the block right. This is a very natural and reasonable nature, but its extension is very broad, and the choice of the blocker is like gambling. To achieve true fairness, we need to avoid many problems. Let us illustrate with an example: Suppose A and B are two. A consensus node decides who is the blocker by rolling the dice. If the number of odd points is odd, then A obtains the block right. For even numbers, B obtains the block right. Under fair conditions, the dice are thrown by "God", A and B's chances are half, and if A gets the right to roll the dice, then the fairness is broken. He can experiment and even put out odd points to occupy the block right, and then decide the development of the chain and even carry it out. Attack, this is very scary.

2) Verifiability: The legality of the right to block is publicly verifiable. For example, the hash value of the block header in PoW is less than the difficulty value and can be verified by the whole network operation. This property is an obvious and inevitable requirement. As a decentralized system, the blockchain must be accepted and approved by the whole network. The legality verification of the block is one of the basic requirements, and the legality of the block is legal except for the transaction. In addition to the legitimacy of sex and structure, the legitimacy of the blocker is also a point that must be verified, so any blocker selection algorithm must ensure that the ownership of the block right can be correctly verified.

3) Anonymity: The blocker participates in the consensus through anonymous privacy. This property is not an inevitable requirement. It is proposed because anonymity can solve security risks that may arise in the consensus, such as corrosion attacks. Specifically, if the blocker is known by the whole network between the time of the block right, then the malicious node may corrode it by bribery, etc., and turn the original honest node into a malicious node to attack. Even direct cyber attacks cause the hacker to drop the line, which enhances the attack ability of the malicious node or reduces the block right obtained by the honest node. Therefore, achieving anonymity is also a problem to be considered for the consensus protocol. Many projects Most of them (such as Dfinity, Algorand) use VRF algorithm to achieve anonymity, but VRF also has its own flaws and drawbacks. Now there are projects (such as Ouroboros Crypsinous) that use zero-knowledge proof for anonymous consensus, but have not been implemented.

3. Common blocker selection algorithm

Introduce the significance and measurement standards of the block selector algorithm. We simply enumerate three typical algorithms to specifically understand the current popular blocker selection methods:

1) Competing competition

The method of computing power competition is the earliest use of the block selector algorithm in the blockchain system. The most typical one is the bitcoin system, which is a relatively simple and rude and direct effective way. After the consensus node packs the transaction, the hash value of the block header is repeatedly calculated by continuously adjusting the random number in the block header. When the hash value is smaller than the difficulty value required by the current block, a legal block that meets the requirement is formed, and then the obtained legal block is obtained. The right to block out, become a legitimate blocker, that is, complete the entire mining process. The advantage of this approach is that it is fair to all participating nodes. Any node will not gain an advantage in hash computing. As long as the overall computing power is more than half, it is safe, then the chain is safe. At the same time, this method may have multiple legal blocks and legal distributors in the same block height, and there will be a short fork, which is why the bitcoin system needs to wait for the confirmation time. At present, this kind of blocker selection algorithm is the highest degree of decentralization in the consensus agreement. Of course, with the development of technology and the deepening of research, mining has gradually developed from the initial cpu mining to gpu and asic mining. The computing power is growing rapidly, and many projects have designed new consensus protocols for resisting chip mining by adding storage requirements, such as Zcash's Equihash.

2) Verifiable Random Function (VRF)

The VRF is used for the block selector algorithm to solve the anonymity. The specific method is to set a reasonable threshold first. The node uses its own private key to operate on a random data (such as signature), and the result is less than the set. The threshold is a legal blocker, and the block right is obtained. In this process, the private key operation can only be performed by the node itself, which ensures that other nodes cannot know the block right attribution, and the calculation result such as the signature result can be publicly verified, ensuring that the validity of the block right can be verified and formed intact. The blocker selection process. Obviously, this method is probabilistic. If you want to have as many legal outliers as possible in a certain block height, you need to increase the threshold as much as possible. Otherwise, you want to have as few legal blockers as possible. It is necessary to reduce the threshold as much as possible. This has extremely high requirements on the setting of the threshold, and at the same time, the distribution of the results of the private key operation is also expected to be good. This is often difficult to achieve, and it is easy to appear in a certain area. The block height has a large number of legal outliers and forms a dense bifurcation. A block height does not have a legal blocker and forms a blank. Therefore, although the VRF algorithm solves the anonymity problem, there are still inevitable problems in the specific use.

3) follow-the-satoshi

Follow-the-satoshi is a common block selector algorithm in PoS. The specific method is to sort all the tokens and generate a random number through a random source. Which random number falls on which token number? Then the holder of this token is a legal blocker and has obtained the right to block. This approach is obviously the only certainty. The difficulty lies in how to find a secure random source to generate true random numbers. The Cardano project currently uses the follow-the-satoshi method for the selection of the block. The generation of the random number uses multiple cryptography techniques such as multi-party calculation and threshold secret sharing to ensure the security of the random source. The anonymity of block selector selection has not been implemented. However, in terms of random number generation, another way is to use the hash value of a certain piece of historical data on the chain, which is represented by Algorand, and the hash value of the previous block data and the current block height is used as the hash value. A random number is a good pseudo-random source, but there is still a risk of being deliberately controlled. The generation and related properties of random numbers are not discussed too much here. Interested readers can refer to the previous article.

4. Galaxy ULS algorithm principle flow

  I have talked so much about it, and finally I have to go back to our theme. The Wanchain Galaxy Consensus's block selector algorithm, ULS algorithm, ULS stands for unique leader selection, the only choice of the blocker, the ULS algorithm is designed. At the beginning, it considered fairness, verifiability and anonymity, and adopted a variety of cryptographic methods such as secret sharing and zero-knowledge proof to realize the anonymous selection of the only legal blocker in a fixed time window. On the basis of sex, try to reduce the probability of short forks and improve the efficiency of consensus. Below we will introduce the overall principle flow of the galaxy consensus ULS algorithm.

1) EL star group selection

The EL constellation node is the main body for running the ULS algorithm. Let's start with the source of the EL constellation. There is a brief introduction in the first interpretation of the galaxy consensus. Here we will give a detailed explanation. In the PoS protocol, the right to speak is determined by the amount of equity held, and we implement this correspondence in the selection process of the EL constellation. Based on the current pledge state of the Committee in the Wanchain consensus contract, the equity value of each node and its equity ratio can be calculated. Using the random number provided by the Random Beacon, the follow-the-stake-ratio algorithm is run, similar to the follow-the-satoshi The process, in a vivid way, is that the nodes in the Committee divide the dial of a watch according to its equity ratio. Each node has a time pane with the same proportion of its equity, and then the random number is the hand of God who dials the time pointer. In which time pane falls, the owner of this pane is selected into the EL constellation. Each round is selected independently, and a node may be selected multiple times, so the last EL cluster may be a multiple set. The selected EL constellation will be responsible for running the ULS algorithm.

2) Secret Message Array generation

After the EL constellation is selected, it needs advanced communication communication negotiation on the chain. This process is to generate a secret message sequence inside the constellation for subsequent distribution of block right, which is a key step for us to achieve anonymity. In order to ensure that the secret message sequence is not controlled by some malicious nodes, which affects the subsequent algorithm operation, we split the process into two phases, namely SMA1 and SMA2. In the SMA1 phase, each node in the constellation selects a random number, encrypts it with its own public key, and sends it to the chain to complete the promise of random number selection, ensuring that the random number selected by any node cannot be changed in subsequent stages. In the SMA2 phase, each node in the constellation sends its own chosen random number to the chain with the public key of all nodes (including itself), and provides a proof of coordination (DLEQ proof), which is used in the SMA1 phase. The key-encrypted data ensures that the random number has not changed, and the coordination proof ensures that all public keys are encrypted with the same random number. After this phase is completed, all EL cluster nodes can decrypt themselves and get a random data sequence, which is our secret message sequence, ready to run the block weight allocation algorithm.

3) EL cluster node sorting

After the secret message sequence is generated, the random number is updated, and the newly generated random number is used as a seed to sort the EL cluster nodes. The specific method is to perform the hash operation on the cluster node public key and the random number, and perform the ascending order based on the operation result. This sorting result will be used for subsequent block weight allocation. Obviously, the sorting is based on the new random number after the secret message sequence, and any node can't affect it, it is a completely random sort result.

4) Distribution of block rights

After the above three tasks are completed, the distribution of the block rights can be performed for the EL cluster nodes. In the previous interpretation, we said that a group of EL stars is responsible for the generation of an epoch block. How is the block weight of each slot in the epoch determined? First, the current random number and the epoch number and the slot number are hashed. The result of the operation is the modulus result of the number of EL cluster nodes. For example, the hash value is 2019. At present, the number of EL cluster nodes is 50, and the modulus result is 19, then the EL star The 19th bit in the sorting of the group node is selected as the legal blocker, and the block right is obtained. This selection process is carried out with equal probability. Combined with the equity ratio when EL group nodes are selected, it ensures that the choice of the blocker is reasonable according to the amount of equity held, ensuring fairness; legal applicants are proposing The block needs to provide legality credentials, which can be publicly verified to ensure the verifiability of the block legality; the legitimate blocker chooses to use the secret message sequence, and this message sequence is only inside the EL star group. Sharing, other nodes are unknown, and the anonymity of the selection process is guaranteed. It can be seen that the ULS algorithm is an innovative design that fully considers fairness, verifiability and anonymity , and will play an important positive role in the security and activity of the guarantee chain.

The above briefly introduces the galaxy consensus block selection algorithm – ULS algorithm. The details are described in the galaxy consensus paper. In the subsequent galaxy consensus exploration, we will further introduce other exciting contents in the galaxy consensus design. Stay tuned.

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