Search⌘K

GitHub

X

Website

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, dosen't scale, or need centralized infra that becomes a single point of failure. The W3C standardized a new solution in 2015 called BitstringStatusList. 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,

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 KBin 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:

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.:

{
  "@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.

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:

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:

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 posibility 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

In Rust with sqlx:

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 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

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:

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 an 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,

Each list you see is a separate bitstring with a separate signing authority and this is the db schema that makes this work

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

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 renember 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:

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

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:

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

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:

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

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 scinerio 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 scinerio 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, The formal W3C Recommendation for credential revocation and suspension
• W3C Verifiable Credentials Data Model v2.0, Parent specification for VCs
• Digital Bazaar vc-bitstring-status-list, JS reference implementation
• W3C Data Integrity EdDSA Cryptosuites, The eddsa-jcs-2022 signing specification
• ALLOSAUR: Accumulator with Low-Latency Oblivious and Succinct Revocation, The strongest alternative revocation approach
• CRSet: Cascade-Based Revocation Sets, Bloom filter cascade approach to privacy preserving revocation
• Hyperledger AnonCreds Specification, Accumulator based alternative with full unlinkability

This took me a few weeks to write, thanks for reading, please share 😂❤️