The Evolution of Blockchain Core Technology - Evolution of Consensus Mechanism (1)

Generally speaking, two examples are often mentioned when introducing blockchain: one is the extension of the ancient accounting model to the distributed ledger, and the other is the Byzantine Generals Problem. The purpose of using a distributed ledger is to allow each node to verify transactions, and the Byzantine Generals Problem is related to the consistency of the ledger, which is the consensus mechanism discussed in this article.

The consensus mechanism on the blockchain mainly solves the problem of who will construct the blocks and how to maintain the unity of the blockchain. The theoretical basis of this problem is Byzantine Fault-Tolerant (BFT). BFT has been studied since the 1980s and is now a relatively thorough theory. There are ready-made algorithms for the prerequisites and specific implementations of the solution. However, this article does not intend to start with BFT, because what is to be analyzed is the evolution of the blockchain consensus mechanism, and Satoshi Nakamoto did not adopt BFT. In fact, when I started studying Bitcoin, even for a long time after understanding the POW mechanism, I did not understand the Byzantine Generals Problem. When analyzing HyperLedger Fabric's PBFT and Ant's DBFT later, the Byzantine Generals Problem and traditional distributed consensus algorithms (PAXOS, RAFT) will be fully explained.

The core of the consensus mechanism is the construction and verification of blocks. The process of building blocks in the POW system is generally called "mining", the block construction method of the POS system PPC is generally called "mint", and the block construction method of NXT is generally called "forging".

POW

The consensus mechanism was generally called proof in the past, because Bitcoin uses proof of work (PoW). With the continuous exploration of the consistency problem of distributed ledgers, many methods have been proposed. In particular, many blockchain projects have recently returned to the improvement of the traditional BFT algorithm, and have jumped out of the semantics of "proof" in terms of thinking, so it is further summarized as a consensus mechanism. I remember that when I first encountered the concept of proof of work, I felt very confused and had a headache with this way of expression. After mastering the PoW mechanism, I really understood that it is "to obtain specified results through work, and use the results to prove the efforts that have been made." In fact, we often use proof of work in our daily work and life, such as student test scores, graduation certificates, and driver's licenses. A significant feature of this proof method is that it often requires a lot of work to get the specified results, but this result is easy to verify. Because it is generally difficult for us to monitor in real time whether a person has really paid these workloads, we can only use the results of the workload to prove it.

Back to the design idea of ​​Bitcoin, Satoshi Nakamoto has used asymmetric encryption to solve the ownership problem of electronic currency, used block timestamps to solve the existence problem of transactions, and used distributed ledgers to solve the verification problem of transactions after eliminating the third-party structure. The remaining problem that needs to be solved is double payment, which requires all node ledgers to be unified, and true equality must give everyone the right to keep accounts. Bookkeeping is a simple thing that everyone can do. Obviously, there will be many similar ledgers in the end, but we only need one of them.

Satoshi Nakamoto thought of adding costs to bookkeeping. The general ledger is sorted by pages in chronological order, and a criterion is set for each ledger page to distinguish whether the ledger page is qualified. This increases the difficulty of bookkeeping. At the same time, a random element is added to each ledger page to adjust the difficulty of bookkeeping to ensure that only one person generates a qualified ledger page within a certain period of time. The added cost is the workload, and a qualified ledger page is the proof of workload. For Bitcoin, the so-called ledger page is a block. Blocks are cleverly designed to form a blockchain. A qualified block can be expressed as:

F(Nonce) < Target

Nonce is a random element, Target is the quantification of qualified blocks, and the Target of each accounting node is consistent. In addition, the successful operation of POW also requires the following two agreements:
Best chain principle: The longest chain is considered the correct chain.

Incentive principle: There are rewards for finding qualified blocks.

Article 1 is a hard rule that must be followed unconditionally. If you want to play, you either don’t play or you must follow this principle. After all, the common goal is to find a consistent ledger, and the longest chain represents the greatest workload. Without this agreement, everyone will only construct their own blockchain and cannot unify. Article 2 is a workload incentive. Since bookkeeping has costs, only benefits can drive everyone to keep accounts. Participating in bookkeeping and constructing blocks becomes an investment behavior. Its cost and benefit risks form a game under the constraints of Article 1, driving all nodes to honestly build blocks according to the agreed rules and eventually reach a Nash equilibrium.

