set-membership commitment for the registry

A 32-byte commitment to a set of up to 65 536 members, opened by a path of 16 hashes.

A binary hash tree. The root is one field element on chain; a membership proof carries the sibling hash at every level between a leaf and the root — $O(\log n)$ field elements, no more. The verifier learns only that some leaf hashes to the committed root.

Introduced by Merkle in 1989. The structure itself adds no cryptographic assumption beyond the hash it is built from; here, Poseidon2 over $F_r$. The Merkle tree is the carrier — the security level lives in the hash.

concrete instantiation Poseidon2-hashed binary tree over $F_r$, three depth tiers — 8 / 12 / 16 levels for 256 / 4 096 / 65 536 members — membership proof in $O(\log n)$ constraints, locked at group creation.
arity 2
binary tree
Poseidon2
hash at internal nodes
8 / 12 / 16
depth tiers
256 / 4 096 / 65 536
members per tier
O(log n)
witness size

the shape — anatomy of a binary hash tree

Every non-leaf node is the hash of its two children. One root commits to the whole set.

An authentication path from a leaf to the root is the chain of sibling hashes at every level along the way. The prover knows a leaf and a path; the verifier knows only the root. The relation in question is "I know a leaf and a path that hashes to this committed root."

DEPTH 3 · 8 LEAVES · ARITY 2 root C_g level 2 · h = Poseidon2(left, right) level 1 · h = Poseidon2(left, right) level 0 · leaves = Poseidon2(pk, r) C_g h₂₀ WITNESS h₂₁ h₁₀ h₁₁ h₁₂ WITNESS h₁₃ ℓ₀ ℓ₁ ℓ₂ ℓ₃ ℓ₄ ℓ₅ TARGET LEAF ℓ₆ WITNESS ℓ₇ AUTHENTICATION PATH = SIBLING HASH AT EACH LEVEL · 3 HASHES FOR THIS TREE · 32 B EACH
Leaf
Poseidon2(identity_pk, blinding)
One field element. The blinding factor unlinks the leaf from the identity key under collision resistance of Poseidon2.
Internal node
Poseidon2(left, right)
Same arity-2 compression used at every level — the sponge state's $t = 3$ rate-2 shape compresses two children into one parent in a single permutation call.
Root C_g
one field element · 32 bytes on chain
The group commitment. A whole membership set of up to 65 536 members compresses to a single field element under the root commitment.

The path from a leaf to the root is drawn thicker in blue; the sibling at every level — the witness — is badged in amber. Everything else is structurally present but never crosses the chain boundary.

path verifier — interactive

Pick a leaf. The path lights up. The witness is the sibling at each level.

Path verification cost scales with depth, not with membership-set size. Doubling the leaf count adds one level. That's the entire trade.

selected leaf · ℓ · path to root
witness = sibling hashes · one per level · 32 B each
tier
witness size · this tier
bytes
depth × 32 B = × 32
in-circuit constraints · order of magnitude
–
depth × ~50–200 per Poseidon2 call
membership-set size · this tier
2 members ·
trade Path verification cost scales with depth, not with membership-set size. Doubling the leaf count adds one level — one extra hash in the witness, one extra Poseidon2 call in the circuit. The visualisation stays at depth 4; only the counters above change as you pick a tier.

parameters

Concrete numbers.

Pinned by the deployment. Tier choice is fixed at group creation — the tree shape and hash do not change once a group exists.

Tree shape
binary · arity 2
Hash at internal nodes
Poseidon2 over $F_r$
Leaf encoding
Poseidon2(identity_pk, blinding)
Depth · tier 0 / 1 / 2
8 · 12 · 16 levels
Max membership-set size
256 · 4 096 · 65 536 members
Witness size
depth × 32 B · 256 B / 384 B / 512 B
Update relation cost dominator
path verification · $O(\log n)$ Poseidon2 calls
On-chain footprint
one field element · 32 B per group commitment $C_g$

wiring — witness · in-circuit · on-chain

Where the Merkle tree shows up across the deployment lifecycle.

The leaves and the path live entirely in the prover's witness. The hashes run inside the circuit. The chain stores one field element — the current root $C_g$ — and nothing about who is in the set.

