SESSION ID: CRYP-W11 SoK: A Consensus Taxonomy in the Blockchain Era Juan Garay and Aggelos Kiayias Texas A&M University and University of Edinburgh & IOHK #RSAC #RSAC A Consensus Taxonomy 2 #RSAC Consensus/Broadcast  One of the most fundamental problems in distributed computing  Important role in cryptographic protocols  Renewed interest with the advent of blockchain protocols like Bitcoin – New protocol paradigms – Wider research community – Applications expanded to novel settings 3 #RSAC Consensus (Byz. Agreement) [PSL80, LSP82] n parties t corrupted v2 v1 Adversary v3 ... vn Consensus Protocol vi ∈ V = {0,1} v v 4 v ... v #RSAC Consensus (Byz. Agreement) [PSL80, LSP82] (2)  Consensus: n parties start with an initial value vi • • • Agreement: All honest parties output the same value Validity: If all honest parties start with the same input (say, v), then they output this value Termination: Parties eventually terminate Single-sender/source version (“Byzantine Generals,” Broadcast)  • Validity: If sender is honest, then all honest parties output his value 5 #RSAC Broadcast (aka Byz. Generals) [PSL80, LSP82] n players t corrupted v1 v2 Sender (“Dealer”) Message v v3 vn-1 …  Validity: If dealer is honest, vi = v  Agreement: vi = vj  Termination: Every player eventually outputs a value 6 #RSAC Consensus (Byz. Agreement) [PSL80, LSP82] (2)  Consensus: n parties start with an initial value vi • • • Single-sender/source version (“Byzantine Generals,” Broadcast)  •  Agreement: All honest parties output the same value Validity: If all honest parties start with the same input (say, v), then they output this value Termination: Parties eventually terminate Validity: If sender is honest, then all honest parties output his value Fundamental problems in fault-tolerant distributed computing and cryptographic protocols (secure multi-party computation ─ MPC) 7 #RSAC Complexity Measures  Rounds: r = t+1 [LSP82, FL82]  Resiliency: • Unconditional setting: n > 3t [LSP82] 8 #RSAC Impossibility of Consensus with n ≤ 3t [PSL80, LSP82] 9 #RSAC Complexity Measures  Rounds: r = t+1 [LSP82, FL82]  Resiliency: • Unconditional setting: n > 3t [LSP82, GM92] • Cryptographic setting: − Broadcast: n > t [LSP82, DS82] − Consensus:n > 2t [DS82, Fit03] 10 #RSAC Complexity Measures  Rounds: r = t+1 [LSP82, FL82]  Resiliency: – Unconditional setting: n > 3t [LSP82, GM92] • Cryptographic setting: − Broadcast: n > t [LSP82, DS82] − Consensus: n > 2t [DS82, Fit03]  Message/Bit complexity: m = Ω(n2) [DR85, CW92, BGP92,…] 11 #RSAC Cryptographic (“Authenticated”) Consensus Protocols  Setup: Public-key infrastructure (PKI)  Assumption: Digital signatures secure against adaptive chosen-message attacks [GMR88]  [DS82]: r = t+1, poly(n) − Broadcast: − Consensus: n>t n > 2t 12 #RSAC Cryptographic (“Authenticated”) Consensus Protocols (2) [DS82] broadcast protocol (informal) ( n > t ):  Source signs its input value and sends to all parties  r = 1,…,t+1: If any value vi ∈ V = {0,1} has been newly added to a set of accepted values, sign it and send value and signatures to everybody o If a value/signatures message is received by any party containing valid signatures by at least r distinct players including the sender, then accept the value and update signatures  If only one accepted value, then the party outputs that value; otherwise a default value o 13 #RSAC Randomized Consensus Protocols  [BO83, Rab83]: Introduction of randomization to distributed algorithms (2015 Dijkstra Prize)  Expected constant no. of rounds; probabilistic, non-simultaneous termination [DRS90]  Consensus reduces to access to “common coin” [Rab83]  [FM88]: Common coin from “scratch” • [KK06]: Common coin in the cryptographic setting 14 #RSAC Talk Plan  Introduction (Consensus/Broadcast)  Consensus Lower Bounds  Blockchain-based Consensus • • • Blockchain basics A blockchain abstraction: The Bitcoin backbone protocol Is a genesis block really needed?: Consensus from scratch  A Consensus Taxonomy  A Ledger Consensus Taxonomy  References #RSAC On the Necessity of an Honest Majority for Consensus t < n/2 regardless of the resources available to the parties 16 #RSAC On the Necessity of an Honest Majority for Consensus (2)  Scenario [Fit03]: n parties equally divided with respect to their initial values ∈ {0,1}. Adv. corrupts ∅, P0 and