In terms of specific implementation, Bitcoin uses a hash algorithm. The principles and characteristics of the hash algorithm have been discussed in detail in the previous article (Evolution of Mining). Logically, Bitcoin performs a hash operation on the entire block, but the actual implementation does not use the entire block data as a parameter of the hash function. The block can be roughly divided into two parts: the blockchain header and the transaction list. The transaction list is constructed into a Merkle tree and finally condensed into a Merkleroot built into the block header. The block header has only 6 fields, a total of 80 bytes. The first benefit of this design is that it facilitates hash operations. Each operation only requires 80 bytes of parameter input, rather than the data of the entire block, but any changes in the transaction list can be reflected in the hash operation results.

Bitcoin uses SHA256 hash operation, and each time two SHA256 operations are performed consecutively to obtain the final result. The result of the previous operation is used as the input of the next operation, that is, Double SHA256, generally referred to as SHA256D. Expanding the above formula, the basis for judging the qualified Bitcoin blocks is as follows:

SHA256D(nVersion,hashPreBlock,hashMerkleRoot,nTimes,nBits,Nonce)<MAXTARGET/Diff

The 6 parameters on the left side of the formula (block header) have been explained in the previous article. MAXTARGET is the maximum target value, a constant; Diff represents the difficulty, which is the same across the entire network. MAXTARGET/Diff is what is commonly referred to as the current target value.

Obviously, the core of POW is: the greater the computing power, the greater the probability of mining a block, and the greater the weight of maintaining the security of the blockchain. Compared with other consensus mechanisms, POW has simple logic, is easy to implement, has a fault tolerance of 50%, and its security has strict mathematical proof.

POS

POW is not perfect. There are two main points that it is criticized for. One is the waste of energy. The other is that the risk and benefit game will inevitably lead to joint mining, and large computing power mining pools may pose a threat to the decentralization of the system.

So in 2011, a digital currency enthusiast named Quantum Mechanic proposed the Proof-of-Stake (POS) mechanism on the Bitcointalk forum. After sufficient discussion, the mechanism was proven to be feasible. If POW is mainly based on computing power, the greater the computing power, the greater the probability of mining a block, POS is based on balance. In layman's terms, the more coins you have, the greater the probability of mining a block. POS qualified blocks can be expressed as:

F(Timestamp) < Target * Balance

Compared with POW, the search space on the left side of the formula changes from Nonce to Timestamp. The value range of Nonce is infinite, while Timestamp is extremely limited. The block time of a qualified block must be within the specified range of the previous block time. Blocks that are too early or too advanced will not be accepted by other nodes. The target value on the right side of the formula introduces a multiplication factor balance. It can be seen that the larger the balance, the larger the overall target value (Target * Balance), and the easier it is to find a block. Because Timestamp is limited, the success rate of POS block casting is mainly related to Balance.

POS only represents a consensus mechanism concept, which can be implemented in many ways. The following focuses on analyzing two more classic implementation ideas.

Peercoin

Peercoin (PPC) was released in August 2012. Its biggest innovation is that its mining method is a mixture of POW proof of work and POS proof of equity. POW is mainly used to issue currency. In the future, it is expected that as the difficulty of mining increases and the output decreases, the system security will be mainly maintained by POS. Currently, there are two types of blocks in the blockchain, POW blocks and POS blocks. The author of PPC is Sunny King, a cryptocurrency geek who is also unwilling to disclose his identity. He is also the inventor of Primecoin.

To master the POS mechanism of Peercoin, you need to focus on understanding several core concepts designed by Sunny King specifically for PPC: Coinstake, Kernel, Stake Modifier, Modifier Interval, Stake Reward, Coinage, etc.

Coinstake

In order to implement POS, Sunny King designed a special transaction called Coinstake, which was designed based on Satoshi Nakamoto's Coinbase design. In essence, Coinbase and Coinsake are both transactions, but with some hard restrictions on their input and output.

The design of Coinstake needs to be different from Coinbase so as not to disrupt the original POW mechanism of the system. Let’s briefly compare the differences in their structures.

Coinbase structure requirements:

The input quantity must be equal to 1, and the input's prevout field (specifying the output of the previous transaction) must be empty.
The number of outputs must be greater than or equal to 1.

