Fundamentals of Consensus #

Byzantine Generals Problem (Lamport et al., 1982) #

  • N (fixed) generals, one is commander
  • Some generals are loyal, some are traitors (incl. commander)
  • Commander sends out order to attack or retreat
    • Commander is loyal: send out same order to all generals
    • Commander is traitor: sends out different orders to confuse
  • Goal: all loyal generals should take the same action
    • Which should be the one issued by the commander, if commander is loyal

Generalized consensus problem #

  • Solution to a consensus problem is a consensus protocol
  • To generalize Byzantine Generals Probelm: generals are nodes, the commander is the leader, loyal generals are honest nodes, traitors are the adversary

The adversary #

  • Role of an adversary: corrupt nodes, making them adversarial
  • Types of adversaries:
    • Induces crash faults if the adversarial nodes do not send or receive any messages
    • Induces omission faults if the adversarial nodes can selectively choose to drop or let through messages sent or received
      • Note: omission fault adv. can emulate crash fault adv. in all cases => stronger adversary
    • Byzantine faults (Byzantine adversary): adversarial nodes can deviate from protocol arbitrarily
  • Typical assumption: adversary cannot forge signatures
  • Adaptive vs. static adversary:
    • Static adversary: corrupts nodes of its choice pre-protocol execution
    • Adaptive adversary: can dynamically corrupt nodes during protocol execution
  • Bounds on adversary’s power:
    • Assume upper bound on number of nodes $f$ that can be adversarial, as a fraction of the $n$ nodes

Communication #

  • Nodes can send messages to each other within the protocol
  • Time proceeds in discrete rounds
  • Adversary controls delivery of messages, with limits:
    • Synchronous network: adversary must deliver messages sent by honest nodes to recipients within $d$ rounds
    • Async. network: adversary can delay any message for arbitrary, but finite, number of rounds
    • Partial synchrony: exists a known $t$ and event called Global Stabilization Time (GST) where
      • GST eventually happens after some finite time that can be chosen arbitrarily by adversary
      • Message sent by honest node at round $t$ is delivered to recipient by round $d + max(GST, t)$
      • In effect, network async. until GST, after which it behaves like synchronous

State machine replication (SMR) #

  • Theoretically, could have centralized bank, but want to decentralize
  • SMR participants:
    • Replicas: receive transactions, execute SMR protocol
    • Clients: learners, each outputs a log
      • Tries to learn what correct ledger should be
  • Goal: ensure clients output same logs
    • Compared to Byzantine Generals Problem: this is multi-shot: log is continuously output, rather than single value output
    • Also: learners (log output) are separate from nodes executing protocol
  • e.g. Replicas $r_1 \ldots r_5$, Clients $c_1 \ldots c_4$
    • Replicas receive transactions $tx_1 \ldots tx_4$
    • Clients ask replicas what log sequence should be

Security for SMR #

  • Let $LOG_t^{i}$ be the log ouptut by client $i$ at round $t$
  • Secure SMR protocol guarantees:
    • Safety (consistency): for clients $i, j$, times $t, s$: $LOG_t^{i}$ should be a prefix of $LOG_s^{j}$, or vice versa
    • Liveness: if a transaction $tx$ is output to a honest replica at some time $t$, then for all clients $i$, times $s \ge t + T_{conf}$, then $tx \in LOG_s^{i}$

Baby streamlet #

  • Time: epochs of $2d$ rounds
    • For each epoch $e$, leader $L_e$ chosen by public hash function $H$
    • Blocks: each block is associated with an epoch
  • $n$ replicas, fixed before protocol execuction, every replica knows all other replica public keys (creating authenticated communication channels)
  • At each epoch $e = 1, 2, \ldots$:
    • Propose: at start of epoch $e$, $L_e$ identifies longest seen chain and proposes new block extending that chain
    • Finalization rule: client finalizes block (and prefix) at tip of longest chain; tiebreak by smaller epoch
  • Proving security under $f < n/3$, partial synchrony, Byzantine adversary:
    • Safety: no two blocks can be finalized at the same height
      • However, with adversarial leader and pre-GST:
        • Adv. sends $B_1$ to Alice, which gets notarized
        • Adv. sends $B_2$ to Bob, which gets notarized
        • Both are plopped on top of $B_1$ at the same time, which is not safe
      • Therefore, Baby Streamlet is not safe (so not secure)!

Teen streamlet #

  • Setup: same as baby streamlet
    • Additionally: votes: vote on block by a replica is its signature on the block
    • Notarization: block notarized in view of replica or client if observed over $2n/3$ signatures from distinct replicas on the block
  • At each epoch, in adition to propose:
    • Vote: $d$ rounds into epoch $e$: each honest replica votes for first valid epoch $e$ proposal from $L_e$ that extends longest notarized chain in its view. If no such block, no vote
    • Finalization rule: client finalizes block and prefix once observed notarization of block
  • Proving security under same constraints:
    • Safety: now works under constraints, because cannot get over $2n/3$ votes for duplicate notarization with only adversarial votes

Streamlet #

  • At each epoch:
    • Propose: leader $L_e$ identifies longest notarized chain that it has seen so far and proposes new block extending that chain; tiebreak adversarial
    • Vote: same as teen streamlet
    • Finalization rule: upon seeing three adj. blocks in notarized chain with consecutive epoch numbers, client finalizes second of three blocks and entire prefix change
  • Secure: yes
  • However, inefficient: requires $\Theta(n^3)$ messages per block
    • Protocols like HotStuff are as secure and achieve $\Theta(n)$ message complexity per block