Prover · off-chain (witness)
In-circuit · R_Mem / R_Upd
On-chain · Soroban contract storage
witness · private
leaf = Poseidon2(identity_pk, blinding)
One field element. The prover knows the opening — the identity key and the blinding factor that compress to the leaf.
witness · 32 B × depth
authentication path
The sibling hash at every level between the leaf and the root. Tier 2 carries 16 siblings; tier 0 carries 8. None of this ever crosses the chain boundary.
witness · opening
leaf ↔ identity key
The opening that ties the leaf to the prover's identity key — the binding the membership relation checks alongside the path.
boundary Nothing in the witness ever crosses the chain boundary. The verifier sees the proof and the public input — not the leaf, not the path, not the opening.
R_Mem · read
path hashes to C_g
$R_{\mathrm{Mem}}$ verifies that the witness path, starting from the leaf, hashes correctly to the committed root $C_g$ — the membership relation used for reads.
R_Upd · write
C_g' is a legal successor
$R_{\mathrm{Upd}}$ additionally proves the successor root $C_g'$ is the result of inserting / removing / rotating a leaf under the policy contract's mutation rules.
F_r · arity-2
Poseidon2 calls · one per level
Each level of the path is one arity-2 Poseidon2 compression. Constraint count is depth × per-call cost — the same gadget at every level.
cost dominator Update relation cost dominator: path verification. $O(\log n)$ Poseidon2 calls — the dominant term across all three tiers. Larger trees only increase the path length, not the per-node cost.
Soroban · contract storage
current root C_g · 32 bytes
The contract stores only the current root — one field element. The verifier knows nothing about leaves; it sees the proof, the public input (which includes $C_g$, and for updates $C_g'$), and the verifying key.
PLONK verifier
checks the proof against C_g
The on-chain verifier accepts the proof iff the public input matches: the root the membership proof opens against is the root the contract currently stores.
no history The contract commits to the current root only. There is no historical-root commitment on chain; an application that needs historical membership proofs must keep its own log.

Cool/blue tint for the prover and in-circuit lanes — those run off-chain inside the prover. Amber for the on-chain lane — the only call site the chain actually pays for. The Merkle tree is, structurally, a witness data structure; the chain only ever sees its 32-byte projection.

security

The tree adds no assumption beyond the hash. Both horizons inherit Poseidon2's stance.

Two cards, two horizons — both green. The Merkle tree is the carrier; the security level lives entirely in the hash at the internal nodes. A second-preimage on any one of those would let an adversary substitute an alternate leaf.

classical · holding

Soundness reduces to Poseidon2 collision resistance.

A second-preimage on any internal node would let an adversary substitute an alternate leaf, breaking authorisation soundness. The reduction is tight: the hash gives you the tree.

  • Same security level across all three depth tiers — larger trees only increase the path length, not the per-node security.
  • Sponge-mode argument carries over from Poseidon2's indifferentiability proof.
  • The membership relation $R_{\mathrm{Mem}}$ is the in-circuit verification of the path; soundness of $R_{\mathrm{Mem}}$ is exactly soundness of the path checks.
post-quantum · conjectured

Inherits the hash's PQ stance. The tree adds zero further quantum vulnerability.

Grover halves the bit-security level on collision resistance; no Shor-style attack applies to a hash-based tree. The security delta vs Poseidon2 alone is zero.

  • In a PQ-secure configuration the Merkle structure is unchanged — only the surrounding SNARK and curve change.
  • The "what breaks under Shor" caveat lives entirely in the SNARK + curve, not in the membership data structure.
  • A wider Poseidon2 (state width $t$, digest size) recovers the bit-security margin without touching the tree's shape.
tier · locked
Tier choice is locked at group creation. A group whose membership grows past its tier's bound — 256 for tier 0, 4 096 for tier 1, 65 536 for tier 2 — cannot be expanded in-place. The membership set must be migrated to a larger-tier contract: a deployment-level operation, not a per-user one.

binary tiered vs sparse merkle vs verkle

Three membership-set commitments. Three different trades.

Binary tiered is the smallest moving-parts choice for a fixed-scale membership set. Sparse Merkle pays a per-update cost for non-membership support over a key universe. Verkle trades the post-quantum break for shallower trees.

this page

Binary tiered

binary hash tree · three depth tiers
Structure
binary hash tree · arity 2
Depth
$O(\log n)$ · 8 / 12 / 16 levels
Witness size
32 B × depth
In-circuit cost dominator
Poseidon2 path verify · depth × ~50–200 / call
PQ stance
conjectured PQ-secure · inherits hash
Supports non-membership
no · membership only
Representative deployment
this deployment · tiered membership registries

Sparse Merkle

binary tree over the full key universe
Structure
binary tree over all 2^k keys (e.g. $k = 256$)
Depth
fixed = key bit-length
Witness size
larger · padding hashes along empty branches
In-circuit cost dominator
per-update cost is higher — more sibling hashes to recompute
PQ stance
conjectured PQ-secure · inherits hash
Supports non-membership
yes · and membership
Representative deployment
Aztec · Ethereum state trie

Verkle

k-ary tree · KZG commitments at internal nodes
Structure
k-ary tree · vector commitment per node
Depth
$\log_k n$ · much shallower than binary
Witness size
smaller · single opening per level
In-circuit cost dominator
polynomial recommit on update
PQ stance
broken under Shor · KZG inherits curve break
Supports non-membership
no · membership only
Representative deployment
Ethereum state-trie successor proposal

Binary tiered is the smallest moving-parts choice for a fixed-scale membership set. Sparse Merkle pays a per-update cost for non-membership support over the full key universe. Verkle trades the post-quantum break for shallower trees and smaller proofs.

no history
No history beyond the current root. The contract commits only to $C_g$; an application that needs historical membership proofs — proofs that a member was in the set at some past root — must keep its own log. The Merkle tree itself does not carry past roots.

references

Primary literature.

Two sources. The original Merkle construction, and the Poseidon2 paper that supplies the hash at the internal nodes.