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, 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
          • 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
    • Byzantine Generals Problem Paper (introduction part)
    • Bitcoin Forum - BFT
• 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

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
• 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
  • Reference
    • Eth2 Book (PoW/PoS, Sybil)
• 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 (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

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
        • This is designed to restore finality in the event of the permanent failure of large numbers of validators
• Reference
  • Eth2 Book
  • Perspectives on the CAP Theorem Paper
  • 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 (introduction part)
  • Gasper Paper

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 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, 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
  • A CBC Casper Tutorial
  • 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
        • 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^{\prime }\to c$ where checkpoint
            $c^{\prime }$ 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^{\prime }$, checkpoints
            $c$ and
            $c^{\prime }$ are not conflicting, and
            $h(c^{\prime })=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
  • 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(Valicatorp,sloti))=blockB$
        • Proposes a block
          $B$
    • Attesting
      • LMD-GHOST vote
        • For each slot
        • Run LMD-GHOST and vote for the block that attester think is correct
      • 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
  • Gasper Paper (4, 8, 9 sections)

Reference

• Eth2 Book
• The Byzantine Generals Problem (paper)
• Bitcoin Forum
• Practical Byzantine Fault Tolerance (paper)
• Wikipedia
• Ethereum.org
• Perspectives on the CAP Theorem (paper)
• A CBC Casper Tutorial
• Casper FFG: Consensus Protocol for the Realization of Proof-of-Stake
• Casper the Friendly Finality Gadget (paper)
• Three Attacks on Proof-of-Stake Ethereum (paper)
• Combining GHOST and Casper (paper)
• Consensus-spec