[Resource Topic] 2021/180: Apollo -- Optimistically Linear and Responsive SMR

Welcome to the resource topic for 2021/180

Apollo – Optimistically Linear and Responsive SMR

Authors: Adithya Bhat, Akhil Bandarupalli, Saurabh Bagchi, Aniket Kate, Michael Reiter


Existing Byzantine fault-tolerant (BFT) state-machine replication (SMR) protocols in the standard (bounded) synchrony and weak synchrony models rely on equivocation detection to ensure safety. To perform a commit (or output a transaction block), this detection inherently requires O(n^2) communication overhead among n nodes and waiting for O(\Delta) time, where \Delta is the worst-case network delay. The quadratic communication overhead limits scalability. Moreover, as the typical network latency \delta tends to be much smaller than \Delta, 51\% honest-majority (and hence synchronous or weakly synchronous) solutions become slow as compared to 67\% honest-majority asynchronous protocols working at network speed. The observation that SMR commits do not have to be treated separately motivates this work. We propose UCC (Unique Chain Commit) rule, a novel yet simple rule for hash chains where extending a block by including its hash is treated as a vote for the block and all its direct and indirect parents. When a block obtains f+1 such votes, where f is the maximum number of faulty nodes in the system, we commit the block and its parents. We use this UCC rule to design Apollo, an SMR protocol with rotating leaders which has a linear communication complexity. Apollo proposes and commits a block every \delta time units with every block having a latency of (f+1)\delta. When compared to existing works which use equivocation detection, we improve the optimistic commit latency when (f+1)\delta<2\Delta. We prove the security of our protocol in both standard and weak synchrony models. We also implement and compare Apollo with the state of the art protocol, and demonstrate Apollo having commit latencies independent of and less than the \Delta parameter, and also show significant gains in response rates with increasing n. For instance, when n=3, Apollo can commit blocks of size 2000 as fast 3 ms. For n=65, Apollo produces $3$x more committed transactions per second than the state of the art Sync HotStuff protocol.

ePrint: https://eprint.iacr.org/2021/180

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .