Crset Private Vc Revocation

一、背景与动机

1.1 自主主权身份（SSI）

自主主权身份（Self-Sovereign Identity, SSI）是一种以用户为中心的数字身份方法，允许个人控制自己的身份数据而无需依赖中心化机构。欧洲区块链服务基础设施（EBSI）和美国国土安全部已在基于 SSI 的系统上开展实践，用于签发数字文凭和移民记录等。

1.2 可验证凭证（VC）

可验证凭证（Verifiable Credentials, VCs）是经过数字签名的结构化数据对象，用于表示可证明的声明，例如身份证件、职业执照或组织角色。与任何凭证系统一样，撤销之前签发的 VC 的能力至关重要——用于纠正错误、响应密钥泄露或反映状态变更。

1.3 现有撤销方案的核心缺陷

现有撤销机制普遍存在一个被忽视的隐私问题：签发方活动泄露。

机制	撤销数据量	持有者隐私	依赖方隐私	签发方隐私	非交互式
Bitstring Status List	< 1 bit/容量	PIR	否	仅速率	是
AnonCreds Revocation	> 12 B/容量	PIR	是	否	否
Prevoke	未知	是	是	仅速率	否
Evoke	≥ 32 B/撤销	是	取决于 gossip	仅速率	否
Sitouah et al.	≥ 2 B/有效凭证	是	是	仅速率	否
CRSet	≈ 6 bit/容量	是	是	是	是

W3C Bitstring Status List（BSL） 虽然压缩效率高，但每次撤销都是可被外部观察者发现的，使得攻击者可以推断出员工离职等内部信息。AnonCreds 虽提供持有者匿名性，但累加器的公开数据仍暴露了签发方层面的撤销信息（本质上也是一个比特串）。

传统 PKI 机制（CRL、OCSP）同样不适用：CRL 暴露聚合撤销数量，OCSP 在验证时泄露使用元数据。

核心问题：没有现有方案能同时保护签发方活动的绝对数量与相对变化，而这对于企业采用 SSI 是一个实质性障碍。

二、系统设计目标

2.1 利益相关方模型

SSI 生态中包含三类角色：

签发方（Issuer）：签发 VC，如雇主签发员工 ID。
持有者/主体（Subject）：接收并持有 VC，如员工。
依赖方（Relying Party, RP）：验证 VC，如门禁系统。

每个角色都可能成为试图推断敏感元数据的攻击者。签发方若参与撤销检查（如托管数据到自己的 Web 服务器），则可监控 RP 的验证行为，从而侵犯持有者和 RP 的隐私。外部观察者则可访问公开撤销数据，推断签发或撤销事件（如员工流失率）。

因此，需要保护两类核心信息：

展示活动（Presentation Activity）：VC 被展示时产生的元数据。
签发方活动（Issuer Activity）：签发与撤销行为的详情。

2.2 设计目标

可参数化容量：签发方应能灵活配置撤销机制实例的最大容量，以适应不同规模的用例，并在数据大小与时间跨度之间进行权衡。
签发方活动保密性：
- 分析单个快照时，攻击者不能推断已撤销或已签发 VC 的数量。
- 分析连续多个版本的撤销数据时，攻击者依然不能提取签发方的元数据（绝对数量和相对变化均需保护）。
展示活动保密性：持有者与 RP 之间的展示过程对外完全不可见，包括签发方在内的任何人都无法得知某张 VC 被展示了。
良好互操作性：无需修改已有的钱包代理（Wallet Agent）和传输协议，所有撤销检查所需信息均兼容 W3C VC 标准的 credentialStatus 字段。

三、数据结构选型

3.1 Bloom 过滤器基础

Bloom 过滤器是最广泛使用的近似成员查询（AMQ）数据结构，由长度为 $m$ 的比特串和哈希函数 $h: {0,1}^* \to \mathbb{N}_m$ 组成：

