UTXO commitment at scale: measured costs of the sparse-tree engine

This page reproduces docs/UTXO-COMMITMENT-SCALE.md from qanum-core v0.9.0 (release tag). Links to files that are not published on this site are shown as plain text until the source repository is public.

Status: measured 2026-10-19, after the rework of the sparse-tree cache (branch nodes only, a chain memo per coin). It replaces the results of 2026-09-17, whose per-block figure did not hold as the set grew (§3). Harness: tests/utxo_commitment_scale_benchmark.rs (manual #[ignore], release build). Hardware: the development machine, an aarch64 SoC (the ARM build machine of benchmarks/2026-10-14_arm), pinned to one Gold core (taskset -c 6, CPU part 0xd0d), one heavy job at a time.

1. What is measured

For each set size N:

• chainstate B/entry: UtxoSet in RAM;
• growth: the cache warms as a chain grows, in blocks of 800 outputs;
• cache B/entry at N: leaf map (leaf hash and chain memo per coin) plus the bounded node cache, RSS delta with the UtxoSet growth subtracted;
• steady delta: apply_block_root_delta on a warm cache, with the hashes per block and the cached nodes. The block shape is set by QANUM_UTXO_SCALE_INPUTS / QANUM_UTXO_SCALE_OUTPUTS (default 800 / 800);
• reconstructive compute_utxo_root: the per-block cost without a cache, and the bit-exact oracle (delta == reconstructive is asserted);
• cold-cache probe: at N = 20 000, a full rehydrate and the journal of a delta on a cold cache (§6).

2. Results

415 in / 830 out is a full level-5 block: at most 415 ML-DSA-87 spends fit the authorization limit, here as payments of one input and two outputs.

• Cache: 194 B per coin at N = 500 000 (run started at 500k); chainstate 189 to 192 B per coin. In the run that measured 100k first, the 500k case reuses freed memory, so its RSS deltas are not meaningful.
• Equivalence held at every size.
• Cold-cache probe (N = 20 000): rehydrate 4 287 ms; a cold delta journaled 19 entries for one touched leaf (bound 256).

3. How the delta is computed

The tree has 256 levels, so each coin sits under a chain of about 240 single-child nodes. Until this revision the cache stored every node it visited, chain nodes included, against a cap of 250 000 nodes, and pruned everything at depth 16 or more when full: several times per block at 100 000 coins and above. The untouched subtrees next to every touched path were then recomputed, so the work grew with N. On this machine (unpinned) a block of 800 in / 800 out cost 1.2 s at 100 000 coins and 5.4 s at 500 000 (5.8 M hashes). The run of 2026-09-17 on an EPYC VPS measured 4.3 s at 500 000 and read it as O(block); it was not.

Now:

• a subtree with one coin is hashed in one loop and never cached; the cache keeps branch nodes and the root;
• each coin keeps a memo of its chain hash at depth 64 (or deeper when needed), about 34 more bytes per coin (measured), so a single-coin neighbour costs about 45 hashes instead of about 240;
• when full, the cache drops its deepest nodes first, down to three quarters of the cap (default MAX_SPARSE_CACHE_NODES = 250 000, settable with set_max_nodes).

A set of N coins has about 1.44 N cached nodes (144 499 at 100 000). Past about 170 000 coins the default cap no longer holds them all, the deepest are dropped and the small subtrees under them are recomputed from the chain memos: that is the step from 305 ms to 612 ms between 100 000 and 500 000. With a cap of 2 N, an unpinned probe measured 335 ms at 500 000, for about 100 to 145 more bytes per coin.

4. Findings

1. The incremental engine is a requirement. On this core the reconstructive engine costs 28.2 s at 100 000 coins and 137.6 s at 500 000 (linear in N) and exceeds the 75 s block interval at about 270 000 coins. Every path without a cache pays it per block (§5). With several cores the full recomputation divides by about the number of cores (§5), but stays linear in N.
2. The steady delta stays well inside the interval: 0.53 to 0.61 s for a full block at 500 000 coins, under 1 % of 75 s. It still grows slowly with N while the node cache cannot hold every branch node (§3). No extrapolation is given; 1 M has not been measured.
3. Memory: peak RSS 300 MB at 500 000 coins, against 600 MB on 2026-09-17 (other hardware; the drop comes from not caching chain nodes). Leaf map plus node cache: about 194 B per coin.
4. Equivalence is intact at every measured size.

5. Cold paths

A cold cache costs a full recomputation: rehydrate at startup (ChainManager::warm_sparse_cache) and after the cache is cleared, and the paths that carry no cache (rebuilds from the block store, the template fallback canonical_template_utxo_root, tests), which compute the whole root for each block. Both run on one engine: the 256 subtrees one key byte deep are hashed on scoped threads (at most 8; one thread below 16 384 coins) and the 8 levels above them on the calling thread. The bytes are those of the one-thread recursion (compute_utxo_root_reference, checked by tests at every thread count).

On this machine, 6 cores, not pinned, at 500 000 coins: rehydrate 20.1 s (106 s on one thread), compute_utxo_root 19.6 s (142.0 s with the one-thread recursion). The number of hashes does not change (about 237 per coin); only the wall clock does.

6. Transient memory of a cold traversal

A cold traversal (rehydrate, or a delta or template preview with no cached nodes) holds the leaf map (§4, finding 3), a sorted list of the leaves while the map is built (about 100 B per coin, freed before the walk), one reference per coin during the walk (40 B) and the node cache, bounded by its cap; each thread keeps at most its share of the cap. rehydrate journals nothing; a delta journals only the nodes above a touched leaf, at most 256 per leaf (19 for one leaf in the probe). A design that journals every visited node needs about 242 entries (about 16 KB) per coin: an earlier harness measured about 4 GB RSS when rehydrating 250 000 coins, and the OS killed the 1 M attempt. Anyone who pays fees can grow the UTXO set, so the bound protects every node that restarts.

cold_cache_delta_journals_only_the_touched_path and rollback_keeps_untouched_nodes_valid (tests/sparse_tree_cache.rs) lock the bound and the soundness of a revert. warm_delta_work_is_bounded_by_the_touched_paths and tiny_node_cap_keeps_roots_and_exact_reverts (src/sparse_tree_cache.rs) bound the work of a warm delta and check roots and reverts with a 16-node cap.

7. Reproduction

cargo test --release --test utxo_commitment_scale_benchmark --no-run
# full blocks of 800 in / 800 out at 100k and 500k:
QANUM_UTXO_SCALE_SIZES=100000,500000 taskset -c 6 \
  cargo test --release --test utxo_commitment_scale_benchmark -- \
  --ignored --nocapture --test-threads=1
# full level-5 blocks at 500k:
QANUM_UTXO_SCALE_SIZES=500000 QANUM_UTXO_SCALE_INPUTS=415 \
  QANUM_UTXO_SCALE_OUTPUTS=830 taskset -c 6 \
  cargo test --release --test utxo_commitment_scale_benchmark -- \
  --ignored --nocapture --test-threads=1

The first command took 409 s on this core (growth to 500 000 in 600 blocks, then the reconstructive reference); the second 344 s.