TL;DR
This paper presents the first Byzantine Broadcast (BB) protocol that achieves expected constant round complexity even when a majority of nodes are corrupt. This is a significant advancement, as previous protocols could only achieve this under honest majority or with a limited number of corruptions. The new protocol achieves this by introducing novel techniques for maintaining a "trust graph" and a "TrustCast" building block, operating under a weakly adaptive adversary model.
What Problem Does This Paper Address?
Byzantine Broadcast (BB) is a fundamental problem in distributed systems where a sender wants to reliably broadcast a message to all other nodes, even if some nodes are malicious (Byzantine) and try to disrupt the process. A key metric for evaluating BB protocols is their "round complexity" – how many rounds of communication are needed to complete the broadcast.
For a long time, it was known that BB can be achieved in expected constant rounds when the majority of nodes are honest. However, the question of whether this constant-round complexity could be achieved when a dishonest majority (more than half the nodes are corrupt) was a major open problem. Previous work showed some progress for corruptions slightly above half (e.g., $f < n/2 + o(n)$), but these results were not applicable to the more general case of a significant dishonest majority (e.g., $f \approx 0.51n$). This paper tackles this long-standing challenge, aiming to achieve expected constant-round BB even when $f > n/2$.
Methods
The paper introduces several novel techniques to achieve their goal:
- Trust Graph Maintenance: Nodes maintain an undirected "trust graph" where an edge $(u, v)$ signifies mutual trust. The protocol ensures that honest nodes always form a clique in each other's trust graphs and that the diameter of these graphs remains small. This is crucial because the round complexity is tied to the diameter. They introduce mechanisms for nodes to remove distrusted parties and edges, even without direct cryptographic evidence, by relying on complaints and collective distrust.
- TrustCast Building Block: This is a novel primitive that weakens full consensus. In TrustCast, a sender aims to propagate a message. An honest node either receives a valid message from the sender or removes the sender from its trust graph. This primitive is designed to work with the trust graph mechanism.
- Weakly Adaptive Adversary Model: The protocol is secure against a "weakly adaptive" adversary. This means the adversary can corrupt nodes at any time and inject messages, but it cannot retroactively remove messages sent by a node before it was corrupted in the same round. This is a slightly weaker model than "strongly adaptive," making the protocol's achievement more significant.
- Epoch-Based Protocol with Leader Election: The protocol proceeds in epochs. Each epoch involves a "Propose" phase (where nodes propose messages), an "Elect" phase (where a leader is chosen using Verifiable Random Functions - VRFs), a "Prepare" phase (where nodes prepare messages based on the leader's charisma), a "Vote" phase, and a "Commit" phase. The use of VRFs for leader election is key to handling adaptive adversaries.
- AckCast Extension: To counter adaptive adversaries, they extend TrustCast to "AckCast." In AckCast, after a sender sends a message, all nodes send an acknowledgment (ACK). This ensures that a valid proposal is not only signed by the sender but also acknowledged by everyone, making it difficult for an adversary to forge a proposal even after corrupting the leader.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- The Diameter of Trust is Key: The paper establishes a direct link between the diameter of honest nodes' trust graphs and the protocol's round complexity. Keeping this diameter small is a primary goal of the trust graph maintenance mechanism.
- Bootstrapping from Weak Primitives: The "TrustCast" primitive is a clever way to build a more complex protocol (Byzantine Broadcast) from a simpler, yet robust, building block. This is a common strategy in distributed systems research.
- Weakly Adaptive is Sufficient for Constant Rounds: The paper demonstrates that achieving constant-round BB under dishonest majority is possible even with the slightly weaker, but more practical, weakly adaptive adversary model. This is a significant result, as many protocols struggle with stronger adaptive adversaries.
- VRFs for Robust Leader Election: The use of Verifiable Random Functions (VRFs) for leader election is crucial for handling adaptive adversaries. VRFs ensure that a leader's identity is not revealed until after they have committed to a proposal, making it harder for the adversary to target and disrupt the process.
Key Results
- First Expected Constant Round BB under Dishonest Majority: The paper presents the first Byzantine Broadcast protocol that achieves expected $O((n/(n-f))^2)$ rounds, even when $f > n/2$. This is a major theoretical breakthrough.
- Security under Weakly Adaptive Adversary: The protocol is proven secure against a weakly adaptive adversary.
- Assumptions: The protocol relies on a trusted setup and the Decisional Linear (DLIN) assumption in bilinear groups.
Limitations and Future Work
- Gap with Lower Bound: While the paper achieves expected constant rounds, there remains an asymptotic gap with the lower bound of $O(n/(n-f))$ rounds proven by Garay et al. for the narrow regime where $n-f = o(n)$. Bridging this gap is identified as an exciting direction for future work.
- Trusted Setup: The protocol requires a trusted setup, and it's an open question whether this assumption can be weakened.
- Strongly Adaptive Adversary: The current protocol does not directly support the strongly adaptive adversary model. A companion work by the authors explores this, achieving polylogarithmic round complexity. It remains an open question whether constant-round BB is possible under a strongly adaptive adversary with 51% corruption.
Summary updated