Byzantine Fault Tolerance (BFT)

Like many good stories, ours also begins with war. In the fifth century, the titular city-state of Byzantium was expanding. In one particular excursion, several Byzantine legions all surrounded the same fortress. Knowing their only chance to topple its impregnable walls is if all generals work together, they need to somehow agree among themselves whether to attack or retreat. Most crucially, they must all reach the same decision. But here is the crux: generals are far too important to allow more than two of them to be in the same place. Arranging for all generals to convene and reach a decision together is far too dangerous. The decision must rely on one-on-one conversations between two generals. Of course, this is simple if all generals are honest. But what if some generals are compromised and are trying to manipulate our protocol to get some, but not all, generals to attack?

This is called the Byzantine fault tolerance problem.

My gratitude to Quai network for sponsoring this segment of the book

The Byzantine Generals Problem (BGP)

While the historical theme has its charm, we abandon it in favor of a more colloquial jargon. (After all, it would be weird if, three chapters from now, we referred to miners as generals.)

The BGP problem describes a network of nodes. These nodes can send messages to each other. A consensus protocol is a procedure for a network to agree on one option from a given list. (e.g., a bunch of generals having to decide whether to attack or retreat). The nodes communicate in rounds. In each round, any node can send a message to any other node. An important restriction that might be a little less intuitive is that all messages are sent first, and only then are they received. This is a mathematical convenience that ensures the messages in each round depend only on those received in previous rounds.

We've already mentioned one such protocol: majority voting. In this protocol, each node tells all other nodes its preference, and nodes agree to accept the popular choice. This protocol only takes one round.

Majority voting is a very simple protocol. Unfortunately, it also turns out to be a very bad protocol. Recall the story of the generals, and assume there are only three of them: Nicephorus, who wants to fight; Martin, who wants to retreat; and Euphemius, who is secretly a traitor to Byzantium.

Nicephorus and Martin are loyal to Byzantium and its protocols, so they broadcast their true intentions. However, Euphemius the treacherous had other plans: he told Martin that he wanted to fight, and Nicephorus that he wanted to retreat! Consequently, Nicephorus the fierce was coerced to retreat, while Martin the calm-minded was tricked into fighting alone, leading to a great defeat!

This shows that majority voting lacks fault tolerance. A faulty (or Byzantine) node is a general term for any node that deviates from the protocol, whether due to malice or an actual fault. When analyzing the protocol's security, we don't care what caused a deviation. We care about conditions assuring that no deviation can break the protocol.

More formally, a Byzantine Fault Tolerance (BFT) protocol guarantees that all non-faulty nodes reach a mutual agreement within some known number of rounds. We usually quantify the fault tolerance with a number $0\le\alpha\le 1$, indicating how many faulty nodes the protocol can handle. We call a consensus protocol $\alpha$-BFT if it remains correct as long as the fraction of faulty nodes is at most $\alpha$.

With this terminology, we can state the first major result of the field.

The $3f+1$ Theorem (Pease, Shostak, Lamport, 1980):

• There is no $\alpha$-BFT protocol for $\alpha > 1/3$.

• Under certian conditions, there exists a $1/3$-BFT protocol.

I'm actually hiding a subtlety here. There are two variations of the impossibility part of PSL's theorem. One for $\alpha > 1/3$, assuming the existence of digital signatures, and one for $\alpha \ge 1/3$ without assuming the existence of digital signatures. In a world without cryptography, we need strictly fewer than a third of nodes to be faulty. But if we presume digital signatures exist, we can handle a scenario in which exactly a third of the nodes are faulty.

This is a book about permissionless ledgers, so everything we do is deeply rooted in the assumption that cryptography exists. Hence, I chose to focus on the latter variant.

The name $3f+1$ comes from denoting the number of faulty nodes by $f$, and noting that assuming $\alpha < 1/3$ is the same as assuming that there are at least $3f+1$ nodes in total.

We will provide a more accurate version shortly. To specify what the "certain conditions" are, we must first introduce synchronicity models.

Safety and Liveness

Note that the $\alpha$-BFT definition packs in two requirements: that an $\alpha$ minority cannot cause a split decision, and that it cannot delay the decision indefinitely.

These two properties are best treated separately and are often referred to as safety and liveness. In consensus protocols, security is usually broken into these two properties. It is a common mistake, and one that production-level networks unfortunately fall into, to consider safety and ignore liveness.

Majority voting is an example of how safety can fail. We should also see an example of a liveness failure.

