Popular Science: Blockchain and Distributed Systems

Editor's Note: This article comes fromDenglian Community, reprinted by Odaily with authorization.

Editor's Note: This article comes from

, reprinted by Odaily with authorization.

consensus algorithm

The popularity of blockchain technology has promoted the further development of traditional distributed technology. From the perspective of the essence of blockchain technology, it is basically inseparable from the core technology of traditional distributed systems and cryptography. So is blockchain technology really worth studying? Did the blockchain choose us, or did we choose the blockchain? This article understands blockchain from the perspective of a distributed system researcher.

People often think of blockchain as a distributed database, or a distributed ledger, which is inaccurate and confusing. Compared with the distributed databases we often see, the blockchain has two main differences: consensus algorithm and chain structure. These two complement each other and together constitute the uniqueness of the blockchain.

secondary title

consensus algorithm

• The consensus algorithms adopted by distributed databases are generally based on a series of algorithms derived from Paxos. The security of these algorithms relies on the assumption of centralization, that is, all nodes are managed by a trusted center. Under this assumption, all nodes are considered "honest", that is, all nodes try their best to deliver the message, and the message will not be tampered with. If a small number of nodes go down or lose connection, it will not affect the security of the protocol.

• However, the consensus algorithm in the blockchain does not assume centralization, and each node can be considered to have independent behavior, which is also the origin of the "decentralization" of the blockchain. The protocol allows some nodes (generally less than 1/3) to be Byzantine nodes. They can choose to follow or violate the protocol according to their own wishes, send arbitrary messages or pretend to be down. A Byzantine node can be a node fully controlled by an attacker, or a node with serious bugs in its own software. This type of algorithm is called a Byzantine fault-tolerant algorithm, or BFT for short. It can be clearly seen that the fault tolerance of the consensus algorithm of the blockchain is much higher than that of the traditional distributed database, so it is often less efficient.

• The research on the BFT consensus algorithm has been started for a long time, and the most influential one is the PBFT (Practical BFT) proposed by Turing Award winner Barbara in 1999 OSDI [1]. However, due to the high complexity of the algorithm, it is difficult to carry out large-scale deployment. In addition, this type of algorithm also requires the identity of each node to be known, that is to say, when the protocol is initialized or when a new node joins, an access control (Access Control) mechanism is required to ensure that nodes can authenticate each other identity. Based on the above reasons, the research on traditional BFT protocols did not make much progress until 2010.

Great resource consumption. Miners participating in the network need to pay huge hardware and electricity costs.

Extremely low performance. The Bitcoin network can process about 7 transactions per second, and the average generation time of each block is about 10 minutes.

transaction uncertainty. Even if a block is confirmed in the Bitcoin network, due to the possible fork of the blockchain, the block still has the risk of being rewritten. Only after waiting for a block to be confirmed several times (for example, 6 times) can the risk of this block being rewritten be reduced enough. This also further increases the latency for transactions to be confirmed.
In order to reduce the above costs, many researchers have made remarkable efforts. For example, in order to improve the performance of the consensus algorithm, researchers from Cornell University proposed Bitcoin-NG [2] at the NDSI in 2016. Researchers from MIT and Stanford proposed Prism [3] at CCS in 2019 to further expand Bitcoin. In addition, in order to reduce resource consumption, researchers from MIT proposed Algorand based on Proof-of-Stake at SOSP in 2017, which removed the consumption of mining.

secondary title

chain structure
Another innovation brought by the blockchain is the chain structure. Each block is linked with the previous block through hash, all the way back to the initial block, forming an endless chain. One advantage of this structure is that when a node confirms a block, it means that all previous blocks on the chain where the block is located are confirmed at the same time. Based on this chain structure, it is easy to adopt a "longest chain" principle in the blockchain to release new blocks. For example, in Bitcoin, due to network problems and malicious attacks, a miner may see multiple chains, but miners always tend to mine on the longest chain.

Even if you find a chain longer than the chain you are in halfway through mining, you have to switch to the longer chain. The "longest chain" principle is not necessarily obligatory, and it will not have a serious impact on protocol security, but when all miners abide by this principle, each miner can expect the maximum benefit. Of course, there are exceptions. When a miner occupies relatively large resources (less than 50%), a "selfish mining" (selfish mining) [4] strategy can be adopted, which violates the "longest chain" principle and seeks higher earnings.

The chain structure of the blockchain has also brought great inspiration to researchers who study traditional BFT, and many BFT protocols tailored for the blockchain have begun to emerge. The most famous of these is the LibraBFT [5] consensus protocol adopted by Facebook. LibraBFT is based on HotStuff [6], proposed by researchers from VMware. HotSutff improves the performance of traditional BFT by adopting the chain structure of blockchain, enabling the protocol to be deployed in a network with hundreds of nodes. Let me briefly explain the magic of this chain structure.

In order to solve this problem, HotStuff introduces a chain structure on the basis of PBFT. Due to the characteristics of the chain structure mentioned above, a node's vote for a block is actually a vote for all previous blocks on the chain where this block is located. Therefore, the chained HotStuff reduces the different voting stages and only retains the unified Propose-Vote form. This is shown in the figure below (source [6]).

Summarize

HotStuff further utilizes the characteristics of the chain structure to specify the voting rule and the block confirmation rule (commit rule), so as to ensure the security of the protocol. The chain structure makes the BFT protocol simple and elegant, and it can perform well the pipelined operation, which improves the performance of the protocol and greatly reduces the state space.