Prevoke：一种保护隐私的可配置可验证凭证撤销方案

论文来源：2024 IEEE International Conference on Blockchain (Blockchain)
作者：Praveensankar Manimaran 等，挪威奥斯陆大学 & 巴西圣保罗联邦大学

一、背景知识

在正式进入论文内容之前，我们需要先建立几个基础概念。

1.1 自我主权身份（SSI）

自我主权身份（Self-Sovereign Identity，SSI） 是一种新型数字身份管理理念，核心思想是：个人应该完全拥有并自主控制自己的身份数据，不需要依赖任何中央机构（如政府、银行、平台）来管理。

举个现实中的类比：

传统身份：你的身份证由政府颁发并管理，你无法自主决定谁能查看你的信息。
SSI 身份：你持有自己的数字身份凭证，可以自主决定把哪些信息分享给谁，就像你自己保管实体证件一样。

SSI 系统中有四种角色：

角色	说明	现实类比
Issuer（发行者）	颁发数字凭证的机构	大学（颁发毕业证）、雇主（颁发工牌）
Holder（持有者）	持有并保管凭证的个人	毕业生、员工
Verifier（验证者）	验证凭证真实性的机构	银行、新雇主
Registry（注册中心）	存储凭证相关元数据和撤销信息的公共账本	区块链 / DLT

1.2 可验证凭证（VC）

可验证凭证（Verifiable Credential，VC） 是传统实体证件（护照、文凭、驾照等）的数字化形式，具有以下特点：

密码学安全：通过数字签名保证内容不可篡改
机器可验证：验证方可以用程序自动核验其真实性
隐私友好：持有者可以只披露凭证中的部分信息（选择性披露）

一张典型的 VC 包含：

发行者信息（谁签发的）
声明（claims）：如姓名、年龄、职位、薪资等
证明（proof）：如数字签名

可验证展示（Verifiable Presentation，VP） 是在 VC 基础上的进一步封装，允许持有者只展示 VC 中的部分字段，保护更多隐私。

1.3 分布式账本技术（DLT）

分布式账本技术（Distributed Ledger Technology，DLT） 是区块链的更广泛概念，是一种去中心化的数据存储方式。数据一旦写入，不可篡改，并对所有参与节点公开。论文中使用以太坊（Ethereum） 作为 DLT 基础设施。

1.4 布隆过滤器（Bloom Filter）

布隆过滤器 是一种空间效率极高的概率型数据结构，用于判断某个元素是否在集合中。

✅ 确定性结论：如果布隆过滤器说"不在集合中"，那一定不在（无假阴性）
⚠️ 概率性误差：如果布隆过滤器说"在集合中"，有一定概率是误判（存在假阳性）

工作原理简述：

使用 $k$ 个哈希函数，将每个元素映射到长度为 $m$ 的位数组上的 $k$ 个位置，将这些位置设为 1
查询时，计算同样的 $k$ 个哈希位置，若全为 1 则"可能存在"，若有任何一个为 0 则"一定不存在"

关键参数：

$m$：位数组长度
$k$：哈希函数个数
$p$：假阳性率（False Positive Rate），可配置

1.5 默克尔树累加器（Merkle Tree Accumulator，MTAcc）

默克尔树（Merkle Tree） 是一种树形数据结构，其中：

叶子节点存储数据的哈希值
非叶子节点存储其子节点哈希值的合并哈希
根节点（Root）是整棵树的"摘要"，任何数据的改变都会导致根节点变化

默克尔树累加器（MTAcc） 将默克尔树的根哈希作为整个数据集的"累加器"（摘要），可以用来：

成员证明（Membership Proof）：证明某个元素确实在集合中，且结果是确定性的（无假阳性）
见证值（Witness）：每个元素都有一个"见证值"，包含从该叶子节点到根的路径上所有兄弟节点的哈希值

与布隆过滤器的核心区别：MTAcc 的成员查询是完全确定的，不存在误判；但每次 MTAcc 更新时，所有元素都需要更新自己的见证值，代价较高。

1.6 BBS 签名方案

BBS 签名方案 是一种特殊的数字签名方案，支持：