Consider a toy protocol called the indecisive dictator. In this setting, one all-powerful dictator decides everything. The problem is that the dictator sometimes acts on an impulse and changes their mind soon after. To provide the dictator with some leeway, the consensus protocol accepts the dictator's decree only if it is consistent across two consecutive rounds. In this situation, if the dictator herself is Byzantine, she can delay the decision indefinitely by constantly changing her mind.

This example is not as convoluted as it seems. It is a purified example of a subtle phenomenon called a balancing attack, in which a small collusion of Byzantine nodes can convince all the remaining nodes to change their minds. This does not compromise safety, as the nodes constantly change their minds together, so at any point, they all agree on the same thing. But it is a problem because the agreement remains unstable and never converges on a single option.

As we will see, liveness is trivially true for the PSL protocol: the number of rounds is known in advance, and the proof shows that it is sufficient. Nothing that participants do can trigger additional rounds. This is the exception to the rule. More modern BFT protocols improve performance by adapting the number of rounds based on the protocol's progress. For such protocols, it is plausible that an attacker could exploit this mechanism to perform a liveness attack.

We will revisit safety and liveness more thoroughly in the next chapter, in the context of probabilistic consensus.

Synchronicity Models

So far, we have not really discussed the properties and limitations of "a network". We talked in terms of entities transmitting messages. We didn't stop to think about the assumptions we had to make about the ability to send messages.

In fact, we made a very strong implicit assumption, can you see it? It hides in the presumption that we can divide our protocol into rounds. This means that the network can somehow tell when a round has ended and the next round has started.

This assumption is called the synchronous model, and in many cases, it is considered too good to be true. To see what other options are out there, we need a clearer way to state our assumption.

A common way to do it is by message delay. Say that you know that any message is guaranteed to arrive within two seconds. You can decree that a round is four seconds long, and that messages must be transmitted within the first two seconds, and arrive before the round ends. That way, you are guaranteed that no messages are lost. Or are you? We are forgetting something...

Exercise: What are we forgetting, and how can you fix it?

Solution

The remaining unaccounted for assumption is that everyone knows when the round starts. But in practice, this will usually be announced to the network by messages from other peers, and these new round messages can themselves be delayed!

So a better solution is to make each round six seconds long. Two seconds for receiving the round end message, two seconds for responding, and two seconds for receiving the next round end message.

Note that an end message contains the results of the round, so a participant cannot send messages for the new round without seeing the end message of the previous round.

There are many other fixes, but this is one of the simplest.

This motivates the following:

In the synchronous model, there is a known network delay bound $\Delta$ such that any message that sent at time $t$ arrives before $t+\Delta$.

The synchronous model is reasonable in sufficiently controlled networks, but it is not suitable at all for a global, permissionless network like a distributed ledger.

With this vocabulary, we can provide a more accurate statement of the PSL theorem:

The $3f+1$ Theorem (Pease, Shostak, Lamport, 1980):

• There exists a $1/3$-BFT protocol in the synchronous model

• There is no $\alpha$-BFT protocol for $\alpha > 1/3$

Note that only the first statement needed adjustment. Since the synchronous model is the most presumptuous one, showing that something is impossible in this model implies it is impossible in all models.

In the other corner, we have a model with no guarantees at all:

In the asynchronous model, it is guaranteed that messages arrive eventually, but there is no guarantee (not even a probabilistic one) on how long each message will take, the order they arrive in, and so on.

It would definitely be terrific to have Byzantine agreement under such Spartan assumptions. Unfortunately, there can't be:

Theorem (Michael Fischer, Nancy Lynch, and Michael Paterson, 1985):

For any $\alpha>0$, no consensus protocol is $\alpha$-BFT in the asynchhronous model.

The proof is subtle, but the key insight is simple: we can always find a scenario where a single message changes the outcome. By delaying this one message sufficiently long, we can change the consensus. Hence, liveness is only guaranteed after such a message could not have been transmitted. But since we have no bound on the message delay, this means no wait is long enough to provide liveness.

FLP actually prove a subtler theorem that implies the statement above. To fully state their original statement, we must foray into different types of faults and failures. This digression is unnecessary for our purposes, as most of the book pertains to proof-of-work, where such distinctions are unhelpful. I refer the curious to a series of online lectures by Tim Roughgarden.

This statement, and actually all statements we have made, only consider deterministic finality, in which you are guaranteed that the protocol converges. As we will see later, more can be achieved by relaxing this to a probabilistic consensus, where convergence is guaranteed up to a small factor. Most of the book is dedicated to probabilistic consensus, albeit in the somewhat different context of proof-of-work rather than BFT.

