Byzantine Fault Tolerance

Lamport, Shostak, Pease 1982 · Castro & Liskov 1999 · Wikipedia

The Byzantine generals problem: nodes can send contradictory messages. To tolerate f Byzantine faults, you need at least 3f + 1 nodes. With fewer, a traitor can make honest nodes disagree. PBFT (Practical Byzantine Fault Tolerance) makes this work in practice with three rounds of communication.

Byzantine generals problem

Generals surround a city. They must agree to attack or retreat. Some generals are traitors who send conflicting messages. The loyal generals must all reach the same decision, and if they all start with the same preference, that preference must win. With fewer than 3f + 1 generals, f traitors can prevent agreement.

Scheme

; Byzantine generals: 3f+1 nodes to tolerate f traitors.
; With 4 nodes, tolerate 1 traitor. With 3, cannot.

(define (bft-required f) (+ (* 3 f) 1))

(display "To tolerate 1 traitor: need ")
(display (bft-required 1)) (display " nodes") (newline)
(display "To tolerate 2 traitors: need ")
(display (bft-required 2)) (display " nodes") (newline)
(display "To tolerate 3 traitors: need ")
(display (bft-required 3)) (display " nodes") (newline)

; Why 3f+1? With fewer, a traitor can create a tie.
; f traitors + f honest on one side + f honest on other side
; = 3f. The (f+1)th honest node breaks the tie.
(display "3 nodes, 1 traitor: ")
(display (if (>= 3 (bft-required 1)) "safe" "UNSAFE"))

PBFT overview

Practical BFT (Castro and Liskov, 1999) works in three phases: pre-prepare (leader assigns sequence number), prepare (2f+1 nodes agree on order), commit (2f+1 nodes confirm). Total messages per request: O(n^2). Expensive, but it works with Byzantine faults and has been deployed in production systems.

Scheme

; PBFT message complexity.
; n = 3f + 1 nodes.
; Pre-prepare: 1 message from leader
; Prepare: each node sends to all others = n*(n-1)
; Commit: each node sends to all others = n*(n-1)
; Total per request ~ 2*n^2

(define (pbft-messages f)
  (let* ((n (+ (* 3 f) 1))
         (per-phase (* n (- n 1)))
         (total (+ 1 per-phase per-phase)))
    (display "f=") (display f)
    (display ", n=") (display n)
    (display ", messages=") (display total) (newline)))

(pbft-messages 1)   ; n=4
(pbft-messages 2)   ; n=7
(pbft-messages 3)   ; n=10
(pbft-messages 10)  ; n=31 -> expensive

Neighbors

Cross-references

🔐 Cryptography Ch.8 — digital signatures authenticate messages, enabling BFT

← Raft by june.kim CAP Theorem →