将可验证凭证撤销扩展到数百万用户

Shodipo Ayomide

2026年3月14日

阅读约 11 分钟

••• 次浏览

••• 次点赞

本文译自英文原文。阅读英文原文

本页内容

位串列表如何解决这个问题
把凭证绑定到位串上
字节级的位操作
并发写入安全
为什么顺序分配索引会泄露信息
每个凭证三个列表
托管式发布
证明你有权撤销
200 万不够用时怎么办
发布流水线
理想的防抖逻辑
一路上我学到的更多关键经验
非原子的三重分配
防抖避免重复发布风暴
双重存储，双重完整性
规模化下的数字
必读链接

•••

假设你已经签发了 200 万个可验证凭证，可能是员工工牌、KYC 证明、年龄证明、钱包证明，也就是你的系统签过名、通过网络分发给员工的所有东西。现在有一台设备被攻破了，你需要地球上每一个验证方都在几分钟内拒绝那一个凭证，同时不能暴露被撤销的是哪个凭证，不能要求验证方向你部署的签发方服务器发请求，也不能对撤销列表做 O(n) 扫描。这就是凭证撤销问题。

常规的做法，比如 CRLs 证书吊销列表 和 OCSP 在线证书状态协议，要么泄露隐私，要么无法扩展，要么需要中心化的基础设施，而它会成为单点故障。W3C 在 2015 年标准化了一个新方案，叫作 BitstringStatusList。围绕它构建系统，就能处理数以百万计的凭证、并发撤销、多个权威方各自独立地暂停凭证、为保护隐私而对 VC 随机分配索引，以及一条准备好了再延迟发布的流水线。

位串列表如何解决这个问题

可以把位串（bitstring）想象成一个巨大的状态寄存器，每个凭证都会在这个巨大的位串里被分配一个索引。位 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。验证方拿到它，解压，读取那个位。一次请求，一次位检查，搞定。

这就是它能扩展的原因：无论撤销了多少凭证，位串的大小都是固定的。一个 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 KB	170:1
1%	20,971	~8 KB	32:1
10%	209,715	~90 KB	2.8:1
50%（随机）	~1M	~256 KB	1: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 要求：

statusListIndex 是十进制字符串，而不是整数
位串的最小大小是 131,072 个条目，即 16 KB，默认采用这个值是为了群体隐私
条目中的 statusPurpose 必须（MUST）与状态列表凭证中的 statusPurpose 一致
按 RFC 1952 进行 GZIP 压缩，使用前缀 u 进行 multibase 编码，即“base64url，无填充”

字节级的位操作

这是最酷的部分。位串在每个字节内是 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。位串本身与用途无关，撤销的不可逆性是一条业务规则，而不是数据结构的属性

并发写入安全

我们亲身经历过这样一种情况：多个服务可能在同一时间撤销凭证。如果没有明确的协调，同一个列表上的两次并发位翻转就会损坏（corrupts）这个 bitstring。典型的丢失更新问题。服务器 A 读取位串并翻转位 100，但服务器 B 在 A 写回之前读取了同一个位串，并翻转了位 200。B 写回，覆盖了 A 的修改，很遗憾，位 100 永远没有被设置上。

我是怎么解决的？悲观行级锁

在 Rust 中使用 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))
}

这里发生了什么：

SELECT ... FOR UPDATE 获取行级锁，并发事务会在这里阻塞
检查该位是否已被设置，“幂等”
在内存中翻转该位，再把更新后的位串写回
锁在整个事务期间一直持有，读取、翻转、写入、记日志

算一下：7 种凭证类型 × 3 种用途，就是 21 个状态列表，所以不同凭证类型上的并发撤销永远不会相互争抢。同一个列表上的撤销通过 FOR UPDATE 串行化。锁的持有时间不到 5ms，“一次读、一次写、一次日志插入”，在每秒 100 次撤销的情况下，队列深度保持在 1 以下。

不过 I/O 上的取舍是真实存在的。每次撤销都要从 Psql 读取 256 KB，翻转一个位，再写回 256 KB，外加 WAL。算下来每次撤销大约有 ~768 KB 的 I/O。按每分钟 1,000 次撤销计算，就是 ~750 MB/minute。在现代 SSD 上 Psql 处理起来没问题，但这是扩展时面临的主要挑战。为了更高的吞吐量，我们的做法是批量翻转位，把撤销请求累积在一个队列里，然后在一次读取、修改、写入的流程中统一应用。

为什么顺序分配索引会泄露信息

如果你按顺序分配索引，“凭证 1 => 索引 0，凭证 2 => 索引 1，依此类推”，那么一个留心的观察者只要知道两个凭证的索引，就能推断出它们的签发顺序，以及它们之间大约签发了多少个凭证。索引应当（SHOULD）随机分配，永远不要按顺序（SEQUENTIALLY）分配。

从更技术的角度来看，这里的解决方案是一个带密钥的 Feistel 置换密码，它把顺序计数器映射为伪随机索引。它是一个双射，100% 确定，同一个计数器总是映射到同一个索引，并且有密钥就能逆向还原

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