We need a model that is not unreasonably accommodating like the synchronous model, but not as harsh as the asynchronous model. A good compromise is the partially synchronous model, proposed by Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer in 1988.

In the partly synchronous model there is a delay $\Delta$ on the time it takes messages to arrive, but it is not known

This is one of several equivalent formulations of this model. This variation is the simplest to understand, but not the simplest to work with. The Global Stabilization Time (GST) formulation is arguably most commonly used in the literature. I again refer the studious reader to Tim Roughgarden's lectures.

The idea of this model is to capture network conditions. In reality, delay bounds may change, but we assume such changes are not constant. For periods of minutes or even hours, $\Delta$ is usually constant. So instead of talking about an oxymoronic "constant that changes," we can talk about a "constant we don't know", which is exactly how this model works.

This model seems to be the best playground for BFT protocols. In the synchronous model, there are already "perfect" protocols that satisfy most applications. No protocol survives the asynchronous model. But the partially synchronous model seems to hit the sweet spot where useful protocols are possible, but it seems that "perfect" protocols are not, and there is room for plenty of interesting trade-offs and approaches.

PSL's Protocol

We fully flesh out the protocol for the special case of four nodes making a binary choice. That's enough nodes to understand the internal structure without bogging ourselves down with details.

Let us call our nodes John, Paul, George, and Ringo. Instead of nodes, we will refer to them as Beatles, stressing that this is not the standard terminology. The Beatles are trying to decide whether they should call their new album Revolver or Rubber Soul.

The protocol's rules are the same for all participants, so we assume John's point of view.

The first round of the protocol is very simple: each Beatle tells the others how they would like to call the album. After the first round, John should have three pieces of information, which could look, for example, like this:

Paul wants to call the album Revolver

George wants to call the album Revolver

Ringo wants to call the album Rubber Soul

This is a good start, but we already know it is not quite enough. What could Paul do with this information? In particular, how could he know that the remaining Beatles were consistent, and that, say, Paul didn't tell George they wanted to call the album Rubber Soul?

To verify that, all Beatles now tell all other Beatles all they have learned in the first round. An example will make this less confusing. After the round is over, John should have six more pieces of information. If anyone were honest, they should look like this:

Paul said that George wants to call the album Revolver

Paul said that Ringo wants to call the album Rubber Soul

George said that Paul wants to call the album Revolver

George said that Ringo wants to call the album Rubber Soul

Ringo said that Paul wants to call the album Revolver

Ringo said that George wants to call the album Revolver

This is enough information for John to deduce that (discounting his own vote) there is a two-to-one agreement for Revolver. If John also wants to call the album Revolver, then we are done here: all Beatles will see Revolver as preferred by most of the band, and agree on the name.

But what if John wants to call the album Rubber Soul? How do we handle the ensuing tie? An interesting question that I will defer until we discuss tie-breaking rules.

So we see that (up to tie-breaking) the protocol works nicely if everyone is playing nicely. But that was already true for simple majority voting! The real meat lies in how this protocol responds to faults.

Say that Ringo really wants to call the album Rubber Soul, and he knows John is on his side. What if he lies to John about what George and Paul had to say? Then John would see the following messages:

Paul wants to call the album Revolver

George wants to call the album Revolver

Ringo wants to call the album Rubber Soul

Paul said that George wants to call the album Revolver

Paul said that Ringo wants to call the album Rubber Soul

George said that Paul wants to call the album Revolver

George said that Ringo wants to call the album Rubber Soul

Ringo said that Paul wants to call the album Rubber Soul

Ringo said that George wants to call the album Rubber Soul

Note the two emphasized lines in the end. They are inconsistent with previous lines. John notes a contradiction: Paul tells him he wants to call the album Revolver. But Ringo tells him that Paul wants to call the album Rubber Soul! How can he resolve the contradiction?

A naive answer would be that he should trust Paul, since first-hand information is always better than second-hand. But if we always preferred first-hand information, then all rounds but the first are actually meaningless, and we revert to simple majority voting.

The secret is essentially second-order majority voting. John goes over all claims of Paul's preference, including those from Paul himself, and takes the majority. In this case, he will note that both Paul and George attest that Paul wants to call the album Revolver, giving them a majority against Ringo's claims.

Note that this has nothing to do with Paul's actual preference. The goal here is to reach a consensus. It doesn't matter what this agreement reflects, as long as everybody agrees.

It is not hard to complete the argument and convince ourselves that no matter how Ringo tries to cheat, he will fail as long as the remaining Beatles stick to the protocol.

