What full-chain membership proofs teach about privacy systems

Privacy systems that hide an actor among others are limited by how many others. A ring signature hides a real input among a fixed number of decoys, and the size of that ring is bounded by the cost of the signature. A small set is a weak guarantee, and it degrades further under statistical analysis across many transactions.

The obvious improvement is to make the set everything: prove membership in the entire history of outputs rather than in a sample of sixteen. The reason it was not done earlier is cost. A naive proof over millions of elements is not something you attach to every transaction.

The construction that made this tractable builds the set as a tree of commitments and proves a path through it in zero knowledge, layer by layer. The technique is known in the literature as curve trees.

The efficiency trick is to alternate between two elliptic curves arranged so that the scalar field of one is the base field of the other. Arithmetic that is expensive to express inside a proof over one curve becomes native in the other, so each layer of the tree is proved on the curve where its operations are cheap, and the proof passes between them. The result is a membership proof whose size and verification cost grow with the depth of the tree rather than with the size of the set.

Alongside this sits work on proving discrete logarithm relationships efficiently, and on generalising the Bulletproofs argument to the shapes these proofs need. The engineering summary is that the primitive stopped being theoretical.

Once you can prove membership in a large committed set at reasonable cost, a family of problems collapses into one shape.

Each of these is currently solved by handing an identifier to a verifier who then knows more than they need. The membership proof formulation separates the question "are you entitled" from the question "who are you", and only the first one has to be answered.

• Eligibility to vote, without revealing which voter
• Possession of a credential or qualification, without revealing the holder
• Membership of a sanctioned or excluded set, or proof of absence from it
• Entitlement to a benefit, without disclosing identity to the party granting it
• Age or threshold attributes, proved against an issued credential rather than a document scan

A membership proof alone allows unlimited reuse, so systems pair it with a nullifier: a value derived deterministically from the secret credential, published when the right is exercised, which lets everyone see that this right has been used without learning whose it was.

The subtlety is scope. A nullifier derived only from the credential links every use across every context, which reconstructs a pseudonymous identity and destroys much of what was gained. Binding the nullifier to the context, so that the same credential produces unlinkable nullifiers in different elections or different services, is the difference between a privacy system and a pseudonym system.

This is the detail most often got wrong in derivative designs, and it is not a cryptographic weakness. It is a specification decision.

Proof generation is heavy compared to a signature, and heavy on a constrained device may mean seconds or a delegated prover, which reintroduces a party to think about. Verification is cheaper but not free, and it multiplies by the number of verifiers.

There is also the set maintenance problem. The tree has to be built, updated and published, and every participant needs a consistent view of its root. In a blockchain that infrastructure already exists. Outside one, it has to be designed, and that design carries governance questions about who publishes the root and how disagreement is resolved.

These are the questions that decide whether a proposal is deployable, and they are systems questions rather than cryptographic ones.

Cryptographic primitives reach mainstream systems years after they become practical, and usually through people who understood them while they were still awkward. Membership proofs at large scale look like one of those primitives.

The reason to read the Monero work specifically is that it is being built under adversarial conditions with real constraints on proof size, verification cost and backwards compatibility. Research written under those constraints tends to transfer better than research written without them.