Ashwa Consensus

The DAG ordering algorithm. Converts a partial order of parallel blocks into a canonical total order using depth, cumulative work, and hash tie-breaking. Deterministic across nodes, no voting, no committee, no proposer lottery.

1. What Ashwa Does

A DAG gives a partial order. Blocks can be ancestors or descendants of each other, or neither. To execute transactions, the network needs a total order: a sequence in which every pair of blocks has a definite relative position.

Ashwa Consensus is the function that produces this total order. It takes the DAG as input and produces a canonical sequence. Two honest nodes with the same DAG view compute the same sequence — bit-for-bit.

Ashwa : 𝒢 → 𝒮

  𝒢 = (V, ≺_h)     DAG of valid blocks
  𝒮               canonical total order over V

  For every pair b_i, b_j ∈ V:
    Ashwa determines exactly one of:
      b_i ≺_ord b_j    (b_i comes first)
      b_j ≺_ord b_i    (b_j comes first)
      b_i = b_j        (identical blocks)

  No pair is left undecided. The output is a strict total order.

2. What Kaspa's GHOSTDAG Does

GHOSTDAG is the most cited DAG ordering algorithm, used by Kaspa. It works by computing a k-cluster of each block — a set of blocks that are "close" in the DAG — and ordering blocks by their blue set size (the number of blocks in the most-connected subgraph reachable from them).

GHOSTDAG (Kaspa) sketch:

  1. For each block b, compute blue_set(b):
       - Blue set starts as ancestors(b)
       - Blocks within distance k of the blue set's "blue score" boundary
         are added to the blue set
       - k is a protocol parameter (typically 18 for Kaspa)

  2. Order blocks by blue score:
       blue_score(b) = |blue_set(b)|

  3. Ties broken by hash.

  Key idea: blue score ≈ "how much well-connected work is
  behind this block." Blocks with more deep-connectivity come
  first.

  k controls the trade-off between safety (larger k = more
  conservative) and liveness (smaller k = faster finality).

3. How Ashwa Differs

Ashwa Consensus and GHOSTDAG share the goal (canonical DAG ordering), but differ in the specific ordering rule and the underlying DAG shape. The differences are structural, not cosmetic.

AspectGHOSTDAGAshwa (Sahyadri)
Ordering primitiveBlue set size + k-clusterDepth + cumulative work + hash
Parent selectionTypically 1-2 parentsMultiple parents via parents_by_level
Depth metricBlue score (blue set size)Longest path from genesis
Work metricBlue work (accumulated PoW in blue set)Sum of ancestor difficulty
Tie-breakingHashHash
k parameterYes (18 typical)Not present in ordering rule
Multi-parent compressionNoparents_by_level field

The most significant difference is the parent model. GHOSTDAG blocks typically reference 1-2 parents and derive ordering from a k-cluster analysis. Ashwa blocks reference multiple parents per level, stored in a compressed parents_by_level structure, and derive ordering from depth plus cumulative work.

4. Formal Ordering Rule

The Ashwa ordering rule is stated as a function of three quantities computed from the DAG. No parameter, no cluster, no external input.

Definitions:

  depth(b) = length of the longest path from genesis to b
             (in number of blocks)

  W(b)     = d(b) + Σ_{p ∈ parents(b)} W(p)

    where d(b) is block b's own difficulty
    W(b) is the sum of difficulties over the entire ancestor
    closure of b

  hash(b)  = SHA3-256(block_header_bytes)

Ordering relation:

  For blocks b_i ≠ b_j ∈ V:

    b_i ≺_ord b_j  ⟺
        depth(b_i) < depth(b_j)
      ∨ ( depth(b_i) = depth(b_j)
          ∧ W(b_i) > W(b_j) )
      ∨ ( depth(b_i) = depth(b_j)
          ∧ W(b_i) = W(b_j)
          ∧ hash(b_i) < hash(b_j) )