But what if Ringo was innocent, and it was Paul and George who colluded to enact the name Revolver, despite half of the Beatles being against it? Now John will see the following messages:

Paul wants to call the album Revolver

George wants to call the album Revolver

Ringo wants to call the album Rubber Soul

Paul said that George wants to call the album Revolver

Paul said that Ringo wants to call the album Revolver

George said that Paul wants to call the album Revolver

George said that Ringo wants to call the album Revolver

Ringo said that Paul wants to call the album Revolver

Ringo said that George wants to call the album Revolver

In this case, the plot is successful. John will note that both Paul and George claim that Ringo wants Revolver, but only Ringo claims that Ringo wants Rubber Soul. By majority decision, Ringo wants to call the album Revolver.

Again, this might seem a bit unfair. Who should Paul and George decide for Ringo? And we have to remember again that this is about reaching a decision, not about what decision is reached. Paul cannot tell whether the contradictions he observes are due to Paul and George trying to force a name on Ringo, or to Ringo professing inconsistent opinions to manipulate the result somehow. Sticking to the PSL protocol ensures that no matter what, a single Beatle cannot coerce the decision.

This protocol can be extended to $n=3f+1$ Beatles (or any other rhythmic coleopterans) by adding more rounds. So by the end of the fourth round, John will hold messages such as

George said that Ringo said that said that Paul said that Yoko wants to call the album Let it Be

One can prove by induction that if at most $f$ of the nodes are faulty, then the protocol is guaranteed to provide consensus after $f+1$ rounds, provided there are at least $3f+1$ nodes.

PSL Complexity*

Security is important, but practicality is also important. Fault-tolerance isn't going to help anyone if it requires a trillion rounds or an exabyte of RAM.

There are three benchmarks for the efficiency of a consensus protocol. The communication complexity measures the number of rounds the protocol requires. The space complexity measures how much RAM each participant needs. The time complexity measures the amount of processing required to compute the result. The effect of the message length on complexity is baked into the time complexity, as we assume each non-faulty party, at the very least, reads valid messages in their entirety. Note that the space complexity might be smaller than the message length. There are protocols in which the messages can be read as a stream and do not need to be stored in their entirety at any point.

In the PSL protocol, the number of required rounds is proportional to the number of nodes: we need $f+1$ rounds to obtain full $1/3$-BFT security for $3f+1$ nodes. That's already far from ideal. For example, the Ethereum network has more than 750,000 validators. Directly applying PSL would require 250,000 rounds per block.

What about time complexity? We answer this by analyzing message lengths.

Recall the Beatles. In the first round, John only stated his own preference. In the second round, in each message, John had to state the preferences he heard from $n-1$ other Beatles. In the third round, he has to state, for each of the $n-1$ other Beatles, the preference they claim for the remaining $n-1$ Beatles (including John himself). In the $k$th round, John has to list at least $(n-1)^{k-1}$ preferences. Note that each preference is a binary value (because we assumed only two voting options), so the number of bits John must transmit in the $k$th round is also at least $(n-1)^{k-1}$.

The final round is $k=f+1$, in which John must transmit $(n-1)^{f}=\Omega\left((n-1)^{n/3}\right)$ bits, which is exponentially large.

Exercise: How does having a different number of options affect this computation?

Solution

If we have $m$ options, and we have to state $p$ preferences, we will need $\log_2(m^p)$ bits. But we note that $\log_2(m^p) = \log_2(m)\log_m(m^p)=p\log_2(m)$, so the total number of bits is the same up to a constant $\log_2(m)$.

It is generally good advice to remember that $\log_2(m)$ is exactly the number of bits required to state one out of $m$ possibilities.

Practical BFT

Fortunately, PSL was just the first in a royal lineage of BFT protocols.

In 1999, Miguel Castro and Barbara Liskov introduced the Parctical Byzantine Fault Tolerance (PBFT) protocol. PBFT's most significant contribution is in terms of the synchronicity model. It is one of the first protocols that works in the partially synchronous model. But more than that, it reduces the time complexity to $O(n^2)$. An extreme improvement over the exponential complexity of PSL.

Several improvements of various sorts succeeded PBFT, such as Zyzzyva and ABsTRACTs, which provide improved performance, Aaardvark, which provides improved robustness, and Adapt, which switches between protocols to respond to changing conditions. More recent protocols, such as HotStuff and Marlin, further reduce the complexity to linear. Finally, we would be remiss not to mention a few protocols specifically crafted for proof-of-stake, such as Alphabet and Tendermint.