Validated Asynchronous Byzantine Agreement in Honey Badger BFT — Introduction and Implementation

Note: This blog assumes that readers are familiar with some terms in cryptography and distributed systems. If some details are not elaborated, feel free to contact me!

Background

Byzantine Agreement (BA) is a common consensus problem to be solved in modern distributed systems. It also serves as an important part to many other mainstream consensus problems, ex: Atomic Broadcast, State Machine Replica, etc.

Although it has been proved in FLP impossibility that any consensus problems cannot be solved with even a single failure in asynchronous networks, efforts have been made to either (1) loosen the network conditions (partially synchronous networks) and (2) using randomness in async setting.

Introduction

Validated Asynchronous Byzantine Agreement (VABA) is a randomized consensus algorithm in asynchrounous setting. It was designed in 2018 by Ittai Abraham, Dahlia Malkhi, and Alexander Spiegelman (see reference), which can solve BA in expected O(1) round and O(n²) messages with less than 1/3 faulty parties.

In this article we will not go through all the proof of the protocol, but instead explaning the general idea and its implementation. After that we will also show that it can be used in Honey Badger BFT to lower the expected number of rounds.

VABA overview

VABA is based on views. In each view we will have 3 stages: broadcast, leader selection, and view-change. We will introduce the three stages one by one.

Stage 1: 4-round provable broadcast by every parties

At the beginning, each parties will start a 4-round broadcast by itself. In each round, the followers will sign the shared signature and send it back. The leader will get the threshold signature and send it in the next round broadcast. After the leader get the 4th threshold signature, the broadcast is regarded done by the leader.

The animation of the broadcast phase. Each parties, when receiving the value with the signature, will do the validation and save the value into key/lock/commit value, respectively. Note that 1) the broadcast will be initiated by all the parties instead of only one party. (this figure only show one case of broadcast for simplicity). So every parties will store a key/lock/commit value for all the other parties. 2) We will not wait for all the parties to finish the broadcast, which will be discussed next

The key, lock and commit value saved in 2, 3, and 4th round is to guarantee the committed value was received by enough parties (2 f + 1 parties) so as to safely enter the next view.

End of Stage1: When 2 f + 1 parties done broadcasting, skip the rest of broadcast

We don’t wait all the parties to finish the broadcast, since there may be byzantine nodes who deliberately delay the message. When certain party finish its broadcast it will send a done message to other parties. When receiving 2 f + 1 done message, one will send skip messages to all the other parites to stop the broadcast. (too see more details, please refer to the paper at the bottom)

The animation of the skipping process. In this case, P1, P3 and P4 finished the broadcast while P2 didn’t. After the skipping message, all the parties skip the broadcast phase and proceed to the leader election phase. Note that even though the animation is shown step by step, the message in the network is totally asynchronous and orderlesss.

Stage 2: Leader Election

After skipping the message, we will use the cryptographic coin-tossing method to randomly pick a party to be the leader of this view. The leader election follows the following rules:

1. (termination and agreement) if f + 1 honest parties evoked leader election, all the honest party will decide on the same leader
2. (randomness) the probability of a party to be selected is 1/n where n is the total number of parties.

Stage 3: View Change

All the parties will send out a view-change message to other parties, telling others whether it holds the key/lock/commit value stored for the leader. If someone holds the commit value, all the parties will decide on this commited value; if not, they will wait for 2 f + 1 view-change message and proceed to the next view with the stored key value.

In this case, P2 is selected its broadcast is not fully finished. Even so, P4 has received the commited value from P2 in the 4th round of broadcast, so everyone is safe to decide when receiving the view-change message from P4.

Question: Why will it finish in expected O(1) round?

1. Before the leader election, at least 2 f + 1 parties has finished the broadcast.
2. If the finished party is selected, at least f + 1 honest parties will hold the commited value and include it in the view-change message. Thus causing all the parties decide in this view ( Note that all the parties will wait for 2 f + 1 view-change messages)

Contribution to Honey Badger BFT and its implementation

Honey Badger BFT is an randomized asynchronous Byzantine Fault Tolerance protocol which can solve the state machine replica (also Blockchain) without any network assumption. It is an alternative proposed by Andrew Miller in 2016. Please can refer to the link here to see more details.

The time bottleneck of Honey Badger BFT is caused by multiple 1-bit Byzantine Agreement (BA), which is run in parallel with the Reliable Broadcast Protocol (RBC).

1. When RBC is finished by a certain party, it will input 1 into BA;
2. When BA finished with at least 2 f + 1 decided 1, put an input 0 to the rest of BA
3. Take the input from RBC where the BA decided 1

The 1-bit BA can be substituted by the ABA in following way:

1. All the parites will store an n-bit input value and initially they are all 0s
2. When RBC is finished by a certain party, flip 0 to 1;
3. When there are 2 f + 1 1s in the store input value, input it into VABA
4. Take the input from RBC where the VABA decided 1 in certain bits (for example if the decided value is 1011, then pick the input from RBC in P1, P3 and P4)

Since VABA will finished in expected O(1) Round, it will reduce running time of the whole protocol to expected O(1) time for each epoch.

Following the Honey Badger BFT python codebase, I implemented the VABA using the same cryptographic package. The codebase will be available soon in the future.

Reference

Abraham, Ittai, Dahlia Malkhi, and Alexander Spiegelman. “Validated asynchronous byzantine agreement with optimal resilience and asymptotically optimal time and word communication.” arXiv preprint arXiv:1811.01332 (2018).