Buscar⌘K

GitHub

X

Sitio web

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

Digamos que has emitido 2 millones de credenciales verificables, pueden ser acreditaciones de empleados, atestaciones KYC, pruebas de edad, atestaciones de wallet, todo lo que tu sistema ha firmado y distribuido alguna vez por la red a los empleados. Ahora un dispositivo queda comprometido y necesitas que todos los verificadores del planeta rechacen esa única credencial en cuestión de minutos, sin revelar qué credencial se revocó, sin obligar a los verificadores a hacer peticiones a tu servidor emisor desplegado, y sin hacer un escaneo O(n) de una lista de revocación. Ese es el problema de la revocación de credenciales.

Los enfoques habituales como las CRLs Certificate Revocation Lists y OCSP Online Certificate Status Protocol o filtran privacidad, o no escalan, o necesitan una infraestructura centralizada que se convierte en un punto único de fallo. El W3C estandarizó una nueva solución en 2015 llamada BitstringStatusList. Construir tu sistema alrededor de ella le permite manejar millones de credenciales, revocaciones concurrentes, varias autoridades que suspenden de forma independiente, asignación aleatoria de índices para las VC por privacidad, y un pipeline de publicación diferida que publica cuando todo está listo.

Cómo lo resuelven las Bitstring lists

Piensa en un bitstring como un registro de estado enorme donde cada credencial recibe un índice dentro de un bitstring gigante. Bit 0 = válida, bit 1 = revocada o suspendida, según tu diseño. Para revocar la credencial #94,567, por ejemplo, cambias el bit 94,567 de 0 a 1, y para comprobar si está revocada, solo lees ese mismo bit, y eso es todo,

Index:     0  1  2  3  4 ... 94567 ... 2097151
Bitstring: 0  0  0  1  0 ...   1   ...    0
 
                                ↑
                      credential #94567 is revoked here

¡Un pipeline de revocación bastante simple! El bitstring se comprime con GZIP, se codifica en base64url con un prefijo multibase u, se firma y se publica como una Verifiable Credential en sí misma, la BitstringStatusListCredential. Un verificador la descarga, la descomprime y lee el bit. Una descarga, una comprobación de un bit, y listo.

Por eso escala: el bitstring tiene un tamaño fijo sin importar cuántas credenciales se revoquen. Una lista de 2 millones de entradas ocupa 256 KB sin comprimir, pero con tasas de revocación típicas por debajo del 1%, GZIP lo reduce a 1-3 KB. Una CDN lo sirve en ms.

Tasas de compresión para una lista de 2,097,152-bit de 256 KB:

Con tasas de revocación del mundo real, todo el estado de 2 millones de credenciales cabe en menos de 8 KB. Una CDN puede cachearlo y servirlo fácilmente.

Vincular una credencial a un bitstring

Cuando se emite una credencial, incrustas una entrada credentialStatus que apunta a la lista de estado. Por ejemplo:

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

Cada verificador desreferencia statusListCredential, descomprime el bitstring, lee el bit 94,567 y, si es 1, la credencial está revocada, si es 0 sigue activa.

Algunos requisitos del W3C que vale la pena conocer:

• statusListIndex es un string decimal, no un entero
• El tamaño mínimo del bitstring es de 131,072 entradas 16 KB, el valor por defecto para la privacidad de grupo
• El statusPurpose de la entrada DEBE coincidir con el statusPurpose de la credencial de la lista de estado
• Compresión GZIP según RFC 1952, codificación multibase con prefijo u, "base64url, sin padding"

Manipulación de bits a nivel de byte

Esta es la parte divertida. El bitstring es big-endian dentro de cada byte, así que el índice 0 es el bit "más significativo", el que está más a la izquierda, del 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)

En 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 qué 7 - (index % 8)? La especificación del W3C define el índice 0 como el bit más a la izquierda, así que en un byte 0b1000_0000, esa es la posición de bit 7 contando desde 0 por la derecha. La resta convierte el orden de la especificación al orden del byte.

Compresión y codificación al formato del 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 es lo que hace que la suspensión sea reversible. Las operaciones de revocación NUNCA deben llamar a clear_bit, una vez que una credencial se revoca, queda muerta para siempre, y esto se aplica en la capa de servicio, donde el servicio de revocación expone endpoints suspend/unsuspend pero solo revoke, sin unrevoke. Al bitstring en sí le da igual el propósito, la irreversibilidad de la revocación es una regla de negocio, no una propiedad de la estructura de datos

Seguridad en escrituras concurrentes

Existe una posibilidad, que vivimos en carne propia, de que varios servicios estén revocando credenciales al mismo tiempo. Sin una coordinación clara, dos cambios de bit concurrentes en la misma lista corrompen (corrupts) el bitstring. El clásico problema de la actualización perdida. El servidor A lee el bitstring y cambia el bit 100, pero el servidor B lee el mismo bitstring antes de que A escriba y cambia el bit 200. B escribe, sobrescribiendo el cambio de A, y por desgracia el bit 100 nunca se activa.

