# Outline: Ethereum's Consensus Protocol

###### tags: `blockchain-research`

### What is Consensus

#### Background
+ The Byzantine Generals Problem
+ Background
+ Basic idea: abstract
+ The background of consensus knowledge
+ In a 1982 [paper](https://lamport.azurewebsites.net/pubs/byz.pdf), **Leslie Lamport**
+ What is it
+ The army are **divided** into several generals
+ Generals communicate **only** through **messenger**
+ Generals must decide **a common plan** of action
+ Howevery, some of generals are **traitors**, trying to **prevent** the loyal generals from **reaching agreement**
+ The generals must have an **algorithm** to guarantee👇
1. All loyal generals decide upon the **same plan** of action (attack or retreat)
2. A small number of traitors **cannot** cause the loyal generals to **adopt a bad plan**
+ The definitions
+ BGP
+ as above👆
+ BFT (Byzantine fault tolerant)
+ BF (Byzantine faults)
+ traitor generals
+ malicious nodes
+ BFT (Byzantine fault tolerant)
+ Any algorithms that can tolerate Byzantine faults
+ Some BFT algorithms
+ \> 51% general votes algorithm
+ pBFT
+ in a 1999 [paper](https://www.scs.stanford.edu/nyu/03sp/sched/bfs.pdf)
+ consists of one leader node (sending requests) and backup nodes (voting)
+ votes > $\frac{2}{3}$
+ Can tolerate Byzantine faults, allowing the 33% malicious nodes
+ Communication is fast. All nodes reach the result at the same time (but the number of nodes cannot be too many)
+ High barriers to entry (participant list)
+ Nakamoto consensus
+ Casper FFG
+ Gasper
+ Reference
+ [Eth2 Book](https://eth2book.info/bellatrix/part2/consensus/preliminaries/#byzantine-generals)
+ [Byzantine Generals Problem Paper](https://lamport.azurewebsites.net/pubs/byz.pdf) (introduction part)
+ Bitcoin Forum - [BFT](https://bitcoin.stackexchange.com/a/97102/136952)
+ Sybil attack
+ The definition
+ An attack by creating vast numbers of **duplicate identities** at a low (or zero) cost
+ Example
+ Background
+ a blockchain, use \> 51% algorithm
+ If you run a software (open sourced) you can be a general and **vote**
+ Execute a attack
+ You can make **many virtual machines** and run this "general software"
+ And control voting of all machines
+ Now you create many duplicate identities at a very low cost
+ Vote, take over the system
+ Conclusion
+ All blockchain consensus protocols need to defense Sybil attack
+ Reference
+ [Wikipedia](https://en.wikipedia.org/wiki/Sybil_attack)
#### The definitions
+ What is "consensus"
+ The definition
+ Consensus is a computer science problem of achieving system-wide **agreement** in the presence of **crash failure**/**Byzantine faults**
+ computer process crash
+ traitor generals
+ Reference
+ [Wikipedia](https://en.wikipedia.org/wiki/Consensus_(computer_science))
+ What is PoW and PoS
+ The definition
+ Proof-of-Work and Proof-of-Stake are essentially **Sybil resistance mechanisms**
+ Prevent duplicate identities with **limited resources** (hash power, network's coin)
+ Sybil resistance mechanisms
+ One-GPU-one-vote
+ One-stake-one-vote
+ [One-human-one-vote](https://archive.devcon.org/archive/watch/6/1-human-1-vote-money-legos-more-democratic-daos/?playlist=Devcon%206&tab=YouTube)
+ Reference
+ Eth2 Book ([PoW/PoS](https://eth2book.info/altair/part2/consensus/preliminaries#proof-of-stake-and-proof-of-work), [Sybil](https://eth2book.info/altair/part2/incentives/staking#introduction))
+ What is consensus protocol
+ The definition
+ The consensus protocol is **an agreed suite of algorithms** for a set of entities (nodes, people, etc) to follow
+ a set of algorithms
+ defined into protocol
+ Reference
+ Gasper [Paper](https://arxiv.org/pdf/1710.09437.pdf) (2.1 part)
+ What is consensus mechanism
+ The definition
+ The consensus mechanism is the **combination** of all components
+ Contains protocol-level (code) and non-protocol level (social layer)
+ PoS, consensus protocols, economic incentives, and community legitimacy are **all part of** the consensus mechanism
+ Reference
+ [Ethereum org](https://ethereum.org/en/developers/docs/consensus-mechanisms/#what-is-a-consensus-mechanism)

### What is the consensus protocol of Ethereum

#### Background
+ CAP Theorem
+ The definition
+ client-servers model
+ client makes **requests** to a server
+ when a server receives a request, it sends a **response**
+ Consistency, Availability, Partition-tolerance
+ Consistency
+ Availability
+ Partition-tolerance
+ Why - Example
+ the servers are **partitioned** into two disjoint sets: {$p1$} and {$p2, . . . , pn$}
+ All requests sent from {$p1$} to {$p2, . . . , pn$} are lost
+ A more general framework
+ The impossibility of guaranteeing both **safety** and **liveness** in an **unreliable distributed system**
+ The definitions
+ Safety
+ The original definition
+ Informally, an algorithm is safe if **nothing bad ever happens**
+ In blockchain context
+ Consistency: If we were to ask different (honest) nodes about **the state of the chain** at some point, then we should always get **the same answer**, no matter which node we ask
+ The blockchain transaction history will not contain two **conflicting** blocks
+ Liveness
+ The original definition
+ By contrast, an algorithm is live if **eventually something good happens**
+ In blockchain context
+ The chain can always add a new block
+ Unreliable distributed system
+ Internet
+ A Blockchain Example
+ If AWS goes offline, all Ethereum nodes will be divided into two groups
+ AWS group
+ non-AWS group
+ Nodes within a group can communicate, but two groups cannot communicate
+ Blockchain history inconsistency
+ In practice
+ Bitcoin only has Liveness guarantee, probabilistic Safety guarantee
+ Ethereum prioritises liveness
+ If a partition occurs, a **hard fork** will be initiated
+ i.e. [Inactivity leak](https://eth2book.info/bellatrix/part2/incentives/inactivity)
+ This is designed to restore finality in the event of the permanent failure of large numbers of validators
+ Reference
+ [Eth2 Book](https://eth2book.info/bellatrix/part2/consensus/preliminaries/#safety-and-liveness)
+ Perspectives on the CAP Theorem [Paper](https://groups.csail.mit.edu/tds/papers/Gilbert/Brewer2.pdf)
+ Gasper Paper (2.5 part)

#### General intro
+ General intro
+ The Proof-of-Stake (PoS) Ethereum consensus protocol is constructed by applying the finality gadget **Casper FFG** on top of the fork choice rule **LMD-GHOST**
+ Reference
+ Three Attacks on Proof-of-Stake Ethereum [Paper](https://arxiv.org/pdf/2110.10086.pdf) (introduction part)
+ Gasper [Paper](https://arxiv.org/pdf/1710.09437.pdf)

#### Fork-choice rule
+ The defination
+ The fork-choice rule is the rule for **choosing a branch** when a blockchain **fork** ocuurs
+ Subsequent blocks will be added to this chain (branch)
+ Bitcoin and PoW Ethereum's fork-choice rule
+ They use **the longest chain rule**
+ The longest chain represents **the most cumulative "work" done** under proof of work
+ New blocks continue to be **added** to the longest chain (highest block), which is "liveness" too
+ GHOST
+ The background
+ GHOST was proposed in a 2015 [paper](https://eprint.iacr.org/2013/881.pdf) to improve Bitcoin's fork choice rules
+ Many people say that GHOST is also used in PoW Ethereum, but Ethereum **never** actually implemented it
+ The definition
+ The **heaviest chain rules**, the chain with the most votes becomes the **canonical chain**
+ LMD-GHOST
+ The background
+ LMD-GHOST is a variant of GHOST that only considers the latest vote (LMD = latest message driven)
+ Proposed in a 2017 [paper](https://github.com/vladzamfir/research/blob/master/papers/CasperTFG/CasperTFG.pdf), V.zamfir tries to combine GHOST with Casper
+ The definition
+ Calculate the block with **the most votes**, return it as **the head of the chain**, and add subsequent blocks to this block
+ Number of votes = block + it's descendants
+ The workflow
+ Start at the genesis block
+ Each time there is a fork, **choose** the block’s subtree where more of LMs (latest messages) are supported
+ Repeat, until you research a block **with no children** then return this block as the head of the chain
+ Reference
+ [Eth2 Book](https://eth2book.info/bellatrix/part2/consensus/preliminaries/#fork-choice-rules)
+ [A CBC Casper Tutorial](https://vitalik.ca/general/2018/12/05/cbc_casper.html)
+ Casper FFG and Gasper papers (LMD-GHOST part)
#### Finality gadget
+ Safety
+ Bitcoin and PoW Ethereum have no "finality gadget" and “security guarantees”
+ Whoever constructs the new longest chain can change the previous blocks
+ Under the Casper FFG, the finalized block of PoS Ethereum cannot be modified
+ Requires huge attack cost, $\frac{2}{3}$ of the total staking amount
+ Casper FFG
+ The background
+ Based on the pBFT algorithm, but with many new features
+ Punishment mechanism
+ slashing conditions
+ Permissionless system
+ dynamic validators
+ Modular overlay
+ clean and have a modular design
+ Protocol's main components
+ Checkpoint tree
+ Casper is designed to work with a wide class of **blockchain protocols** with **tree-like structures**
+ Checkpoint tree
+ Checkpoint block
+ The blocks whose height is a multiple of a constant H
+ For example, H = 100, blocks = 0, 100, 200, 300, ...
+ In Ethereum, H = 32
+ Checkpoint tree
+ Finality on Checkpoint blocks
+ Checkpoint blocks form a Checkpoint tree
+ Future: [single-slot finality](https://notes.ethereum.org/@vbuterin/single_slot_finality)
+ There is a research direction to reduce H to 1
+ In this way, each block (slot) is a checkpoint block
+ Can speed up finality time (from 32 slots to 1 slots, 384s to 12s)
+ Checkpoints pair
+ The definition
+ $checkpoint(s,t)$
+ The pair is a link from source checkpoint to target checkpoint
+ Pair is the content of validator votes (i.e. attestations)
+ Supermajority Link
+ Pairs with $\frac{2}{3}$ staker votes
+ Justification and Finalization
+ Genesis Block
+ The genesis block is justified/finalized by default
+ Justification
+ a checkpoint $c$ is called justified if
+ (1) it is root
+ (2)there exits a supermajority link $c' \to c$ where checkpoint $c'$ is **justified**
+ Finalization
+ a checkpoint $c$ is finalized if and only if
+ (1) it is root
+ (2) checkpoint $c$ is **justified**, and there exits a supermajority link $c \to c'$, checkpoints $c$ and $c'$ are not conflicting, and $h(c')=h(c)+1$
+ Finalized blocks as part of the canonical chain
+ Slashing conditions
+ Note
+ Validator violations will be punished
+ All violating validators can be traced (by signature)
+ The definition
+ A validator must not publish two distinct votes for the same target height
+ A validator must not vote within the span of other votes
+ My comments
+ Reference
+ [medium](https://medium.com/unitychain/intro-to-casper-ffg-9ed944d98b2d)
+ Casper FFG paper
+ Gasper paper (Casper FFG part)
#### Gasper
+ Re-call "general intro"
+ The Proof-of-Stake (PoS) Ethereum consensus protocol is constructed by applying the finality gadget **Casper FFG** on top of the fork choice rule **LMD-GHOST**
+ High-Level Overview
+ Proposer proposal and run fork-choice rule to add new block
+ Attesters publishe the attestations and broadcast
+ How it works
+ Randomly selected committee
+ At **each epoch**, all validators are **equally assigned** to 32 slots through "committee"
+ Numbers
+ Minimum 1 committee per slot, maximum 64
+ Minimum 128 validators per committee, maximum 2048
+ At least 32 * 1 * 128 = 4096 validators are required
+ Up to 32 * 64 * 2048 = 4194304(419.43w) validators are allowed
+ There are currently 456620 validators
+ Proposer and attester
+ The **first member** in the committee as proposer, and **the remaining members** as attesters
+ There is **only one** proposer, the **rest** are all attesters
+ Proposing blocks and attesting are done **immediately**, then **broadcast** the block and attestation
+ Proposal
+ Proposer runs LMD-GHOST and proposes a block
+ run $HLMD(view(Valicator\ p, slot\ i)) = block\ B$
+ Proposes a block $B$
+ Attesting
+ [LMD-GHOST vote](https://github.com/ethereum/consensus-specs/blob/dev/specs/phase0/validator.md#lmd-ghost-vote)
+ For each slot
+ Run LMD-GHOST and vote for the block that attester think is correct
+ [FFG vote](https://github.com/ethereum/consensus-specs/blob/dev/specs/phase0/validator.md#ffg-vote)
+ For checkpoint pair
+ After two rounds, new epoch will be finalized and be a part of canonical chain
+ Block be finalized
+ Justification
+ In the first round of voting, change the checkpoint(epoch) status to $Justified$
+ Finalization
+ Voting to justified checkpoint
+ Change the checkpoint(epoch) status to $Finalized$
+ Reward and Penalities
+ Reward proposers and attesters
+ Run "Slashing conditions" to check if any validator violates the rules
+ Penalty if violated
+ Done
+ Reference
+ [Consensus-spec](https://github.com/ethereum/consensus-specs)
+ Gasper Paper (4, 8, 9 sections)

### Reference
+ [Eth2 Book](https://eth2book.info/bellatrix/)
+ The Byzantine Generals Problem ([paper](https://lamport.azurewebsites.net/pubs/byz.pdf))
+ [Bitcoin Forum](https://bitcoin.stackexchange.com/questions/75923/bft-vs-bitcoin-pow-vs-pbft/97102#97102)
+ Practical Byzantine Fault Tolerance ([paper](https://pmg.csail.mit.edu/papers/osdi99.pdf))
+ [Wikipedia](https://en.wikipedia.org/wiki/Consensus_(computer_science))
+ [Ethereum.org](https://ethereum.org/en/developers/docs/consensus-mechanisms/#what-is-a-consensus-mechanism)
+ Perspectives on the CAP Theorem ([paper](https://groups.csail.mit.edu/tds/papers/Gilbert/Brewer2.pdf))
+ [A CBC Casper Tutorial](https://vitalik.ca/general/2018/12/05/cbc_casper.html)
+ [Casper FFG: Consensus Protocol for the Realization of Proof-of-Stake](https://medium.com/unitychain/intro-to-casper-ffg-9ed944d98b2d)
+ Casper the Friendly Finality Gadget ([paper](https://arxiv.org/abs/1710.09437))
+ Three Attacks on Proof-of-Stake Ethereum ([paper](https://arxiv.org/pdf/2110.10086.pdf))
+ Combining GHOST and Casper ([paper](https://arxiv.org/abs/2003.03052))
+ [Consensus-spec](https://github.com/ethereum/consensus-specs)