Property (Total order):

  The relation ≺_ord is:
    - Irreflexive:  ¬(b ≺_ord b)
    - Asymmetric:   b_i ≺_ord b_j ⟹ ¬(b_j ≺_ord b_i)
    - Transitive:   b_i ≺_ord b_j ∧ b_j ≺_ord b_k ⟹ b_i ≺_ord b_k

  Every pair of distinct blocks has exactly one relation.

5. Why This Ordering

Three design decisions explain the ordering rule. Each addresses a specific property that a DAG-native chain requires.

Design choice 1: Depth first

  Deeper blocks have more history behind them. Ordering them first
  ensures that a block is never ordered before any of its ancestors.
  This is the "causal consistency" property.

  Without depth-first: a shallow block could be ordered before its
  ancestor, breaking causality.

Design choice 2: Cumulative work second

  Among blocks at the same depth, the one with more total work in its
  ancestry is "more secure" — it is harder to reorg out. Ordering by
  work ensures that the most-secured block comes first.

  Without work-based tie-breaking: parallel blocks at the same depth
  would have arbitrary relative order, and the network would have to
  rely on hash ties too often.

Design choice 3: Hash third

  When depth and work are equal, hash provides a deterministic tie-
  break. Any node computing SHA3-256 over the same header arrives
  at the same result. No randomness, no external input.

  Without hash tie-break: some pairs of blocks would be unordered,
  and the total order would not exist.

6. Finality

Finality is not a separate algorithm in Ashwa — it follows directly from cumulative work. A block is final when its work is large enough that no plausible adversary could produce a competing chain.

Definition 6.1 (Finality)

  final(b)  ⟺  W(b) > W_adversary / ε

  where:
    W_adversary = total work an adversary can produce
    ε           = protocol safety margin

  Because W(b) monotonically grows as more blocks reference b,
  finality is a threshold that is crossed once and stays crossed.

Reorg probability:

  Let α = adversary hash rate fraction, β = 1 - α, α < β.

    Pr[reorg(k)] ≤ (α / β)^k

  where k is block depth behind the finalized block.

  Sample values (α = 0.30, β = 0.70):
    k = 3:   Pr ≤ 0.079
    k = 6:   Pr ≤ 0.0066
    k = 12:  Pr ≤ 4.3e-5
    k = 24:  Pr ≤ 1.9e-9

  The bound decays geometrically. Each additional block multiplies
  the required attacker work by 1/(α/β).

7. Determinism Guarantee

Two honest nodes with the same DAG compute identical orderings. This is the property that makes Ashwa safe in a distributed setting.

Claim 7.1 (Determinism)

  For any two honest nodes A, B:

    view_A = view_B  ⟹  order_A = order_B

  Proof sketch:

    The ordering is a function of three quantities computed
    from the DAG alone:

      depth(b)  — determined by the DAG structure
      W(b)      — determined by the DAG structure and header bits
      hash(b)   — determined by the block header bytes

    None of these depend on node state, wall-clock time, or
    network position. Two nodes with the same DAG compute the
    same three values for every block.

    The lexicographic combination of the three values
    determines the ordering. Same inputs → same ordering.

8. Network Partitions

During a network partition, both sides continue producing blocks. When the partition heals, both DAGs merge and Ashwa orders the merged graph.

Partition scenario:

  Group A produces DAG_A during partition.
  Group B produces DAG_B during partition.

  After heal:
    DAG_merged = DAG_A ∪ DAG_B

  Ashwa applies to DAG_merged. All blocks enter the canonical
  order. No block is discarded.

  Transaction handling:
    Duplicate transactions (same flash_id) — replay protection
    rejects the second application.

    Conflicting transactions (same balance spent twice in
    different blocks) — both enter the canonical order, but the
    second one fails balance validation and is dropped at
    execution time.

  This differs from a linear chain, where one side of the
  partition must be discarded.

9. Comparison with Longest-Chain Consensus

