Brief introduction of LibraBFT algorithm

Since I am determined to expand my popularity, I have to occasionally pick up hot spots. Just before I have already told many people about Hotstuff, I also introduced BFT in the previous column, so I can just talk about LibraBFT.

First of all, people who are not familiar with BFT can check out my previous three articles: https://zhuanlan.zhihu.com/p/41329283 https://zhuanlan.zhihu.com/p/45238823 https://zhuanlan.zhihu .com/p/52251671

Then, in fact, I saw Hotstuff after I finished the third post. I was very hesitant to add this algorithm to the development trend of the consensus algorithm. Later I gave up, because I think the new algorithm is endless. Of course, I am a bit regretful about this decision now – or else I can take it out now. Another point, but also unfortunately, the use of BLS to reduce the BFT message complexity is exactly what I expanded to the next article. But the content is here I am going to briefly describe, and then the details can continue to focus on my column.

Hotstuff BFT

Hotstuff this paper I remember was sent to arxiv at the beginning of the year. It was a Chinese doctor of Cornell, and the paper was officially published on this year's PODC. However, before it was officially released, it was already used by LibraBFT.

• Analysis: Libra's imagination and realistic resistance from the core mechanism
• Research Report | 2019 Global Digital Currency Trends and Latest Regulatory Policies
• Raised $60 million in 4 hours, valuation approaching Ethereum, Algorand into the rookie

We don't specifically mention the details of Hotstuff, but rather some of Hotstuff's ideas and contributions. Of course, I think that for many blockchain practitioners, the specific details may not be interesting. At the same time, when you look at the paper directly, it is actually not as clear as this idea.

1, BFT in the big network

This is not really a contribution from Hotstuff, but it is actually what I said in the first article of the BFT. It is a new scene and challenge brought by the blockchain to the BFT algorithm. The first of these challenges is to reduce the message complexity of O(n^2) to O(n). However, this is not a Hotstuff innovation, because basically all current BFTs have O(n) message complexity.

Hotstuff's approach to achieving O(n) message complexity is actually a more classic approach, which is to use aggregated signatures, and then assume that the leader is honest to let the leader collect signatures. The method of using aggregated signatures is actually from Byzcoin. In fact, many consensus algorithms are not limited to BFT algorithms, such as Dfinity, and they are also used. This method will be written in detail in the later section of the expansion, and will not be described here.

2, the combination of BFT and chain

The traditional BFT consensus approach is two rounds of consensus, with the first round of preparation and the second round of commit. Many projects that use BFT for blockchain still adopt the mode of “doing two rounds of communication first, then reaching consensus, and finally getting on the chain”, while Hotstuff adopts “first-up chain, adding aggregated signatures to the block, so, After n blocks, it can be considered as a consensus through n rounds of communication." Therefore, in fact, there is no need to distinguish between the so-called prepare, commit two rounds of communication, just simply define the behavior of each round of nodes as "leader responsible for the block and collect signatures", then "other nodes are responsible Sign the block out of the leader", then, as long as 2f+1 signatures are collected, the leader can produce a block, and then there are n blocks that are equivalent to reaching a consensus. The advantage of this is that O(n) communication complexity allows the honest node to know "I know that message m will become a consensus", but O(n^2) communication is required to make every honest node convinced "I I also know that all honest nodes also know that the message m is a consensus, and that the leader collects the signature and pops out this way. When everyone sees the block b, the honest node will know "I know b is the consensus", but When you see a b' after b, the honest node is equal to knowing that "all signatures know that b is a consensus." So, every time you go out of the block, you only need O(n) message complexity, but with the help of an honest leader and aggregated signature, we have reached the previous O through two rounds of O(n) message complexity. (n^2) effect.

And, this thing and the first round of b's consensus are in sync. In other words, after the process of each round of BFT is also chained, the communication complexity is reduced by half. This point, although there have been similar ideas before, but I personally think that Hotstuff is the first to put this idea exactly in the algorithm, which I think is very interesting, and at the same time, is also a direction in the future.

In fact, this method is gradually moving from two directions – the first is from the direction of BFT, everyone gradually realizes that the chain structure can save a lot of things in BFT, for example, we do not need sequencing, and for the latter Block consensus is actually equivalent to a consensus on the previous block, and many BFT algorithms, such as avalanche (another part of the Hotstuff author), have begun to notice this; and from the blockchain consensus algorithm, especially In the pursuit of finality, people find that the fact that a block is followed by 2f+1 nodes is equivalent to reaching BFT, and if multiple people sign these blocks, this process can be accelerated, like this. It is also reflected in algorithms such as Polkadots. Hotstuff can be said that these two ideas have reached the most concise integration at this stage.

3, BFT's rapid response

The most complicated problem in the actual application of the large network BFT algorithm is actually the view change (a mechanism that proposes to change the leader when the leader does not respond). I have heard more than one person using the PBFT algorithm. This is because in fact PBFT and all traditional BFT are actually based on the traditional Byzantine generals (see my previous article), that is, we will first assume that the leader is honest, and then lead him to reach consensus. Therefore, view change is a last resort. All honest nodes need to be time out first, then reach a consensus on the view change. Then, they will tell the new leader, the new consensus, and the new consensus. The leader also broadcasts the message to announce the view change, so the cost of the view change is O(n^3) (O(n^2) is used after the aggregate signature).

