Rechercher⌘K

GitHub

X

Site web

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

Disons que vous avez émis 2 millions d'attestations vérifiables, que ce soit des badges d'employés, des attestations KYC, des preuves d'âge, des attestations de wallet, tout ce que votre système a pu signer et distribuer sur le réseau aux employés. Maintenant, un appareil est compromis et vous avez besoin que chaque vérificateur de la planète rejette cette attestation précise en quelques minutes, sans révéler quelle attestation a été révoquée, sans obliger les vérificateurs à envoyer des requêtes à votre serveur émetteur déployé, et sans parcours en O(n) d'une liste de révocation. C'est ça, le problème de la révocation des attestations.

Les approches classiques comme les CRLs Certificate Revocation Lists et OCSP Online Certificate Status Protocol soit font fuiter des données privées, soit ne passent pas à l'échelle, soit nécessitent une infra centralisée qui devient un point de défaillance unique. Le W3C a standardisé une nouvelle solution en 2015, appelée BitstringStatusList. Construire votre système autour d'elle lui permet de gérer des millions d'attestations, des révocations concurrentes, plusieurs autorités qui suspendent indépendamment, une attribution aléatoire des index des VC pour la confidentialité, et un pipeline de publication paresseuse quand tout est prêt.

Comment les listes bitstring résolvent ce problème

Voyez un bitstring comme un énorme registre d'état où chaque attestation se voit attribuer un index dans un énorme bitstring. Bit 0 = valide, bit 1 = révoqué ou suspendu selon votre conception. Pour révoquer l'attestation #94,567 par exemple, vous basculez le bit 94,567 de 0 à 1, et pour vérifier si elle est révoquée, vous lisez simplement ce même bit, et c'est tout,

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

Un pipeline de révocation plutôt simple ! Le bitstring est compressé en GZIP, encodé en base64url avec un préfixe multibase u, signé, et publié lui-même comme une Verifiable Credential, la BitstringStatusListCredential. Un vérificateur la récupère, la décompresse, lit le bit. Un seul fetch, une seule vérification de bit, terminé.

Voilà pourquoi ça passe à l'échelle : le bitstring a une taille fixe, quel que soit le nombre d'attestations révoquées. Une liste de 2 millions d'entrées pèse 256 KB non compressée, mais avec des taux de révocation typiques inférieurs à 1 %, GZIP la réduit à 1-3 KB. Un CDN la sert en quelques ms.

Taux de compression pour une liste 2,097,152-bit de 256 KB :

Avec des taux de révocation réels, l'état complet de 2 millions d'attestations tient en moins de 8 KB. Un CDN peut facilement mettre ça en cache et le servir.

Lier une attestation à un bitstring

Quand une attestation est émise, vous y intégrez une entrée credentialStatus qui pointe vers la liste de statuts. Par exemple :

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

Chaque vérificateur déréférence statusListCredential, décompresse le bitstring, lit le bit 94,567, et s'il vaut 1, l'attestation est révoquée, s'il vaut 0, elle est toujours active.

Quelques exigences du W3C bonnes à connaître :

• statusListIndex est une chaîne décimale, pas un entier
• La taille minimale du bitstring est de 131,072 entrées 16 KB, valeur par défaut pour la confidentialité de groupe
• Le statusPurpose de l'entrée DOIT correspondre au statusPurpose de la status list credential
• Compression GZIP selon la RFC 1952, encodage multibase avec le préfixe u, « base64url, sans padding »

Manipulation de bits au niveau de l'octet

C'est la partie sympa. Le bitstring est en big-endian au sein de chaque octet, donc l'index 0 correspond au bit le plus à gauche, « le plus significatif », de l'octet 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);
}

Pourquoi 7 - (index % 8) ? La spec du W3C définit l'index 0 comme le bit le plus à gauche, donc dans un octet 0b1000_0000, c'est la position de bit 7 en comptant à partir de 0 depuis la droite. La soustraction convertit l'ordre de la spec en ordre des bits dans l'octet.

