Paper 2021/180

Apollo -- Optimistically Linear and Responsive SMR

Adithya Bhat and Akhil Bandarupalli and Saurabh Bagchi and Aniket Kate and Michael Reiter

Abstract

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.