PBFT
Resources
Papers
Miguel Castro and Barbara Liskov (MIT)
OSDI'99
Formal proof of safety and liveness of pBFT using I/O automata
Tutorials
King Abdullah Uni.
CS 240: Computing Systems and Concurrency Lecture 11 (Marco Canini)
Alysson Neves Bessani (University of Lisbon)
pBFT, Zyzzyva, BFT-SMaRt, etc.
A Guided Tour on the Theory and Practice of State Machine Replication
Byzantine Fault-Tolerant State Machine Replication
View-change-ack
Alberto Montresor (Università di Trento)
New view with multiple pre-prepare (which has a certificate from a previous view)
Implementations
Model
Weak synchrony
The delay bound is time varying, but eventually does not grow faster than a polynomial function of time
Protocol
View change
$ O(n^3)authenticator complexity
The first proposal in a new view includes$ O(n)view-change (or "status") messages
Each status message includes $ O(n)signatures on the highest certified block (lockedQC)
FAQ: Why?
First of all, only $ 2f + 1nodes are assumed to be live
However, $ 2f + 1honest nodes might have missed the highest QC
So, each view-change contains the highest QC, and the leader picks up the highest QC
Therefore, the highest QC must be verifed
Two-rounds of votes
From HotStuff paper,
The practical aspect is that a stable leader can drive a consensus decision in just two rounds of message exchanges.
The first phase guarantees proposal uniqueness through the formation of a quorum certificate (QC) consisting of (n−f) votes.
The second phase guarantees that the next leader can convince replicas to vote for a safe proposal.