Tower BFT: Solana’s High Performance Implementation of PBFT

In this blog post, we will explore Tower BFT, Solana’s custom implementation of PBFT that prefers liveness to consistency. Tower BFT leverages Solana’s PoH as a clock before consensus to reduce messaging overhead and latency .

“In order to provide aliveness, replicas must move to a new view, if they are unable to execute a request. However, it is important to maximize the period of time, when at least 2f + 1 non-faulty replicas are in the same view, and to ensure that this period of time increases exponentially until some requested operation executes” (Practical Byzantine Fault Tolerance, Miguel Castro and Barbara Liskov).

Solana implements a derivation of PBFT, but with one fundamental difference. Proof of History (PoH) provides a global source of time before consensus. Our implementation of PBFT uses the PoH as the network clock of time, and the exponentially-increasing time-outs that replicas use in PBFT can be computed and enforced in the PoH itself.

PoH is a Verifiable Delay Function implemented as a sequential hash function. We use a loose definition of a VDF, since verification requires (compute time)/(number of cores). The basic principles of how PoH works are as follows:

1. Sha256 loops as fast as possible, such that each output is the next input.
2. The loop is sampled, and the number of iterations and state are recorded.

The recorded samples represent the passage of time encoded as a verifiable data structure. In addition, this loop can be used to record events.

1. Messages that reference any of the samples are guaranteed to have been created after the sample.
2. Messages can be inserted into the loop and hashed together with the state. This guarantees that a message was created before the next insert.

This data structure guarantees both time and order of events embedded within, and this core idea is the basis of all of the major technical optimizations in Solana.

Stated another way: Imagine you are on an island, and a bottle floats by with a thumb drive inside. On that drive is the Solana PoH ledger. Using only the PoH ledger, you can compute the state of all the nodes in the network. For example, a node is considered failed if a vote for the ledger has not been recorded in the last X hashes. We can consider the ledger to be valid if over the last X hashes hashes a supermajority of the network that has signed validation messages.

1. All the nodes that examine this data structure will compute the exact same result, without requiring any peer-to-peer communication.
2. The PoH hash uniquely identifies that fork of the ledger; and
3. A validation vote message is only valid if the PoH hash that it voted on is present in the ledger.

This brings us to voting and PBFT. Since the ledger itself works as a reliable network clock, we can encode the PBFT time-outs in the ledger itself.

1. A vote starts with a time-out of N hashes.

A Validator guarantees (with slashing) that once a vote for a PoH hash has been cast, the Validator will not vote for any PoH hash that is not a child of that vote, for at least N hashes.

2. The time-outs for all the predecessor votes double

To render operations more manageable, voting is restricted to a fixed period of hashes, which we call slots. Our goal for slots is the number of hashes that represents around 400ms. Every 400ms, the network has a potential rollback point, but every subsequent vote doubles the amount of real time that the network would have to stall before it can unroll that vote.