Achieving Total Order in State Machine Replication and Consensus Protocols
Exploring the concepts of state machine replication and consensus protocols such as BFT (Byzantine Fault Tolerance) in the context of blockchain technology. The content delves into the importance of total order requirement in maintaining consistency and reliability in distributed systems.
Download Presentation
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.
E N D
Presentation Transcript
Blockchains Lecture 8
State Machine Replication, BFT, and Blockchains
State Machine Replication Single Server Architecture
State Machine Replication Single Server Architecture A single point of failure!
State Machine Replication State Machine Replication Interactive protocol among servers State machine replication gives safety and liveness.
State Machine Replication State Machine Replication (SMR) Replicas maintain the same state Replicas start in the same state Operations are deterministic Replicas execute operations in the same order (i.e., total order) Replicas send replies to clients Clients vote on replica replies
Roughly, Consensus: All About Achieving Total Order [Lamport, ACM TOPLAS 1984] Blockchains (modeled as state machine replication) $100 $100 $100
The Total Order Requirement Client 1: Deposit $100 $100 $200 Client 1: Deposit $100 $100 $200 $100
The Total Order Requirement Chase: Charge 10% Client 1: Deposit $100 $100 $200 $180 Chase: Charge 10% Client 1: Deposit $100 $180 $100 $200 $100
The Total Order Requirement Chase: Charge 10% Client 1: Deposit $100 $100 $200 $180 Chase: Charge 10% Client 1: Deposit $100 $180 $100 $200 $100
The Total Order Requirement Chase: Charge 10% Client 1: Deposit $100 $100 $90 $190 Chase: Charge 10% Client 1: Deposit $100 $190 $100 $90 $100
The Total Order Requirement Chase: Charge 10% Client 1: Deposit $100 $100 $90 $190 Chase: Charge 10% Client 1: Deposit $100 $180 $100 $200 $100
State Machine Replication Crash Fault-Tolerant SMR 2f+1 replicas to tolerate f failures Example: Paxos: SMR for crash failures [Lamport, ACM TOCS 1998]; going back to 1989 The most important backbone architecture Each major service BigTable, Chubby, Spanner, Azure, Amazon Web Services, Ceph, IBM SAN, VMware NSX,
State Machine Replication Paxos [Lamport. Paxos made simple. ACM SIGACT News 2001] [Lamport, ACM TOCS 1998]; going back to 1989 For fundamental contributions to the theory and practice of distributed and concurrent systems, notably the invention of concepts such as causality and logical clocks, safety and liveness, replicated state machines, and sequential consistency. Turing Award 2013
State Machine Replication Byzantine Fault-Tolerant SMR (BFT Protocols) Traditionally important Powerful: Byzantine/arbitrary failures & attacks Systems, distributed systems, theory, crypto, security, Recently gain prominence Real threats to real systems Blockchains Mission-critical systems (SpaceX)
State Machine Replication Byzantine Fault-Tolerant SMR (BFT Protocols) Traditionally important Powerful: Byzantine/arbitrary failures & attacks Systems, distributed systems, theory, crypto, security, Recently gain prominence Real threats to real systems Blockchains Mission-critical systems (SpaceX)
State Machine Replication PBFT 3f+1 replicas to tolerate f Byzantine failures [Castro and Liskov, OSDI 1999] For contributions to practical and theoretical foundations of programming language and system design, especially related to data abstraction, fault tolerance, and distributed computing. Turing Award 2008
Normal Case Client sends request to all Why not just send to one?
Normal Case Primary sends pre-prepare message to all Records operation in log as pre-prepared
Normal Case Replicas check the pre-prepare and if it is ok: Record operation in log as pre-prepared Send prepare messages to all All to all communication
Normal Case Replicas wait for 2f+1 matching prepares Record operation in log as prepared Send commit message to all Trust the group, not the individuals
Normal Case Replicas wait for 2f+1 matching commits Record operation in log as committed Execute the operation Send result to the client
Normal Case Client waits for f+1 matching replies
BFT Request Pre-Prepare Prepare Commit Reply Client Primary Replica 2 Replica 3 Replica 4
View Change (Quite Complex!) Replicas watch the primary Request a view change send a do-viewchange request to all new primary requires f+1 requests sends new-view with this certificate Rest is similar
Improved Performance Lower latency for writes (4 messages) Replicas respond at prepare Client waits for 2f+1 matching responses Fast reads (one round trip) Client sends to all; they respond immediately Client waits for 2f+1 matching responses
Improvements Batching Run protocol every K requests
Blockchains are SMR (e.g., PBFT) Yet with three differences: In blockchains, only append-only operations are allowed; delete, for instance, is disabled. Blockchains operations are batched and written in the database; SMR does not explicitly require this. Blockchains typically allow anyone to deploy programs ( smart contracts ); SMR typically only allows the system designer to write fixed programs. In this sense, blockchains are more general!
