Shodipo Ayomide の写真
すべての記事

検証可能なクレデンシャルの失効を数百万ユーザー規模にスケールさせる

·
2026年3月14日
·
11 分で読めます
·
••• 回閲覧
·
••• いいね

英語の原文から翻訳した記事です。 英語で読む

検証可能なクレデンシャルの失効を数百万ユーザー規模にスケールさせる

例えば、200 万件の検証可能なクレデンシャルを発行したとしましょう。従業員バッジ、KYC の証明、年齢証明、ウォレットの証明など、あなたのシステムがこれまでに署名し、ネットワークを通じて従業員に配布してきたあらゆるものです。そこで、あるデバイスが侵害され、地球上のすべての検証者に、そのクレデンシャル 1 件を数分以内に拒否させる必要が出てきました。しかも、どのクレデンシャルが失効したのかを明かさず、検証者にデプロイ済みの発行者サーバーへのリクエストを求めず、失効リストを O(n) でスキャンすることもなく、です。これがクレデンシャル失効の問題です。

CRLs Certificate Revocation Lists や OCSP Online Certificate Status Protocol のような従来のアプローチは、プライバシーが漏れるか、スケールしないか、単一障害点になる中央集権的なインフラを必要とするかのいずれかです。W3C は 2015 年に、BitstringStatusList という新しいソリューションを標準化しました。これを中心にシステムを構築すれば、数百万件のクレデンシャル、同時に発生する失効、複数の権限者による独立した一時停止、プライバシーのための VC へのランダムなインデックス割り当て、そして準備ができてから遅延して公開するパイプラインに対応できます。

Bitstring リストはこれをどう解決するのか

ビット列（bitstring）を巨大なステータスレジスタだと考えてください。すべてのクレデンシャルには、巨大なビット列の中の インデックス が 1 つ割り当てられます。ビット 0 = 有効、ビット 1 = 失効または一時停止で、どちらにするかは設計次第です。例えばクレデンシャル #94,567 を失効させるには、ビット 94,567 を 0 から 1 に反転させます。失効しているかを確認するには、同じビットを読むだけです。それですべてです。

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

失効のパイプラインはとてもシンプルです！ ビット列は GZIP で圧縮され、u の multibase プレフィックス付きで base64url エンコードされ、署名されて、それ自体が Verifiable Credential である BitstringStatusListCredential として公開されます。検証者はそれを取得し、展開して、ビットを読みます。1 回の取得と 1 回のビットチェックで完了です。

これがスケールする理由です。ビット列は、失効したクレデンシャルの数に関係なく固定サイズです。200 万エントリのリストは非圧縮の状態で 256 KB ですが、一般的な失効率である 1% 未満なら、GZIP によって 1-3 KB まで縮みます。CDN ならミリ秒単位で配信できます。

2,097,152-bit 256 KB のリストの圧縮率：

埋まり率セットされたビット数圧縮後のサイズ比率
0%（空）0~300 バイト870:1
0.1%2,097~1.5 KB170:1
1%20,971~8 KB32:1
10%209,715~90 KB2.8:1
50%（ランダム）~1M~256 KB1:1

現実的な失効率なら、200 万件のクレデンシャルのステータス全体が 8 KB 未満に収まります。CDN ならそれをかんたんにキャッシュして配信できます。

クレデンシャルをビット列に紐づける

クレデンシャルを発行するときは、ステータスリストを指す credentialStatus エントリを埋め込みます。例えば：

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

すべての検証者は statusListCredential を参照してビット列を展開し、ビット 94,567 を読みます。それが 1 ならクレデンシャルは失効しており、0 ならまだ有効です。

知っておく価値のある W3C の要件：

バイトレベルでのビット操作

ここが面白いところです。ビット列は各バイトの中で big-endian なので、インデックス 0 はバイト 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)

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

なぜ 7 - (index % 8) なのでしょうか？ W3C の仕様ではインデックス 0 をいちばん左のビットと定義しているので、バイト 0b1000_0000 で言えば、右から 0 で数えてビット位置 7 にあたります。この引き算によって、仕様上の順序をバイト内の順序に変換しているのです。

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

注意：一時停止を元に戻せるのは clear_bit があるからです。失効の操作では決して clear_bit を呼んではいけません。一度失効したクレデンシャルは永久に無効であり、これはサービス層で強制されています。失効サービスは suspend/unsuspend のエンドポイントを公開していますが、revoke だけで unrevoke はありません。ビット列自体は用途を問いません。失効が不可逆であることはビジネスルールであって、データ構造の性質ではないのです

同時書き込みの安全性

