Unlinkability Is a Property of the Whole Envelope, and We Broke Ours Once

The failure has a non-cryptographic version, and it is the one to hold in your head

A company runs an anonymous employee survey. No names, no departments, nothing identifying in the answers. To avoid double-counting, it asks each respondent to enter their employee number.

The answers reveal nothing. The employee number, present on every submission from the same person, reconnects all of them to an individual. No amount of care with the rest of the form fixes it.

That field is a correlation handle: any value that is present across separate interactions and distinctive enough to single somebody out. It does not need to look sensitive. A serial number, a session token, a reused public key, a de-duplication identifier added for a good operational reason, a timestamp precise enough to be unique. Each one is sufficient on its own.

Why the cryptography is the easy half

Selective disclosure and unlinkable presentation proofs are mathematically well understood, and a vendor can implement them correctly and still ship a system that links every user.

Because unlinkability is not a property of the proof. It is a property of everything a verifier receives: the proof, the header around it, the transport, the metadata, and every field somebody added because it was convenient. One constant field in the envelope defeats the entire construction, and it will do so silently, because the cryptography keeps working perfectly while it happens.

This is why "we use BBS+" answers a smaller question than the one a buyer is asking.

We shipped exactly that defect

Version one of our BBS+ presentation envelope embedded a per-credential verification identifier in the signed header.

By itself, that field was a correlation handle as strong as publishing the holder's identifier outright. Anyone comparing two presentations could have linked them using nothing else, no matter what the rest of the format got right.

It was found in our own internal review rather than by an external auditor, and fixed in version two by demoting the field to an always-hidden message. The reason our presentation format carries a version field at all is that defect.

We write this down because a vendor's list of what it got right is not evidence about the class of mistake it makes. What it caught, how, and what it changed structurally afterwards is.

What a buyer can do instead of trusting the claim

Ask for two serialized presentations produced by the same holder for two different verifiers, and diff them. Every field that is identical is a candidate handle, and the vendor should be able to say, for each one, why it is shared by a whole cohort rather than by one person.

For our implementation you can run that yourself, from a clean directory, with no account and no credentials:

npm i @solidus-network/auth @solidus-network/bbs
node node_modules/@solidus-network/auth/demo/unlinkability-demo.mjs

It produces two presentations from one credential and prints the pooled correlation surface. What is shared across both envelopes is the presentation type, the format version, the epoch, the message count, and whichever claims each verifier itself asked for. Those are cohort constants, shared by every holder of that credential type in that epoch. What is absent from both is the holder's subject identifier, the verification identifier, and the document hash.

The demo also prints that the two proofs share a handful of bytes at matching positions out of several hundred, indistinguishable from the random baseline it prints beside them, and that regenerating a proof for the same challenge produces a different one. That is what randomised, non-reusable proofs look like from the outside.

The boundary, which the tool prints too

This is unlinkability at the presentation layer and nothing else.

It does not defend against a verifier recognising a returning visitor by IP address, timing, cookies or device fingerprint. It does not defend against two verifiers pooling data they collected themselves, an email address or a phone number given at signup. Those are real correlation channels and cryptography does not close them.

A vendor whose privacy claim does not name that boundary has either not thought about it or is hoping you will not. Ours prints it in the output of its own demo, which is the placement least likely to be edited out of a slide.

What to ask any vendor claiming unlinkable credentials

"Show me two presentations from the same holder, and tell me which fields are constant." This converts a cryptography discussion into a diff, and it is the single highest-yield question in this area.

"For each constant field, is it shared by a cohort or by a person?" Cohort constants are unavoidable and fine. Per-holder constants are the whole failure.

"What handle have you removed since your first version?" Every honest implementation has one. A vendor with no answer has either not looked or is not telling you.

"What does your unlinkability claim explicitly not cover?" If network-level and out-of-band correlation are not in the answer, the claim is bigger than the property.

Where this leaves a decision

If unlinkability matters to you, do not buy it on a protocol name, and do not buy ours on one either.

The audit status of this implementation

The unlinkability implementation described here is unaudited.