插入：将元素 $d$ 对应的位 $h(d)$ 置为 1。
查询：检查位 $h(d')$ 是否为 1。可能产生假阳性，但不产生假阴性。

3.2 过滤器级联（Filter Cascade）

在已知子集（如已签发的 VC ID）上，通过将一个 AMQ 的假阳性编码到下一级 AMQ 中，直到不再出现假阳性，可以消除假阳性。这对于撤销场景非常高效。

3.3 为何选择 Bloom 过滤器而非其他

论文考察了多种更现代的过滤器：

Cuckoo Filter：桶中显式存储了指纹（哈希值），攻击者可以直接计数，不符合隐私要求。
XOR Filter / Binary Fuse Filter：假阳性率不可自由配置（仅有 0.4% 和 0.002%），而构建高效级联需要约 50% 的假阳性率。这些过滤器固定的低假阳性率会导致级联数据量显著增大。

因此，可灵活配置假阳性率的 Bloom 过滤器是最适合构建撤销级联的选择。

四、CRSet 机制详解

4.1 标识符与哈希

每张 VC 被随机分配一个 256 位的撤销 ID（与 VC 的 id 字段完全无关）：

$$\text{ID} \in U = {0, 1}^{256}$$

在任意时间点 $i$，签发方维护三个集合：

$C_i$：已签发 VC 的 ID 集合
$R_i \subseteq C_i$：已撤销 VC 的 ID 集合
$V_i \subseteq C_i$：仍有效 VC 的 ID 集合，且 $R_i \cap V_i = \emptyset$

必须使用密码学哈希函数（如 SHA-256），而非普通快速哈希。这确保攻击者无法通过逆向过滤器中的设置位来推断可能的 ID 集合。

4.2 填充（Padding）机制

问题：即使使用级联，攻击者仍可通过分析 Bloom 过滤器的元数据（如每级过滤器的大小、设置位的数量）来推断元素数量。

解决方案：引入填充，用随机生成的 ID 将有效集合和撤销集合分别填充到固定大小：

填充后的集合：$\hat{R}$（含真实撤销 ID + 随机填充），$\hat{V}$（含真实有效 ID + 随机填充）
约束：$R \subseteq \hat{R}$，$V \subseteq \hat{V}$，$\hat{R} \cap \hat{V} = \emptyset$

固定比例：为防止泄露有效/撤销 ID 的比例，采用固定比例：

$$n_{\max} = |\hat{V}| = \frac{1}{2}|\hat{R}|$$

这确保了签发方在极端情况下也能紧急撤销所有有效凭证（$x = 1/2$ 是最坏情况的撤销率上界）。

长期容量分析（设年签发量 $v$，撤销率 $x$，年均增长 $\delta$，VC 有效期 $t$ 年）：

$$|\hat{V}| \geq (1-x) \cdot v \sum_{i=y-t}^{y} \delta^i, \quad |\hat{R}| \geq \frac{1}{1-x}|\hat{V}|$$

4.3 发布机制

定期强制发布：为实现完美可否认性，签发方必须在固定间隔（如每 24 小时）重新创建并发布过滤器级联，无论是否有新的撤销发生。这使得观察者无法通过发布时间推断撤销事件。

发布载体：使用以太坊的 Blob 携带交易（EIP-4844）作为去中心化存储，相较于写入主链数据成本较低。

容量计算：

级联总大小（比特）$\approx 5.64 \times n_{\max}$
一个 Blob（128 KB）可支持：$n_{\max} \approx 128\text{KB} / 6\text{bit} \approx 170{,}000$ 张 VC

凭证状态字段格式（符合 W3C VC 标准）：

{
  "credentialStatus": {
    "id": "eip155:1:0x32...53:dd...d3",
    "type": "CRSetEntry"
  }
}

id 字段采用 CAIP-10 标准引用区块链账户，末尾拼接撤销 ID。Blob 有官方保留期限，与定期更新（只需最新版本）完美匹配。

4.4 核心算法

算法 1：创建 CRSet 过滤器级联

输入：有效 ID 集合 V，撤销 ID 集合 R，填充容量 n_max
输出：填充后的 Bloom 过滤器级联及其盐值

1. (cascade, salt) ← ([], 随机256位值)
2. (p₀, p) ← (√p/2, 1/2)        // 目标假阳性率（两概率策略）
3. included ← pad(V, n_max)       // 有效 ID 填充至 n_max
4. excluded ← pad(R, 2·n_max)     // 撤销 ID 填充至 2·n_max
5. for i = 0; |included| > 0; i++:
   a. cascade[i] ← bloom({id∥i∥salt | id ∈ excluded}, p₀ or p, 1)
   b. fps ← {id ∈ excluded | id∥i∥salt ∈ cascade[i]}  // 假阳性
   c. excluded ← included
   d. included ← fps
6. return (cascade, salt)

关键设计点：

每次更新都必须完整重建，禁止增量更新（否则差分可被量化）。
引入确定性盐（层级索引）确保不同层的哈希行为符合随机性假设。
引入随机盐（整个级联共用）：一方面抵抗暴力破解，另一方面在创建过程无法收敛时重新采样（生成新盐）以重试。
最优假阳性率：实验确定 $p = 0.53$，接近理论最优 $1/2$。

算法 2：检查 ID 是否有效（未被撤销）

输入：VC 的撤销 ID，过滤器级联及盐值
输出：True 表示有效（在级联中），False 表示已撤销

1. for i = 0; i < len(cascade); i++:
   if id∥i∥salt ∉ cascade[i]:
       return (i mod 2 == 1)  // 偶数层确认成员，奇数层否定成员
2. return (len(cascade) mod 2 == 1)

前提假设：仅对真实存在的 VC 的 ID 进行查询（$\text{id} \in R \cup V$）。RP 只在收到由签发方正确签名的 VC 后，才会获取该签发方的 CRSet 进行查询，因此此假设在实践中成立。

4.5 性能特征

级联总大小：$\approx 5.64 \times n_{\max}$（线性增长）
级联层数：对于数十万张 VC，约为 40 层（对数增长）——这是最坏情况下的查询复杂度
空间效率：约 6 bit/容量，介于 BSL（< 1 bit）和 AnonCreds（> 12 B）之间

五、隐私形式化证明

5.1 撤销机制的形式化定义

将撤销机制定义为一个概率函数：

$$\text{create}: {(V, R, n) \in (2^U \times 2^U \times \mathbb{N}) \mid V \cap R = \emptyset} \to {0,1}^*$$

正确性要求：$d \in V \Rightarrow d \in S_i$，$d \in R \Rightarrow d \notin S_i$。

5.2 选择计数不可区分游戏（CCIG）

游戏 $\text{CCIG}(\text{create}, A, l, n)$：

攻击者 $A$ 选择两组不同的、合理的 VC 计数序列（有效数量 $NV_0, NV_1$ 和撤销数量 $NR_0, NR_1$，共 $l$ 个时间步，每个计数 < $n$），发送给挑战者。
挑战者随机选取比特 $b$，对每个时间点 $i$ 随机生成符合 $NV_{b,i}$ 和 $NR_{b,i}$ 的 ID 集合，构成合理历史，并生成对应撤销数据 $S_i$ 发回攻击者。
攻击者输出预测 $\hat{b}$，若 $\hat{b} = b$ 则赢得游戏。

定义 1（选择计数不可区分性）：若对所有高效算法 $A$、历史长度 $l$ 和容量 $n$，有：

$$\left| \Pr[\text{CCIG}(\text{create}, A, l, n) = 1] - \frac{1}{2} \right| \text{ 可忽略}$$

则称该撤销数据结构是选择计数不可区分的。

5.3 CRSet 满足该定义的证明草图

引理 1：修改版游戏 $G_1$（用随机填充替换真实 ID）的胜率恰好为 $1/2$。

证明：$G_1$ 中输出 $S$ 完全不依赖于隐藏比特 $b$，猜测是最优策略。

引理 2：任何高效攻击者都无法区分 $G_0$（原始游戏）和 $G_1$（随机填充游戏）。

证明：CRSet 的输出本质上是一组哈希值。由于假设哈希函数为随机预言机，对于任意两个输入分布 $X, Y$，有：

$$\left| \Pr_{s,x}[A(s, h(x|s)) = 1] - \Pr_{s,y}[A(s, h(y|s)) = 1] \right| \leq 2\epsilon_{\text{RO}}$$

其中 $\epsilon_{\text{RO}}$ 可忽略。这意味着不同输入集合产生的哈希集合无法被区分。

定理 1（CRSet 是选择计数不可区分的）：

综合两个引理：

$$\left| \Pr[G_0(A, l, n) = 1] - \frac{1}{2} \right| \text{ 可忽略} \quad \blacksquare$$

六、实现与评估

6.1 核心实验评估

实现：Python 核心库，基于修改版 rbloom，使用 SHA-256 哈希函数。

机器学习隐私验证实验 1（有监督回归）：

数据集：200 万条记录（有填充 vs 无填充），容量约 $\hat{r} = 10^5$。
特征：级联总大小、过滤器层数、前三层大小及设置位数量（标准归一化）。
模型：岭回归 + Lasso 回归，指标：MSE 和 $R^2$。

结果：

有填充：$R^2 \approx 0$，MSE 接近数据方差，模型只能给出均值预测——级联结构不泄露任何撤销数量信息。
无填充：模型可轻易预测 VC 数量，印证了填充的必要性。

机器学习隐私验证实验 2（深度神经网络，无特征工程）：

数据集：两组各 10,000 个均匀分布数据点，均值约 10,000 张有效 VC。
模型：多层全连接网络 + Dropout + BatchNorm，80-10-10 分割，MAE 指标。

结果：

无填充：训练和验证 MAE 均收敛到 0，网络可从二进制表示中提取 VC 数量。
有填充：训练 MAE 下降（出现记忆化），但验证 MAE 稳定在约 5,000（与均匀分布的期望绝对偏差完全吻合），即等同于随机猜测——印证了 CRSet 的隐私保护特性。

性能评估（AMD Ryzen 7 Pro 7840U，32 GB RAM）：

容量	创建时间	总大小
$10^2$ VC	~5 秒	~$10^5$ 字节
$10^7$ VC	~200 秒	~$10^7$ 字节

创建时间和总大小在对数空间中均呈近线性增长，可预测性强。
100,000 次创建测试中，未观测到一次创建失败。

6.2 端到端评估

JavaScript 实现（面向 Web 部署），包含四个组件：

CRSet Cascade：纯 JavaScript 库，实现填充级联，使用 SHA-256。
CRSet Check (CRSC)：供 RP 调用的撤销检查库。
CRSet Issuer Backend (CRSIB)：签发方后端服务，提供 REST API，管理撤销 ID 和 CRSet 更新发布。
CRSet Demonstrator：完整演示场景，模拟签发方和 RP 的 Web 应用，基于 OID4VC 协议交互。

RP 验证流程：

标准 VC 验证软件检查格式和签名。
CRSC 从 statusEntry.id 中提取地址，通过区块链 RPC（Moralis）获取最新 Blob 哈希。
从共识层（Blobscan）获取 Blob 数据，拼接反序列化为过滤器级联。
检查撤销 ID 是否在级联中。

主要性能瓶颈：两次网络往返（获取 Blob 哈希 + 获取 Blob 数据）。

发布成本：Blob gas 费用波动较大，2024 年末至 2025 年初为 2–50 Gwei，每个 Blob 成本从数美分到约 57 USD 不等。Pectra 升级后增加了每区块的 Blob 配额，成本已迅速降至数美分量级。

七、实践局限性

长期隐私风险：CRSet 是基于哈希的机制，数据公开存储，理论上攻击者可通过暴力破解，随时间逐渐提取信息。
容量切换可见性：当签发方因当前实例容量耗尽而创建新实例时（体现为新的以太坊地址），观察者若看到使用新实例的新 VC，可推断旧实例已满。但由于地址之间无内在关联，且实例通常可设计为覆盖数十年，实际泄露的信息极为有限。
区块链访问复杂度：通过第三方 API 提供商访问 Blob 数据可能损害展示活动的保密性（第三方可记录查询日志）。谨慎的 RP 可维护自己的节点。
发布成本无上界：Blob 费用直接由以太币汇率和 Blob 需求驱动，无硬性上限，这是规模化部署的一个挑战。

八、总结与思考

8.1 论文贡献

识别并形式化了 SSI 撤销机制中被忽视的签发方隐私问题，定义了「选择计数不可区分性」这一严格隐私概念。
提出 CRSet：基于填充 Bloom 过滤器级联的非交互式撤销机制，同时保护签发方、RP 和持有者三方隐私。
实现与评估：通过 Python 核心实验和 JavaScript 端到端原型，实验验证了 CRSet 的隐私特性和性能表现。

8.2 核心权衡

CRSet 以空间效率换取了更强的隐私保护：

BSL 约 < 1 bit/容量，但完全暴露签发方活动。
CRSet 约 6 bit/容量，但实现了三方全面隐私保护。
考虑到一个 Blob 即可容纳约 17 万张 VC 的撤销数据，这一权衡在实际应用中是合理的。

8.3 关键洞察

填充是隐私的关键：无论是传统机器学习还是深度神经网络，均证明了无填充的级联可被轻易推断元素数量，而有填充的级联等同于随机噪声。
非交互式设计降低了采用门槛：无需修改钱包代理和传输协议，现有 W3C VC 基础设施可直接兼容。
定期发布是隐私的时序保障：固定间隔发布（不论是否有新撤销）消除了时序信息泄露的可能。

相关资料#

一、背景与动机#

1.1 自主主权身份（SSI）#

1.2 可验证凭证（VC）#

1.3 现有撤销方案的核心缺陷#

二、系统设计目标#

2.1 利益相关方模型#

2.2 设计目标#

三、数据结构选型#

3.1 Bloom 过滤器基础#

3.2 过滤器级联（Filter Cascade）#

3.3 为何选择 Bloom 过滤器而非其他#

四、CRSet 机制详解#

4.1 标识符与哈希#

4.2 填充（Padding）机制#

4.3 发布机制#

4.4 核心算法#

4.5 性能特征#

五、隐私形式化证明#

5.1 撤销机制的形式化定义#

5.2 选择计数不可区分游戏（CCIG）#

5.3 CRSet 满足该定义的证明草图#

六、实现与评估#

6.1 核心实验评估#

6.2 端到端评估#

七、实践局限性#

八、总结与思考#

8.1 论文贡献#

8.2 核心权衡#

8.3 关键洞察#

相关资料