Chapter 1: From BFT to PoW

We start our story at the "birthplace" of distributed consensus theory, the 1980 seminal paper Reaching Agreement in the Presence of Faults by Pease, Shostak and Lamport (PSL).

In this paper, PSL introduce the Byzantine generals problem (BGT), which was the first to formulate many identical participants trying to reach an egalitarian decision without any central authority.

Even without describing what this means exactly, it is quite clear that if it is guaranteed that all participants follow the protocol, then the problem becomes trivial: each participant tells all other participants their opinion, and the most favorable possibility wins. The problem starts when we consider participants that deviate from the protocol. For example, in the simple majority voting scenario a single deviator can cause the entire consensus to collapse!

Hence, the real question is how many faulty players can a protocol endure while guaranteeing a consensus will be reached. The property of being able to handle the presence of faulty players has since been named Byzantine fault tolerance (BFT), in honor of the original problem.

Lamport et al. provided a protocol that can survive $f$ faulty nodes, given that there are $3f+1$ nodes in total (they also showed this could be slightly improved to $3f$ nodes assuming the existence of digital signatures). Equally importantly, they proved a theorem establishing that no BFT protocol could handle any more faults. This is known to this day as the $3f+1$ theorem, or simply as the one-third byzantine security limit.

Imagine everyone's surprise then, when in 2009 the psudonymous Satoshi Nakamoto published the Bitcoin Whitepaper, exhibiting a brand new form of consensus that maintains impressive security properties as long as at least half of the nodes are following the protocol. What is going on here? Did Satoshi prove PSL wrong? Is the $3f+1$ theorem false?

Not at all. There are two factors that allowed Satoshi to break the one-third consensus barrier. First, he assumed that we can use cryptography to prove the passage of time, and showed how proof-of-work can implement such a capability. Second, he relaxed the security requirements: instead of requiring that there is a fixed number of rounds after which a transaction will certainly never revert, he "compromised" for "just" having the probability of revert decrease very very fast as rounds (which can now be converted to time, thanks to the first assumption) pass.

In this first chapter, we do not yet consider proof-of-work based protocols. We do consider proof-of-work itself as a form of sybilness, and discuss what it achieves that BFT protocols arguably cannot.