実際に私たちが経験したことですが、複数のサービスが同時にクレデンシャルを失効させる可能性があります。きちんと調整しないまま同じリストに対して 2 つのビット反転が同時に行われると、bitstring が corrupts、つまり壊れてしまいます。典型的なロストアップデートの問題です。サーバー A がビット列を読み取ってビット 100 を反転させますが、A が書き戻す前にサーバー B が同じビット列を読み取り、ビット 200 を反転させます。B が書き戻すと A の変更は上書きされ、残念ながらビット 100 は一度もセットされないままになります。

私がこれをどう直したか？ 悲観的な行レベルロックです

悲観的な行レベルロック

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

ここで起きていること：

計算してみましょう。7 種類のクレデンシャル × 3 つの用途で 21 のステータスリストになるので、異なる種類のクレデンシャルに対する同時の失効が互いに競合することはありません。同じリストへの失効は FOR UPDATE によって直列化されます。ロックの保持時間は 5ms 未満「読み取り 1 回、書き込み 1 回、ログの挿入 1 回」で、毎秒 100 件の失効でもキューの深さは 1 未満に収まります。

ただし、I/O のトレードオフは無視できません。失効のたびに Psql から 256 KB を読み取り、1 ビットを反転させ、256 KB を書き戻し、さらに WAL も書かれます。失効 1 件あたり、おおよそ ~768 KB の I/O です。毎分 1,000 件の失効なら ~750 MB/minute になります。最新の SSD 上の Psql なら問題なく処理できますが、これがスケーリングにおける最大の課題です。より高いスループットが必要になったとき、私たちはビット反転をバッチ化しました。失効をキューに貯めておき、1 回の読み取り、変更、書き込みの流れでまとめて適用するのです。

連番でのインデックス割り当てが情報を漏らす理由

インデックスを連番で割り当てると「クレデンシャル 1 => インデックス 0、クレデンシャル 2 => インデックス 1、以下同様」、注意深い観察者は 2 つのクレデンシャルのインデックスを知るだけで、その発行順と、そのあいだに発行されたクレデンシャルのおおよその数を推測できてしまいます。インデックスはランダムに割り当てるべきで、決して連番にしてはいけません。

より技術的な観点から言うと、ここでの解決策は、連番のカウンターを疑似ランダムなインデックスに対応付ける、鍵付きの Feistel 置換暗号 です。これは全単射で、100% 決定的です。同じカウンターは常に同じインデックスに対応し、鍵があれば元に戻せます

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

SHA-256 をラウンド関数に使う、6 ラウンドの Feistel ネットワーク：

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
}

これがうまくいった理由：

つまり、2 つのクレデンシャルを手に入れたハッカーや攻撃者がいても、そのあいだに何件発行されたのか、どれが 1 番目でどれが 2 番目、3 番目に発行されたのかを特定することはできません。この置換は、これまでにいくつのインデックスが割り当てられたかに関係なく、常に 2^21（2,097,152）の空間全体に対して動作します

クレデンシャルごとに 3 つのリスト

失効リスト 1 つでは足りません。それぞれが異なる statusPurpose を持ち、本番環境では実際には 3 つの独立したステータスの次元が必要になります。

クレデンシャルごとに 3 つのリスト
シナリオ誰が操作するかどのリストか元に戻せるか？
従業員が解雇された発行者revocationいいえ、クレデンシャルは永久に無効
不正調査が保留中発行者suspension「issuer」はい、証拠によって疑いが晴れた後に発行者が一時停止を解除
ユーザーがスマートフォンの紛失を報告保有者suspension「holder」はい、再登録後に保有者が新しいデバイスから一時停止を解除

ここで見ている各リストは、それぞれ別の署名権限者を持つ別々の bitstring です。これを実現している DB スキーマがこちらです

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

こいつが、(credential_type, purpose, authority, sequence) の組み合わせごとに有効なリストがちょうど 1 つだけになることを保証してくれます

クレデンシャルの発行時には 3 つの割り当てを行います。1 つのクレデンシャルに対して 3 つの独立したインデックスを割り当て、その 3 つすべてがクレデンシャルの credentialStatus 配列にも入ります

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

すべての検証で 3 つすべてをチェックし、クレデンシャルが有効なのは次の場合だけです：

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

カストディアル型の公開

ここで私たちは少し混乱しました。どのビットを反転させるかは保有者がコントロールし、保有者は署名付きの承認メッセージを送ります。失効サービスは、ビット反転を受け付ける前にそれを検証する必要があります。しかし、保有者が権限を持つリストも含め、すべてのステータスリストクレデンシャルを圧縮し、署名し、公開するのは発行者のインフラだということを忘れないでください

このカストディアルモデルがなければ、すべての保有者がそれぞれ独自の Arweave へのアクセス、signing keys、CDN での配信を必要とします。それは現実的ではありません。BitstringStatusListCredential の発行者は、VerifiableCredential の発行者と異なっていても構いません。誰がビットを反転できるかは承認によって決まり、誰がリストに署名して配布するかは公開によって決まります。

