Consensus Series: PBFT

_kitchen
_kitchen
Nov 6 · 5 min read

Last week we covered the technical preliminaries for understanding consensus in depth. This week, we’ll give a high level overview of the PBFT (Practical Byzantine Fault Tolerant) consensus algorithm. While we consider newer protocols including PaLa a strict upgrade over PBFT, understanding PBFT is still crucial. Many of the terminology and ideas behind newer classical consensus protocols come from this protocol.

We use PBFT as a learning tool from which we will establish the language and ideas that PaLa and Thunderella protocols will build on. We do not cover other seminal classical consensus protocols such as 3 phase commit protocols and Paxos which employ similar ideas. Finally note that the consensus protocol presented here is slightly modified to be applicable for blockchain consensus.

Source: Practical Byzantine Fault Tolerance,OSDI, 1999

Terminology

Normal-case operation

  • Request: the user sends transactions to the primary.
  • Pre-prepare: the primary produces a proposal containing transactions and forwards to all replicas.
  • Prepare: Upon receiving a proposal, backups will verify it, and if it succeeds, they will broadcast prepare message to all other replicas. Backups do nothing if verification fails. This is the first round of voting.
  • Commit: Upon receiving prepare messages from ⅔ of all backups, replicas will now broadcast commit messages. This is the second round of voting.
  • Reply: the client sees the result of consensus.

In most circumstances, normal-case operation requirements are met and the primary is able to rapidly process new transactions. Since only ⅔ of backups need to agree in the prepare and commit phase, PBFT can already tolerate up to ⅓ of backups going or even acting byzantine. But what happens if the primary goes down?

View-change

During a view-change, replicas may not agree on the latest state of consensus — remember that the primary was responsible for leading consensus up until now. Since we are in the partially synchronous network setting, we can not guarantee that all replicas will see a ⅔ majority vote in the first round if it exists. A replica who sees a ⅔ majority vote for a proposal in the first round can not assume that others have seen it as well and therefore there is no agreement.

Thankfully, PBFT required 2 rounds of voting where replicas do not vote in the second round until they’ve seen results from the first round. Thus, upon seeing ⅔ majority vote in the second round, the replica is guaranteed that at least ⅔ of replicas have seen results from the first round. This knowledge about knowledge replaces the synchrony assumption where nodes are simply assumed to have seen a message (a round of votes in this case) after a certain amount of time has passed.

With this mechanism in place, the new primary can continue from the last proposal that received ⅔ majority vote in the second round. View-change messages also include the last proposal a backup has seen ⅔ majority vote in the first round. Assuming fewer than ⅓ nodes are byzantine, one can show that if anyone has seen a ⅔ majority vote in the second round, there must be at least 1 honest backup who successfully broadcasted a view-change message indicating that they have seen ⅔ majority vote in the first round for that proposal. The proof is just an application of the pigeonhole principle however the reasoning is more complex and described in detail in 4.5.1 of the PBFT paper.

Takeaway

PBFT is a message heavy algorithm. There are 3 rounds of messages and each message must be sent to all other replicas. It thus has O(n2) message overhead where n is the number of replicas.

Alternatives

ThunderCore

Real Blockchain. Real Benefits.

_kitchen

Written by

_kitchen

Product and Research Specialist @ ThunderCore and also a lot of other things

ThunderCore

Real Blockchain. Real Benefits.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade