Leader Selection Algorithms

This is Part 3 of our technical deep dive series, see Part 1 or Part 2 to learn more.

 

In our previous technical deep dive articles we introduced Wanchain’s Galaxy Consensus in Part 1, and we discussed its random beacon design in Part 2. In this article, we will be taking a closer look at leader selection algorithms, and at Galaxy Consensus’s Unique Leader Selection (ULS) algorithm.

As described in Part 1, in the process of consensus, the nodes will form two large groups — the RNP (Random Number Proposer) group and the EL (Epoch Leader) group. The former is responsible for the generation of random numbers, while the latter is responsible for block production. One of the key problems for any consensus protocol is determining which individual node will be the block producer. This article will explore how the block producer is chosen from within the EL group (leader selection).

1. The significance of rational leader selection

In Part 1 of this series, we explained that the two core issues to be addressed in any blockchain consensus protocol are Leader selection and Chain selection. Rational leader selection is of utmost importance to the safety and liveness of a chain and is the cornerstone of a healthy consensus protocol (You can read more about safety and liveness in this excellent blog article from the Interchain Foundation).

The proliferation of a chain is essentially the continuous connection of blocks, and it is block producers who package and propose new blocks. Block producers decide which transactions are written into the block and put on chain, and also determine the development direction of the chain through parent block selection. Under the conditions where a network consists of both good and malicious nodes, a good leader selection algorithm ensures that the honest nodes get the right to produce blocks and lead the development of the chain. Of course, since different consensus protocols make different security assumptions, the design of the leader selection algorithm varies between chains. Let’s explore some of the concepts and considerations significant to leader selection algorithms:

Safety:

Let us first talk about the significance of the choice of the block producer to a chain’s safety. Safety refers to the property of a distributed computing system which ensures that ‘nothing bad will happen.’ In the case of Bitcoin or other cryptocurrencies, this could refer to double spending or other cases of the wrong information going on chain.

Security Assumptions by Protocol Type:

Different protocols can ensure safety under different security assumptions. Let’s take a look at some of the more well known protocols and their security assumptions:

Proof of Work (PoW): 50% or more honest participants:
PoW protocols use hash operations to select block producers, that is, the nodes repeatedly perform hash functions in order to find some random data to solve a problem. This is the process commonly referred to as mining. The answer to the problem is not predictable, and no node has any advantage in solving the problem, it is purely a computational competition. Under this type of system, as long as more than 50% of the work is from honest nodes, the safety of the chain is ensured.

Byzantine Fault Tolerant (BFT) protocols: 2/3 or more honest participants:
BFT-like protocols usually adopts the turn taking or probability selection for leader selection. No matter which method is adopted, the consensus protocol must ensure that the majority of block production rights go to honest nodes, and also require that the participating nodes vote on the proposed blocks. Only the block that has won more than 2/3 of the votes is the final valid block, thus ensuring the safety of the chain.

Proof of Stake (PoS): more than 50% honest participants:
PoS protocols randomly select the block producers according to their proportion of stake in the system. The key to the security of this type of system is a secure source of randomness which ensures that honest participants are chosen to lead the development of the chain, thereby ensuring the safety of the chain.

The above introduces the designs of common consensus protocols with different security assumptions. Of course there are many variations on the above described protocols which will not be discussed in detail here. It can be seen from the above that a rational leader selection algorithm is extremely important for the safety of the chain.

Liveness:

Let us briefly discuss the significance of leader selection for the liveness of a chain. Liveness refers to the ability of a chain to continuously process transactions without stalling, and the assurance that valid transactions will be confirmed after some period of time. Block producers are responsible for the propagation of the chain, and are responsible for chain liveness. In general, to ensure chain liveness, two problems need to be solved:

First, the liveness of the block producers must be guaranteed. Block producers must actively participate in the consensus process, not be offline or dormant in such a way which influences the propagation of the chain.

Second, data consistency between nodes must be guaranteed. honest nodes must be able to receive valid legal transactions, and honestly package them into the block for confirmation.

Together with the above discussion of safety, the chain’s liveness can be guaranteed. The liveness of the block producer is guaranteed by the leader selection algorithm. Leader selection is a generalized concept, and does not necessarily refer to any specific selection algorithm, but must considered in the overall design.

2. Important considerations for a leader selection algorithm

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

