Non-membership tree

Research preview

This page describes the candidate scheme analysed in PSE's Merkle tree-based approaches blog post. It is not implemented in this repository. No witness generator, accumulator update protocol, or in-circuit gadget ships in revocation/ today.

What a non-membership tree gives you

Status lists and bit-vector accumulators answer "is identifier $x$ in the revoked set?". A non-membership tree answers the dual: "prove $x \notin S$ where $S$ is the issuer-controlled revoked set." In ZK, the witness is a short opening of a Merkle tree that demonstrates $x$ sits between two adjacent leaves of a sorted set — neither equal to nor containing $x$.

The reason this is the candidate of choice for an OpenAC-compatible scheme:

• The opening is short ($O(\log n)$ hashes) and constant-shape in-circuit.
• The witness can be verified with the same SHA-256 / Poseidon gadgets already used in jwt.circom / show.circom.
• The wallet never sends the identifier $x$ in the clear — it appears only as a private input to the Show circuit, alongside the disclosed claims.

Structure (informal)

Let $S = \{x_1 < x_2 < \ldots < x_k\}$ be the issuer's revoked set, sorted as field elements. Pad with $0$ and $p-1$ sentinels. Build a Merkle tree over the sorted leaves and publish the root $R$ inside an issuer-signed metadata blob.

To prove $x \notin S$, the wallet finds the adjacent pair $(x_i, x_{i+1})$ with $x_i < x < x_{i+1}$ and supplies:

• the leaves $x_i$, $x_{i+1}$ and their adjacency proof (typically a co-path of sibling hashes);
• the comparisons $x_i < x$ and $x < x_{i+1}$ as field-arithmetic constraints in the Show circuit;
• a check that the issuer's signature on $R$ verifies under the issuer's revocation key.

The verifier learns: a fresh proof verifies; the issuer's published root was used; nothing about $x$.

What still has to be designed

Question	Why it matters
Hash choice (SHA-256 vs. Poseidon vs. Pedersen)	Drives circuit cost. SHA-256 is already in the JWT circuit; Poseidon is cheaper inside Spartan2 but adds a second hash to audit.
Update cadence	Wallets must keep witnesses fresh after each issuer publish. Determines how stale a proof can be before the verifier rejects it.
Revocation key separation	Whether the issuer's revocation root is signed with the same key as the credential or a separate scheme key, and how rotation works.
Wallet privacy from the issuer	The wallet must fetch witness updates without identifying itself — a CDN model with cacheable, addressable witness blobs is one option.
Anti-correlation across issuers	If many issuers each publish their own tree, a wallet that selects an update for only one issuer leaks the issuer. Batched / dummy fetches may be required.

Alternatives surveyed in the literature

• RSA accumulators. Compact witnesses but trusted setup (the RSA modulus), additional cryptographic assumptions, and harder to verify inside Spartan2.
• Cryptographic accumulators with batch updates (CL accumulator family). More efficient update at the cost of pairing-based assumptions that do not fit the current backend.
• W3C Bitstring Status Lists. Cheap and standardized, but the index is the identifier. Suitable only for the out_of_band profile.

See DIF Labs Privacy-preserving revocation mechanisms for a broader survey.

Status

When a concrete circuit and witness-update API land in revocation/, this page will replace the description above with code references to the implementation.