Compression et encodage au format 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))
}

REMARQUE : clear_bit est ce qui rend la suspension réversible. Les opérations de révocation ne doivent JAMAIS appeler clear_bit, une fois qu'une attestation est révoquée, elle est morte pour toujours, et c'est imposé au niveau de la couche service, où le service de révocation expose des endpoints suspend/unsuspend mais uniquement revoke, pas de unrevoke. Le bitstring lui-même est agnostique quant à la finalité, l'irréversibilité de la révocation est une règle métier, pas une propriété de la structure de données

Sécurité des écritures concurrentes

Il peut arriver, et nous l'avons vécu, que plusieurs services révoquent des attestations en même temps. Sans coordination claire, deux basculements de bits concurrents sur la même liste corrompent (corrupts) le bitstring. Le problème classique de la mise à jour perdue. Le serveur A lit le bitstring et bascule le bit 100, mais le serveur B lit le même bitstring avant que A ne réécrive et bascule le bit 200. B réécrit, en écrasant la modification de A, et malheureusement le bit 100 n'est jamais positionné.

Comment j'ai corrigé ça ? Avec un verrouillage pessimiste au niveau de la ligne

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

Ce qui se passe ici :

• SELECT ... FOR UPDATE prend un verrou au niveau de la ligne, les transactions concurrentes sont bloquées ici
• Vérifie si le bit est déjà positionné « idempotent »
• Bascule le bit en mémoire, réécrit le bitstring mis à jour
• Verrou conservé pendant toute la transaction, lecture, basculement, écriture, log

Les calculs : avec 7 types d'attestations × 3 finalités, ça fait 21 listes de statuts, donc les révocations concurrentes sur des types d'attestations différents n'entrent jamais en concurrence entre elles. Les révocations sur une même liste sont sérialisées via FOR UPDATE. Le verrou est tenu moins de 5 ms « une lecture, une écriture, une insertion de log », et à 100 révocations/seconde, la profondeur de la file reste inférieure à 1.

Le compromis en I/O est bien réel, cela dit. Chaque révocation lit 256 KB depuis Psql, bascule un bit, réécrit 256 KB, plus le WAL. Ça fait à peu près ~768 KB d'I/O par révocation. À 1 000 révocations/minute, ça fait ~750 MB/minute. Psql gère ça sans problème sur des SSD modernes, mais c'est le principal défi de passage à l'échelle. Pour un débit plus élevé, ce que nous avons fait, c'est regrouper les basculements de bits, accumuler les révocations dans une file et les appliquer en un seul flux lecture, modification, écriture.

Pourquoi l'attribution séquentielle des index fait fuiter de l'information

Si vous attribuez les index de façon séquentielle « attestation 1 => index 0, attestation 2 => index 1, et ainsi de suite », un observateur attentif qui connaît les index de deux attestations peut en déduire leur ordre d'émission et le nombre approximatif d'attestations émises entre les deux. Les index DEVRAIENT être attribués aléatoirement, jamais SÉQUENTIELLEMENT.

D'un point de vue plus technique, la solution ici est un chiffrement par permutation de Feistel à clé, qui fait correspondre des compteurs séquentiels à des index pseudo aléatoires. C'est une bijection, 100 % déterministe, le même compteur correspond toujours au même index, et c'est réversible avec la clé

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

Un réseau de Feistel à 6 tours avec une fonction de tour 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
}

Pourquoi ça a marché :

• Chaque compteur correspond à un index unique « bijectif », une propriété démontrable des réseaux de Feistel équilibrés avec ≥4 rounds
• Des clés différentes produisent des permutations différentes. Chaque liste dérive sa propre clé, SHA-256(master_secret || list_id || "index-permutation")
• Surcoût négligeable, 6× SHA-256 par attribution, ~18μs

