Source-linked AI summary
All You Need is DAG
Idit Keidar, Eleftherios Kokoris-Kogias, Oded Naor, Alexander Spiegelman
TL;DR
Byzantine Atomic Broadcast needs asynchronous agreement that preserves total order and eventually includes correct processes’ proposals. DAG-Rider builds a reliable-broadcast DAG and locally orders its messages without extra communication. It claims optimal resilience, time, and amortized communication, with post-quantum-safe safety and eventual ordering of correct proposals.
Problem
Byzantine Atomic Broadcast must provide total order, progress, and eventual inclusion of all proposals from correct processes for Byzantine State Machine Replication.
Method
DAG-Rider reliably broadcasts proposals into a structured DAG, then processes locally observe their DAGs and order delivered messages without extra communication.
Results
DAG-Rider is presented as the first asynchronous BAB protocol with optimal resilience, optimal round complexity, and optimal amortized communication complexity.
Takeaways & Limitations
All proposed values from correct processes are eventually ordered, while the protocol's safety can be post-quantum secure without relying on asymmetric cryptographic assumptions.
Takeaways & Limitations
The communication analysis assumes round numbers fit in a constant number of bits and that the DAG never reaches round number 2^128.
Abstract
from arXiv · showhide
We present DAG-Rider, the first asynchronous Byzantine Atomic Broadcast protocol that achieves optimal resilience, optimal amortized communication complexity, and optimal time complexity. DAG-Rider is post-quantum safe and ensures that all messages proposed by correct processes eventually get decided. We construct DAG-Rider in two layers: In the first layer, processes reliably broadcast their proposals and build a structured Directed Acyclic Graph (DAG) of the communication among them. In the second layer, processes locally observe their DAGs and totally order all proposals with no extra communication.
1 INTRODUCTION
DAG-Rider addresses Byzantine Atomic Broadcast for scalable Byzantine SMR by combining reliable-broadcast communication with local DAG ordering. It claims optimal resilience, time, and amortized communication, while eventually ordering all proposals from correct processes.
- Byzantine Atomic Broadcast requires total order, progress, and eventual inclusion of all proposals from correct processes.
- DAG-Rider is presented as the first asynchronous BAB protocol with optimal resilience, optimal round complexity, and optimal amortized communication complexity.Its safety properties are post-quantum secure under the stated coin implementation.
- DAG-Rider uses reliable broadcast to build a DAG, then locally orders delivered messages without extra communication.Processes use one coin flip per O(n) decisions on values proposed by different processes.
- O(n^3) communication per decision arises with Bracha broadcast, while a probabilistic-progress alternative reduces this to O(n^2 log(n)).
- O(n) amortized communication is achieved by batching O(n log(n)) proposals with asynchronous verifiable information dispersal.
- DAG-Rider separates communication from ordering logic, supports broadcast-dependent trade-offs, and keeps detailed ordering pseudocode under 30 lines.
2 MODEL AND BUILDING BLOCKS
The model has n = 3f + 1 asynchronous processes with fewer than n/3 Byzantine faults and an adaptive adversary. DAG-Rider relies on reliable rebroadcast and a delayed global perfect coin.
- The system contains n = 3f + 1 processes, with up to f < n/3 Byzantine processes and reliable links between correct processes.Communication is asynchronous, and the adversary may adaptively corrupt up to f processes.
- Efficient gossip and asynchronous verifiable information dispersal instantiate reliable broadcast with subquadratic communication or batching support.
- Reliable rebroadcast provides agreement, integrity, and validity for messages associated with senders and rounds.Agreement and validity hold with probability 1 under the defined abstraction.
- The global perfect coin gives correct processes a common leader, eventual termination after f + 1 invocations, unpredictability, and fair probability 1/n.
- A threshold-signature implementation can realize the global perfect coin using an (f + 1)-of-n threshold.
3 PROBLEM DEFINITION
Byzantine Atomic Broadcast lets processes agree on an ordered sequence of messages for state machine replication. Its specification combines reliable broadcast properties with total order and eventual inclusion requirements.
- BAB allows processes to agree on a sequence of messages for State Machine Replication.
- Asynchronous BAB cannot be solved deterministically because of FLP, so the protocol uses a global perfect coin for liveness with probability 1.
- Total order requires every correct process to deliver messages in the same relative order.
- BAB separates transaction sequencing and execution: BAB orders transactions, while an execution engine validates them before applying them.
- BAB requires all messages broadcast by correct processes to be eventually ordered and provides chain quality of at least (f + 1)r correct broadcasts in prefixes of size (2f + 1)r.
- Communication is measured in bits sent by honest processes per ordered transaction, with asynchronous time defined using message-delay units.
4 DAG ABSTRACTION
DAG-Rider represents reliable-broadcast messages and their references as a DAG whose rounds and edges organize communication. Strong edges support progression and ordering, while weak edges preserve eventual inclusion.
- DAG abstraction: Each DAG vertex represents a reliable-broadcast message with a source, round, transaction block, strong edges, and weak edges.
- DAG abstraction: Each local DAG view records round-indexed vertices, with at most n vertices per round and distinct sources.Reliable broadcast prevents a process from generating two vertices in the same round.
- DAG abstraction: Every vertex has at least 2f + 1 strong edges to the previous round and up to f weak edges to earlier rounds lacking another path.
- DAG construction: The path and strong_path utilities distinguish paths using all edges from paths using only strong edges.
- DAG construction: A delivered vertex enters a buffer after verification, and it joins the DAG once all vertices referenced by its strong or weak edges are present.
- DAG construction: Processes advance rounds after collecting at least 2f + 1 current-round vertices and reliably broadcast a new vertex containing a queued transaction block.
- DAG construction: Weak edges connect orphan vertices that otherwise lack a path, ensuring delayed vertices can still enter the total order and satisfy BAB validity.
5 DAG-RIDER: DAG-BASED ASYNCHRONOUS BAB PROTOCOL
DAG-Rider combines a four-round wave structure, randomized leader selection, and a commit rule to order proposals from locally observed DAGs. Strong paths ensure consistent leader ordering, while reliable broadcast and the global coin provide agreement and expected constant-wave progress.
- Protocol overview: DAG-Rider equips a local DAG with a global perfect coin so processes can decide delivery order without extra communication.Each process observes its local DAG and deduces which transaction blocks to deliver and in what order.
- Wave structure: Each wave contains four consecutive DAG rounds, and a process completes a wave after its fourth round has at least 2f+1 vertices.The kth round of wave w is round(w,k) = 4(w−1) + k.
- Leader commitment: The protocol retrospectively selects a wave leader with the global coin and commits it when at least 2f+1 vertices in the fourth round have a strong path to it.If the leader is absent or lacks the required strong paths, the process commits no leader for that wave.
- Total ordering: When a committed leader has strong paths to earlier uncommitted leaders, those leaders are committed and ordered before it.The protocol checks preceding waves recursively, using strong paths to determine which leaders may have been committed by other processes.
- Agreement: Lemma 1 states that every later-wave leader visible to any correct process has a strong path to a previously committed leader.This property ensures that processes commit the same waves’ leaders and thereby satisfy agreement.
- Liveness: Correct processes commit a leader with probability at least 2/3−ε per wave and therefore commit every 3/2 waves in expectation.The coin is invoked after wave completion, limiting the adversary’s ability to predict the leader before the relevant DAG set is fixed.
- Delivery: Once leaders are ordered, processes deterministically deliver previously undelivered transaction blocks in their leaders’ causal histories.Reliable broadcast gives common causal histories for vertices shared by correct processes.
6 ANALYSIS
DAG-Rider’s analysis establishes the BAB properties and shows that its structured DAG supports efficient ordering of many correct-process proposals.
- Correctness: DAG-Rider satisfies integrity, total order, agreement, and validity for Byzantine Atomic Broadcast.The protocol also guarantees that every vertex broadcast by a correct process eventually enters all correct processes’ DAGs.
- Correctness: Every vertex added to one correct process’s DAG is eventually added to every other correct process’s DAG.Reliable broadcast agreement and quorum-based DAG checks preserve common vertices across correct processes.
- Correctness: At most one vertex is selected as the leader of any wave by all correct processes, and committed waves occur in increasing wave order.The global perfect coin gives a common process choice, while stack operations enforce increasing committed-wave numbers.
- Correctness: 2f + 1 vertices in an earlier wave and 2f + 1 vertices in a later wave are connected by strong paths when a process completes the wave.This common-core structure underpins the protocol’s leader and total-order reasoning.
- Complexity: 3/2 + 𝜖 is an upper bound on the expected number of waves until the commit rule is met.Because each wave has constant-size message chains, the expected number of time units between commits is constant, and each commit includes at least O(n) correct-process proposals.
- Complexity: O(n) is DAG-Rider’s amortized communication complexity.A round costs O(n^3 log(n)) bits while ordering O(n^2 log(n)) values, yielding the stated amortized bound.
7 RELATED WORK
Prior asynchronous Byzantine protocols explored randomized consensus, cryptographic and information-theoretic assumptions, and communication DAGs, but existing alternatives had higher complexity or inefficiencies.
- Asynchronous Byzantine Agreement: Early asynchronous Byzantine Agreement protocols used randomization to bypass FLP impossibility but had exponential communication and time complexity.Later work pursued lower complexity under information-theoretic or computational assumptions.
- Byzantine Atomic Broadcast: Other Byzantine Atomic Broadcast protocols use cryptographic safety, signatures-free designs, or failure detectors, but have higher expected communication complexity.These approaches differ in their assumptions and mechanisms while remaining less communication-efficient than DAG-Rider according to the paper.
- DAG-based protocols: HashGraph and Aleph realize communication-DAG interpretation in Byzantine settings, but HashGraph uses an unstructured DAG and an inefficient binary agreement protocol.The cited comparison associates HashGraph with expected exponential time complexity.
8 CONCLUSION
DAG-Rider is presented as an asynchronous Byzantine Atomic Broadcast protocol combining optimal complexity with safety that does not rely on cryptographic assumptions.
- Conclusion: DAG-Rider achieves optimal resilience, optimal amortized communication complexity, and optimal time complexity.The conclusion also highlights perfect load balancing and modular separation of concerns as design features.
- Conclusion: Reliable broadcast makes all correct processes eventually see the same DAG, ruling out Byzantine equivocation for safety.The authors identify this as the basis for avoiding cryptographic assumptions for safety.