Introduction
Byzantine consensus is the foundational technology for modern blockchains, enabling distributed networks to reach agreement despite malicious nodes. However, a significant gap remains between theoretical efficiency and practical implementation, particularly regarding bit complexity—the total volume of data transmitted. As transaction batches ($L$) grow larger, the communication overhead often becomes a bottleneck.
The Problem: The "Curse of GST"
In partially synchronous networks, the transition to stability is marked by Global Stabilization Time (GST). The authors identify a phenomenon called the "Curse of GST": an adversary can manipulate network timing so that multiple leaders broadcast large values simultaneously just as the network stabilizes. This results in a worst-case bit complexity of $O(n^2L)$, far exceeding the theoretical lower bound of $\Omega(nL + n^2)$.
The DARE Architecture
To address this, the authors propose DARE (Disperse, Agree, REtrieve). This framework decouples the dispersal of data from the consensus on its identity.
The DARE protocol operates in three distinct phases:
- Dispersal: Leaders attempt to disperse their proposals using a "view synchronizer" and staggered broadcast rates. This prevents adversarial timing from overwhelming the network.
- Agreement: Once a value is successfully dispersed and a threshold signature (proof of dispersal) is obtained, nodes run consensus on only the hash of the value ($O(\kappa)$ bits).
- Retrieval: Nodes use the agreed-upon hash and dispersal proof to reconstruct the original large value.
Leveraging STARKs for Efficiency
The protocol is further optimized in DARE-Stark by integrating STARKs (Succinct Transparent ARguments of Knowledge). While typically used for privacy, STARKs here provide succinctness. A leader provides a tiny proof that a large value is valid and its erasure-coded shards are correct, drastically reducing the data sent during dispersal.
Key Results and Comparison
DARE-Stark achieves a near-optimal bit complexity of $O(nL + n^2 \kappa)$, matching the efficiency of a simple best-effort broadcast while maintaining $O(n)$ worst-case latency.
As shown in the table above, DARE and DARE-Stark significantly improve upon previous state-of-the-art protocols like HotStuff and PBFT for large values of $L$. DARE achieves $O(n^{1.5}L + n^{2.5}\kappa)$, while DARE-Stark reaches the near-optimal $O(nL + n^2\kappa)$ bound.
Conclusion
DARE and DARE-Stark demonstrate that the $O(n^2L)$ bottleneck is not an inherent limitation of consensus. By separating concerns and utilizing succinct proofs, these algorithms pave the way for more scalable blockchain architectures. While STARKs introduce computational overhead, their bandwidth benefits for large transaction batches are substantial.
Summary updated