V4 Octary State Tree

The STARK side of UPP commits every note to a single on-chain Merkle tree. Every shield writes a new leaf, every transfer and withdraw spends one. The geometry of that tree shapes everything about what fits in a transaction — both the cost of a single insert and the maximum size of a useful proof. UPP's STARK tree is 8-ary, depth 11, hashed with Poseidon31.

Octary geometry

Each non-leaf node has 8 children rather than 2, so the tree reaches its capacity in 11 levels rather than 32. Capacity is $8^{11} = 8{,}589{,}934{,}592$ leaves — an order of magnitude beyond any realistic STARK-rail demand (Bitcoin processed roughly 1 billion transactions over its entire history). The headroom isn't a binding constraint, but the depth is. Each insert hashes its way up from the leaf to the root once per level, so the level count is the lever that controls insert cost.

The choice of depth 11 specifically was a margin call: depth 10 (~1.07 B leaves) is uncomfortably close to capacity; depth 12 (68.7 B) pays for one extra permutation per insert with no real benefit. nextIndex is a uint40 (uint32 would saturate well before reaching the full $8^{11}$ leaf space).

hashEight — one absorb, one permutation

Each level squashes 8 child digests into one parent. Poseidon31's sponge rate is 8, so all 8 inputs fit in a single absorb and one permutation produces the parent. No chunking, no extra hashing.

The on-chain Solidity, the off-chain Rust prover, and the SDK's TypeScript mirror all agree on a single Poseidon31 implementation. Cross-pinned constants. Cross-pinned ladder of empty-subtree roots. The AIR enforces the same parent_k = hashEight(children[0..7]) constraint at every level — no chunking allowed, the compiler is not permitted to fold the binding into the children muxes (would push degree past 3).

Each level costs one permutation. The full insert is 11 permutations, top to bottom.

The gas reality

What an insert actually costs on-chain, and why it shapes the API surface:

Three things this chart determines:

1. Shielding is uneventful. ~14M is well under both the per-tx RPC cap (16.77M, see Known Limitations §4) and the block limit. Single transaction, no UX seams.
2. An atomic transfer is unsubmittable from a normal wallet. ~28M comes in below the block limit (so the chain could mine it) but above the 16.77M RPC cap (so every public RPC rejects it before it gets near a miner). That's the awkward middle.
3. Splitting the transfer across two calls — a small commit and one flush per output — fits. Each piece is under the RPC cap. This is the commit/flush split, and it's what every V4 transfer in the demo actually does today.

The next page picks up the thread: how the split works, what the FIFO queue between commit and flush looks like, and why the recipient's note can't be spent until both halves land.

See also

• Commit/flush split — Why a V4 transfer is two transactions, and how the FIFO queue ties them together
• Known Limitations §3 — The user-facing UX cost of the split
• STARK Vault overview — Where the octary tree sits in the broader post-quantum design