When Facebook announced the Libra Blockchain, I was keen to learn about the consensus protocol that would power their cryptocurrency and distributed infrastructure. Having extensively gone through their released developer documentation, I'd like to present in this post a technical simplification of the LibraBFT consensus algorithm.

Before we can delve into the analysis of LibraBFT algorithm, we need to understand why the choice of a consensus algorithm is a critical decision for protocol developers to make. On any open distributed ledger network a consensus mechanism functions to:

• Prevent double spend and even store transaction data in distributed ledgers.
• Ensure transaction validation by endorsing, ordering and validating transactions.
• Facilitate the decision-making model between network participants (developers, miners, exchanges, users)

Each networks consensus mechanism ensures critical participant agreements on collaboration, co-operation, equal-rights, participation and activity are written in the consensus algorithm of choice.

LibraBFT Algorithm

Similar to all Byzantine Fault Tolerance (BFT) based networks LibraBFT nodes called Validators, are entities in the Libra network that collectively decide which transactions will be added to the Libra Blockchain. Validator processes each have a designated validator called a Leader responsible for proposing new blocks and obtaining signed votes from the other validators on their proposals.

These Validator nodes use a consensus algorithm that can tolerate the presence of malicious (Byzantine) validators by maintaining the history of all the transactions on the blockchain, they also keep the current state to execute transactions and to calculate the next state.

The Libra protocol uses a variant of the HotStuff consensus protocol, a recent Byzantine fault-tolerant (BFT) consensus protocol, called LibraBFT. It provides safety (all honest validators agree on commits and execution) and liveness (commits are continually produced) in the partial synchrony model defined in the paper "Consensus in the Presence of Partial Synchrony" by Dwork, Lynch, and Stockmeyer (DLS) and mentioned in the paper "Practical Byzantine Fault Tolerance" (PBFT) by Castro and Liskov, as well as newer protocols such as Tendermint. Consenus Overview, Libra Technical Whitepaper

The HotStuff consensus algorithm is a leader-based Byzantine fault-tolerant replication protocol. It was proposed by VMware Research in March 2018 and is being officially published at the 2019 ACM Symposium on Principles of Distributed Computing.

HotStuff attempts to address the complexity of practical BFT. To maintain its liveness property, non-faulty replicas run commands identically and produce similar responses for each command. In this model, N ≥ 3f + 1 (3 honest, 1 faulty nodes) is required for non-faulty replicas to agree on the same commands in the same order and progress can be ensured deterministically.

LibraBFT assumes that at any point in time 3f + 1 votes are distributed among a set of validators that may be honest or Byzantine (faulty). LibraBFT remains safe, preventing attacks such as double spends and forks when at most f (one) votes are controlled by malicious validators — also implying that the total amount of malicious nodes on the network doesn't exceed more than 1/3 of the total number of network nodes in the system.

LibraBFT remains live, committing transactions from clients, as long as there exists a global stabilization time (GST), after which all messages between honest validators are delivered to other honest validators within a maximal network delay. In addition to traditional guarantees, LibraBFT maintains safety during its block generation and confirmation following more of a “Commander and Lieutenant” format. When a client sends a request to the primary node the request is processed as follows:

1. Leader block proposals are organized into a chain using cryptographic hashes.
2. If the proposal is valid and timely, each honest node will sign it and send a vote back to the leader.
3. After the leader has received enough votes to reach a quorum, it aggregates the votes into a Quorum Certificate (QC) that extends the same chain again.
4. The QC is broadcast to every node.
5. If the leader fails to assemble a QC, participants will timeout and move to the next round.
6. Eventually, enough blocks and QCs will extend the chain in a timely manner, and a block will match the commit rule of the protocol.
7. When this happens, the chain of uncommitted blocks up to the matching block become committed.

According to the Libra whitepaper, the choice for the HotStuff protocol as the basis for LibraBFT is based on: (i) simplicity and modularity; (ii) ability to easily integrate consensus with execution; and (iii) promising performance in early experiments. The HotStuff protocol decomposes into modules for safety (voting and commit rules) and liveness (pacemaker). This decoupling provides the ability to develop and experiment independently and on different modules in parallel.

Conclusion

Many blockchain projects use BFT consensus protocols today, for example, Hyperledger's pBFT consensus protocol. I hope this short article has helped you understand how HotStuff and its LibraBFT implementation will be deployed to secure the LIbra Network. Although its a solid project, Facebook has yet to get the green light from regulators to launch this project as projected in 2020.

To read more:

• LibraBFT —  https://developers.libra.org/docs/assets/papers/libra-consensus-state-machine-replication-in-the-libra-blockchain.pdf
• HotStuff BFT consensus —  https://arxiv.org/pdf/1803.05069.pdf
• Practical Byzantine Fault Tolerance —  http://pmg.csail.mit.edu/papers/osdi99.pdf
• Tendermint consensus algorithm —  https://arxiv.org/pdf/1807.04938.pdf

• use of secure programming languages for protocols & smart contracts
• development of satellite, radio and alternative means of transport/relay
• adoption of off-the-shelf devices for cryptocurrency purposes
• design of non-custodial services offered by trusted or centralized third party

Overall, expect the distributed and decentralized protocol industry to continue to grow as new methods of security engineering, risk management and crypto-economics are developed.