失効させる権利があることを証明する

失効 API は誰でも呼び出せるべきなので、呼び出し元が反転を求めたそのビットを本当に所有しているという証明が必要です。

ドメイン分離を用いた署名付きの承認メッセージ：

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

revoke:v1 と holder-suspend:v1 というプレフィックスの違いによって、クロスオペレーションリプレイと呼ばれる攻撃を防げます。両方に同じ鍵が使われていたとしても、発行者の失効用の署名を使って保有者の一時停止を行うことはできません

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

保有者による一時停止にも同じパターンが当てはまりますが、主な違いが 3 つあります

200 万件で足りなくなったら

next_index がリストのサイズに達したら、新しいリストにローテーションします。それだけです：

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

「同時ローテーションの安全性」 2 つの txn が、どちらもリストを満杯だと判断することがあります。CREATE は ON CONFLICT DO NOTHING を使うので、2 つ目のトランザクションは、すでに作成されたリストを SELECT する処理にそのまま進みます。どちらも同じ新しいリストで割り当てを続行するはずで、リストが重複することもありません。

どのような規模になるか：

発行されたクレデンシャル数用途ごとのリスト数リストの総数 3「用途 × 7 種類」
100 万種類ごとに 121
1,000 万種類ごとに ~5105
1 億種類ごとに ~481,008

各リストは、それぞれ単独で公開・キャッシュできます。クレデンシャルの statusListCredential の URL は、ローテーションするエイリアスではなく特定のリストを指しているので、検証者がローテーションに気づくことはありません。

公開パイプライン

psql の中でのビット反転は、検証者からは見えません。更新されたビット列は、圧縮され、署名され、公開されなければなりません。これは結果整合性のパイプラインです

公開とアンカリングの流れ

理想的なデバウンスのロジック

例えば大規模な侵害が起きて、30 秒以内に 50 件のクレデンシャルが失効したとします。そのたびに 256 KB を圧縮し、署名し、永続ストレージにアップロードし、CDN にプッシュする公開フローを、50 回も別々にのんびり回したくはありませんよね。自動公開の仕組みは、最後の更新から指定された debounce_secs default 60s だけ待ってから公開します。更新が途切れずに届き続ける場合でも、max_delay_secs default 120s によって強制的に公開されます

最悪の場合でも古さには上限があります。最大遅延の 120s + 圧縮・署名・アップロードの ~2s = 最初のビット反転から検証者が利用できるようになるまで ~122 seconds です。

補足： 「代わりにアキュムレーターを検討すべきとき」 脅威モデルとして、ユーザーに対する提示の非連結性と非失効証明が必要な場合です。例えば匿名投票や、プライバシーを重視した年齢確認の仕組みなどです。計算コストやインフラのコストは高くなりますが、こちらの方がプライバシーの保証は強力です

道中で学んだその他の重要なこと

アトミックでない 3 つの割り当て

クレデンシャルの発行時に、3 つのステータスエントリのために 3 回の独立した呼び出しを行っていました。2 回目の呼び出しが失敗すると、1 回目の割り当ては孤立してしまいます。そこで私は、3 つの割り当てすべてを 1 つの DB トランザクションで行う RPC を用意しました

デバウンスで再公開の嵐を防ぐ

デバウンスがないと、100 件のクレデンシャルをバッチで失効させたときに、100 回の別々の公開フローがトリガーされます。そのそれぞれが 256 KB を圧縮し、署名し、永続ストレージにアップロードし、CDN にプッシュするのです。これは無駄です。60s のデバウンスを追加したことでこれらが 1 回の公開にまとめられ、120s の最大遅延によって最悪の場合の古さにも上限ができました。これにより、バッチ処理中の公開負荷がおよそ 50× 削減されました

二重のストレージ、二重の完全性

永続ストレージはイミュータビリティを与えてくれますが、イミュータビリティだけでは、中身が期待どおりのものであることは証明できません。ブロックチェーンのアンカーは SHA-256(credential_json) をオンチェーンに記録します。検証時にはストレージから取得し、ハッシュを計算して、オンチェーンのハッシュと比較します。どちらかのシステムが改ざんされても、その不一致はかんたんに検出できます

大規模時の数字

7 種類のクレデンシャル、3 つの割り当て、2M-bit のリストを持つシステムで、1,000 万件のクレデンシャルを発行した場合

必須リンク

これを書くのに数週間かかりました。読んでいただきありがとうございます。ぜひシェアしてください 😂❤️

•••
この記事をシェア：

最新情報を受け取る

最新の記事をメールでお届けします。