¿Cómo lo arreglé? Bloqueo pesimista a nivel de fila

En Rust con 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))
}

Qué está pasando aquí:

• SELECT ... FOR UPDATE obtiene un bloqueo a nivel de fila, las transacciones concurrentes se bloquean aquí
• Comprueba si el bit ya está activado "idempotente"
• Cambia el bit en memoria y escribe de vuelta el bitstring actualizado
• El bloqueo se mantiene durante toda la transacción, leer, cambiar, escribir, registrar

Las cuentas: con 7 tipos de credencial × 3 propósitos son 21 listas de estado, así que las revocaciones concurrentes sobre distintos tipos de credencial nunca compiten entre sí. Las revocaciones sobre la misma lista se serializan a través de FOR UPDATE. El bloqueo se mantiene menos de 5ms "una lectura, una escritura, una inserción de log", y a 100 revocaciones/segundo, la profundidad de la cola se mantiene por debajo de 1.

Aun así, el precio en I/O es real. Cada revocación lee 256 KB de Psql, cambia un bit y escribe 256 KB de vuelta, más el WAL. Eso es más o menos ~768 KB de I/O por revocación. A 1,000 revocaciones/minuto, eso son ~750 MB/minute. Psql lo maneja bien en SSDs modernos, pero es el principal reto de escalado. Para un throughput más alto, lo que hicimos fue agrupar los cambios de bit, acumular revocaciones en una cola y aplicarlas en un único flujo de lectura, modificación y escritura.

Por qué la asignación secuencial de índices filtra información

Si asignas los índices de forma secuencial "credencial 1 => índice 0, credencial 2 => índice 1, y así sucesivamente", un observador atento que conozca dos índices de credenciales puede deducir su orden de emisión y el número aproximado de credenciales emitidas entre ellas. Los índices DEBERÍAN asignarse de forma aleatoria, nunca de forma SECUENCIAL.

Desde un punto de vista más técnico, la solución aquí es un cifrado de permutación Feistel con clave que mapea contadores secuenciales a índices pseudoaleatorios. Es una biyección, 100% determinista, el mismo contador siempre se mapea al mismo índice, y es reversible con la clave

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

Una red Feistel de 6 rondas con función de ronda 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 qué funcionó:

• Cada contador se mapea a un índice único "biyectivo", una propiedad demostrable de las redes Feistel balanceadas con ≥4 rounds
• Claves distintas producen permutaciones distintas. Cada lista deriva su propia clave, SHA-256(master_secret || list_id || "index-permutation")
• Sobrecarga despreciable, 6× SHA-256 por asignación, ~18μs

Así que un hacker o actor que obtenga dos credenciales no puede determinar cuántas se emitieron entre ellas, ni cuál se emitió primero, segundo o tercero. La permutación siempre opera sobre el espacio completo de 2^21 (2,097,152) sin importar cuántos índices se hayan asignado hasta el momento

Tres listas por credencial

Una sola lista de revocación no basta. Cada una con un statusPurpose distinto, y en producción en realidad necesitas tres dimensiones de estado independientes,

Cada lista que ves es un bitstring separado con su propia autoridad de firma, y este es el esquema de db que hace que esto funcione

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

Esta restricción se asegura de que haya exactamente una lista activa por cada combinación (credential_type, purpose, authority, sequence)

Asignación triple durante la emisión de la credencial, tres asignaciones de índice independientes para una sola credencial, y las tres también irían en el array credentialStatus de la 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?;

Cada verificación comprueba las tres, la credencial solo es válida si:

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

Publicación en custodia

Aquí es donde nos confundimos un poco. El titular controla qué bit se cambia, envía un mensaje de autorización firmado que el servicio de revocación debería verificar antes de aceptar el cambio de bit. Pero recuerda que la infraestructura del emisor comprime, firma y publica todas las credenciales de listas de estado, incluidas las de autoridad del titular

Sin este modelo de custodia, cada titular necesitaría su propio acceso a Arweave, sus signing keys y su distribución por CDN. Lo cual no es realista. El emisor de la BitstringStatusListCredential puede ser distinto del emisor de la VerifiableCredential. La autorización determina quién puede cambiar bits. La publicación determina quién firma y distribuye la lista.

Demostrar que tienes derecho a revocar

Cualquiera debería poder llamar a la API de revocación, así que necesitas una prueba de que quien llama es realmente dueño del bit que pidió cambiar.

Mensajes de autorización firmados con separación de dominio:

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

El prefijo revoke:v1 frente a holder-suspend:v1 evita algo llamado replay entre operaciones, donde la firma de revocación de un emisor no se puede usar para realizar una suspensión de titular aunque se use la misma clave para ambas

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 la suspensión por parte del titular se aplica el mismo patrón, con tres diferencias principales

• El DID del firmante siempre debe coincidir con el DID del sujeto, no con el del emisor
• La clave pública siempre se resuelve de forma dinámica a partir del documento DID a través del servicio DID
• El prefijo del mensaje sería holder-suspend:v1 en lugar de revoke:v1