批量签名：一次签名可以覆盖多条消息
选择性披露：持有者可以只出示部分已签名的消息，同时用零知识证明证明其余消息的存在性
不可关联性：每次生成的零知识证明都是随机的，不同验证者无法将同一持有者的多次证明关联起来

BBS 方案的核心算法包括：

算法	说明
`BBS-KeyGen`	生成密钥对 $(sk, pk)$
`BBS-Sign`	用私钥对一组消息签名
`BBS-Verify`	用公钥验证签名
`BBS-ProofGen`	生成零知识证明（只披露部分消息）
`BBS-ProofVerify`	验证零知识证明

二、问题背景：VC 撤销面临哪些隐私挑战？

2.1 为什么需要撤销？

可验证凭证可能因以下原因需要撤销：

取消：员工离职，需要撤销其工作证明 VC
更新：员工信息（如薪资、职位）变更，旧 VC 需要作废
私钥丢失：发行者或持有者的私钥丢失，相关 VC 需要全部撤销

2.2 撤销带来的隐私问题

撤销信息通常存储在公开的注册中心（如区块链上），这会暴露敏感信息。论文通过一个**职场身份（Workforce Identity）**的用例来说明：

场景：Employer 1（雇主1）给员工 Bob 颁发了一张员工 VC，Bob 想去 Employer 2 应聘，于是向 Employer 2 出示了这张 VC。

在这个场景下，论文识别出以下三条隐私需求（Privacy Requirements，PR）：

三、三大隐私需求（核心概念）

PR1：不暴露持有者与验证者的关联

问题描述：如果 Employer 2（验证者）在验证 Bob 的 VC 时，需要直接联系 Employer 1（发行者），那么 Employer 1 就会知道"Bob 正在找其他工作"——这可能直接损害 Bob 的工作状态。

这个问题也被称为 “Phone Home"问题：验证者每次验证都要"打电话"给发行者，从而让发行者获悉持有者的动向。

解决思路：将撤销状态存储在公开账本（智能合约），验证者直接查询账本，不与发行者交互。

PR2：不泄露被撤销持有者的身份

问题描述：当 Employer 1 撤销 Bob 的 VC 时，如果撤销记录中包含 Bob 的可识别信息（如姓名、员工ID等），第三方观察者就能推断出"Bob 离职了”——如果 Bob 是高管，这可能影响公司股价。

解决思路：撤销信息只存储哈希值或随机化后的数据，不直接暴露个人信息。

PR3：不泄露撤销率

问题描述：即使不知道谁被撤销，如果第三方能观察到每段时间内的撤销数量，就可以推算出"员工流失率（churn rate）"。这是商业敏感信息，可能暗示公司管理不善或工作环境恶劣。

解决思路：通过概率数据结构（布隆过滤器）和只存储部分树层级，隐藏精确的撤销数量。

四、现有方案的不足

论文对比了三种现有方案：

方案	PR1	PR2	PR3	主要缺陷
IOTA Id	✅	❌	❌	使用 bitmap，直接暴露撤销数量和身份索引
Indy	✅	✅	❌	使用双线性累加器；每次撤销后所有持有者需更新见证值，性能差；最多支持 32768 张 VC
Schumm et al.	✅	❌	❌	每次撤销对应一笔独立交易，直接暴露撤销次数；不处理假阳性

结论：没有任何现有方案同时满足三大隐私需求。

五、Prevoke 方案设计

5.1 核心思路

Prevoke 的核心是两阶段验证：

                ┌─────────────────────────────────────┐
                │           智能合约（DLT）              │
                │  ┌─────────────┐  ┌──────────────┐  │
                │  │ Bloom Filter │  │ MTAcc（前z层）│  │
                │  │（存已撤销VC）│  │（存有效VC）   │  │
                │  └─────────────┘  └──────────────┘  │
                └─────────────────────────────────────┘
                           ↑查询
验证者 ──── Phase 1 ──→ 查布隆过滤器
               │
               │ 在过滤器中？（可能已撤销或假阳性）
               │
               └── Phase 2 ──→ 查 MTAcc（确定性验证）

