What is the stunner of the HotStuff algorithm used by Facebook Libra?

Chain Wen interviewed Yin Maofeng, the first author of the paper.

The Libra white paper recently published by Facebook has attracted continuous attention from all walks of life, and the technical documents published on its website have also been reviewed by many experts. The document mentions that the Libra blockchain will use the "LibraBFT" consensus algorithm based on the Byzantine fault-tolerant consensus, while LibraBFT is a variant of "HotStuff".

Technical paper on the LibraBFT consensus protocol used in the Libra blockchain

• Media: Encrypted currencies reshape the global financial order?
• Three serious naive myths of Facebook coins
• Dialogue with Meng Yan: Facebook sets off a wave of digital currencies

What kind of "stunner" is this algorithm called HotStuff?

In the past, we found that the HotStuff algorithm paper was published by the cloud computing company VMWare's research team, and its security and usability have been fully mathematically proven. There are 5 authors, Maofan Yin, Dahlia Malkhi, Michael K. Reite, Guy Golan Gueta, Ittai Abraham.

HotStuff algorithm paper

Https://arxiv.org/pdf/1803.05069.pdf

In fact , Ted Yin , the first author of the "HotStuff" algorithm paper, is an old friend of Chain. Yin Maofan, a 25-year-old graduated from Shanghai Jiaotong University this year, is currently pursuing a Ph.D. degree at Cornell University. His current main direction is basic research in distributed systems. The instructor is the famous computer scientist Emin Gun Sirer. The mentor is Robbert van Renesse.

After Facebook officially released the Libra white paper, Yin Maofan accepted an interview with the chain, he explained the details of HotStuff for us.

Those who enter the field of distributed consensus algorithms for the first time are easily stunned by a lot of nouns. In-depth study, you will find a variety of naming stories behind these nouns. For example, the DLS algorithm is an abbreviation for three authors: Dwork, Lynch, and Stockmeyer. The PBFT algorithm is the " Practical Byzantine Fault Tolerance" , and the BFT is naturally "Byzantine Fault Tolerance" (the BFT will be used uniformly below) . So, how did the name of the newcomer HotStuff come from?

Yin Maofan explained that the reason for the name is HotStuff , because the word has three meanings in English: one is a sexy person, the other is a hot thing, and the other is the name of a little demon in an animation. Everyone knows that Ethereum's next-generation consensus algorithm, Casper, comes from an animated character. So, HotStuff can be compared to it.

In an interview with the chain, Yin Maofan took the opportunity to translate the Chinese word into a stunner. Therefore, the title of this article is not a sensation. Yin Maofan said that the stunner has two meanings, one is a peerless beauty, and the other is a rare treasure. The HotStuff is translated into a stunner.

According to reports, HotStuff has been deployed on a network with more than 100 copies, exceeding the throughput of BFT-SMaRt while maintaining a similar delay, and in the more practical test performance is higher than the latter .

What are the advantages of HotStuff compared to consensus protocols for other distributed systems? The following is a question and answer from the chain reporter and Yin Maofan:

Chain smell: The consensus agreement on distributed systems can be roughly divided into two categories, one is the blockchain algorithm represented by bitcoin (or called the Nakamoto consensus), and the other is the classic BFT algorithm (such as DLS, PBFT). What are the big differences and advantages and disadvantages between the two in terms of application conditions and performance?

Yin Maofan: The difference between the two can be roughly divided into five aspects: 1) member information; 2) performance, including throughput, delay, etc.; 3) anti-witch attack (Sybil attack) – Nakamoto's consensus comes with anti-witch attack The classic BFT requires additional PoS or PoW; 4) scalability; 5) security, ie probability vs. certainty.

The advantage of the Nakamoto consensus is that all participants who do not need to know the consensus in advance do not require accurate member information. Because part of the consensus uses PoW (workload proof) , it is inherently immune to witch attacks. Moreover, the algorithm of Nakamoto's consensus is very simple, and ordinary people can understand it with a little mathematical foundation. The Nakamoto consensus is also easy to expand, with less performance loss at 10 nodes and 1000 nodes (on the one hand because there is no need for broadcast voting, and on the other hand because it is inherently slow, see explanation below). )

The shortcomings of the Nakamoto consensus are also obvious. Because the difficulty of the PoW and the length of the waiting chain are related to security, the performance is fundamentally poor, and the transaction confirmation delay cannot be changed. All existing "magic reforms" based on the Nakamoto consensus (the expansion of the soup without changing the drug) agreement can only increase the throughput. It is of little significance to talk about the throughput after a delay. For example, I can drive a truck and transport a hard drive to transport data. Although it is ultra-high throughput, it is also extremely high latency.

