Wahoo: A DAG-Based BFT Consensus With Low Latency and Low Communication Overhead
Xiaohai Dai, Z. Zhang, Zhengxuan Guo, Chaozheng Ding, Jiang Xiao, Xia Xie, Rui Hao, Hai Jin
Abstract
To parallelize data processing within BFT consensus protocols, <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Directed Acyclic Graph</i> (DAG) structures have been integrated into consensus design, shaping the realm of DAG-based BFT protocols. Existing DAG-based protocols rely on the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Reliable Broadcast</i> (RBC) protocol or its variants for block dissemination, which ensures consistency and totality properties of the data delivery. However, the inherent communication overhead of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O</i> ( <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) in RBC (where <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> is the total replica count) results in an unwieldy <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O</i> ( <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> ) overhead in current DAG-based solutions, as each replica disseminates blocks through RBC in parallel. In response to this issue, we propose two new broadcast protocols: <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Provable Broadcast</i> (PBC) and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Enhanced Provable</i> Broadcast (EPBC). Both PBC and EPBC maintain the consistency property of data delivery, similar to RBC, while offering linear communication overhead without totality. Leveraging these broadcast protocols, we devise Wahoo, a novel DAG-based BFT protocol that significantly reduces communication overhead to <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O</i> ( <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ). To address the absence of the totality property, we introduce a block retrieval mechanism to assist replicas in acquiring missing blocks. Additionally, under favorable conditions, Wahoo achieves a low latency of 4δ (where δ symbolizes the actual network delay), rivaling the best performance of existing DAG-based protocols. Various experiments showcase Wahoo’s high performance, owing to its substantially reduced communication overhead.