布隆过滤器：只存储已撤销的 VC（的哈希索引）
MTAcc：只存储有效的 VC（的哈希摘要）
验证时，先查布隆过滤器：
- 如果不在过滤器中 → VC 有效（布隆过滤器无假阴性，可信）
- 如果在过滤器中 → 可能已撤销，也可能是假阳性 → 进入第二阶段查 MTAcc 确认

5.2 四大流程详解

流程一：Setup（初始化）

发行者在系统启动时执行一次，主要完成：

根据参数计算布隆过滤器的大小 $m$ 和哈希函数数量 $k$：
$$m = -\frac{r \ln p}{(\ln 2)^2}, \quad k = \frac{m}{r} \ln 2$$
其中：
- $n$：预计发行 VC 总数
- $r$：预计撤销 VC 数量
- $p$：可接受的假阳性率
- $z$：在智能合约中存储 MTAcc 的层数（从根节点第0层开始）
初始化空的布隆过滤器和 MTAcc
使用 BLS12-381 密码套件生成 BBS 密钥对 $(sk, pk)$
部署以太坊智能合约，将 $pk$ 和空数据结构写入合约

$z$ 参数的意义：智能合约只存储 MTAcc 的前 $z$ 层（根节点为第 0 层）。$z$ 越大，存储的层数越多，持有者更新见证值时越能自给自足（不需要联系发行者），但费用也越高。

流程二：Issuance（发行）

每次为持有者发行一张 VC：

发行者为 VC 生成唯一标识符 vcID（随机字符串）
用 vcID 通过 $k$ 个哈希函数计算布隆过滤器索引 bfIndexes（注意：此时不更新过滤器，因为 VC 尚未撤销）
将 H(vcID)（vcID 的哈希）插入 MTAcc 的对应叶子节点（leafIndex 递增）
计算该叶子的见证值 witness，以及在第 $z$ 层的祖先节点值 ancestor
用 BBS 签名对以下内容签名：vcID、H(vcID)、bfIndexes、claims
构造 VC 并连同 witness 和 ancestor 发送给持有者
将更新后的 MTAcc 前 $z$ 层写入智能合约

持有者收到 VC 后：

用 BBS-Verify 验证签名
用见证值验证 VC 确实已被纳入 MTAcc

流程三：Revocation（撤销）

发行者撤销一张或多张 VC（支持批量撤销，这是满足 PR3 的关键）：

对每张待撤销的 VC：
- 用 vcID 计算 bfIndexes，将对应位设为 1（更新布隆过滤器）
- 在 MTAcc 中找到该 VC 对应的叶子节点，将其内容替换为随机字符串的哈希 H(r)（使该叶子"失效"）
将更新后的布隆过滤器和 MTAcc 前 $z$ 层写入智能合约

批量撤销的隐私作用：一次交易可以撤销多张 VC，使第三方无法通过交易数量推断撤销率，（PR3）。因为只能看到前z层的默克尔树。

流程四：Verification（验证）

第一步（持有者生成证明）：

生成随机 nonce（防止证明被重放）
用 BBS-ProofGen 生成零知识证明 $\pi$，其中：
- 选择性披露部分 claims（子集 $C$）
- 同时包含 bfIndexes 和 H(vcID)（但不暴露原始 vcID 和完整 claims）
将 VP（包含 $\pi$、nonce、bfIndexes、H(vcID)、披露的 $C$）发送给验证者

第二步（Phase 1 验证）：

验证者用 BBS-ProofVerify 验证零知识证明的有效性
将 bfIndexes 发送给智能合约，查询布隆过滤器
若不在过滤器中 → ✅ VC 有效，验证完成
若在过滤器中 → 进入 Phase 2

第三步（Phase 2 验证，仅当 Phase 1 结果为"可能撤销"时触发）：