Donc un hacker ou un acteur qui obtient deux attestations ne peut pas déterminer combien ont été émises entre les deux, ni laquelle a été émise en premier, en deuxième ou en troisième. La permutation opère toujours sur l'espace complet de 2^21 (2 097 152), quel que soit le nombre d'index déjà attribués

Trois listes par attestation

Une seule liste de révocation ne suffit pas. En production, il vous faut en réalité trois dimensions de statut indépendantes, chacune avec un statusPurpose différent,

Chaque liste que vous voyez est un bitstring distinct avec une autorité de signature distincte, et voici le schéma de base de données qui fait fonctionner tout ça

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

Ce petit gars garantit qu'il y a exactement une liste active par combinaison (credential_type, purpose, authority, sequence)

Triple attribution lors de l'émission d'une attestation, trois attributions d'index indépendantes pour une seule attestation, et les trois se retrouvent aussi dans le tableau credentialStatus de l'attestation

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

Chaque vérification contrôle les trois, l'attestation n'est valide que si :

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

Publication en mode custodial

C'est là que nous nous sommes un peu embrouillés. Le détenteur contrôle quel bit est basculé, il envoie un message d'autorisation signé que le service de révocation doit vérifier avant d'accepter le basculement. Mais rappelez-vous que c'est l'infra de l'émetteur qui compresse, signe et publie toutes les status list credentials, y compris celles dont l'autorité est le détenteur

Sans ce modèle custodial, chaque détenteur aurait besoin de son propre accès Arweave, de ses propres signing keys et de sa propre distribution CDN. Ce qui n'est pas réaliste. L'émetteur de la BitstringStatusListCredential peut être différent de l'émetteur de la VerifiableCredential. L'autorisation détermine qui peut basculer les bits. La publication détermine qui signe et distribue la liste.

Prouver que vous avez le droit de révoquer

N'importe qui doit pouvoir appeler l'API de révocation, donc vous avez besoin d'une preuve que l'appelant possède réellement le bit qu'il demande de basculer.

Des messages d'authentification signés avec séparation de domaine :

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

Le préfixe revoke:v1 vs holder-suspend:v1 empêche ce qu'on appelle un rejeu entre opérations, où la signature de révocation d'un émetteur ne peut pas être utilisée pour effectuer une suspension par le détenteur, même si la même clé est utilisée pour les deux

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

Pour la suspension par le détenteur, le même schéma s'applique avec trois différences principales

• Le DID du signataire doit toujours correspondre au DID du sujet, pas à celui de l'émetteur
• La clé publique est toujours résolue dynamiquement à partir du document DID via le service DID
• Le préfixe du message est holder-suspend:v1 au lieu de revoke:v1

Que se passe-t-il quand 2 millions ne suffisent plus

Quand next_index atteint la taille de la liste, vous passez à une nouvelle liste, c'est tout :

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

« Sécurité de la rotation concurrente » Deux txn peuvent toutes les deux voir la liste comme pleine. Le CREATE utilise ON CONFLICT DO NOTHING, donc la seconde transaction se rabat sur un SELECT de la liste déjà créée. Les deux poursuivent alors l'attribution sur la même nouvelle liste. Et aucune liste en double.

Ce que ça donne :

Chaque liste peut être publiée et mise en cache séparément. Les vérificateurs ne remarquent pas la rotation, parce que l'URL statusListCredential de l'attestation pointe vers une liste précise, pas vers un alias qui tourne.

Le pipeline de publication

Un basculement de bit dans psql est invisible pour les vérificateurs. Le bitstring mis à jour doit être compressé, signé et publié. C'est un pipeline qui finit par être cohérent

Logique de debounce idéale