PropertyLongest-chain (Nakamoto)Ashwa (Sahyadri)
Orphan blocksPresent (competing blocks discarded)None (all valid blocks enter DAG)
OrderingLongest chain winsDeterministic function of DAG
FinalityProbabilistic — probability decreases with depthThreshold — crossed once, deterministic
Parallel block productionDiscouraged (waste)Encouraged (all blocks contribute)
Work wasteOrphaned work is wastedAll work contributes to cumulative weight
ThroughputLimited by block intervalScales with parallelism

10. Implementation

Ashwa runs as part of block validation. Every node runs it locally, with no coordination required. The ordering function is computed from block headers alone.

Header fields used by Ashwa:

  pub struct Header {
      parents_by_level: CompressedParents,  // DAG ancestors
      bits:             u32,                // difficulty (for W(b))
      blue_work:        BlueWorkType,       // cumulative work cache
      blue_score:       u64,                // blue set size cache
      daa_score:        u64,                // DAA score
      ...
  }

  parents_by_level: Compressed multi-level parent references
  bits:             Per-block difficulty from the header
  blue_work:        Cached cumulative work (recomputable from parents)
  blue_score:       Cached blue set size

Ordering procedure (per new header):

  1. Fetch parents from parents_by_level
  2. Compute depth(b) = max(depth(parent)) + 1
  3. Compute W(b) = bits_to_difficulty(bits) + Σ W(parent)
  4. Compare against existing blocks at the same depth using the
     ordering rule (depth, W, hash)
  5. Insert b into the canonical order at the correct position

  No global state. No coordination. No voting. Just arithmetic.

11. Limitations

Limitation 11.1: Depth as a proxy

  Depth (longest path from genesis) is a proxy for "amount of
  history." It is not a perfect measure — a block with many
  short parents may have less total work than a block with one
  long parent. This is why work is the second tie-breaker.

Limitation 11.2: No k-cluster protection

  GHOSTDAG uses a k-parameter to prevent deep DAG attacks where
  an adversary builds a long parallel chain. Ashwa's simpler
  ordering may be more vulnerable to such attacks at very high
  adversarial hash rates.

  In practice, honest-majority assumption (α < β) makes this
  infeasible. The concern is theoretical, not operational.

Limitation 11.3: Reorg cost grows with depth

  A reorg at depth k invalidates all chain proofs at depths > k.
  The chain proof must be rebuilt from the reorg point forward.

  Reorg depth is typically small (< 5 blocks), so rebuild cost
  is bounded. But the invariant "chain proof always covers
  full chain" requires the rebuild.

Limitation 11.4: Assumes synchronized clocks (weakly)

  The DAA score adjustment assumes timestamps are roughly
  accurate. A large timestamp manipulation could distort
  difficulty adjustment. The current implementation validates
  timestamps against a parent-relative window; extreme
  manipulation is rejected.

Limitation 11.5: No formal proof of optimality

  Ashwa's ordering rule is designed to satisfy the three
  properties in Section 5 (causal consistency, work priority,
  determinism). It is not proven optimal against arbitrary
  adversarial DAGs. A more sophisticated ordering might
  achieve better properties at the cost of complexity.
  Sahyadri chooses simplicity for verifiability.

12. Summary

Ashwa Consensus is Sahyadri's DAG ordering algorithm. It converts a partial order of parallel blocks into a canonical total order using three quantities: depth, cumulative work, and hash. Two honest nodes with the same DAG compute identical orderings — no voting, no committee, no parameter.

Compared to GHOSTDAG, Ashwa uses multi-parent blocks (parents_by_level) and a simpler ordering rule (depth first, work second, hash third) without a k-cluster parameter. The trade-off is simplicity and verifiability versus GHOSTDAG's stronger formal guarantees against adversarial DAG construction.

Finality is a threshold: a block is final when its cumulative work exceeds what an adversary could produce. Reorg probability decays geometrically with depth. Network partitions merge without discarding work. No orphan blocks. No wasted hash power.

The algorithm is not a new idea — it is a specific instantiation of DAG-based ordering principles adapted to Sahyadri's multi-parent header structure. Its formal properties are what matter: determinism across nodes, threshold finality, and no reliance on any external input.