Consensus

# 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

• 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
• Byzantine faults (Byzantine adversary): adversarial nodes can deviate from protocol arbitrarily
• Typical assumption: adversary cannot forge signatures
• Static adversary: corrupts nodes of its choice pre-protocol execution
• 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
• 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