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.
| Aspect | GHOSTDAG | Ashwa (Sahyadri) |
|---|---|---|
| Ordering primitive | Blue set size + k-cluster | Depth + cumulative work + hash |
| Parent selection | Typically 1-2 parents | Multiple parents via parents_by_level |
| Depth metric | Blue score (blue set size) | Longest path from genesis |
| Work metric | Blue work (accumulated PoW in blue set) | Sum of ancestor difficulty |
| Tie-breaking | Hash | Hash |
| k parameter | Yes (18 typical) | Not present in ordering rule |
| Multi-parent compression | No | parents_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
| Property | Longest-chain (Nakamoto) | Ashwa (Sahyadri) |
|---|---|---|
| Orphan blocks | Present (competing blocks discarded) | None (all valid blocks enter DAG) |
| Ordering | Longest chain wins | Deterministic function of DAG |
| Finality | Probabilistic — probability decreases with depth | Threshold — crossed once, deterministic |
| Parallel block production | Discouraged (waste) | Encouraged (all blocks contribute) |
| Work waste | Orphaned work is wasted | All work contributes to cumulative weight |
| Throughput | Limited by block interval | Scales 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.