Engineering · 2026-05-02

Credential Revocation at Scale: Bitstring Status List vs Accumulator Proofs

By J. W. Bouckaert

Revocation, the neglected half of verifiable credentials

Issuance gets the demos. Revocation runs the system.

A verifiable credential is, in practice, a long-lived bearer artifact. The holder controls when and where to present it. The issuer cannot phone home to invalidate it after the fact, because the entire point of a W3C Verifiable Credential is that verifiers do not need to call the issuer to trust it. Yet credentials must sometimes be invalidated, employees leave, drivers' licenses expire mid-cycle, an issuer discovers a fraudulent enrolment, a wallet is compromised. Revocation is how the ecosystem reconciles long-lived artifacts with a world that changes.

Two strategies dominate production deployments in 2026:

1. Bitstring Status List (W3C Recommendation, VC Bitstring Status List v1.0, May 2025). This is the spec the community knew as StatusList2021 during its draft years; the rename happened on the path to Recommendation. Each credential carries an index into a public bitstring; verifiers fetch the bitstring and check the bit.
2. Cryptographic accumulators. The issuer maintains a single short cryptographic value (the accumulator) representing the set of currently-valid credentials. Each holder carries a non-revocation witness; verifiers check the witness against the published accumulator. This is the model behind AnonCreds and most ZKP-first credential systems.

These two models look like they solve the same problem. They don't. The cost surfaces, the privacy properties, and the operational footprint diverge sharply at scale. This article works through both, with reproducible cost models at 1M, 10M, and 100M credential populations.

For background on why we treat credential lifecycle as part of identity threat response, see Verifiable Credentials Without Blockchain and SIM Signals × Verifiable Credentials: A Cross-Reference Trust Model.

Model A: Bitstring Status List, in one paragraph

The issuer publishes a JSON document containing a base64-encoded, gzip-compressed bitstring of length N. Each credential it ever issued is assigned an index i into that bitstring. Bit i = 0 means valid, bit i = 1 means revoked (the spec also allows multi-bit encodings for richer status, but the binary case dominates). When a verifier checks a credential, it fetches the status list URL, decompresses the bitstring, and reads bit i. The W3C spec mandates a minimum length of 131,072 bits (16 KiB raw, much smaller after gzip when sparsely populated) to provide herd anonymity for the indexed credential.

Properties that follow directly from the construction:

Model B: Cryptographic accumulators, in one paragraph

An accumulator is a short cryptographic commitment to a set. The classical RSA accumulator (Benaloh-de Mare 1993, refined by Camenisch-Lysyanskaya 2002) commits to a set S as A = g^{∏_{x∈S} x} mod n where n is an RSA modulus and each set element x is a prime. Each member x holds a non-revocation witness w_x = g^{∏_{y∈S, y≠x} y} mod n such that w_x^x ≡ A (mod n). To prove membership in zero-knowledge, the holder presents a Camenisch-Lysyanskaya-style proof that they know an x and w_x satisfying that relation, without revealing x. When a credential is revoked, the issuer publishes a new A'; every still-valid holder must update their witness using a public delta. Pairing-based variants (Nguyen, Vitto-Biryukov, ALLOSAUR) trade RSA group operations for elliptic-curve pairings, with different cost surfaces but the same shape.

That last row matters. We've written about hybrid post-quantum signatures and why KEM is replacing classical key exchange; the same threat model applies here. Lattice-based accumulators exist in the literature (Libert-Ling-Nguyen-Wang) but are not yet production-ready at the scales we care about.

Cost surfaces

The naive question, "which is faster?", produces misleading answers because the cost surfaces are different shapes. Bitstring Status List moves bytes; accumulators move CPU cycles. The right question is, "what does each model cost the ecosystem at population N?" Below are reproducible estimates, modeled with stated assumptions. These are not measurements from a specific deployment, they are first-principles bounds that any team can replicate in a spreadsheet.

Storage at the issuer

Bitstring Status List grows linearly with the number of credentials ever issued (not just currently valid). Accumulators grow with the size of the revocation delta log, which is what holders consume to keep their witnesses fresh. The delta log is unbounded over time but bounded per epoch, and it is the operational pain point of the accumulator model.