There are two problems in this: one is the message complexity of the view change, and the other is that the view change must wait until the honest node agrees on the view change.

A very interesting new idea of ​​Hotstuff is to turn the two rounds of traditional BFT consensus into three rounds, and then turn the cost of view change into O(n). This can be understood as follows: the traditional view change is O(n^2) message complexity, that is, all honest nodes will confirm that all honest nodes do go to the next view before the view change, but in Hotstuff. , view change does not need to wait for "I know that other people also know the view change" can do this, so the message complexity is reduced to O (n), that is, as long as the built-in time out of the honest node is up, Then you can send a view change to the new leader to start the view change.

Why do you need to turn two rounds into three rounds? Because of the simplification of the previous BFT+chain structure, strictly speaking, the two communication complexity O(n) blocks and the PBFT O(n^2) message complexity are different from the prepare and commit – when there is When the two blocks are connected, the two sides are equivalent, but in fact, the message complexity of each block is only O(n), which does not mean that all honest nodes know that "all honest nodes will reach a consensus." Similarly, the message complexity of view change is only O(n), so if a view changes when a message has the first block, then the honest node will have an inconsistency as to whether the first block has reached a consensus. Because prepare and view change seem to make sense.

After turning the two rounds into three rounds, we solved this problem. Because we can stipulate that anything after two rounds is a consensus, and if it is not two rounds, it is not counted – for both prepare and view change. So, if the view change happens after the first round, then we don't think the previous prepare is correct, and the view change is the same. Conversely, if a view change occurs after the second round, the message has already been sequenced because it has gone through two rounds, even after the view change.

So overall, the core idea of ​​Hotstuff is as follows:

1. The structure of the aggregate signature is used to change the message complexity of each round to O(n).

2. The consensus of O(n^2) is changed into a block submission of two rounds of O(n) message complexity with a chain structure.

3, in this structure, the message complexity of view change is reduced to O (n), and then in order to prevent inconsistencies caused by view change, the two rounds of block submissions into three rounds.

Overall, although the first two are also interesting, the core advantage is that view change becomes easier, regardless of duration, message complexity, or work pressure for the next leader. Although the cost is that it requires more than one round of communication, such delays, whether for the possible delay of the view change in the century, or for us who are accustomed to the delay of the blockchain consensus algorithm, are not worth mentioning.

LibraBFT

LibraBFT is basically Hotstuff, but with two changes on it.

One of the points is to add a realistic consideration to the use of Hotstuff in the blockchain, such as the introduction of the concept of epoch (generation), allowing consensus node replacement, plus incentives and punishment mechanisms, etc…

Another point is the improvement in synchronization (may not be improved):

Hotstuff is valid in the partial synchrony network (the upper limit of message delay in the network, but this upper limit is unknown), which is already a very strong asynchronous assumption. It is the same as PBFT, but now many blockchain algorithms are already in With synchronization assumptions. The concept of the round in Hotstuff is more like a few steps of PBFT, which means that this round is actually not a time concept, but like PBFT, it is automatically entered after the last step (collecting signatures, publishing blocks). of. In other words, a block may appear very quickly, but it may take a long time to change the view. So, LibraBFT uses the pacemaker mechanism to make every round of time have an upper limit.

The above is an introduction to LibraBFT. In my opinion, Hotstuff is a very interesting and perhaps even the most instructive algorithm for the consensus algorithm for future blockchains. Libra's adoption of this algorithm is also very reasonable, because Hotstuff not only has the high output of most BFTs, but also solves most of the problem of view change of BFT, but in practice it is very influential in the BFT algorithm. Problems used in a blockchain environment.

Of course, for Libra itself, my comments are in this post:

https://bbs.vechainworld.io/topic/197/%E6%88%91%E5%AF%B9%E4%BA%8Efacebook%E7%9A%84%E5%8A%A0%E5%AF%86 %E8%B4%A7%E5%B8%81libra%E7%9A%84%E7%9C%8B%E6%B3%95

Anyway, for Facebook, this is a project that can threaten the financial industry, dominate the blockchain field, and even the mainstream currency wrench; retreat to create a gimmick, hot spot, increase stock price, and finally engage in a Facebook version of Alipay or WeChat payment project Even if it is stopped by the relevant agencies, it can still be the image of the privacy theft before the whitewashing, and it becomes a challenger of power and old-fashioned. For Facebook, it will almost succeed, but it is only a matter of degree. However, in any case, it will have a profound impact on the blockchain domain, not because of what it does, not because of its technology, not because of its possible achievements, but because it is Facebook. Therefore, what I did not mention in the above opinion is that I think that whether it is successful or not, its impact on the entire industry of the blockchain may not be positive – if it has achieved great success, now The route we can see is the failure of the blockchain to challenge the Internet giant, and the blockchain field is once again occupied by predators; if it does not achieve great success and is only a successful gimmick, we will see other Numerous followers of the predators appeared on the platform, and after cutting a circle of leeks, they left the scene, leaving a blockchain industry that no longer has any vitality.

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