Chris Liu

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2024-138

May 17, 2024

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2024/EECS-2024-138.pdf

Byzantine fault tolerant protocols provide powerful tools to cope with the presence of arbitrary failures, but have historically struggled to do so at scale. The creation of new, scalable BFT protocols regularly hinges on the unearthing of novel insights, the process of which is often error-prone. Alternatively, localized, rule-driven rewrites have shown promise in recent work through their ability to mechanically scale existing CFT protocols like Paxos using decoupling and partitioning techniques. These techniques are powerful, but are unable to be safely applied to a BFT environment as-is. We introduce modifications to these rewrites such that they can be safely applied to BFT protocols, and additionally prove the correctness of our modified rewrites on arbitrary BFT protocols. To this end, we must formally model the capabilities of Byzantine nodes: we propose a Borgesian simulator, a proof concept meant to reframe Byzantine actors as random actors, capable of simulating all possible Byzantine behavior through random outputs. We reason on the Borgesian simulator to prove that the possible outputs a Byzantine actor can create before and after our modified rewrites are the same. We additionally introduce a new rewrite, partial independent decoupling, to adapt our suite of rewrites to design patterns common in BFT protocols such as PBFT. Our proposed rewritten version of PBFT is thus capable of view changes and checkpointing while optimizing the critical path.

Advisors: Natacha Crooks

---

BibTeX citation:

@mastersthesis{Liu:EECS-2024-138,
    Author= {Liu, Chris},
    Title= {EVIL SERVERLESS CONSENSUS},
    School= {EECS Department, University of California, Berkeley},
    Year= {2024},
    Month= {May},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2024/EECS-2024-138.html},
    Number= {UCB/EECS-2024-138},
    Abstract= {Byzantine fault tolerant protocols provide powerful tools to cope with the presence of arbitrary failures, but have historically struggled to do so at scale. The creation of new, scalable BFT protocols regularly hinges on the unearthing of novel insights, the process of which is often error-prone. Alternatively, localized, rule-driven rewrites have shown promise in recent work through their ability to mechanically scale existing CFT protocols like Paxos using decoupling and partitioning techniques. These techniques are powerful, but are unable to be safely applied to a BFT environment as-is. We introduce modifications to these rewrites such that they can be safely applied to BFT protocols, and additionally prove the correctness of our modified rewrites on arbitrary BFT protocols. To this end, we must formally model the capabilities of Byzantine nodes: we propose a Borgesian simulator, a proof concept meant to reframe Byzantine actors as random actors, capable of simulating all possible Byzantine behavior through random outputs. We reason on the Borgesian simulator to prove that the possible outputs a Byzantine actor can create before and after our modified rewrites are the same. We additionally introduce a new rewrite, partial independent decoupling, to adapt our suite of rewrites to design patterns common in BFT protocols such as PBFT. Our proposed rewritten version of PBFT is thus capable of view changes and checkpointing while optimizing the critical path.},
}

EndNote citation:

%0 Thesis
%A Liu, Chris 
%T EVIL SERVERLESS CONSENSUS
%I EECS Department, University of California, Berkeley
%D 2024
%8 May 17
%@ UCB/EECS-2024-138
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2024/EECS-2024-138.html
%F Liu:EECS-2024-138