Coinstake structure requirements:

The number of inputs is greater than or equal to 1, and the prevout field of the first input cannot be empty, which means that the Kernel must exist.
The number of outputs must be greater than or equal to 2, and the first output must be set to a null value.

There are also special requirements for the location of these two special transactions in the blockchain. Satoshi Nakamoto stipulated that the first transaction of each block must be placed in Coinbase, otherwise, Coinbase cannot appear in other locations of the block. Sunny King obviously did not want to break this rule, so he added a rule that for POS blocks, the second transaction must be placed in Coinstake, otherwise, Coinstake cannot appear in other places. In other words, as long as the second transaction is Coinstake, then this block will be treated as a POS block.

Neither Coinbase nor Coinstake will be broadcasted separately, but only exist in the block, so client nodes are generally not allowed to enter the memory pool. When spending these two transactions, they need to check whether they are mature.

Kernel Protocol

The first input (Input 0) of coinstake is called Kernel. Kernel does play a core role in the POS mechanism, and the determination of qualified blocks is closely related to it. The PPC qualified block determination conditions are:

SHA256D(nStakeModifier + txPrev.block.nTime + txPrev.offset + txPrev.nTime + txPrev.vout.n + nTime)< bnTarget * nCoinDayWeight

Each parameter on the left side of the formula has a clear design purpose, among which,

nStakeModifier : A regulator designed specifically for POS. According to the above formula, if there is no parameter nStakeModifier, when a person receives a coin and gets the network confirmation, he can immediately calculate in advance when he can forge a block in the future. This is obviously not in line with the design goal. Sunny King hopes that POS miners will do blind exploration like POW miners to maintain the blockchain online in real time. The design of nStakeModifier is to prevent POS miners from calculating in advance. nStakeModifier can be understood as an attribute of the POS block. Each block corresponds to an nStakeModifier value, but nStakeModifier does not change for every block. However, the protocol stipulates that it must be recalculated every certain period of time (Modifier Interval). The value is related to the previous nStakeModifier and the latest block hash value. Therefore, POS miners cannot calculate in advance because they do not know the future block hash value.

That is to say, in the PPC system, in addition to the blockchain and the coin chain (the transaction signature history of the coin), there is also a rarely mentioned chain hidden - the equity regulator chain.

It is worth mentioning that Sunny King added this regulator in the later versions of PPC. At the beginning, he used nBits.

txPrev : The previous transaction corresponding to Kernel.

txPrev.block.nTime : The timestamp of the block where txPrev is located. The time when a transaction is included in the block cannot be determined by the transaction initiator. The node may estimate the timestamp in the future that is beneficial to itself through advance calculation. This parameter is to prevent the node from using this estimation advantage to generate a large number of transactions in advance.

txPrev.offset : The offset of txPrev in the block, used to reduce the probability of network nodes generating coinstake at the same time.

txPrev.nTime : txPrev construction time, design target is the same as txPrev.offset.

txPrev.vout.n : Kernel output index in txPrev, design target is like txPrev.offset.

Looking at the right side of the equation,
bnTarget : The current target difficulty benchmark value of the entire network, similar to the current difficulty value in POW, recorded by nbits.
nCoinDayWeight : Kernel's coin age.

From the above formula, we can see that Sunny King hopes to provide sufficient randomness to POS miners on the one hand, and on the other hand, the search space is strictly limited to the timestamp field of Coinstake to ensure that the biggest factor affecting finding a qualified blockchain is the coin age of the Kernel.

When a node forges a block, it first selects one from all its UTXOs as the Kernel, constructs the coinstake, and calculates the hash. If it is unqualified, the coinstake is reconstructed. The timestamp Time will change during reconstruction, and the Kernel can also be changed to obtain a different Coinstake, and this cycle repeats until a qualified block is found.

Coinage

The coin age, also called coin days, is mentioned above. If 1.5 coins exist in the blockchain for 10 days, the coin age value is:

Coinage = 1.5*10 = 15

PPC uses coin age instead of directly using balance to calculate. Once a UTXO is spent, its coin age is reset to zero, and the new UTXO coin age starts from 0.

stakeReward

Equity incentives, commonly known as interest, are calculated as follows:

