AsynchronousByzantine Fault Tolerance(BFT) consensus protocols are gaining attention for their resilience against network attacks. Among them,Multi-valued Byzantine Agreement(MVBA) protocols play a critical role, which accepts input values from each replica and returns a consistent output. The state-of-the-art MVBA protocol, sMVBA, has a good-case latency of$6\delta$and an expected bad-case latency of$12\delta$, with$\delta$representing the network delay. Additionally, sMVBA exhibits a communication of$O(n^{2})$in both good and bad cases. Although it outperforms other MVBA protocols, sMVBA still lags behind partially-synchronous counterparts. For instance, PBFT achieves a good-case latency of$3\delta$, and HotStuff boasts a good-case communication of$O(n)$. This paper introduces a novel MVBA protocol, Pako, aiming for performance comparable to partially-synchronous protocols. Pako leverages an existing MVBA protocol as a black box and introduces an additional view with an optimistic path to commit values efficiently. Two Pako variants, Pako1 and Pako2, provide a trade-off between latency and communication. To be more specific, Pako1 achieves a good-case latency of$3\delta$with$O(n^{2})$communication, while Pako2 reduces the communication to$O(n)$with a slightly higher good-case latency of$5\delta$. A series of experiments demonstrate Pako's significant outperformance of counterparts.

To improve the throughput of Byzantine Fault Tolerance (BFT) consensus protocols, the Directed Acyclic Graph (DAG) topology has been introduced to parallel data processing, leading to the development of DAG-based BFT consensus. However, existing DAG-based works heavily rely on Reliable Broadcast (RBC) protocols for block broadcasting, which introduces significant latency due to the three communication steps involved in each RBC. For instance, DAGRider, a representative DAG-based protocol, exhibits the best latency of 12 steps, considerably higher than non-DAG protocols like PBFT, which only requires 3 steps. To tackle this issue, we propose LightDAG, which replaces RBC with lightweight broadcasting protocols such as Consistent Broadcast (CBC) and Plain Broadcast (PBC). Since CBC and PBC can be implemented in two and one communication steps, respectively, LightDAG achieves low latency.In our proposal, we present two variants of LightDAG, namely LightDAG1 and LightDAG2, each providing a trade-off between the best latency and the expected worst latency. In LightDAG1, every block is broadcast using CBC, which exhibits a best latency of 5 steps and an expected worst latency of 14 steps. Since CBC cannot guarantee the totality property, we design a block retrieval mechanism in LightDAG1 to assist replicas in retrieving missing blocks. LightDAG2 utilizes a combination of PBC and CBC for block broadcasting, resulting in the best latency of 4 steps and an expected worst latency of 12(t+1) steps, where t represents the number of actual Byzantine replicas. Since a Byzantine replica may equivocate through PBC, LightDAG2 prohibits blocks from directly referencing contradictory blocks. To ensure liveness, we propose a mechanism to identify and exclude Byzantine replicas if they engage in equivocation attacks. Extensive experiments have been conducted to evaluate LightDAG, and the results demonstrate its feasibility and efficiency.

To parallelize data processing within BFT consensus protocols,Directed Acyclic Graph(DAG) structures have been integrated into consensus design, shaping the realm of DAG-based BFT protocols. Existing DAG-based protocols rely on theReliable Broadcast(RBC) protocol or its variants for block dissemination, which ensures consistency and totality properties of the data delivery. However, the inherent communication overhead ofO(n2) in RBC (wherenis the total replica count) results in an unwieldyO(n3) 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:Provable Broadcast(PBC) andEnhanced ProvableBroadcast (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 toO(n2). 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.