TockCuckoo: Two-Phase BFT With Linearity and Responsiveness

It is critical to achieve the following objectives inpartially synchronous Byzantine Fault Tolerance (BFT) pro-tocols: 1) two-phase commit regime; 2) standard optimisticresponsiveness; and 3) linear communication complexity. Thesethree properties significantly affect the efficiency of BFT proto-cols. A number of attempts, such as HotStuff and Tendermint,have been made to solve this problem, but they typically manageto achieve only a subset of these properties. In this work,we propose a two-phase BFT protocol called TockCuckoo thatfully achieves the aforementioned three properties. A primarychallenge in two-phase BFT protocols is HiddenLock: whena leader lacks visibility into the latest locked block states ofhonest replicas, it cannot safely proceed, potentially stalling theprotocol. To address this issue, we introduce the proactive votingparadigm, which explicitly distinguishes between rejection andnon-receipt states. After global stable time, an honest leader canalways collect sufficient votes through proactive voting, enablingquick responses. TockCuckoo operates in continuous rounds ofproactive voting, ensuring responsiveness. The proactive votingprocess requires only linear communication overhead, whichdirectly results in TockCuckoo achieving linear communicationcomplexity overall. Furthermore, we introduce TockCuckoo+,an extension of TockCuckoo. By introducing a cross-pipelineddesign, TockCuckoo+ enables more frequent block proposalswithout sacrificing the key characteristics of TockCuckoo, leadingto improved throughput. Our experiments in wide-area networksdemonstrate that, TockCuckoo reduces commit latency by 20%to 40% compared to HotStuff across different network sizes, andTockCuckoo+ achieves a throughput increase of 1.1× to 1.5×over HotStuff.