验证者向持有者请求 MTAcc 证明
持有者检查智能合约中第 $z$ 层的祖先节点是否与发行时收到的 ancestor 一致：
- 一致：说明该 VC 的 co-path 上没有其他 VC 被撤销，可以从智能合约中计算出最新见证值
- 不一致：说明 co-path 上有 VC 被撤销，需要联系发行者获取最新见证值
持有者构造 MTAcc 证明并发送给验证者
验证者从智能合约获取 MTAcc 根哈希，验证 MTAcc 证明：
- 证明有效 → ✅ VC 未被撤销（Phase 1 是假阳性）
- 证明无效 → ❌ VC 已被撤销

六、隐私分析：Prevoke 如何满足三大需求？

PR1 满足情况

验证者直接从智能合约（公开账本）查询布隆过滤器和 MTAcc，全程不与发行者交互，因此发行者无法得知持有者的验证行为。

PR2 满足情况

布隆过滤器和 MTAcc 中只存储 vcID 的哈希值（H(vcID)），而非原始标识符
由哈希函数的单向性保证，无法从哈希反推出 vcID 或持有者身份
持有者通过 BBS 零知识证明分享数据，不暴露完整 VC

PR3 满足情况

两个机制共同保障：

布隆过滤器的概率性：多张 VC 共享同一组布隆索引位，无法从过滤器中直接数出撤销了多少张 VC
只存储 $z$ 层 MTAcc：MTAcc 中第 $z$ 层的每个节点覆盖 $2^{h-z}$ 张 VC（$h$ 为树的高度）。观察者只能推断某次更新影响了 1 到 $2^{h-z}$ 张 VC，无法得知精确数量

七、实验评估

7.1 实验配置

编程语言：Go
区块链：私有以太坊网络（Ganache v7.9.1）
部署环境：挪威 NREC 云服务（32核 AMD EPYC CPU，128GB 内存）

7.2 Q1：Phase 1 vs Phase 2 效率对比

配置：$n=1000$，$r=100$，$p=0.1$，$z$ 从 0 到 10 变化

结论：

Phase 1（布隆过滤器查询）：耗时稳定在 13~16 ms，与 $z$ 无关
Phase 2 总耗时：随 $z$ 增大从 40 ms 增长到 3200 ms
- 原因：$z$ 越大，持有者需要从智能合约下载的数据呈指数级增长

实践建议：不要把 $z$ 设得过大，否则 Phase 2 会非常缓慢。

7.3 Q2：撤销效率

撤销时间随撤销数量线性增长，因为每次撤销只需更新 $k$ 个布隆索引和 $z$ 个 MTAcc 节点，是可预期的稳定开销。

7.4 Q3 & Q4：$z$ 值和撤销模式对见证值更新的影响

配置：$n=100,000$，$r=10,000$，$p=0.001$（预计约 100 个假阳性）

两种撤销模式对比：

随机模式（random）：随机选择 VC 撤销 → MTAcc 中变化分散，即使存储超过一半的层（$z=16$），仍有部分持有者需联系发行者更新见证值
最旧优先模式（oldest-first）：总是撤销最早发行的未撤销 VC → MTAcc 中变化集中，只需存储少量层（$z=4$）就能让大多数持有者自行更新

实践建议：如果应用场景的撤销模式较为规律（如按序撤销），$z$ 可以设置较小以节省费用；若撤销是随机的，需要更大的 $z$ 或完善的发行者基础设施。

7.5 Q5：Gas 费用与参数关系

配置：$r=10,000$，$z$ 从 0 到 20，不同 $p$ 值

结论：

$z$ 增大 → Gas 线性增加（每次撤销多更新 $z$ 个节点）
$p$ 减小（假阳性率降低）→ 布隆过滤器变大（$m$ 和 $k$ 增大）→ Gas 线性增加

实际费用参考（以 Gas 价格 12 Gwei、ETH 价格 3,037 USD 计算）：

$p$ 值	费用区间（每次撤销）
$p = 0.1$	$2.9 \sim 7.45$ USD
$p = 0.0001$	$7.64 \sim 12.2$ USD

7.6 Q6：假阳性数量随撤销增长的变化

结论：

假阳性数量随撤销数增加而增加，在 $r$ 达到设计容量时接近 $p \times n$
超过设计容量后，假阳性数量指数级增长
布隆过滤器稀疏时（撤销数量少），假阳性极少（如 $p=0.001$ 时，撤销 6000 张以前几乎没有假阳性）

