# Scaling Verifiable Credential Revocation to Millions of Users > You've issued 2 million verifiable credentials. An employee's phone has been stolen. You need every verifier in the world to reject that one credential within a few minutes, without revealing which one, and without O(n) scanning. By Shodipo Ayomide, published Mar 14, 2026. Web version: https://blog.shodipoayomide.com/scaling-verifiable-credential-revocation-to-millions-of-users ![Scaling Verifiable Credential Revocation to Millions of Users](https://blog.shodipoayomide.com/banners/scaling-verifiable-credential-revocation-to-millions-of-users.png) Let's say you have issued 2 million verifiable credentials, could be employee badges, KYC attestations, age proofs, wallet attestations, everything your system has ever signed and distributed across the network to employees. Now a device gets compromised and you need every verifier on the planet to reject that one credential within minutes, without revealing which credential was revoked, without requiring verifiers to make requests to your deployed issuer server, and without `O(n)` scanning through a revocation list. That's the credential revocation problem. The regular approaches like `CRLs` **Certificate Revocation Lists** and `OCSP` **Online Certificate Status Protocol** either leaks privacy, doesn't scale, or need centralized infra that becomes a single point of failure. The `W3C` standardized a new solution in 2015 called [BitstringStatusList](https://www.w3.org/TR/vc-bitstring-status-list/). Building your system around this allows it to handle millions of credentials, concurrent revocations, multiple authorities suspending independently, randomized index assignment for VC for privacy, and a lazy publish when ready pipeline. ## How Bitstring list's Solves this Think of a bitstring as a massive status register where every credential gets assigned **an index** in a massive bitstring. Bit `0` = valid, bit `1` = revoked or suspended depends on your design. To revoke credential `#94,567` for instance, you flip bit `94,567` from `0` to `1` and to check if it's revoked, you just read that same bit, and that's everything, ```bash Index: 0 1 2 3 4 ... 94567 ... 2097151 Bitstring: 0 0 0 1 0 ... 1 ... 0 ↑ credential #94567 is revoked here ``` Pretty simple pipeline for revocation! The bitstring gets `GZIP` compressed, `base64url` encoded with a `u` multibase prefix, signed, and published as a `Verifiable Credential` itself, the `BitstringStatusListCredential`. A verifier grabs it, decompresses, reads the bit. One fetch, one bit check, all done. This is why it scales: the bitstring is fixed size no matter how many credentials get revoked. A 2 million entry list is `256 KB`in its uncompressed state, but at typical revocation rates under 1%, `GZIP` shrinks that to `1-3 KB`. A `CDN` serves it in ms. Compression ratios for a `2,097,152-bit` `256 KB` list: | Fill rate | Set bits | Compressed size | Ratio | |-----------|----------|-----------------|-------| | 0% (empty) | 0 | ~300 bytes | 870:1 | | 0.1% | 2,097 | ~1.5 KB | 170:1 | | 1% | 20,971 | ~8 KB | 32:1 | | 10% | 209,715 | ~90 KB | 2.8:1 | | 50% (random) | ~1M | ~256 KB | 1:1 | At real world revocation rates the entire status for 2 million credentials fits in under `8 KB`. A CDN can cache and serve that easily. ## Binding A Credentials to A Bitstring When a credential is issued, you embed a `credentialStatus` entry pointing to the status list. For e.g.: ```json { "@context": [ "https://www.w3.org/ns/credentials/v2", "https://www.w3.org/ns/credentials/status/v1" ], "type": ["VerifiableCredential", "EmployeeIDCredential"], "issuer": "did:polygonid:issuer", "credentialSubject": { "name": "Alice", "employeeId": "E-1234" }, "credentialStatus": { "type": "BitstringStatusListEntry", "statusPurpose": "revocation", "statusListIndex": "94567", "statusListCredential": "https://status.privado.id/credentials/employee-ids" } } ``` Every verifier dereferences `statusListCredential`, decompresses the bitstring, reads bit `94,567` and if it's `1`, the credential is revoked if 0 it's still active. Some `W3C` requirements worth knowing: - `statusListIndex` is a decimal string, not an integer - Minimum bitstring size is `131,072` entries **16 KB**, defaulted to for herd privacy - The `statusPurpose` in the entry MUST match the `statusPurpose` in the status list credential - `GZIP` compression per `RFC 1952`, multibase encoded with prefix `u`, "base64url, no padding" ## Bit Manipulation at the Byte Level This is the cool part. The bitstring is `big-endian` within each byte, so index `0` is the leftmost "most significant" bit of byte `0`. ```bash Bit layout within a byte: Byte index = floor(bit_index / 8) Bit offset = 7 - (bit_index % 8) Example: index 0 => byte 0, bit 7 (MSB) index 7 => byte 0, bit 0 (LSB) index 8 => byte 1, bit 7 (MSB) ``` In Rust: ```rust pub fn get_bit(bitstring: &[u8], index: u32) -> bool { let byte_index = (index / 8) as usize; let bit_offset = 7 - (index % 8); (bitstring[byte_index] >> bit_offset) & 1 == 1 } pub fn set_bit(bitstring: &mut [u8], index: u32) { let byte_index = (index / 8) as usize; let bit_offset = 7 - (index % 8); bitstring[byte_index] |= 1 << bit_offset; } pub fn clear_bit(bitstring: &mut [u8], index: u32) { let byte_index = (index / 8) as usize; let bit_offset = 7 - (index % 8); bitstring[byte_index] &= !(1 << bit_offset); } ``` Why `7 - (index % 8)`? The `W3C` spec defines index `0` as the leftmost bit, so in a byte `0b1000_0000`, that's bit position `7` counting from `0` on the right. The subtraction converts spec ordering to byte ordering. Compression and encoding to `W3C` format: ```rust use flate2::write::GzEncoder; use flate2::Compression; use base64::{engine::general_purpose::URL_SAFE_NO_PAD, Engine}; pub fn compress_and_encode(bitstring: &[u8]) -> String { // compress let mut encoder = GzEncoder::new(Vec::new(), Compression::default()); encoder.write_all(bitstring).unwrap(); let compressed = encoder.finish().unwrap(); // encode format!("u{}", URL_SAFE_NO_PAD.encode(&compressed)) } ``` NOTE: `clear_bit` is what makes suspension reversible. Revocation operations must NEVER call `clear_bit`, once a credential is revoked, it's permanently dead and this is enforced at the service layer where the revocation service exposes `suspend`/`unsuspend` endpoints but only `revoke` no `unrevoke`. The bitstring itself is purpose agnostic, the irreversibility of revocation is a business rule, not a data structure property ## Concurrent Write Safety There is a possibility which we experienced where multiple services might be revoking credentials at the same time. Without clear coordination, two concurrent bit flips on the same list `corrupts` the `bitstring`. The classic lost update issue. Server A reads the bitstring and flips bit `100`, but Server B reads the same bitstring before A writes back and flips bit `200`. B writes back, overwriting A's change, bit 100 never gets set unfortunately. How I fixed this? Pessimistic row level locking ![pessimistic row level locking](https://i.ibb.co/234SsZ9L/diagram.png) In Rust with `sqlx`: ```rust pub async fn set_bit_tx( &self, tx: &mut Transaction<'_, Postgres>, list_id: &str, bit_index: u32, ) -> Result<(bool, i32)> { // get row lock, concurrent txns block here let record = sqlx::query_as::<_, StatusListRecord>( "SELECT * FROM status_lists WHERE list_id = $1 FOR UPDATE" ) .bind(list_id) .fetch_optional(&mut **tx) .await? .ok_or(Error::NotFound)?; let already_set = get_bit(&record.bitstring, bit_index); if already_set { return Ok((true, record.total_revoked)); // idemp } let mut bitstring = record.bitstring.clone(); set_bit(&mut bitstring, bit_index); sqlx::query( "UPDATE status_lists SET bitstring = $2, total_revoked = total_revoked + 1, updated_at = NOW() WHERE list_id = $1" ) .bind(list_id) .bind(&bitstring) .execute(&mut **tx) .await?; Ok((false, record.total_revoked + 1)) } ``` What's happening here: - `SELECT ... FOR UPDATE` gets a row level lock, concurrent transactions blocked here - Checks if the bit is already set "idempotent" - Flips the bit in memory, writes the updated bitstring back - Lock held for the full transaction, read, flip, write, log The maths: with 7 credential types × 3 purposes that's 21 status lists, so concurrent revocations on different credential types never contend with each other. Same-list revocations serialize through `FOR UPDATE`. Lock hold time is under 5ms "one read, one write, one log insert", and at 100 revocations/second, the queue depth stays under 1. The I/O trade-off is real though. Each revocation reads `256 KB` from Psql, flips one bit, writes `256 KB` back, plus `WAL`. That's give or take `~768 KB` of I/O per revocation. At 1,000 revocations/minute, that's `~750 MB/minute`. Psql handles this fine on modern SSDs, but it's the primary scaling challenge. For higher throughput what we did was to batch bit flips, accumulate revocations in a queue and apply them in a single read, modify, write flow. ## Why Sequential Index Allocation Leaks Information If you assign indices sequentially "credential 1 => index 0, credential 2 => index 1, and so o", an observer who pays attention knows two credential indices can infer their issuance order and the approx number of credentials issued between all of them. Indices SHOULD be assigned randomly never SEQUENTIALLY. From a more technical stand point the solution here is a keyed [Feistel permutation cipher](https://lib.rs/crates/feistel-permutation-rs) that maps sequential counters to pseudo random indices. It's a bijection, 100% deterministic, same counter always maps to same index, and reversible with the key ```bash Counter: 0 1 2 3 4 5 ↓ Feistel permutation Index: 847 23 1902 556 12 2041 ``` A 6-round `Feistel` network with `SHA-256` round function: ```rust const FEISTEL_ROUNDS: u8 = 6; pub fn permute_index(counter: u32, size: u32, key: &[u8]) -> u32 { let k = size.trailing_zeros(); let half_a = (k + 1) / 2; let half_b = k / 2; let mut left = counter >> half_b; let mut right = counter & ((1u32 << half_b) - 1); let (mut left_bits, mut right_bits) = (half_a, half_b); for round in 0..FEISTEL_ROUNDS { let f = sha256_round(key, round, right) & ((1u32 << left_bits) - 1); let new_right = left ^ f; left = right; right = new_right; std::mem::swap(&mut left_bits, &mut right_bits); } (left << right_bits) | right } ``` Why this worked: - Every counter maps to a unique index "bijective", provable property of balanced Feistel networks with `≥4 rounds` - Different keys produce different permutations. Each list derives its own key, `SHA-256(master_secret || list_id || "index-permutation")` - Negligible overhead, `6×` `SHA-256` per allocation, `~18μs` So a hacker or actor who obtains two credentials cannot determine how many were issued between them, or which was issued first or second or third. The permutation always operates on the full `2^21` (2,097,152) space regardless of how many indices have been allocated so far ## Three Lists Per Credential A single revocation list isn't enough. Each with a different `statusPurpose`, and in production you actually need three independent status dimensions, ![3 lists per cred](https://i.ibb.co/xqTJ16pv/diagram2.png) | Scenario | Who acts | Which list | isReversible? | |----------|----------|------------|-------------| | Employee terminated | The Issuer | revocation | No, credential permanently gone | | Fraud investigation pending | The Issuer | suspension "issuer" | Yes, issuer unsuspends after cleared with evidence | | A user reports lost their phone | The Holder | suspension "holder" | Yes, holder unsuspends from their new device after re-enrollment | Each list you see is a separate `bitstring` with a separate signing authority and this is the db schema that makes this work ```sql CREATE TABLE status_lists ( list_id TEXT PRIMARY KEY, credential_type TEXT NOT NULL, status_purpose TEXT NOT NULL, list_authority TEXT NOT NULL, bitstring BYTEA NOT NULL, next_index INTEGER NOT NULL DEFAULT 0, total_issued INTEGER NOT NULL DEFAULT 0, total_revoked INTEGER NOT NULL DEFAULT 0, sequence_number INTEGER NOT NULL DEFAULT 1, CONSTRAINT uq_type_purpose_authority_seq UNIQUE (credential_type, status_purpose, list_authority, sequence_number) ); ``` This guy ensures exactly one active list per `(credential_type, purpose, authority, sequence)` combination Triple allocation during credential issuance, three independent index assignments for single credential, all three also would be in the credential's `credentialStatus` array ```rust let rev = allocate_index(cred_type, cred_id, "revocation", "issuer").await?; let iss = allocate_index(cred_type, cred_id, "suspension", "issuer").await?; let hld = allocate_index(cred_type, cred_id, "suspension", "holder").await?; ``` Every verification checks all three, the credential is valid only if: ``` NOT revoked AND NOT issuer suspended AND NOT holder suspended all strictly ``` ### Custodial Publishing This is where we got a little bit confused. The holder controls which bit gets flipped, they send a signed authorization message that the revocation service should verify before accepting the bit flip. But remember the issuer's infra compresses, signs, and publishes all status list credentials, including holder authority ones Without this custodial model, every holder would need their own `Arweave` access, `signing keys`, and `CDN` distribution. Which is not realistic. The issuer of the `BitstringStatusListCredential` may differ from the issuer of the `VerifiableCredential`. Authorization determines who can flip bits. Publishing determines who signs and distributes the list. ## Proving You Have the Right to Revoke Anyone should be able to call the revocation API, so you need proof that the caller actually owns that bit it called to be flipped. Signed auth messages with domain separation: ```bash Issuer revocation: SHA-256("{namespace}:revoke:v1:{cred_id}:{list_id}:{index}:{nonce}:{timestamp}") Holder suspension: SHA-256("{namespace}:holder-suspend:v1:{cred_id}:{list_id}:{index}:{nonce}:{timestamp}") ``` The prefix `revoke:v1` vs `holder-suspend:v1` stops something called a cross operation replay where an issuer's revocation signature cannot be used to perform a holder suspension even if the same key is used for both ```rust pub fn verify_issuer( &self, issuer_did: &str, issuer_public_key: &[u8], credential_id: &str, status_list_id: &str, status_list_index: i32, ) -> Result<()> { let signer_did = self.verification_method.split('#').next().unwrap_or(""); if signer_did != issuer_did { return Err(Error::AuthorizationFailed("DID mismatch")); } if self.nonce.len() < 32 { return Err(Error::AuthorizationFailed("nonce too short")); } let message = format!( "{}:revoke:v1:{}:{}:{}:{}:{}", self.namespace, credential_id, status_list_id, status_list_index, self.nonce, self.created_secs ); let hash = sha256(message.as_bytes()); match self.signature_type.as_str() { "Ed25519Signature2020" => ed25519_verify(issuer_public_key, &hash, &self.signature)?, "EcdsaSecp256k1Signature2019" => secp256k1_verify(issuer_public_key, &hash, &self.signature)?, _ => return Err(Error::UnsupportedSignatureType), } Ok(()) } ``` For the holder suspension, the same pattern applies with three main differences - The signer `DID` must always match the subject `DID` not the issuer - The public key is always resolved dynamically from the `DID` document via the `DID` service - The message prefix would be `holder-suspend:v1` instead of `revoke:v1` ## What Happens When 2 Million Isn't Enough When `next_index` reaches the list size, you rotate to a new list, that's all: ```bash employee-ids (seq 1) => 2,097,152 entries => FULL employee-ids-2 (seq 2) => 2,097,152 entries => FULL employee-ids-3 (seq 3) => 412,000 entries => ACTIVE ``` ```rust let allocation = match allocate_next_index_tx(&mut tx, list_id, max_index).await { Ok(counter) => (list_id.clone(), counter), Err(Error::StatusListFull) => { let new_list = create_next_list_tx( &mut tx, credential_type, base_list_id, current_sequence, size_bits, status_purpose, list_authority, ).await?; let counter = allocate_next_index_tx(&mut tx, &new_list.list_id, max_index).await?; (new_list.list_id, counter) } Err(e) => return Err(e), }; ``` "Concurrent rotation safety" Two txn's may both see the list as full. The `CREATE` uses `ON CONFLICT DO NOTHING`, so the second transaction falls through to a `SELECT` of the already created list. Both should proceed with allocation on the same new list. And no duplicate lists. What it'll look like: | Credentials issued | Lists per purpose | Total lists 3 "purposes × 7 types" | |-------------------|-------------------|-------------------------------------| | 1 million | 1 per type | 21 | | 10 million | ~5 per type | 105 | | 100 million | ~48 per type | 1,008 | Each list can be published and cached on its own. Verifiers don't notice rotation because the credential's `statusListCredential` URL points to a specific list, not a rotating alias. ## The Publishing Pipeline A bit flip in psql is invisible to verifiers. The updated bitstring has to be compressed, signed, and published. That's an eventually the same pipeline ![publishing & anchoring flow](https://i.ibb.co/HTcMQSR2/daigarm3-2.png) ### Ideal Debounce Logic If 50 credentials get revoked within 30 seconds, say, a full scale compromise, you don't want to chill for 50 separate publish flows each compressing `256 KB`, signing, uploading to a permanent storage, and pushing to CDN. The auto publisher waits for a specified `debounce_secs` `default 60s` after the last update before publishing. If updates keep coming in simply, `max_delay_secs` `default 120s ` forces a publish nontheless Worst case scenario staleness is bounded, `120s` max delay + `~2s` compress/sign/upload = `~122 seconds` from first bit flip to verifier availability. **SIDE NOTE:** "When to consider accumulators instead" if your threat model requires presentation unlinkability to users and non revocation proofs, say for anonymous voting or a privacy age verification setup. The computational and infra costs are higher, but the privacy guarantees are stronger here ## More key things I learned along the way ### Non Atomic Triple Allocation Three independent calls for the three status entries during credential issuance. If call 2 fails, call 1's allocation is orphaned. What I then did was to setup an RPC that does all three allocations in a single db transaction ### Debounce Prevents Republishing Storms Without debounce, revoking `100` credentials in a batch triggers `100` separate publish flows, each will be compressing `256 KB`, signing, uploading to the permanent storage, and pushing to the CDN. That's unnecessary. The `60s` debounce added collapses these into a single publish and the `120s` max delay bounds worst case scenario staleness. This cut our publishing load by roughly `50×` during a batch operation ### Dual Storage, Dual Integrity Permanent storage gives you immutability, but immutability alone doesn't prove the content is what you expect. The blockchain anchor records a `SHA-256(credential_json)` onChain. Verification gets from storage, hash it, compare with the onChain hash. If either system is tampered with, the mismatch is detectable easily ### The Numbers at Scale For a system with 7 credential types, triple allocation, and `2M-bit` lists at 10 million credentials issued - Status lists, ~105 active "5 per type × 7 types × 3 purposes" - DB bitstring storage, ~105 × 256 KB = ~27 MB - Index allocations, 30 million rows "3 per credential" - Published credentials, ~105 × 3 KB = ~315 KB total on the CDN - Per revocation, ~768 KB DB I/O, under 5ms lock hold, 60-120s publish latency at most - Per verification, ~9 KB CDN download, under 10ms total "warm cache" - Throughput ceiling "single PostgreSQL", ~200 revocations/sec per list, ~1000 allocations/sec per list, ~10,000 status checks/sec ## Essential Links - [W3C BitstringStatusList v1.0](https://www.w3.org/TR/vc-bitstring-status-list/), The formal W3C Recommendation for credential revocation and suspension - [W3C Verifiable Credentials Data Model v2.0](https://www.w3.org/TR/vc-data-model-2.0/), Parent specification for VCs - [Digital Bazaar vc-bitstring-status-list](https://github.com/digitalbazaar/vc-bitstring-status-list), JS reference implementation - [W3C Data Integrity EdDSA Cryptosuites](https://www.w3.org/TR/vc-di-eddsa/), The eddsa-jcs-2022 signing specification - [ALLOSAUR: Accumulator with Low-Latency Oblivious and Succinct Revocation](https://eprint.iacr.org/2022/1362), The strongest alternative revocation approach - [CRSet: Cascade-Based Revocation Sets](https://arxiv.org/abs/2501.17089), Bloom filter cascade approach to privacy preserving revocation - [Hyperledger AnonCreds Specification](https://hyperledger.github.io/anoncreds-spec/), Accumulator based alternative with full unlinkability > This took me a few weeks to write, thanks for reading, please share 😂❤️