Proving Something Is Absent Is Harder Than Proving It Is Present, and Revocation Needs the Hard One

What runs is a single unsharded structure; the sharded design in our architecture documents is unbuilt.

Two proofs that sound symmetrical and are not

"This is in the set" is easy. Hand over the item and a short path of hashes leading to a root everyone already agrees on. The verifier recomputes and compares. Small, fast, and it needs no trust in the party providing it.

"This is not in the set" is the hard one. You cannot hand over an item that is not there, and a party that simply omits something has produced an identical result to a party for whom the thing genuinely does not exist.

The naive answer is to send the whole set, which defeats the purpose. The useful answer is a structure where absence has a shape you can point at.

Why identity needs the hard one constantly

Because most of the questions a verifier asks are negative.

Is this credential not revoked. Is this issuer not removed. Is this key not rotated away.

Each is an absence claim, and each has to be answered without the verifier downloading everything or trusting the answering party. A system that can only prove presence has to fall back on "trust me that it is not there", which is exactly the position a verifiable system exists to avoid.

How the structure gets there

By having a defined position for every possible entry rather than only for the ones that exist.

Once every possible key has a home, absence becomes a positive statement: the position where this would live contains nothing, and here is the proof of that. The proof is the same shape and roughly the same size as a presence proof.

The counter-intuitive part is that this requires a structure with an astronomically large number of positions, almost all empty. That works because empty subtrees are identical and can be computed rather than stored, so the enormous structure is cheap.

What this buys a verifier in practice

A non-revocation answer that does not require trusting us.

A verifier can be handed a proof that a credential's position is empty and check it against a root, rather than accepting our assertion. That is the difference between a system where the operator's honesty is a dependency and one where it is checkable.

What it does not buy is freshness. A proof is against a root at a moment. If a verifier's root is stale, the proof is correct and the answer is old, which is a separate problem addressed by how often roots are published rather than by the structure.

What to ask any system making absence claims

"Can you prove a thing is not in your set, or only that it is?" Many systems quietly cannot, and the gap shows up exactly at revocation.

"What root am I checking against, and how old is it?" A valid proof against a stale root is a correct answer to yesterday's question.

"Is the structure that is running the one in your architecture document?" For us, no: sharding is designed and unbuilt.

"Has the storage layer been reviewed?" For us, no. State-model bugs are quiet and consequential.

Where this leaves a decision

If you need audited state infrastructure, ours has not been reviewed, and a structure being standard is not the same as an implementation being checked.

If your requirement is that non-revocation is something you can verify rather than something you take on trust, that property is real, it is what runs today, and the freshness of the root you check against is the part that stays your problem.