1. Fair
   The block production rights are distributed according to the qualifications of the consensus nodes. For example, the higher the computation power in PoW, the greater the chance of obtaining the right to be the block producer, and the greater the amount of stake held in PoS, the greater the chance of obtaining the block production right. The concept is very natural and reasonable, but not easy to put into practice. To achieve true fairness, we need to avoid many problems. Let us illustrate with an example: Suppose A and B are two block producers. Which node gets the block production right is decided by rolling dice. If an odd number is rolled, then A obtains the block production right. For if an even number is rolled, then B obtains the block production right. Under fair conditions, the dice are thrown by “God”, and A and B’s chances are each 50%. If, however, A gets the right to roll the dice, then it is no longer fair. He can experiment and even change the numbers on the dice in order to get the block production rights, and then can decide to develop the chain in any way he/she wishes.
2. Verifiable:
   The legality of the right to block should be publicly verifiable. For example, the hash value of the block header in PoW can be easily verified by the whole network. This property is an obvious and inevitable requirement. As a decentralized system, the blockchain must be accepted and approved of by the whole network. The verification of valid blocks is one of the basic requirements. In addition to verifying the legitimacy of the transactions and the structure of the block, the validity of the block producer must also be able to be verified, so any leader selection algorithm must ensure that the ownership of the block right can be verified.
3. Anonymity: The block producer should be able to participate anonymously. This property is not an inevitable requirement. It is proposed because anonymity can solve security risks that may arise in consensus, such as corrosion attacks. Specifically, if the block producer is known by the whole network, then the malicious nodes may corrupt it through bribery, and turn the original honest node into a malicious node. The block producer may even be susceptible to cyber attacks, and be knocked offline in order to benefit malicious nodes. Therefore, achieving anonymity is also a problem to be considered when developing a consensus protocol. Many projects (such as Dfinity, Algorand) use the VRF algorithm to achieve anonymity, but VRF also has its own flaws and drawbacks. There are some proposals (such as Ouroboros Crypsinous) which use zero-knowledge proofs for anonymous consensus, but have not yet been implemented.

3. Common leader selection algorithms

After explaining the importance of leader selection and discussing the important design considerations for a leader selection algorithm, we will now describe three popular leader selection algorithms.

1. Hash rate competition

A competition based on hashing power is the earliest block selection algorithm used in the context of blockchains. The most typical one is the Bitcoin system, which is a relatively simple and crude, although effective method. After the consensus nodes bundle the transactions, 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 valid block that meets the requirement is formed, and then broadcast to the network. The first node to do this then becomes a valid block producer, that is in short, the complete mining process. The advantage of this approach is that it is fair to all participating nodes. No node will gain an advantage in computing hashes. As long as half of the overall computing power is safe, then the chain is safe. At the same time, this method may have multiple legal blocks and legal block producers a the same block height, so there will be short term forks, which is why the Bitcoin system needs to wait for confirmation time. At present, this kind of leader selection algorithm has the highest degree of decentralization amongst all consensus protocols. 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. 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 algorithm is used for the leader selection algorithm to solve the issue of anonymity. The specific method is to first set a reasonable threshold value. The nodes then user their own private keys to perform a calculation using some random data, and if the result of the calculation is less than the threshold, then that node wins the right to be the legal block producer. In this process, the private key calculations can only be performed by the node itself, which ensures that other nodes cannot know who earned the right to block production, and the calculation result can be publicly verified, ensuring that the validity of the block production rights can be verified, thus forming the entire leader selection process.

Obviously, this method is probabilistic. If you want to have as many legal block producers as possible at a certain block height, you need to increase the threshold value as much as possible. Otherwise, if you want to have as few legal block producers as possible, then you should to reduce the threshold value as much as possible.

This means the setting of the threshold value can have a great impact on the greater system as a whole, and it is very difficult to achieve an optimal value. If the threshold is high, then it could lead to a large number of legal block producers at some block height, leading to many forks. If the threshold value is low, there may not be any legal block producer at all. Therefore, although the VRF algorithm solves the anonymity problem, it has a number of drawbacks as well.

3. Follow-the-satoshi

Follow-the-satoshi is a common leader selection algorithm in proof of stake protocols. This method relies on generating a random number, and then using that number to pick a random token from amongst all the staked tokens. Whoever is the owner of that token is selected as the valid block producer. The challenge of this approach lies in how to find a secure random source to generate true random numbers. Cardano currently uses the follow-the-satoshi method for the selection of block producers.