In terms of security, compared with the traditional BFT consensus, the Nakamoto consensus only provides a probabilistic security guarantee, while the BFT is 100% secure. The security mentioned here, or consistency, is whether you can avoid double flowers. In fact, the probability that a bitcoin can produce double bars in six blocks is not as low as everyone thinks, and there is a consensus failure of up to 13% probability (ie, 30% of nodes in BFT). From this point of view, if you want to compare fairly, the efficiency of the Nakamoto consensus is very low. (The six blocks have taken an hour. )

Looking at the classic BFT consensus, the premise or shortcoming is that you need to know all the participants and ask for 100% accurate member information. In addition, the classic BFT consensus is relatively difficult to expand. Before HotStuff, most classic BFTs required all node broadcasts, which brought square-level complexity (including the algorithms described in the Tendermint paper) . Adding a large number of nodes can cause network congestion. Moreover, the Leader node can withstand the load of the entire network (the load is extremely uneven) , making it difficult to expand to thousands of nodes without much performance loss.

The advantage of the BFT consensus is that because the consensus does not use meaningless PoWs, the speed of the classic BFT consensus protocol is related to the speed at which the network sends a large number of short messages, without the additional energy consumption and waiting time of the Nakamoto consensus. Trading delays are very small. If network latency is not considered, transactions are on the order of tens to hundreds of milliseconds. If network latency is considered, it is the same order of magnitude as network latency.

Chain smell: Your paper concludes that HotStuff is based on a new framework that builds a bridge between the classic BFT foundation and the blockchain. How to understand this sentence?

Yin Maofan: Our paper is called “Symptom Agreement: Seeing the BFT Consensus in the Lens of Blockchain” .

The reason for this is that its algorithmic framework (which can spawn multiple derived algorithms) uses a tree/chain structure, much like a blockchain. In addition, similar to the traditional blockchain, a node currently has a chain that is considered to be the "main chain", and voting will only vote for new parts that are currently considered to be expanded on the main chain. Like a blockchain, if the sidechain is "good" enough, it becomes the new backbone. In the blockchain, this is determined by the length of the chain (elderly wins) , while in HotStuff it is determined by the block that most recently succeeded in getting the majority of the votes.

On the other hand, HotStuff is a member of the traditional BFT system. This algorithm framework can well explain PBFT, DLS, Tendermint, Casper and other protocols, reaching a certain degree of induction and unification. In addition, the biggest difference between the same type of algorithm and the biggest contribution is that there is no special case for HotStuff's core transition algorithm; unlike PBFT, which has a "normal" execution process and a "special" change process, HotStuff unifies both. That is, there is no explicit special treatment, and it can be considered as a potential change. This makes it easy to write the basic security part of a HotStuff-based consensus system. Compared to PBFT's thousands of lines of code, HotStuff only needs tens or hundreds of lines.

Another feature that is superior to the same type of algorithm is that it is very friendly to engineers. It clarifies the logic of correctness and guaranteed performance from an algorithmic level. Once the dozens of lines of security guarantees are completed, the rest of the optimization based on the specific application scenario (including the change mechanism, policy) will not touch this part again, making the system always safe.

Chain smell: The PBFT algorithm can run in an asynchronous environment such as the Internet, and some optimizations make it faster than previous consensus algorithms. But it also has some problems, such as detecting bad primary nodes and re-selecting new master nodes (view change) is very inefficient. For example, to reach consensus, PBFT requires a square-level message exchange, which means that each computer must communicate with all other computers on the network. In short, the expansion of PBFT is clearly not enough. What solutions does HotStuff have for these problems?

Yin Maofan: First of all, HotStuff reduced the cost of the transition from square to linear for the first time, which means it has the same complexity as Paxos/Raft, a non-BFT protocol widely used in the IT industry. In addition, although in theory the protocol such as Tendermint can be reduced to the same complexity by combining digital signatures, these protocols essentially need to wait for the largest possible network delay between blocks, so that the actual implemented system becomes a synchronization. system. The HotStuff idea jumped out of the original framework and proposed a minimalist algorithmic system that makes it easy to break the magic of this traditional BFT. After testing, it can defeat the existing fastest traditional BFT implementation with simple code implementation and low theoretical complexity, and has unlimited potential in commercial systems.

Chain News: Facebook's Libra white paper suggests that the Libra blockchain starts with a “licensed blockchain” and the future goal is to become an unlicensed network. From licensing to non-licensing, is there a viable technology path? The difficulty lies in capacity expansion (from 100 nodes to thousands of nodes) or is it possible to resist witch attacks?

Yin Maofan: In theory, any license agreement can be converted into a non-licensed agreement. Because traditional consensus protocols (whether BFT or non-BFT) can be reconfigured through the consensus itself to add/delete nodes. However, because of the potential witch attack, this protocol based on accurate member information requires additional access to a PoS or PoW entry mechanism to open the system.

Author: Chain smell ChainNews

Source: Chain News ChainNews (WeChat public number)

Editor's Note: This article has been abridged without changing the author's original intent.

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