Buscar⌘K

GitHub

X

Site

• English
• 简体中文
• Español
• Français
• العربية
• Português
• 日本語

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

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:

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:

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

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:

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:

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

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

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

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:

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,

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

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

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:

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

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:

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

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

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

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, A Recommendation formal do W3C para revogação e suspensão de credenciais
• W3C Verifiable Credentials Data Model v2.0, A especificação mãe para VCs
• Digital Bazaar vc-bitstring-status-list, Implementação de referência em JS
• W3C Data Integrity EdDSA Cryptosuites, A especificação de assinatura eddsa-jcs-2022
• ALLOSAUR: Accumulator with Low-Latency Oblivious and Succinct Revocation, A alternativa de revogação mais forte
• CRSet: Cascade-Based Revocation Sets, Abordagem com cascata de Bloom filters para revogação que preserva a privacidade
• Hyperledger AnonCreds Specification, Alternativa baseada em accumulator com unlinkability total

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