Explore the concept of fault-tolerant consensus in computer systems, covering topics such as Byzantine fault tolerance, replication strategies, consensus types, and fault tolerance bounds. Learn about key protocols like PBFT and motivations behind fault tolerance in system design.
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
Motivation 1: Broadcast Byzantine General s Problem [Lamport, Shostak, and Pease 1982] Attack! Retreat! I ve got your back! OK, I am out 2
Fault Tolerant Broadcast Safety: all lieutenants decide on the same command (if they decide) Validity: if the commander is honest, all lieutenants decide on its command Liveness: All lieutenants eventually decide [Broadcast] If the commander is honest, all lieutenants eventually decide [Reliable Broadcast] 3
Motivation 2: Replication Consider any service What if the server fails? Replicate the service Need consistency Despite some faulty servers End goal: provide the abstraction of a single non-faulty server 4
Fault Tolerant Replication End goal: provide the abstraction of a single non-faulty server Safety (consistency): all servers commit the same sequence of values Validity: application-specific Liveness: keep committing new values 5
Many Faces of Consensus Is every pair of server connected? Yes Is there a bound on message delay? Synchrony (Yes) / Asynchrony (No) / Partial Synchrony (Sometimes) What types of faults may occur? Crash / malicious (Byzantine) How many faults can we tolerate? Complicated 6
Fault Tolerance Bounds Below is an oversimplified summary n = total # of servers; f = # of faulty servers Asynchrony / Partial synchrony Paxos Synchrony Crash f < n f < n / 2 Bitcoin PBFT Byzantine f < n / 2 f < n / 3 7
PBFT Practical Byzantine Fault Tolerance Castro and Liskov, 1999 First practical Byzantine consensus Popularized the term BFT Proposed as replication under partial synchrony Also solves reliable broadcast under asynchrony n = 3f + 1 Assume public key cryptography (signatures). All messages are signed 8
PBFT Leader proposes v; replicas vote Upon receiving n f votes, lock v & vote again Upon receiving n f 2nd-round votes, commit v n = 3f+1 Replica 1 (Leader) Replica 2 Replica 3 Replica 4 propose vote1 vote2 preprepare prepare commit 9
PBFT as Reliable Broadcast Safety: all lieutenants decide on the same command (if they decide) 2f+1 Quorum Intersection f+1 2f+1 n = 3f+1 10
PBFT as Reliable Broadcast Safety: all lieutenants decide on the same command (if they decide) Validity: if the commander is honest, all lieutenants decide on its command Liveness (weak): if the commander is honest, all lieutenants eventually decide 11
PBFT as Replication Need stronger liveness If no progress for too long next leader (Leader) n = 3f+1 Replica 1 Replica 2 Replica 3 Replica 4 propose vote1 vote2 12
PBFT as Replication If no progress for too long next leader Safety under same leader: As before: two voting quorums intersect Safety across leaders: Intuitively: old locking quorum and new voting quorum intersect Once locked v, do not vote for other values Unless safe to unlock it s complicated 13
PBFT as Replication If no progress for too long next leader Safety due to quorum intersection Liveness: Under honest leaders & synchrony Want (standard) liveness in asynchrony? Need randomization due to FLP impossibility! [Fischer, Lynch, Patterson, 1985] 14
PBFT Summary Proposes + two rounds of voting Tolerate f < n/3 Byzantine faults Safe during async, live during sync Key idea: leader-based, quorum intersection, locks, ballots/ranks 16
Bitcoin Bitcoin: A Peer-to-peer Electronic Cash System Nakamoto in late 2008 Implemented and deployed early 2009 An ingenious and unconventional solution to BFT consensus Permissionless An ingenious application of BFT 17
Bitcoin Values = blocks of transactions Mining: solve hard puzzles Puzzle Random function 00000ca780f89 < Threshold ? nonce Proof-of-Work (PoW) Alice pays Bob $10 Alice pays Dan $22 Dan pays Carol $50 Carol pays Bob $50 Dan pays Bob $30 Bob pays Alice $10 PoW PoW PoW 18
Bitcoin Protocol Mine on longest chain & send to all Puzzle = Digest(prev block) || Digest({tx}) || pk Bob Charlie Dave Alice Emily $$$ newly minted coins & tx fees 19
Bitcoin Protocol Mine on longest chain & send to all Commit blocks buried deep If adversary has <50% mining rate, cannot revert a block buried deep Long forks are unlikely Bob Charlie Dave Alice Emily 20
What is Blockchain? Used by most people to refer to the underlying technology of Bitcoin Synonymous to BFT replication Satoshi never used this term Key technique of Bitcoin is PoW chain PBFT = permissioned blockchain? Many proposed applications of BFT and many more to come 21
