Practical Byzantine Fault Tolerance
Miguel Castro and Barbara Liskov (MIT)
Practical Byzantine Fault Tolerance (Ph.D thesis, 2001)
Formal proof of safety and liveness of pBFT using I/O automata
Byzantine Fault Tolerance
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
Distributed Algorithms Practical Byzantine Fault Tolerance
Alberto Montresor (Università di Trento)
New view with multiple pre-prepare (which has a certificate from a previous view)
The delay bound is time varying, but eventually does not grow faster than a polynomial function of time
The first proposal in a new view includes
view-change (or "status") messages
Each status message includes
signatures on the highest certified block (lockedQC)
First of all, only
$ 2f + 1
nodes are assumed to be live
$ 2f + 1
honest 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
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.