# Escalando a revogação de credenciais verificáveis para milhões de usuários

> Você emitiu 2 milhões de credenciais verificáveis. O celular de um funcionário foi roubado. Você precisa que todo verificador do mundo rejeite aquela única credencial em poucos minutos, sem revelar qual é, e sem uma varredura O(n).

Por Shodipo Ayomide, publicado em 14 de mar. de 2026. Versão web: https://blog.shodipoayomide.com/pt/scaling-verifiable-credential-revocation-to-millions-of-users

![Escalando a revogação de credenciais verificáveis para milhões de usuários](https://blog.shodipoayomide.com/banners/scaling-verifiable-credential-revocation-to-millions-of-users.png)

Digamos que você emitiu 2 milhões de credenciais verificáveis, podem ser crachás de funcionários, atestações de KYC, provas de idade, atestações de carteira, tudo o que o seu sistema já assinou e distribuiu pela rede para os funcionários. Agora um dispositivo é comprometido e você precisa que todo verificador do planeta rejeite aquela única credencial em questão de minutos, sem revelar qual credencial foi revogada, sem exigir que os verificadores façam requisições ao seu servidor emissor em produção, e sem uma varredura `O(n)` em uma lista de revogação. Esse é o problema da revogação de credenciais.

As abordagens comuns como `CRLs` **Certificate Revocation Lists** e `OCSP` **Online Certificate Status Protocol** ou vazam privacidade, ou não escalam, ou precisam de uma infra centralizada que vira um ponto único de falha. O `W3C` padronizou uma nova solução em 2015 chamada [BitstringStatusList](https://www.w3.org/TR/vc-bitstring-status-list/). Construir o seu sistema em torno dela permite que ele lide com milhões de credenciais, revogações concorrentes, várias autoridades suspendendo de forma independente, atribuição aleatória de índices para VC por privacidade, e um pipeline preguiçoso que publica quando estiver pronto.

## Como a Bitstring list resolve isso

Pense em uma bitstring como um registrador de status gigante, em que cada credencial recebe **um índice** em uma bitstring enorme. Bit `0` = válida, bit `1` = revogada ou suspensa, depende do seu design. Para revogar a credencial `#94,567`, por exemplo, você troca o bit `94,567` de `0` para `1`, e para checar se ela foi revogada, você só lê esse mesmo bit, e é isso,

```bash
Index:     0  1  2  3  4 ... 94567 ... 2097151
Bitstring: 0  0  0  1  0 ...   1   ...    0

                                ↑
                      credential #94567 is revoked here
```

Um pipeline bem simples para revogação! A bitstring é comprimida com `GZIP`, codificada em `base64url` com um prefixo multibase `u`, assinada e publicada como uma `Verifiable Credential` ela mesma, a `BitstringStatusListCredential`. Um verificador baixa ela, descomprime e lê o bit. Um fetch, uma checagem de bit, pronto.

É por isso que escala: a bitstring tem tamanho fixo, não importa quantas credenciais sejam revogadas. Uma lista de 2 milhões de entradas tem `256 KB` no estado descomprimido, mas com taxas de revogação típicas abaixo de 1%, o `GZIP` reduz isso para `1-3 KB`. Uma `CDN` serve isso em ms.

Taxas de compressão para uma lista `2,097,152-bit` de `256 KB`:

| Taxa de preenchimento | Bits ligados | Tamanho comprimido | Proporção |
|-----------|----------|-----------------|-------|
| 0% (vazia) | 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% (aleatória) | ~1M | ~256 KB | 1:1 |

Com taxas de revogação do mundo real, o status inteiro de 2 milhões de credenciais cabe em menos de `8 KB`. Uma CDN consegue cachear e servir isso facilmente.

## Vinculando uma credencial a uma bitstring

Quando uma credencial é emitida, você embute uma entrada `credentialStatus` apontando para a status list. Por exemplo:

```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"
  }
}
```

Todo verificador resolve a `statusListCredential`, descomprime a bitstring, lê o bit `94,567` e, se ele for `1`, a credencial está revogada, se for 0 ela continua ativa.

Alguns requisitos do `W3C` que vale a pena conhecer:

- `statusListIndex` é uma string decimal, não um inteiro
- O tamanho mínimo da bitstring é de `131,072` entradas, **16 KB**, adotado como padrão para garantir herd privacy
- O `statusPurpose` na entrada DEVE ser igual ao `statusPurpose` na status list credential
- Compressão `GZIP` conforme a `RFC 1952`, codificada em multibase com o prefixo `u`, "base64url, sem padding"

## Manipulação de bits no nível do byte

Essa é a parte legal. A bitstring é `big-endian` dentro de cada byte, então o índice `0` é o bit mais à esquerda, o "mais significativo", do 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)
```

Em 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);
}
```

Por que `7 - (index % 8)`? A spec do `W3C` define o índice `0` como o bit mais à esquerda, então em um byte `0b1000_0000`, essa é a posição de bit `7`, contando a partir de `0` pela direita. A subtração converte a ordem da spec para a ordem do byte.

Compressão e codificação para o formato `W3C`:

```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))
}
```

NOTA: `clear_bit` é o que torna a suspensão reversível. Operações de revogação NUNCA devem chamar `clear_bit`, depois que uma credencial é revogada, ela está morta para sempre, e isso é garantido na camada de serviço, em que o serviço de revogação expõe os endpoints `suspend`/`unsuspend`, mas só `revoke`, sem `unrevoke`. A bitstring em si não sabe nada de propósito, a irreversibilidade da revogação é uma regra de negócio, não uma propriedade da estrutura de dados

## Segurança em escritas concorrentes

Existe uma possibilidade, que a gente viveu na prática, de vários serviços estarem revogando credenciais ao mesmo tempo. Sem uma coordenação clara, duas trocas de bit concorrentes na mesma lista corrompem (`corrupts`) a `bitstring`. O clássico problema de lost update. O servidor A lê a bitstring e troca o bit `100`, mas o servidor B lê a mesma bitstring antes de A gravar de volta e troca o bit `200`. B grava de volta, sobrescrevendo a mudança de A, e o bit 100, infelizmente, nunca é ligado.

Como eu resolvi isso? Locking pessimista no nível da linha

![locking pessimista no nível da linha](https://i.ibb.co/234SsZ9L/diagram.png)

Em Rust com `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))
}
```

O que está acontecendo aqui:

- `SELECT ... FOR UPDATE` pega um lock no nível da linha, e as transações concorrentes ficam bloqueadas aqui
- Checa se o bit já está ligado, "idempotente"
- Troca o bit em memória e grava a bitstring atualizada de volta
- O lock fica preso durante a transação inteira, leitura, troca, escrita, log

A conta: com 7 tipos de credencial × 3 propósitos, são 21 status lists, então revogações concorrentes em tipos de credencial diferentes nunca disputam entre si. Revogações na mesma lista são serializadas pelo `FOR UPDATE`. O tempo de retenção do lock fica abaixo de 5ms, "uma leitura, uma escrita, um insert de log", e a 100 revogações/segundo, a profundidade da fila fica abaixo de 1.

Mas o trade-off de I/O é real. Cada revogação lê `256 KB` do Psql, troca um bit e grava `256 KB` de volta, mais o `WAL`. Isso dá mais ou menos `~768 KB` de I/O por revogação. A 1.000 revogações/minuto, isso é `~750 MB/minute`. O Psql aguenta isso tranquilamente em SSDs modernos, mas esse é o principal desafio de escala. Para um throughput maior, o que a gente fez foi agrupar as trocas de bit, acumular as revogações em uma fila e aplicar todas em um único fluxo de leitura, modificação e escrita.

## Por que a alocação sequencial de índices vaza informação

Se você atribui índices sequencialmente, "credencial 1 => índice 0, credencial 2 => índice 1, e assim por diante", um observador atento que conhece os índices de duas credenciais consegue inferir a ordem de emissão delas e o número aproximado de credenciais emitidas entre elas. Os índices DEVEM ser atribuídos de forma aleatória, NUNCA SEQUENCIAL.

De um ponto de vista mais técnico, a solução aqui é uma [cifra de permutação Feistel](https://lib.rs/crates/feistel-permutation-rs) com chave, que mapeia contadores sequenciais para índices pseudoaleatórios. É uma bijeção, 100% determinística, o mesmo contador sempre mapeia para o mesmo índice, e é reversível com a chave

```bash
Counter:   0   1   2   3   4   5
              ↓ Feistel permutation
Index:   847  23  1902  556  12  2041
```

Uma rede `Feistel` de 6 rodadas com função de rodada `SHA-256`:

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

Por que isso funcionou:

- Todo contador mapeia para um índice único, "bijetivo", uma propriedade demonstrável de redes Feistel balanceadas com `≥4 rounds`
- Chaves diferentes produzem permutações diferentes. Cada lista deriva a sua própria chave, `SHA-256(master_secret || list_id || "index-permutation")`
- Overhead desprezível, `6×` `SHA-256` por alocação, `~18μs`

Então um hacker ou agente mal-intencionado que obtenha duas credenciais não consegue determinar quantas foram emitidas entre elas, nem qual foi emitida primeiro, segundo ou terceiro. A permutação sempre opera sobre o espaço completo de `2^21` (2.097.152), não importa quantos índices já tenham sido alocados até agora

## Três listas por credencial

Uma única lista de revogação não é suficiente. Cada uma com um `statusPurpose` diferente, e em produção você na verdade precisa de três dimensões de status independentes,

![3 listas por credencial](https://i.ibb.co/xqTJ16pv/diagram2.png)

| Cenário | Quem age | Qual lista | É reversível? |
|----------|----------|------------|-------------|
| Funcionário demitido | O Emissor | revocation | Não, a credencial some para sempre |
| Investigação de fraude pendente | O Emissor | suspension "issuer" | Sim, o emissor tira a suspensão depois de liberado com evidências |
| Um usuário relata que perdeu o celular | O Titular | suspension "holder" | Sim, o titular tira a suspensão pelo novo dispositivo depois de se registrar de novo |

Cada lista que você vê é uma `bitstring` separada, com uma autoridade de assinatura separada, e este é o schema do db que faz isso funcionar

```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)
);
```

Esse cara garante exatamente uma lista ativa por combinação `(credential_type, purpose, authority, sequence)`

Alocação tripla durante a emissão da credencial, três atribuições de índice independentes para uma única credencial, e as três também ficam no array `credentialStatus` da credencial

```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?;
```

Toda verificação checa as três, e a credencial só é válida se:

```
NOT revoked  AND  NOT issuer suspended  AND  NOT holder suspended all strictly
```

### Publicação custodial

Foi aqui que a gente se confundiu um pouco. O titular controla qual bit é trocado, ele envia uma mensagem de autorização assinada que o serviço de revogação deve verificar antes de aceitar a troca do bit. Mas lembre que a infra do emissor comprime, assina e publica todas as status list credentials, incluindo as da autoridade do titular

Sem esse modelo custodial, todo titular precisaria do seu próprio acesso ao `Arweave`, das suas `signing keys` e de distribuição via `CDN`. O que não é realista. O emissor da `BitstringStatusListCredential` pode ser diferente do emissor da `VerifiableCredential`. A autorização determina quem pode trocar bits. A publicação determina quem assina e distribui a lista.

## Provando que você tem o direito de revogar

Qualquer um deveria poder chamar a API de revogação, então você precisa de uma prova de que quem chama é realmente dono do bit que pediu para trocar.

Mensagens de autorização assinadas com separação de domínio:

```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}")
```

O prefixo `revoke:v1` vs `holder-suspend:v1` impede uma coisa chamada replay entre operações, em que a assinatura de revogação de um emissor não pode ser usada para fazer uma suspensão de titular, mesmo que a mesma chave seja usada para as duas

```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(())
}
```

Para a suspensão pelo titular, o mesmo padrão se aplica, com três diferenças principais

- O `DID` do signatário sempre tem que ser igual ao `DID` do subject, não ao do emissor
- A chave pública é sempre resolvida dinamicamente a partir do documento `DID` via o serviço de `DID`
- O prefixo da mensagem seria `holder-suspend:v1` em vez de `revoke:v1`

## O que acontece quando 2 milhões não bastam

Quando o `next_index` chega ao tamanho da lista, você faz a rotação para uma lista nova, e é só isso:

```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),
};
```

"Segurança na rotação concorrente" Duas txn's podem ver a lista como cheia ao mesmo tempo. O `CREATE` usa `ON CONFLICT DO NOTHING`, então a segunda transação cai em um `SELECT` da lista já criada. As duas devem seguir com a alocação na mesma lista nova. E nada de listas duplicadas.

Como isso vai ficar:

| Credenciais emitidas | Listas por propósito | Total de listas 3 "propósitos × 7 tipos" |
|-------------------|-------------------|-------------------------------------|
| 1 milhão | 1 por tipo | 21 |
| 10 milhões | ~5 por tipo | 105 |
| 100 milhões | ~48 por tipo | 1.008 |

Cada lista pode ser publicada e cacheada por conta própria. Os verificadores não percebem a rotação, porque a URL `statusListCredential` da credencial aponta para uma lista específica, e não para um alias que rotaciona.

## O pipeline de publicação

Uma troca de bit no psql é invisível para os verificadores. A bitstring atualizada tem que ser comprimida, assinada e publicada. Esse é um pipeline que, no fim, converge para o mesmo estado

![fluxo de publicação e ancoragem](https://i.ibb.co/HTcMQSR2/daigarm3-2.png)

### Lógica ideal de debounce

Se 50 credenciais forem revogadas em 30 segundos, digamos, num comprometimento em larga escala, você não vai querer ficar de boa esperando 50 fluxos de publicação separados, cada um comprimindo `256 KB`, assinando, subindo para um armazenamento permanente e enviando para a CDN. O auto publisher espera um `debounce_secs` definido, `default 60s`, depois da última atualização antes de publicar. Se as atualizações simplesmente continuarem chegando, o `max_delay_secs` `default 120s ` força uma publicação mesmo assim

No pior cenário, a defasagem é limitada, `120s` de atraso máximo + `~2s` de compress/sign/upload = `~122 seconds` desde a primeira troca de bit até a disponibilidade para o verificador.

**OBSERVAÇÃO:**
"Quando considerar accumulators em vez disso" se o seu modelo de ameaça exige unlinkability de apresentação para os usuários e provas de não revogação, por exemplo para votação anônima ou uma configuração de verificação de idade com privacidade. Os custos computacionais e de infra são maiores, mas as garantias de privacidade aqui são mais fortes

## Mais coisas importantes que aprendi pelo caminho

### Alocação tripla não atômica

Três chamadas independentes para as três entradas de status durante a emissão da credencial. Se a chamada 2 falhar, a alocação da chamada 1 fica órfã. O que eu fiz então foi configurar uma RPC que faz as três alocações em uma única transação no db

### O debounce evita tempestades de republicação

Sem debounce, revogar `100` credenciais em lote dispara `100` fluxos de publicação separados, cada um comprimindo `256 KB`, assinando, subindo para o armazenamento permanente e enviando para a CDN. Isso é desnecessário. O debounce de `60s` que adicionamos junta tudo isso em uma única publicação, e o atraso máximo de `120s` limita a defasagem no pior cenário. Isso cortou a nossa carga de publicação em cerca de `50×` durante uma operação em lote

### Armazenamento duplo, integridade dupla

O armazenamento permanente te dá imutabilidade, mas a imutabilidade sozinha não prova que o conteúdo é o que você espera. A âncora na blockchain registra um `SHA-256(credential_json)` onChain. A verificação busca do armazenamento, calcula o hash e compara com o hash onChain. Se algum dos dois sistemas for adulterado, a diferença é fácil de detectar

### Os números em escala

Para um sistema com 7 tipos de credencial, alocação tripla e listas de `2M-bit` com 10 milhões de credenciais emitidas

- Status lists, ~105 ativas "5 por tipo × 7 tipos × 3 propósitos"
- Armazenamento de bitstring no DB, ~105 × 256 KB = ~27 MB
- Alocações de índice, 30 milhões de linhas "3 por credencial"
- Credenciais publicadas, ~105 × 3 KB = ~315 KB no total na CDN
- Por revogação, ~768 KB de I/O no DB, menos de 5ms de lock, no máximo 60-120s de latência de publicação
- Por verificação, ~9 KB de download da CDN, menos de 10ms no total "cache quente"
- Teto de throughput "um único PostgreSQL", ~200 revogações/seg por lista, ~1000 alocações/seg por lista, ~10.000 checagens de status/seg

## Links essenciais

- [W3C BitstringStatusList v1.0](https://www.w3.org/TR/vc-bitstring-status-list/), A Recommendation formal do W3C para revogação e suspensão de credenciais
- [W3C Verifiable Credentials Data Model v2.0](https://www.w3.org/TR/vc-data-model-2.0/), A especificação mãe para VCs
- [Digital Bazaar vc-bitstring-status-list](https://github.com/digitalbazaar/vc-bitstring-status-list), Implementação de referência em JS
- [W3C Data Integrity EdDSA Cryptosuites](https://www.w3.org/TR/vc-di-eddsa/), A especificação de assinatura eddsa-jcs-2022
- [ALLOSAUR: Accumulator with Low-Latency Oblivious and Succinct Revocation](https://eprint.iacr.org/2022/1362), A alternativa de revogação mais forte
- [CRSet: Cascade-Based Revocation Sets](https://arxiv.org/abs/2501.17089), Abordagem com cascata de Bloom filters para revogação que preserva a privacidade
- [Hyperledger AnonCreds Specification](https://hyperledger.github.io/anoncreds-spec/), Alternativa baseada em accumulator com unlinkability total

> Levei algumas semanas para escrever isso, obrigado pela leitura, compartilha aí 😂❤️