Si 50 attestations sont révoquées en 30 secondes, disons lors d'une compromission à grande échelle, vous n'avez pas envie de vous taper 50 flux de publication séparés, chacun compressant 256 KB, signant, envoyant vers un stockage permanent et poussant vers le CDN. L'auto publisher attend un debounce_secs défini default 60s après la dernière mise à jour avant de publier. Si les mises à jour continuent simplement d'arriver, max_delay_secs default 120s force quand même une publication

Dans le pire des cas, le retard est borné, 120s de délai max + ~2s de compression/signature/upload = ~122 seconds entre le premier basculement de bit et la disponibilité pour les vérificateurs.

À NOTER : « Quand envisager plutôt des accumulateurs » si votre modèle de menace exige l'impossibilité de relier les présentations des utilisateurs et des preuves de non révocation, par exemple pour un vote anonyme ou un dispositif de vérification d'âge respectueux de la vie privée. Les coûts de calcul et d'infra sont plus élevés, mais les garanties de confidentialité sont ici plus fortes

D'autres choses importantes que j'ai apprises en chemin

Triple attribution non atomique

Trois appels indépendants pour les trois entrées de statut lors de l'émission d'une attestation. Si l'appel 2 échoue, l'attribution de l'appel 1 se retrouve orpheline. Ce que j'ai fait ensuite, c'est mettre en place une RPC qui fait les trois attributions dans une seule transaction de base de données

Le debounce évite les tempêtes de republication

Sans debounce, révoquer 100 attestations en lot déclenche 100 flux de publication séparés, chacun compressant 256 KB, signant, envoyant vers le stockage permanent et poussant vers le CDN. C'est inutile. Le debounce de 60s ajouté les regroupe en une seule publication, et le délai max de 120s borne le retard dans le pire des cas. Ça a réduit notre charge de publication d'environ 50× pendant une opération en lot

Double stockage, double intégrité

Le stockage permanent vous donne l'immuabilité, mais l'immuabilité seule ne prouve pas que le contenu est bien celui que vous attendez. L'ancrage blockchain enregistre un SHA-256(credential_json) onChain. La vérification récupère depuis le stockage, calcule le hash, le compare avec le hash onChain. Si l'un des deux systèmes est altéré, l'écart se détecte facilement

Les chiffres à grande échelle

Pour un système avec 7 types d'attestations, une triple attribution et des listes de 2M-bit, à 10 millions d'attestations émises

• Listes de statuts, ~105 actives « 5 par type × 7 types × 3 finalités »
• Stockage des bitstrings en base, ~105 × 256 KB = ~27 MB
• Attributions d'index, 30 millions de lignes « 3 par attestation »
• Attestations publiées, ~105 × 3 KB = ~315 KB au total sur le CDN
• Par révocation, ~768 KB d'I/O en base, moins de 5 ms de verrou, 60-120s de latence de publication au maximum
• Par vérification, ~9 KB téléchargés depuis le CDN, moins de 10 ms au total « cache chaud »
• Plafond de débit « un seul PostgreSQL », ~200 révocations/s par liste, ~1 000 attributions/s par liste, ~10 000 vérifications de statut/s

Liens essentiels

• W3C BitstringStatusList v1.0, La recommandation officielle du W3C pour la révocation et la suspension d'attestations
• W3C Verifiable Credentials Data Model v2.0, La spécification parente des VC
• Digital Bazaar vc-bitstring-status-list, Implémentation de référence en JS
• W3C Data Integrity EdDSA Cryptosuites, La spécification de signature eddsa-jcs-2022
• ALLOSAUR: Accumulator with Low-Latency Oblivious and Succinct Revocation, L'approche de révocation alternative la plus solide
• CRSet: Cascade-Based Revocation Sets, Une approche en cascade de filtres de Bloom pour une révocation qui préserve la vie privée
• Spécification Hyperledger AnonCreds, Une alternative basée sur des accumulateurs, avec une impossibilité totale de relier les présentations

Cet article m'a pris quelques semaines à écrire, merci de l'avoir lu, partagez-le s'il vous plaît 😂❤️