stakeReward = nCoinAge * 33 / (365 * 33 + 8) * 0.01 * COIN

The formula can be simplified to:

stakeReward = (0.01 * nCoinAge / 365) * COIN

Among them, nCoinAge is the sum of the ages of all coins input by Coinstake. From the formula, we can know that the income is calculated at an annual rate of 1%. Ideally, assuming that all coins are mined throughout the year, the total amount of tokens has an annual inflation rate of 1%. This design has been criticized by many people. Moreover, this design cannot motivate miners to actively participate in mining to maintain the security of the blockchain, because if the handling fee is not considered, the coin holder opens the node to mint coins every few months, or mints coins online in real time, and the theoretical income is the same.

stakeMinAge

The POS system also has the risk of 51% coin age attack. In order to increase the difficulty of attack, Sunny King has set a minimum age (stakeMinAge) limit for the minting qualification of each UTXO: if a UTXO exists in the blockchain for less than stakeMinAge, it will not be eligible for minting. The minimum coin age of PPC is 8 hours.

Later, some competing currencies added a maximum age (stakeMaxAge) restriction: if a UTXO exists in the blockchain for a time greater than stakeMaxAge, the coin age will always be calculated according to stakeMaxAge.

In the POS mechanism designed by Sunny King, a UTXO is like a miner. After each successful minting of a block, the miner must rest for a while. Therefore, the entire system must ensure that enough "miners" are minting blocks online at the same time to achieve a smooth block output speed.

Nextcoin

In September 2013, a user named BCNext posted a thread on the Bitcointalk forum, announcing the issuance of a new pure POS currency, which was later named Nextcoin, or NXT for short. Unlike other altcoins that directly forked from the Bitcoin source code at the time, BCNext started from scratch, using JAVA to develop NXT from scratch, and made many improvements to the block structure, transaction structure, asymmetric cryptography, etc. NXT has many innovations, and here we will only discuss the most important innovation - Transparent Forging.

NXT's POS implementation is completely different from PPC. The qualified block determination method is:

hit < baseTarget * effectiveBalance * elapseTime

in,
hit :
NXT abandoned Satoshi Nakamoto's UTXO design and adopted the account balance solution. Each account corresponds to a private key. Each block has a generation signature field, and the generation of hits is related to this field. When a user needs to forge a block, he first calculates his unique hit. The calculation process is as follows:

The user signs the generationSignature of the previous block with his own private key to obtain the generationSignature of his own block.
Perform SHA256 operation on the result of the previous step to obtain hashdata.
Take the first 8 bytes (64 bits in total) of hashdata as the hit variable.

The design of generating signatures is somewhat similar to PPC’s stakeModifier, that is, there is a signature chain hidden under the NXT blockchain.

On the right side of the formula,
baseTarget : The baseline difficulty of the entire network. This difficulty is adjusted according to the target of one block per minute.
effectiveBalance : The effective balance of an account. A transfer of coins to an account requires sufficient confirmation to have the right to mint coins, which is called the effective balance.
elapseTime : The time interval between the current time and the last block, calculated as currentTime-lastBlockTime.

Analyzing the above formula, if we still regard the left side of the formula as mining and the right side as the target value, we can see that users have no search space at all, because when the entire network generates a new block, each user's own hit for forging the next block is fixed. On the right side of the formula, each user's target value is proportional to the effective balance of his account, and as time goes by, the target value continues to increase, and the inequality will eventually hold true, that is, in theory, each node can mine that block, but the regulations give priority to the earliest generated block.

Using the above picture to analogize the forging mechanism of NXT, the height (hit) of each cylinder is fixed. Assuming that the height limit rod continues to rise (the target value target continues to increase over time), all cylinders can pass through in the end (qualified blocks), but the cylinder with the shortest height can pass first.

The process of node segment block creation is as follows: the account must be online in real time. When the latest block is generated in the whole network, each account immediately calculates its corresponding hit, and then calculates the expected time value of forging its own block according to the formula elapseTime = hit/(baseTaret * effectiveBalance), and broadcasts this expected time to other nodes in the network. In this way, each node in the whole network knows the expected time of other nodes, and thus knows who will forge the next block first. The account forges the block in its own time window and broadcasts it to the whole network immediately. Other nodes check whether a new block is valid. First, they must check whether the generation signature of the block is valid, and also check whether the timestamp of the new block is consistent with the expected time previously published by the node that generated the block. Every time the client detects that a new block is generated in the network, it will recalculate its expected time and publish it to the whole network.

