Improving the LibraBFT protocol

September 26, 2019
Mathieu Baudet, Novi

We are happy to announce a new release of the LibraBFT technical report.

The LibraBFT protocol operates at the heart of the Libra* blockchain to guarantee secure state machine replication. The new version of the protocol, LibraBFTv2, includes several optimizations that were designed to reduce networking and improve commit latency of the Libra blockchain.

Together with this release, we are happy to make available the code of the Rust simulator used as a reference in the LibraBFT report. This code can be found in the github repository of the research team of Novi**.

Reducing network complexity in practice

LibraBFT is a refinement of the HotStuff protocol that makes explicit the mechanisms used to achieve round synchronization between nodes. Informally, a round is a period of time where a specific leader is trusted to drive progress — typically by proposing a block (B), gathering votes (V), and broadcasting a quorum certificate (C) (see picture below). Round synchronization aims at making nodes eventually execute the same round with sufficiently long overlap so that the leader of this round can succeed.

In the optimistic case (aka “happy path”), LibraBFTv2 reduces the overhead of round synchronization to a single message per node per round (see green arrows in the picture).

The initial “v1” version of LibraBFT relied on probabilistic gossip to ensure uniform propagation of quorum certificates (C). This uniform propagation was needed to achieve round synchronization and guarantee liveness in presence of malicious leaders. While probabilistic gossip is a popular technique suitable to many applications, it typically requires a non-linear number of messages and causes increased latency due to the intermediate hops. From an engineering point of view, the network overhead and the probabilistic nature of gossiping may also complicate debugging.

In contrast, LibraBFTv2 achieves round synchronization in a different way, without using probabilistic gossip. First, the new protocol introduces a new type of failsafe mechanisms that regularly pull missing data in case no progress is made. Second, LibraBFTv2 simplifies the constraints on block proposals. The new constraints ensure that an honest leader can always propose a block and force round synchronization soon after the first honest node enters her round.

The proof of liveness of LibraBFTv2 shows that the new protocol still performs in a satisfying way under Byzantine (worst-case) scenarios, while the number of messages is now linear in the best case.

What’s next?

We expect new releases of the LibraBFT report to continue in the future as the research and the engineering teams of Novi keep improving the theoretical analysis and the implementation of the LibraBFT protocol.

Stay tuned!

*On December 1, 2020, the Libra Association was renamed to Diem Association.
**Novi was first announced as Calibra in 2019.