一个 6 轮的 Feistel 网络，轮函数使用 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
}

为什么这行得通：

每个计数器都映射到唯一的索引，“双射”，这是轮数 ≥4 rounds 的平衡 Feistel 网络可以证明的性质
不同的密钥产生不同的置换。每个列表派生出自己的密钥，SHA-256(master_secret || list_id || "index-permutation")
开销可以忽略不计，每次分配 6× SHA-256，~18μs

所以，拿到两个凭证的黑客或攻击者，无法确定它们之间签发了多少个凭证，也无法确定哪个是第一个、第二个或第三个签发的。无论目前已经分配了多少个索引，置换始终在完整的 2^21（2,097,152）空间上进行

每个凭证三个列表

单个撤销列表是不够的。每个列表有不同的 statusPurpose，在生产环境中你实际上需要三个独立的状态维度，

场景	谁来操作	哪个列表	是否可逆？
员工被解雇	签发方	revocation	否，凭证永久失效
欺诈调查进行中	签发方	suspension “issuer”	是，拿出证据洗清嫌疑后由签发方解除暂停
用户报告手机丢失	持有者	suspension “holder”	是，重新注册后由持有者在新设备上解除暂停

你看到的每个列表都是一个独立的 bitstring，有独立的签名权威方，下面就是让这一切运转起来的数据库表结构

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) 组合恰好只有一个活跃列表

签发凭证时进行三重分配，为单个凭证分配三个独立的索引，三者也都会出现在凭证的 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?;

每次验证都会检查全部三个，只有满足以下条件时凭证才有效：

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

对于持有者暂停，同样的模式也适用，主要有三点不同

签名者的 DID 必须始终与主体的 DID 匹配，而不是与签发方匹配
公钥总是通过 DID 服务从 DID 文档中动态解析
消息前缀是 holder-suspend:v1，而不是 revoke:v1

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

“并发轮换安全”，两个事务可能都看到列表已满。CREATE 使用了 ON CONFLICT DO NOTHING，所以第二个事务会转而 SELECT 已经创建好的那个列表。两者都应该在同一个新列表上继续分配。也不会出现重复的列表。

它看起来会是这样：

已签发凭证数	每种用途的列表数	列表总数 “3 种用途 × 7 种类型”
100 万	每种类型 1 个	21
1000 万	每种类型 ~5 个	105
1 亿	每种类型 ~48 个	1,008

每个列表都可以单独发布和缓存。验证方察觉不到轮换，因为凭证的 statusListCredential URL 指向的是一个具体的列表，而不是一个会轮换的别名。

发布流水线

psql 里的一次位翻转对验证方来说是不可见的。更新后的位串必须经过压缩、签名和发布。这是一条最终一致的流水线

理想的防抖逻辑

如果 30 秒内有 50 个凭证被撤销，比如发生了一次全面的安全事件，你不会想干等 50 个独立的发布流程，每一个都要压缩 256 KB、签名、上传到永久存储、推送到 CDN。自动发布器会在最后一次更新之后等待指定的 debounce_secs default 60s，然后再发布。如果更新一直不断涌入，max_delay_secs default 120s 无论如何都会强制发布一次

最坏情况下的数据陈旧时间是有上限的，120s 最大延迟 + ~2s 压缩/签名/上传 = 从第一次位翻转到验证方可用，共 ~122 seconds。

附注： “什么时候该考虑改用累加器”，如果你的威胁模型要求对用户而言出示凭证时不可关联，并且需要非撤销证明，比如匿名投票或注重隐私的年龄验证场景。计算和基础设施成本会更高，但这里的隐私保障更强

状态列表，~105 个活跃列表，“每种类型 5 个 × 7 种类型 × 3 种用途”
数据库位串存储，~105 × 256 KB = ~27 MB
索引分配，3000 万行，“每个凭证 3 行”
已发布的凭证，~105 × 3 KB = CDN 上总共 ~315 KB
每次撤销，~768 KB 数据库 I/O，锁持有时间不到 5ms，发布延迟最多 60-120s
每次验证，~9 KB 的 CDN 下载，总耗时不到 10ms，“热缓存”
吞吐量上限，“单个 PostgreSQL”，每个列表每秒 ~200 次撤销，每个列表每秒 ~1000 次分配，每秒 ~10,000 次状态检查

必读链接

W3C BitstringStatusList v1.0，W3C 关于凭证撤销与暂停的正式推荐标准
W3C 可验证凭证数据模型 v2.0，VC 的上层规范
Digital Bazaar vc-bitstring-status-list，JS 参考实现
W3C 数据完整性 EdDSA 密码套件，eddsa-jcs-2022 签名规范
ALLOSAUR: Accumulator with Low-Latency Oblivious and Succinct Revocation，最有力的替代撤销方案
CRSet: Cascade-Based Revocation Sets，基于布隆过滤器级联、保护隐私的撤销方案
Hyperledger AnonCreds 规范，基于累加器、具备完全不可关联性的替代方案

这篇文章花了我好几周才写完，感谢阅读，欢迎分享 😂❤️

•••

分享本文：

获取最新动态

将最新文章直接发送到你的收件箱。