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

> 你已经签发了 200 万个可验证凭证。一名员工的手机被偷了。你需要世界上每一个验证方都在几分钟内拒绝那一个凭证，既不能暴露是哪一个，也不能做 O(n) 扫描。

作者 Shodipo Ayomide，发布于 2026年3月14日。网页版本：https://blog.shodipoayomide.com/zh/scaling-verifiable-credential-revocation-to-millions-of-users

![将可验证凭证撤销扩展到数百万用户](https://blog.shodipoayomide.com/banners/scaling-verifiable-credential-revocation-to-millions-of-users.png)

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

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

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

可以把位串（bitstring）想象成一个巨大的状态寄存器，每个凭证都会在这个巨大的位串里被分配**一个索引**。位 `0` = 有效，位 `1` = 已撤销或已暂停，取决于你的设计。比如要撤销凭证 `#94,567`，你就把位 `94,567` 从 `0` 翻转成 `1`，要检查它是否被撤销，只需读取同一个位，就这么简单，

```bash
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` 条目。例如：

```json
{
  "@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` 最左边的那一位，也就是“最高有效位”。

```bash
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 实现：
```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` 格式：

```rust
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 永远没有被设置上。

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

![悲观行级锁](https://i.ibb.co/234SsZ9L/diagram.png)

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

这里发生了什么：

- `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 置换密码](https://lib.rs/crates/feistel-permutation-rs)，它把顺序计数器映射为伪随机索引。它是一个双射，100% 确定，同一个计数器总是映射到同一个索引，并且有密钥就能逆向还原

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

一个 6 轮的 `Feistel` 网络，轮函数使用 `SHA-256`：

```rust
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`，在生产环境中你实际上需要三个独立的状态维度，

![每个凭证 3 个列表](https://i.ibb.co/xqTJ16pv/diagram2.png)

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

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

```sql
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` 数组里

```rust
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，所以你需要证明调用方确实拥有它要求翻转的那个位。

带域分离的签名授权消息：

```bash
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` 的区分，能阻止一种叫作跨操作重放的攻击，这样即使两者使用同一个密钥，签发方的撤销签名也无法被用来执行持有者暂停

```rust
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` 达到列表大小时，你就轮换到一个新列表，仅此而已：

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

```rust
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 里的一次位翻转对验证方来说是不可见的。更新后的位串必须经过压缩、签名和发布。这是一条最终一致的流水线

![发布与锚定流程](https://i.ibb.co/HTcMQSR2/daigarm3-2.png)

### 理想的防抖逻辑

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

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

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

## 一路上我学到的更多关键经验

### 非原子的三重分配

签发凭证时，三个状态条目对应三次独立的调用。如果第 2 次调用失败，第 1 次调用的分配就成了孤儿。后来我的做法是搭建一个 RPC，在单个数据库事务中完成全部三次分配

### 防抖避免重复发布风暴

如果没有防抖，批量撤销 `100` 个凭证会触发 `100` 个独立的发布流程，每一个都要压缩 `256 KB`、签名、上传到永久存储、推送到 CDN。这完全没必要。加上 `60s` 的防抖后，这些会合并成一次发布，而 `120s` 的最大延迟则限定了最坏情况下的陈旧时间。在批量操作期间，这让我们的发布负载降低了大约 `50×`

### 双重存储，双重完整性

永久存储给了你不可变性，但单靠不可变性并不能证明内容就是你所期望的。区块链锚定会在链上记录一个 `SHA-256(credential_json)`。验证时从存储中取出内容，计算哈希，再与链上的哈希比较。无论哪个系统被篡改，这种不一致都很容易被发现

### 规模化下的数字

对于一个有 7 种凭证类型、采用三重分配、使用 `2M-bit` 列表，并已签发 1000 万个凭证的系统

- 状态列表，~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](https://www.w3.org/TR/vc-bitstring-status-list/)，W3C 关于凭证撤销与暂停的正式推荐标准
- [W3C 可验证凭证数据模型 v2.0](https://www.w3.org/TR/vc-data-model-2.0/)，VC 的上层规范
- [Digital Bazaar vc-bitstring-status-list](https://github.com/digitalbazaar/vc-bitstring-status-list)，JS 参考实现
- [W3C 数据完整性 EdDSA 密码套件](https://www.w3.org/TR/vc-di-eddsa/)，eddsa-jcs-2022 签名规范
- [ALLOSAUR: Accumulator with Low-Latency Oblivious and Succinct Revocation](https://eprint.iacr.org/2022/1362)，最有力的替代撤销方案
- [CRSet: Cascade-Based Revocation Sets](https://arxiv.org/abs/2501.17089)，基于布隆过滤器级联、保护隐私的撤销方案
- [Hyperledger AnonCreds 规范](https://hyperledger.github.io/anoncreds-spec/)，基于累加器、具备完全不可关联性的替代方案

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