Verifier work per check

The bitstring path is bandwidth-bound and trivially cacheable, every verifier on the planet can sit behind a CDN edge fetching the same status list, with cache hit ratios approaching 1. The accumulator path is CPU-bound and harder to cache because a fresh accumulator is needed at the verifier's chosen time-of-check. At the latency a login path actually allows (the constraint we hold ourselves to), the difference matters.

Holder work

This is the hidden cost. Bitstring imposes zero work on the holder at presentation time. Accumulators require the holder's wallet to maintain a current non-revocation witness, which means downloading and folding-in every revocation delta since the witness was last updated. For a wallet that comes online once a month after 1M revocations, that is 1M group operations to catch up before the next presentation can produce a valid proof. Production accumulator deployments mitigate this with epoch-based witness rebases, but the work does not vanish, it gets amortized.

Privacy

Status checks are themselves a side channel.

Bitstring Status List leaks two things. First, the verifier learns the credential's index in the bitstring, which is a stable identifier scoped to that issuer. Two verifiers who collude (or one verifier observing a holder over time) can correlate presentations of the same credential. The W3C spec addresses this with herd anonymity, by mandating a minimum bitstring length of 131,072 entries even for small populations, the index alone is insufficient to single out a holder. But the property is k-anonymity, not unlinkability. Second, the issuer can observe status-list fetches and infer when and how often a given index is being checked, which leaks usage patterns.

Accumulators were designed to fix exactly this. The verifier learns only that "this holder possesses a credential whose witness validates against the current accumulator", and nothing about which credential. Properly implemented (with zero-knowledge proofs of the witness relation), the accumulator model offers full unlinkability across presentations and across verifiers. The issuer also cannot link status checks to specific credentials, because there is no per-credential check, only a single accumulator value that every holder validates against.

This is the trade. Bitstring is operationally simple but privacy-modest. Accumulators are operationally expensive but privacy-strong. There is no neutral choice, picking one means picking which property you want to optimize. For our Schrems III data residency posture and zero-PII architecture, the unlinkability property weighs heavier than it might in less-regulated settings.

A decision framework

The right model depends on three questions. Answer them in order.

Three "yes" answers down the bitstring column means ship Bitstring Status List today, it is mature, standardized, and operationally simple. Three "yes" answers down the accumulator column means accept the engineering cost of accumulator infrastructure, it is the only model that delivers the privacy properties.

Most production stacks in 2026 end up with both, bitstring for the high-volume general case, accumulators for the smaller subset of credentials where unlinkability is non-negotiable (citizen-issued ID, health credentials, age assertions for adult-content gating). The two models compose, a holder can carry a credential with both a status list entry and an accumulator witness, and the verifier picks whichever proof matches its threat model.

The PasskeyBridge implementation

Our verifiable credential pipeline supports both models behind a single verifier API. Issuers configure per-credential-type which revocation strategy applies. Verifiers receive a uniform "valid / revoked / unknown" outcome regardless of the underlying mechanism. The choice is a deployment decision.

Operationally, we treat revocation freshness as a first-class signal in the same way we treat carrier-signal freshness (circuit breakers and graceful degradation), if the status list URL is stale beyond its declared TTL or the accumulator publication is delayed, the verifier returns a configurable "unknown" rather than silently treating the credential as valid. That behavior is what separates a revocation system from a revocation theatre.

Sources and further reading

• W3C Bitstring Status List v1.0 (Recommendation, May 2025).
• W3C Verifiable Credentials Data Model 2.0.
• Hyperledger AnonCreds Specification (production accumulator deployment).
• Camenisch and Lysyanskaya, "Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials" (CRYPTO 2002).
• Vitto and Biryukov, "Dynamic Universal Accumulator with Batch Update over Bilinear Groups" (CT-RSA 2022).
• Libert, Ling, Nguyen, Wang, "Zero-Knowledge Arguments for Lattice-Based Accumulators" (EUROCRYPT 2016)—the lattice direction.

Start free · Test the API