Neil Giridharan and Florian Suri-Payer and Matthew Ding and Heidi Howard and Ittai Abraham and Natacha Crooks

EECS Department, University of California, Berkeley

Technical Report No. UCB/

May 1, 2024

http://www2.eecs.berkeley.edu/Pubs/TechRpts/Hold/a7f53363a0b8853d3e64a17a8bf4ba33.pdf

Modern chained Byzantine Fault Tolerant (BFT) systems leverage a combination of pipelining and leader rotation to obtain both efficiency and fairness. These protocols, however, require a sequence of three or four consecutive honest leaders to commit operations. Therefore, even simple leader failures such as crashes can weaken liveness, resulting in high commit latency or lack of commit all together. We show that, unfortunately, this vulnerability is inherent to all existing BFT protocols that rotate leaders with pipelined agreement. To resolve this liveness shortcoming we present BeeGees1, a novel chained BFT protocol that successfully commits blocks even with non-consecutive honest leaders. It does this while also maintaining quadratic word complexity with threshold signatures, linear word complexity with SNARKs, and responsiveness between consecutive honest leaders. BeeGees reduces the expected commit latency of HotStuff by a factor of three under failures, and the worst-case latency by a factor of seven.

Advisors: Natacha Crooks

---

BibTeX citation:

@mastersthesis{Giridharan:31203,
    Author= {Giridharan, Neil and Suri-Payer, Florian and Ding, Matthew and Howard, Heidi and Abraham, Ittai and Crooks, Natacha},
    Title= {BeeGees: Stayin' Alive in Chained BFT},
    School= {EECS Department, University of California, Berkeley},
    Year= {2024},
    Number= {UCB/},
    Abstract= {Modern chained Byzantine Fault Tolerant (BFT) systems leverage a combination of pipelining and leader rotation to obtain both efficiency and fairness. These protocols, however, require a sequence of three or four consecutive honest leaders to commit operations. Therefore, even simple leader failures such as crashes can weaken liveness, resulting in high commit latency or lack of commit all together. We show that, unfortunately, this vulnerability is inherent to all existing BFT protocols that rotate leaders with pipelined agreement. To resolve this liveness shortcoming we present BeeGees1, a novel chained BFT protocol that successfully commits blocks even with non-consecutive honest leaders. It does this while also maintaining quadratic word complexity with threshold signatures, linear word complexity with SNARKs, and responsiveness between consecutive honest leaders. BeeGees reduces the expected commit latency of HotStuff by a factor of three under failures, and the worst-case latency by a factor of seven.},
}

EndNote citation:

%0 Thesis
%A Giridharan, Neil 
%A Suri-Payer, Florian 
%A Ding, Matthew 
%A Howard, Heidi 
%A Abraham, Ittai 
%A Crooks, Natacha 
%T BeeGees: Stayin' Alive in Chained BFT
%I EECS Department, University of California, Berkeley
%D 2024
%8 May 1
%@ UCB/
%F Giridharan:31203