The generation of the random numbers uses multiple cryptography techniques such as multi-party computation and threshold secret sharing to ensure the security of the random source. The anonymity of leader selection has not yet 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 the approach taken 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 such as that is a good pseudo-random source, but there is still a risk of it being deliberately controlled. To learn more about random number generation, you can refer to Part 2 of this series.

4. Galaxy ULS (Unique Leader Selection) algorithm

The Wanchain Galaxy Consensus’s leader selection algorithm termed ULS, or Unique Leader Selection algorithm. It was designed from the ground up to consider fairness, verifiability and anonymity, and employs a variety of cryptographic methods such as secret sharing and zero-knowledge proofs to realize the anonymous selection of a single unique valid block producer in a fixed time window. The algorithm was also designed to reduce the probability of forks and improve the efficiency of consensus. Below we will introduce the overall principle of the Galaxy Consensus’s ULS algorithm.

1. EL group selection
The EL group is the main body for running the ULS algorithm. Let’s start with the source of the EL group. There is a brief introduction of this in Part 1 of this article series, and we will here give a detailed explanation. In a PoS protocol, the right to speak is determined by the amount of stake held, and we implement this in the selection process of the EL group. Based on the current stake in the Wanchain consensus smart contract, the stake value of each node and its stake 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 process. Each node is assigned a certain breadth of time proportional to its stake, and then the random number is used to decide a specific time. Whomever’s breadth of time in which the time is chosen, the owner of that breadth of time is then selected to be in the EL group. Each round is an independent selection, meaning that a node may be selected multiple times, so the final EL group is a multiset (nodes may be chosen more than once within one EL group). The selected EL group will then be responsible for running the ULS algorithm.

2. Secret Message Array generation
After the EL group is selected, it needs to communicate on chain. The process is to generate a secret message sequence inside the group for subsequent assignment of block production rights, 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, we split the process into two phases, SMA1 and SMA2. In the SMA1 phase, each node in the group selects a random number, encrypts it with its own public key, and sends it to the chain as a commitment (CM) for the 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 DLEQ-Proof (discrete log equivalence proof), which is used in the SMA1 phase. The key-encrypted data ensures that the random number has not changed, and the DLEQ proof ensures that all public keys are encrypted with the same random number. After this phase is completed, all EL group nodes can all decrypt the data themselves and get a random data sequence, which is our secret message sequence, and are then ready to run the leader selection algorithm.

3. EL group 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 group nodes. A hash operation is performed on the group node’s public keys and the random number, and the nodes are sorted in ascending order based on the operation result. This result will be used for the allocation of the order of subsequent block production rights. Obviously, the sorting is based on the new random number after the secret message sequence, and no node can affect it, the sorting is completely random.

4. Slot leader selection
After the above three tasks are completed, the distribution of the block production rights can be performed for the EL group nodes. In the previous article, we said that a group of EL nodes is responsible for the generation of blocks within an epoch. How then is the block producer of each slot in the epoch determined? First, the current random number and the epoch number and the slot number are hashed, and the modulus of the number of EL group nodes is used to pick the slot leader. For example, if the hash value is 2019, the number of EL group nodes is 50, the modulus result will be 19, so then the EL node with the number 19 in the order from the previous sorting step is selected as the valid block producer (slot leader). This selection process is carried out with equal probability for all members of the EL group. Combined with the stake rate which is used when the EL group nodes are selected (remember, the EL group is a multiset meaning a single node may appear in it more than once), it ensures that the choice of the block producer is made in accordance with the ratio of stake held by consensus participants. The valid block producer must provide proof of its validity when proposing a block, and this proof must be publicly verifiable in order to guarantee its validity. The secret message array used in the selection of the slot leader is shared only within the EL group, other nodes have no knowledge of it, which guarantees the anonymity of the selection process. It can thus be seen that the ULS algorithm is a design that fully considers fairness, verifiability and anonymity, and will play an important positive role in ensuring the safety and liveness of the chain.

The above is a brief introduction to Galaxy Consensus’s leader selection algorithm — the ULS algorithm. The details are described more fully in the Galaxy Consensus paper. In subsequent technical deep dive articles, we will further introduce other exciting elements of Galaxy Consensus’s design. Stay tuned for more!

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.