Because the hit is the result of the user signing with his own private key, it is highly random for different users. Even users with small balances may be able to forge blocks quickly if they are lucky enough and have a small hit value.

The generation of NXT blocks completely abandons the concept of competition, which is a bit like "God has already arranged everything". Who will generate the next block has already been determined, and all the nodes in the entire network can do is to wait quietly for that moment to come.

As shown in the figure, what if node A does not broadcast a block within its own forging time window? No problem, the network will wait for B's block. However, if A and B are not far apart, or some nodes receive A's block first and some nodes receive B's block first due to network transmission reasons, the network will be forked. At this time, the principle of Bestchain is still to give priority to the longest chain, branches with the same length, and the branch with the smallest highest block timestamp. What if the node forges and broadcasts blocks for all branches? That becomes an attack, and the forks near the latest block of the network will be exacerbated. The way to alleviate the problem is to let the node only mine the optimal branch, which cannot be reflected in the protocol and can only rely on the self-discipline of honest nodes.

Abandoning the concept of competition, NXT consensus has to be highly dependent on the timeline. Although nodes can predict when they can generate blocks in the future, they must wait until that time to broadcast blocks. If the node broadcasts in advance, other nodes in the network will not accept it. BCNext has made restrictions on client implementation: for the latest block, the client only accepts blocks broadcast within 15 seconds before and after the current time of the local machine. This restriction cannot be reflected in the protocol and can only be implemented with the real-time assistance of the client.

No wonder, all NXT tokens are pre-mined. If the miners slowly issue them like Bitcoin, there will inevitably be competition to create blocks, and once there is competition, the blockchain will immediately fall into a fork. The successful operation of the entire set of NXT consensus rules actually has a potential interest game behind it, that is, the coin holders are the users and beneficiaries of the system, and everyone should unite to jointly maintain the blockchain and be an honest node.

Maybe you will think of an attack method: even if you hold a small amount of coins, you can generate a large number of accounts and transfer a small amount of coins to each account, so that you can find a small hit each time and quickly forge blocks. In this way, POS will degenerate into an embarrassing situation similar to POW. BCNext first starts with the asymmetric signature algorithm, using ED25519 to replace Bitcoin's ECDSA. The former is more difficult to calculate than the latter. In addition, the maturity period is increased to 1440 blocks (1 day), that is, once an account's valid balance successfully forges a block, the balance needs to wait for 1 day to regain the forging qualification.

Short-term forks are still inevitable. There will be many branches near the latest NXT block. A transaction needs more confirmations to be safe enough. NXT officially recommends 10 confirmations.

POS2.0

The successful operation of PPC soon attracted a group of followers, among which the more famous ones include Novacoin (NVC) and blackcoin (BLK). The blackcoin community believes that the coin age may be abused by malicious nodes to obtain higher network weight and successfully implement double-spending attacks, so it released the POS2.0 white paper, made several details of PPC, and solved some potential security issues. The most important improvement is to replace the coin age with the balance. The conditions for qualified blocks are:

F(Timastamp) < Target * Number of coins * Age of coin

becomes:

F(Timastamp) < Target * Coins

In this way, no matter how long a UTXO is left, its ability to forge blocks remains unchanged. This can incentivize nodes to stay online more often to mint coins, improve system security, reduce attack paths to a minimum, and significantly increase the number of nodes that keep the network running.

POS3.0

The Blackcoin community later upgraded further and launched the POS3.0 version, which made some optimizations to transaction fees and difficulty adjustments. The most significant change was the change of the 1% annual interest rate reward mechanism to a fixed amount reward (1.5 BLK is fixed for each block). This not only reduced the token inflation rate (considering that tokens may be permanently lost, the low reward mechanism returns to the design idea of ​​a constant total amount), but also meant that the coin holding nodes must be online in real time to obtain income.

DPOS

