DAG-BFT Consensus

UltraDAG uses a DAG-based Byzantine Fault Tolerant consensus protocol. This page provides a technical deep dive into vertex production, finality, ordering, and pruning.

System Model

Validators

The protocol operates with a set of up to 100 active validators, each identified by an Ed25519 public key and weighted by effective stake. Validators produce DAG vertices containing transactions and references to parent vertices.

BFT Fault Model

UltraDAG assumes the standard BFT fault threshold:

$$ n \geq 3f + 1 $$

Where $n$ is the total number of validators and $f$ is the maximum number of Byzantine (arbitrarily faulty) validators. With 100 validators, the protocol tolerates up to 33 Byzantine validators.

Partial Synchrony

The protocol operates under partial synchrony — there exists an unknown Global Stabilization Time (GST) after which all messages between honest validators are delivered within a known bound $\Delta$. Before GST, no timing guarantees are made. Safety holds regardless of timing; liveness requires eventual synchrony.

DagVertex Structure

Each vertex in the DAG contains:

struct DagVertex {
    block: Block,                    // Contains coinbase + transactions
    parent_hashes: Vec<[u8; 32]>,   // Parent vertex hashes (up to MAX_PARENTS)
    round: u64,                      // Monotonically increasing round number
    validator: Address,              // Address of the producing validator
    pub_key: [u8; 32],              // Ed25519 public key of the producer
    signature: Signature,            // Ed25519 signature over signable_bytes()
    topo_level: u64,                 // Computed on insert, not serialized
    // Note: timestamp lives in block.header.timestamp (i64)
}

Round-Based Vertex Production

Vertices are produced in rounds. Each round, every active validator produces exactly one vertex.

Round Advancement

A validator advances to round $r+1$ when either condition is met:

1. Optimistic gate: received vertices from $\geq 2f+1$ validators for round $r$
2. Timer gate: round timer expires (default: 5 seconds)

Round advancement flow: from Round r, a validator advances to Round r+1 either when 2f+1 vertices are received or the timer expires, then produces a vertex for r+1 and broadcasts it to peers.

The optimistic gate enables responsive finality — when the network is healthy, rounds advance as fast as messages propagate, without waiting for the full timer. Under poor network conditions, the timer ensures progress.

Parent Selection

When producing a vertex for round $r+1$, the validator selects parents from round $r$ vertices:

1. Scoring: each candidate parent is scored using blake3(proposer || candidate_hash)
2. Selection: top K_PARENTS (default: 32) by score, capped at MAX_PARENTS (64)
3. Determinism: the Blake3 scoring ensures all honest validators select similar parent sets

Finality

Finality Condition

A vertex $v$ from round $r$ is finalized when more than 2/3 of known validators (by count, not stake) have $v$ as an ancestor. The threshold is ceil(2n/3) where $n$ is the number of known validators. Formally:

$$ \text{finalized}(v) \iff |{i : v \in \text{ancestors}(v_i)}| \geq \lceil 2n/3 \rceil $$

Implementation: BitVec Coverage

Tracking ancestry naively would require traversing the full DAG for each vertex. UltraDAG uses a BitVec-based optimization stored on BlockDag.descendant_validators (a HashMap<Hash, BitVec> with ValidatorIndex for Address <-> usize mapping) for O(1) amortized coverage checking:

1. Each vertex has an associated BitVec of length $n$ (validator count), stored in BlockDag.descendant_validators
2. When validator $i$ produces a vertex with $v$ as an ancestor, bit $i$ is set
3. A vertex is finalized when the count of set bits reaches ceil(2n/3) (checked via count_ones())
4. BitVec inheritance: when a new vertex is inserted, its parents’ BitVecs are updated via BFS upward through ancestors

This makes finality checking constant-time per vertex, regardless of DAG depth.

2-Round Finality

Under normal conditions (all validators honest and online), finality is achieved in 2 rounds:

1. Round $r$: Validator $A$ produces vertex $v$
2. Round $r+1$: All other validators include $v$ (or a descendant) as a parent. After this round, $v$ has >2/3 coverage and is finalized.

At 5-second rounds, this yields ~10 second finality.

The diagram shows 4 validators (Alice, Bob, Carol, Dave) each producing a vertex in Round r. In Round r+1, each validator produces a new vertex referencing multiple parents from Round r. After Round r+1, all Round r vertices have coverage from all 4 validators and are finalized.

Deterministic Ordering

Finalized vertices must be applied to the state engine in a deterministic order agreed upon by all honest validators. UltraDAG uses a simple total ordering:

$$ \text{order}(v_1, v_2) = \text{compare}((v_1.\text{round}, v_1.\text{hash}), (v_2.\text{round}, v_2.\text{hash})) $$

1. Sort by round (ascending)
2. Break ties by vertex hash (lexicographic, ascending)

This ordering is:

• Deterministic: depends only on vertex content, not arrival order
• Unique: Blake3 hashes are collision-resistant
• Fair: hash-based tiebreaking doesn’t favor any particular validator

Equivocation Detection

A validator equivocates if it produces two different vertices for the same round. UltraDAG detects and penalizes equivocation:

Detection

When a node receives a vertex for round $r$ from validator $V$, and already has a different vertex from $V$ for round $r$:

1. Both vertices are retained as equivocation evidence
2. Evidence is gossiped to all peers
3. Once finalized, the evidence triggers deterministic slashing

Slashing

Upon finalized equivocation evidence:

• 50% of the equivocating validator’s stake is burned (removed from total supply)
• The slash percentage is governable (range: 10-100%)
• Delegators to the slashed validator also lose proportionally
• The validator is removed from the active set

Pruning

To keep storage bounded, UltraDAG prunes old DAG vertices:

Pruning Horizon

Vertices older than current_round - PRUNING_HORIZON are eligible for pruning.

Safety Guarantee

Pruning only removes vertices that are deeply finalized — finalized for at least PRUNING_HORIZON rounds. This ensures:

1. No honest validator will ever need a pruned vertex for parent selection
2. No sync request will reference a pruned vertex (checkpoints cover the gap)
3. State derived from pruned vertices is already persisted in the state database

Pruning Process

1. Every 50 rounds in the validator loop, check if any vertices fall below the pruning horizon
2. Remove eligible vertices from the in-memory BlockDag
3. The redb state database retains the computed state — no data loss

Protocol Parameters

Next Steps

• P2P Network — how vertices are propagated
• State Engine — how finalized vertices become account state
• Formal Verification — TLA+ proof of safety properties