实践建议：根据预估撤销数量合理配置 $r$，避免布隆过滤器"溢出"。

八、方案对比总结

九、方案的优势与局限

优势

布隆过滤器无假阴性：有效 VC 的验证基本只需 Phase 1，效率极高
见证值更新频率低：只有"假阳性"的 VC 和已撤销的 VC 需要更新见证值；通过 $z$ 参数可以让大多数更新直接从智能合约完成，减少对发行者的依赖
验证免费：验证过程只读取智能合约状态，在以太坊上不产生 Gas 费
高可用性：以太坊网络拥有 7000+ 活跃节点，数据高度可用
可配置性：通过调整 $n$、$r$、$p$、$z$ 参数适应不同业务场景

局限

发行和撤销产生 Gas 费：更新布隆过滤器和 MTAcc 都需要支付以太坊费用
见证值无法完全消除：虽然频率大幅降低，仍有少数情况需要持有者联系发行者
存储更多层 MTAcc 费用高：$z$ 越大，费用越贵
未来待解问题：验证者可以无限期监控某张 VC 的撤销状态，这是一个尚未解决的隐私隐患

十、结论

Prevoke 是目前首个同时满足 PR1、PR2、PR3 三大隐私需求的 VC 撤销方案。通过将布隆过滤器与默克尔树累加器结合，并部署在以太坊智能合约上，Prevoke 在保护隐私的同时保持了良好的性能。其高度可配置性使其可以适应从员工身份管理到学历认证等多种实际场景。

参考文献

[论文原文] Manimaran et al., “Prevoke: Privacy-Preserving Configurable Method for Revoking Verifiable Credentials,” 2024 IEEE International Conference on Blockchain.
[BBS 签名] Tessaro & Zhu, “Revisiting BBS Signatures,” Advances in Cryptology, Springer, 2023.
[布隆过滤器] Tarkoma et al., “Theory and Practice of Bloom Filters for Distributed Systems,” IEEE Communications Surveys & Tutorials, 2011.
[MTAcc] Loporchio et al., “A Survey of Set Accumulators for Blockchain Systems,” Computer Science Review, 2023.
[W3C VC 标准] Sporny et al., “Verifiable Credentials Data Model v2.0,” W3C.
[以太坊] “Ethereum Whitepaper,” ethereum.org.
[源码] https://github.com/praveensankar/Prevoke

Prevoke：一种保护隐私的可配置可验证凭证撤销方案#

一、背景知识#

1.1 自我主权身份（SSI）#

1.2 可验证凭证（VC）#

1.3 分布式账本技术（DLT）#

1.4 布隆过滤器（Bloom Filter）#

1.5 默克尔树累加器（Merkle Tree Accumulator，MTAcc）#

1.6 BBS 签名方案#

二、问题背景：VC 撤销面临哪些隐私挑战？#

2.1 为什么需要撤销？#

2.2 撤销带来的隐私问题#

三、三大隐私需求（核心概念）#

PR1：不暴露持有者与验证者的关联#

PR2：不泄露被撤销持有者的身份#

PR3：不泄露撤销率#

四、现有方案的不足#

五、Prevoke 方案设计#

5.1 核心思路#

5.2 四大流程详解#

流程一：Setup（初始化）#

流程二：Issuance（发行）#

流程三：Revocation（撤销）#

流程四：Verification（验证）#

六、隐私分析：Prevoke 如何满足三大需求？#

PR1 满足情况#

PR2 满足情况#

PR3 满足情况#

七、实验评估#

7.1 实验配置#

7.2 Q1：Phase 1 vs Phase 2 效率对比#

7.3 Q2：撤销效率#

7.4 Q3 & Q4：$z$ 值和撤销模式对见证值更新的影响#

7.5 Q5：Gas 费用与参数关系#

7.6 Q6：假阳性数量随撤销增长的变化#

八、方案对比总结#

九、方案的优势与局限#

优势#

局限#

十、结论#

参考文献#