The Bitshares project was launched in August 2013. It was an ambitious project that made many changes to the blockchain and introduced many new concepts and features, especially the dazzling new terms such as Bitshares X, polymorphic digital asset trading platform, and asset anchoring, which made people extremely excited and confused. At this time, both POW and POS had been successfully running for a long time, and their advantages and disadvantages had been repeatedly discussed. The two major camps are still arguing to this day. According to the project plan, Bitshares has extremely high requirements for transaction capacity and block speed. Obviously, neither POW or POS can meet the requirements, so Bitshares invented a new consensus mechanism - Delegated Proof-Of-Stake (DPOS), that is, share authorization equity proof.

DPOS is easy to understand. It is similar to the modern corporate board system. The BitShares system calls token holders shareholders, and shareholders vote to elect 101 representatives, who are then responsible for generating blocks. The core issues that need to be addressed are: how representatives are elected, how representatives can freely withdraw from the "board of directors", how representatives collaborate to generate blocks, etc.

If a coin holder wants to become a representative, he must first register with his public key on the blockchain and obtain a unique identity identifier with a length of 32 bits. Users can vote on this identifier in the form of transactions, and the top 101 votes will be selected as representatives.
The representatives take turns to produce blocks, and the revenue (transaction fees) is equally shared. If a representative does not produce blocks honestly, it will be easily discovered by other representatives and shareholders, and he will be immediately kicked out of the "board of directors", and the vacant position will be automatically filled by the representative ranked 102nd in the number of votes.

From a certain perspective, DPOS can be understood as a multi-center system that combines decentralization and

Summarize

Finally, let’s briefly compare and analyze the advantages, disadvantages and characteristics of the above consensus mechanisms from several aspects:

Security

There is a complete mathematical proof of the security of POW, which is an incomparable advantage of POS and DPOS. The blockchain consensus mechanism generally considers both DDOS attack and double payment attack. POW is threatened by 51% computing power attack. Bitcoin's current super computing power makes it costly to destroy the system. POS will also have 51% coin age attack, and the security of DPOS depends entirely on the honesty of the representative. NXT theory can achieve fast transactions, but it requires the forging node to expose its IP, which makes it easy to become a target of DDOS attack, and the representative of DPOS is also easy to become a target of DDOS attack.

Environmental protection

In the impossible triangle theory (decentralization, security, and environmental protection cannot be achieved at the same time), POW completely abandons the need to save energy and maintains system security and decentralized characteristics through huge computing power. POS and DPOS consume almost no extra electricity, but inevitably make sacrifices in the other two characteristics.

Consensus speed

It is difficult for POW to shorten the block time, while POS can shorten the block time relatively, especially NXT, which is faster than PPC. DPOS can also reach consensus in a very short time. BitShares currently generates a block every 30 seconds. However, POS is more likely to generate forks, especially NXT, so transactions need to wait for more confirmations before they are considered safe.

Transaction Capacity

This is the core problem that needs to be solved for the future development of blockchain. Huge transactions easily mean huge bandwidth and storage space. The transaction capacity of POW is difficult to expand. However, since each node of NXT can predict who will forge the next block, it can directly send transactions to the forging node, so the transaction capacity of NXT has great scalability. From a certain perspective, DPOS can be understood as a multi-center system, which has the advantages of both decentralization and centralization. If the representative nodes all run powerful servers and the bandwidth between them is large enough, the transaction processing capacity can theoretically be comparable to that of traditional centralized systems, such as Visa.

Block smoothness

Due to the characteristics of the hash algorithm, POW can achieve a smooth block speed and can adjust the difficulty of the entire network after a period of time. The block generation of POS is mainly related to the balance, and the gradient of the user balance difference is relatively large, so POS generally adjusts the basic difficulty of the entire network for each block. DPOS relies on the synergy of limited representatives. If the representatives do not frequently enter and exit, the block generation interval can almost be fixed.

Finality

POW and PPC reach consensus through competition, and there is no finality. Theoretically, if there is enough computing power, the Bitcoin blockchain can be mined from scratch, but finality can be achieved by relying on detection points. NXT and DPOS strictly rely on the timeline and rely on real-time online detection of nodes, so there is finality.

Combining the advantages of all parties, I personally think that POW is suitable for public chains. If a private chain is built, POS is more appropriate because there is no trust issue with the verification nodes. However, DPOS is more appropriate for alliance chains because of the existence of untrusted local nodes.

The next article will analyze consensus mechanisms such as PBFT, DBFT, and RPCA (Ripple).