Lightweight Approach for State Machine Replication with Median Rule
Explore a lightweight approach for state machine replication utilizing a median rule concept. Understand the motivation behind permissionless proof of work, delegated proof of stake, and BFT consensus protocols. Dive into leaderless BFT consensus protocols, asynchronous message passing, and the goal of efficient leaderless protocol in blockchain technology. Discover a model where a fraction of servers can be blocked based on past round states and an approach similar to Avalanche consensus. Learn about the basic and 8.5.2 median rules for consensus stability under different scenarios 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 made Lightweight: A Median Rule for State Machine Replication Jinfeng Dou , Christian Scheideler June 17th, 2024
Motivation Permissionless proof of work (delegated) proof of stake BFT consensus protocols Blockchain ApPLIED24 1
Motivation BFT consensus protocols leaderless, async msg passing rotating leaders, partially sync msg passing Leaders easy to attack! Blockchain [1]Michael J. Fischer, Nancy A. Lynch, Mike Paterson: Impossibility of Distributed Consensus with One Faulty Process. J. ACM 32(2): 374-382 (1985) ApPLIED24 2
Motivation BFT consensus protocols Goal: efficient leaderless protocol: partial synchrony members can only be blocked trusted execution environment Blockchain ApPLIED24 3
Motivation Our model: n servers synchronous rounds adversary can adaptively block -fraction of servers based on state at past round Server Server Server Network Blockchain Client Client Client ApPLIED24 4
Motivation Our model: n servers synchronous rounds adversary can adaptively block -fraction of servers based on state at past round Our approach: similar to Avalanche (median rule) Avalanche: bit-wise consensus We: entire (groups of) transactions Blockchain [2] Ignacio Amores-Sesar, Christian Cachin, Philipp Schneider: An Analysis of Avalanche Consensus. SIROCCO 2024: 27-44 ApPLIED24 5
The basic median rule z y x Number? Number? z. y. Randomserver x:=median{x,y,z} Random server all honest : O(log n) rounds w.h.p. [3]Benjamin Doerr, Leslie Ann Goldberg, Lorenz Minder, Thomas Sauerwald, Christian Scheideler: Stabilizing consensus with the power of two choices. SPAA 2011: 149-158. ApPLIED24 6 6
The ?, -median rule 8 5 2 8 5 8 Random servers reply 8,5,8,5 8=median rule {5, 8, 8} Example: The 6,3 -median rule [3]Peter Robinson, Christian Scheideler, Alexander Setzer: Breaking the Omega(sqrt{n}) Barrier: Fast Consensus under a Late Adversary. SPAA 2018: 173-182. Pull instead of push. ApPLIED24 7 7
The ?, -median rule 8 2 8 Random servers reply 8,8 =median rule { 8, 8} Example: The 6,3 -median rule ? 1/8 : O(log n) rounds w.h.p. ApPLIED24 8 8
The extend ?, -median rule Transactions C7C4C5C6C8 Let us assume for every transaction is a digit in {0, . . . ,9 } ??=0.74568 Server ?? ApPLIED24 9 9
The extend ?, -median rule 0.74568 0.63127 0.32578164 0.12486 0.32578 := median rule {0.74568, 0.12486, 0.32578} := median rule {0.74568, 0.12486, 0.32578} ?:= 164 ?? ?? ?? := 0.32578 ??:= ?? ? = 0.32578164 Example: The extend 6,3 -median rule ? 1/8 : O(log n) rounds w.h.p. to achieve consensus on transaction ApPLIED24 10 10
Motivation to design the compact ?, -median rule Size of the Bitcoin blockchain from January 2009 to May 26, 2024 (in gigabytes) Bitcoin (BTC) blockchain size as of May 26, 2024 600 Blockchain size in gigabytes 500 400 300 200 100 0 May 01, 2024 May 05, 2024 May 09, 2024 May 13, 2024 May 17, 2024 May 21, 2024 May 25, 2024 May 2009 May 2010 May 2011 May 2012 May 2013 May 2014 May 2015 May 2016 May 2017 May 2018 May 2019 May 2020 May 2021 May 2022 May 2023 Sep 2009 Sep 2010 Sep 2011 Sep 2012 Sep 2013 Sep 2014 Sep 2015 Sep 2016 Sep 2017 Sep 2018 Sep 2019 Sep 2020 Sep 2021 Sep 2022 Sep 2023 Jan 2009 Jan 2010 Jan 2011 Jan 2012 Jan 2013 Jan 2014 Jan 2015 Jan 2016 Jan 2017 Jan 2018 Jan 2019 Jan 2020 Jan 2021 Jan 2022 Jan 2023 Jan 2024 ApPLIED24 11
The compact ?, -median rule committed noncommitted C1C2C3 C?C?+1C?+2 C? C1C2C3 C?C?+1C?+2 C? ?? Server ?? ?? ???? ?? ??: { (?1,?(?1)), (?2,?(?2)), , (??,?(??))} ??????????? ?? ??executed on ??when already ? = ?log? ?????? ??? ApPLIED24 12 12
The compact ?, -median rule committed noncommited C1C2C3 C?C?+1C?+2 C? ?? Server ?? ?? ???? ?? ??: { (?1,?(?1)), (?2,?(?2)), , (??,?(??))} ??: { (?1,?(?1)), (?2,?(?2)), , (??,?(??))} ??????????? ?? ??executed on ??when already ? = ?log? ?????? ??? ApPLIED24 13 13
The compact ?, -median rule t-1, 0. 68 t-2, t, ??:=0.6748 t, ??:=0.748 t-2, 0,0 t-1, 0.6 Requests containing t-2 Receieve { 0.68 , 0.67, 0.47} t-1, 0.47 := median { 0. 68 , 0.67, 0.47} ?:= 48 ?? ?? t-3, := 0.67 ??:= ?? ??:= 0.748 if 6 has waited ? = ?log? ?????? ? = 0.6748 Example: The compact 6,3 -median rule ApPLIED24 14 14
The compact ?, -median rule t-1, 0. 68 t-2, t-2, t, 0,0 t-2, t-1, 0.47 Requests containing t-2 Receieve { 0.68, 0.47} := median { 0.68, 0.47} t-3, Example: The compact 6,3 -median rule ? 1/8 : O(log n) rounds w.h.p. to achieve consensus on transaction ApPLIED24 15 15
Merkle hash forest (a,c) (a,b) (c,d) (e,f) e c d a b f a b c d e f ApPLIED24
Merkle hash forest (a,h) (a,d) (e,h) (a,b) (c,d) (e,f) (g,h) e c d h a b f g a b c d e f g h ApPLIED24
Merkle hash forest (a,h) (a,d) (i,l) (e,h) (a,b) (c,d) (e,f) (g,h) (i,j) (k,l) e c d h a b f g k l i j i j k l a b c d e f g h ApPLIED24
Merkle hash forest (a,h) (a,d) (i,l) (e,h) (a,b) (c,d) (e,f) (g,h) (i,j) (k,l) e c d h a b f g k l i j i j k l a b c d e f g h ApPLIED24