Qué pasa cuando 2 millones no son suficientes

Cuando next_index llega al tamaño de la lista, rotas a una lista nueva, y eso es todo:

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

"Seguridad en la rotación concurrente" Dos txn pueden ver la lista como llena al mismo tiempo. El CREATE usa ON CONFLICT DO NOTHING, así que la segunda transacción pasa a un SELECT de la lista ya creada. Ambas deberían continuar con la asignación en la misma lista nueva. Y sin listas duplicadas.

Así es como se verá:

Cada lista se puede publicar y cachear por separado. Los verificadores no notan la rotación porque la URL statusListCredential de la credencial apunta a una lista concreta, no a un alias que rota.

El pipeline de publicación

Un cambio de bit en psql es invisible para los verificadores. El bitstring actualizado tiene que comprimirse, firmarse y publicarse. Es un pipeline eventualmente consistente

Lógica de debounce ideal

Si se revocan 50 credenciales en 30 segundos, digamos, por un compromiso a gran escala, no quieres quedarte de brazos cruzados con 50 flujos de publicación separados, cada uno comprimiendo 256 KB, firmando, subiendo a un almacenamiento permanente y enviando a la CDN. El publicador automático espera un debounce_secs especificado default 60s después de la última actualización antes de publicar. Si las actualizaciones simplemente siguen llegando, max_delay_secs default 120s fuerza una publicación de todos modos

La obsolescencia en el peor de los casos está acotada, 120s de retraso máximo + ~2s de comprimir/firmar/subir = ~122 seconds desde el primer cambio de bit hasta que está disponible para el verificador.

NOTA AL MARGEN: "Cuándo considerar acumuladores en su lugar" si tu modelo de amenazas requiere que las presentaciones no se puedan vincular a los usuarios y pruebas de no revocación, por ejemplo para votaciones anónimas o una configuración de verificación de edad con privacidad. Los costos computacionales y de infraestructura son más altos, pero aquí las garantías de privacidad son más fuertes

Más cosas clave que aprendí por el camino

Asignación triple no atómica

Tres llamadas independientes para las tres entradas de estado durante la emisión de la credencial. Si la llamada 2 falla, la asignación de la llamada 1 queda huérfana. Lo que hice entonces fue montar un RPC que hace las tres asignaciones en una sola transacción de db

El debounce evita tormentas de republicación

Sin debounce, revocar 100 credenciales en un lote dispara 100 flujos de publicación separados, cada uno comprimiendo 256 KB, firmando, subiendo al almacenamiento permanente y enviando a la CDN. Eso es innecesario. El debounce de 60s que añadimos los colapsa en una sola publicación y el retraso máximo de 120s acota la obsolescencia en el peor de los casos. Esto redujo nuestra carga de publicación aproximadamente 50× durante una operación por lotes

Doble almacenamiento, doble integridad

El almacenamiento permanente te da inmutabilidad, pero la inmutabilidad por sí sola no demuestra que el contenido sea el que esperas. El anclaje en blockchain registra un SHA-256(credential_json) onChain. La verificación lo obtiene del almacenamiento, lo hashea y lo compara con el hash onChain. Si alguno de los dos sistemas se manipula, la discrepancia se detecta fácilmente

Los números a escala

Para un sistema con 7 tipos de credencial, asignación triple y listas de 2M-bit con 10 millones de credenciales emitidas

• Listas de estado, ~105 activas "5 por tipo × 7 tipos × 3 propósitos"
• Almacenamiento de bitstrings en la DB, ~105 × 256 KB = ~27 MB
• Asignaciones de índices, 30 millones de filas "3 por credencial"
• Credenciales publicadas, ~105 × 3 KB = ~315 KB en total en la CDN
• Por revocación, ~768 KB de I/O en la DB, menos de 5ms de bloqueo, 60-120s de latencia de publicación como máximo
• Por verificación, ~9 KB de descarga desde la CDN, menos de 10ms en total "caché caliente"
• Techo de throughput "un solo PostgreSQL", ~200 revocaciones/seg por lista, ~1000 asignaciones/seg por lista, ~10,000 comprobaciones de estado/seg

Enlaces esenciales

• W3C BitstringStatusList v1.0, La Recomendación formal del W3C para la revocación y suspensión de credenciales
• W3C Verifiable Credentials Data Model v2.0, La especificación padre de las VC
• Digital Bazaar vc-bitstring-status-list, Implementación de referencia en JS
• W3C Data Integrity EdDSA Cryptosuites, La especificación de firma eddsa-jcs-2022
• ALLOSAUR: Accumulator with Low-Latency Oblivious and Succinct Revocation, El enfoque alternativo de revocación más sólido
• CRSet: Cascade-Based Revocation Sets, Enfoque de cascada de filtros Bloom para una revocación que preserva la privacidad
• Especificación de Hyperledger AnonCreds, Alternativa basada en acumuladores con desvinculación total

Me llevó unas cuantas semanas escribir esto, gracias por leer, compártelo por favor 😂❤️