Engineering · 2026-05-02
Credential Revocation at Scale: Bitstring Status List vs Accumulator Proofs
By J. W. Bouckaert
Revocation for verifiable credentials
A W3C Verifiable Credential is designed so that a verifier can check it without calling the issuer. The holder decides when and where to present it. Credentials still need to be invalidated: an employee leaves, a licence is withdrawn, an issuer finds a fraudulent enrolment, or a wallet is compromised. Revocation is how an issuer withdraws a credential it can no longer recall directly.
Two approaches are common:
- Bitstring Status List. Bitstring Status List v1.0 became a W3C Recommendation on 15 May 2025. It developed from the earlier StatusList2021 draft. Each credential carries an index into a published bitstring, and a verifier fetches the bitstring and reads the bit.
- Cryptographic accumulators. The issuer publishes one short value that commits to the set of valid credentials. Each holder keeps a witness that proves membership, and the verifier checks the witness against the published value. AnonCreds uses this approach.
They solve the same problem with different costs and different privacy properties. Background on how PasskeyBridge uses credentials is in Verifiable Credentials Without a Blockchain and Cross-Referencing SIM Signals with Verifiable Credentials.
Bitstring Status List
The issuer publishes a status list credential whose encodedList is a GZIP-compressed bitstring, base64-encoded. Each credential is assigned an index. For a revocation list, a set bit means revoked. The specification also allows multi-bit entries for other status values. The minimum list length is 131,072 entries, so that the size of the list does not reveal how many credentials the issuer has.
| Property | Bitstring Status List |
|---|---|
| Issuer state | One entry per credential issued |
| Verifier work | Fetch the list, decompress, read one entry |
| Holder work | None at presentation |
| What the verifier learns | The credential's index, which is stable across presentations |
| What the issuer can learn | When its list is fetched, if it serves the list itself |
| Update | Replace the published list |
A sparse list compresses well, and many verifiers can share one cached copy.
Accumulators
An accumulator is a short commitment to a set. In the RSA accumulator (Benaloh and de Mare, 1993, made dynamic by Camenisch and Lysyanskaya, 2002), each set member is a prime, and the accumulator is a generator raised to the product of all members modulo an RSA modulus. A member's witness is the same value computed without that member. The holder proves in zero knowledge that it knows a member and witness satisfying the relation, without revealing which member it holds. When a credential is revoked, the issuer publishes a new accumulator value and the remaining holders update their witnesses. Pairing-based accumulators follow the same pattern on elliptic-curve groups.
| Property | Accumulator |
|---|---|
| Issuer state | One short value plus a record of revocation updates |
| Verifier work | Fetch the current value and verify a proof |
| Holder work | Update the witness after revocations |
| What the verifier learns | That the holder has a credential valid against the current value |
| What the issuer can learn | Nothing per credential, because there is no per-credential check |
| Update | Publish a new value and the updates holders need |
RSA and pairing-based accumulators rely on problems that Shor's algorithm solves on a large quantum computer. Lattice-based constructions exist in the research literature (Libert, Ling, Nguyen and Wang, EUROCRYPT 2016). The same migration concerns apply as for classical signatures.
Comparing the costs
The two approaches spend different resources. A status list costs bandwidth and storage that grow with the number of credentials ever issued. An accumulator keeps a small published value, but every holder must process revocation updates before it can prove membership, and verifiers must check a proof.
Issuer storage. At one bit per credential, an uncompressed list for one million credentials is 125 KB, and for 100 million it is 12.5 MB. A sparse list compresses to much less. An accumulator value is a single group element, plus the record of updates holders need.
Verifier work. A status list check is a cacheable fetch and a bit read. An accumulator check needs a current accumulator value and a proof verification.
Holder work. A status list puts no work on the holder. An accumulator holder that has been offline must apply every revocation published since its last update. Deployments reduce this with periodic witness rebases, which batches the work.
Privacy
Status lists reveal the credential's index to the verifier. The 131,072-entry minimum gives each credential a large crowd to hide in, but the index is stable, so colluding verifiers, or one verifier seeing the same credential twice, can link presentations. An issuer that serves its own list can also see when it is fetched.
Accumulators with zero-knowledge proofs avoid both problems. The verifier learns only that the credential is valid against the current value, and the issuer has no per-credential check to observe.
The choice is between operational simplicity and stronger unlinkability. Some systems use both: a status list for most credentials and accumulators for credential types where unlinkability is required.
A decision table
| Question | Points to a status list | Points to an accumulator |
|---|---|---|
| Must presentations be unlinkable across verifiers? | No | Yes |
| Are wallets offline for long periods? | Yes | Stale witnesses become a problem |
| Is the population very large with many verifiers? | Yes, lists cache well | Each check needs a current value and a proof |
PasskeyBridge implementation
PasskeyBridge implements status lists only. The shield-vc-status function publishes a StatusList2021Credential whose encodedList is a GZIP-compressed, base64-encoded bitstring padded to at least 131,072 bits. A single tenant list is limited to 1,048,576 bits, and a larger list is refused. The list is rebuilt after each status change.
Status can be read for one credential or a batch by credential ID, and authenticated callers can revoke, suspend or reinstate a credential. A failed registry read returns an error with caching disabled, so a verifier does not receive a cached "unknown" or empty list.
PasskeyBridge does not implement accumulators, and the credentials it issues do not yet carry a credentialStatus entry, so a verifier currently checks status through the API by credential ID.
Sources
- W3C Bitstring Status List v1.0 (Recommendation, 15 May 2025).
- W3C Verifiable Credentials Data Model 2.0.
- Hyperledger AnonCreds Specification.
- Benaloh and de Mare, "One-Way Accumulators: A Decentralized Alternative to Digital Signatures" (EUROCRYPT 1993).
- Camenisch and Lysyanskaya, "Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials" (CRYPTO 2002).
- Libert, Ling, Nguyen and Wang, "Zero-Knowledge Arguments for Lattice-Based Accumulators" (EUROCRYPT 2016).