V'CER: 约束网络中的高效证书验证

论文：V’CER: Efficient Certificate Validation in Constrained Networks 来源：USENIX Security 2022 作者：David Koisser, Patrick Jauernig（TU Darmstadt）；Gene Tsudik（UC Irvine）；Ahmad-Reza Sadeghi（TU Darmstadt）代码：https://github.com/vcer4pki/VCER

一、为什么读这篇论文

证书撤销是 PKI 里一个老生常谈的问题，但在约束网络（IoT、卫星网络）里这个问题被放大了很多倍。现有的 OCSP、CRL 都是为"可靠连接"设计的，一旦设备间歇离线，撤销信息就传不到，安全性就出了问题。这篇论文试图用 Sparse Merkle Tree 的确定性结构来解这道题，思路很有意思，值得仔细读。

二、问题是什么

约束网络长什么样

论文把 IoT 网格、卫星网络这类场景统称为"约束网络"，特点是：

设备层面：计算能力弱、存储小、功耗预算严格
网络层面：带宽低（Z-Wave 最高 100Kbps）、拓扑动态变化、连接间歇中断

卫星网络是个很极端的例子。OPS-SAT 卫星因为极地轨道 + 单一地面站，每天通信窗口不足 6 次，每次不超过 10 分钟。SpaceX Starlink 计划部署 42,000 颗卫星，这些小卫星还有软件 bug、可能遭受攻击，撤销机制不能缺席。

现有方案为什么不行

OCSP：每次验证都要实时请求 CA，约束网络里根本保证不了可靠连接，直接排除。

OCSP Stapling：证明方自己存一份 OCSP 响应随证书一起发。听起来可行，但每份响应约 4KB，假设有效期一天，10 万节点每天就要产生 390MB 的请求流量，完全不现实。

传统 CRL：把所有撤销证书列成一张大表。互联网上真实的 CRL 中位大小是 51KB，最大可达 76MB。就算假设 CRL 只存必要字段（平均 38 Bytes/条），100 万节点一年下来也要超过 3.6MB 的存储，对小设备来说太重了。

CRLite / Let’s Revoke：这两个是近年来改进 CRL 的优秀工作，CRLite 用级联布隆过滤器把存储压到约 112.5KB，Let’s Revoke 用按过期日期分组的 bitvector 压到约 70KB。更新也做了差量设计。但它们有一个共同的致命问题：节点错过更新后，必须单独去请求差量。以 Let’s Revoke 为例，100 万节点有 10% 错过一次更新，光补丁流量就要 195MB。而且它们都需要精心部署代理节点，在动态拓扑里做不到。

论文要解决的核心矛盾

如何在设备存储极小、连接间歇中断的网络里，做到及时、正确的证书撤销验证？

三、系统模型与设计需求

三类实体

CA（Certificate Authority）：颁发证书的权威机构，可以是分布式的，但论文先按单 CA 讨论。每个节点都预存了 CA 的证书并信任其签名。
Node：需要互相验证证书的普通设备。能做哈希和签名验证，但存储和算力有限。
Cacher Node：Node 的一个子集，额外存储一份 Level-Cache（后面详细讲），以提升分布式修复的成功率。

敌手模型

采用经典的 Dolev-Yao 模型：攻击者可以监听、拦截、篡改、注入任意消息，但受到物理约束——无法同时阻断网络里所有通信，也无法联系到已断开连接的节点。假设 SMT 构造是安全的（哈希函数抗碰撞）。

五条设计需求

编号	内容	我的理解
R.1	容忍任意延迟，CA 响应可能丢失或延迟	方案不能依赖 CA 的实时响应
R.2	无单点故障，避免纯依赖中心实体	节点间要能互相帮助
R.3	一致性，验证决策要来自统一信任锚	即使信息分散传播，结论要一致
R.4	极低资源开销，适配受限设备	存储、计算、带宽都要省
R.5	时效性，验证信息要快速传播	撤销了就要尽快让所有人知道

四、背景知识：Sparse Merkle Tree

这一节是读懂后续内容的关键，原文第 2 节写得比较简洁，我展开说说。

普通 Merkle Hash Tree（MHT）

MHT 是一个二叉树，叶子是数据元素的哈希，父节点是两个子节点哈希拼接后再哈希。知道根哈希，就能用 O(log n) 大小的"共路径（co-path）“来证明某个元素在不在树里。

Sparse Merkle Tree（SMT）

SMT 的特别之处：

包含所有可能的叶子位置。比如对于 SHA-256，SMT 有 2^256 个叶子，深度 255。
元素位置由其哈希值决定。H(c5) = 101（3 位示例）就放在位置 101。这个性质是确定性的，不需要维护索引。
空叶子统一赋值 H(∅)。由此可以预计算所有深度的"空分支哈希"存入 EmptyHashesList，大大压缩实际需要存储的节点数。
PoI 可以省略空节点。配合一个与树深度等长的 bitmap（SHA-256 就是 256 bit），标记哪些深度有实际哈希值，PoI 大小压缩到平均 log n 个哈希。
删除元素很容易：把对应叶子改回 H(∅)，根哈希自然变化，旧的 PoI 就失效了。

为什么这对 V’CER 关键

SMT 的确定性结构意味着：给定两个叶子的哈希，可以精确计算出它们在树中分叉的深度，并且可以用一个 PoI 的部分路径去更新另一个 PoI。这正是后面分布式修复算法的基础。

五、V’CER 方案详解

V’CER 由四个步骤组成，用一张图（原文 Figure 3）来描述：

CA ──(1)构建 VF──► 节点
节点 ──(2)处理 VF 更新──► 节点
节点 ──(3)Aggr 交换，识别过期部分──► 节点
节点 ──(4)分布式 PoI 修复──► 节点

5.1 Validation Forest（VF）

VF 是整个方案的核心数据结构，名字叫"验证森林”，因为它是多棵 SMT 的集合。

为什么要多棵树？

如果所有证书都放在一棵 SMT 里，任何一次撤销都会导致根哈希变化，进而导致所有节点的 PoI 都失效——那就又回到了每次更新都要全网重新发 PoI 的老路上。

解决方案是按证书的过期时间分组：每个 epoch（论文示例里是"一周"）对应一棵 Epoch Tree（ET）。某张证书只会在它对应的那棵树里，其余树不受影响。这样大多数 epoch 的树是稳定的，只有正在变化的 epoch（比如最新一周）才频繁更新。

VF 的三个组成部分

① Epoch Roots（Er）：每棵 ET 的根哈希，共 e 个。示例里 e=52，存储约 1.7KB。

② Aggregator（Aggr）：节点间交换的轻量摘要，包含：

Ar（Aggregator Root）：把所有 Er 拼接后哈希，任意一棵树变化都会导致 Ar 变化
At（Aggregator Timestamp）：4 字节 UNIX 时间戳，区分新旧
Ac（Checksums）：各 Er 的校验和，分两级——
- Main checksums：覆盖最新的几个 epoch（变化频繁），每个 epoch 单独一个校验和
- Aggregated checksums：覆盖中间的 epoch（较稳定），每 10 个 epoch 合并成一个校验和
- 示例：2 个 main + 5 个 aggregated = 7 个校验和，每个 2 字节，合计 14 字节
Aggr 总大小：32 + 14 + 4 = 50 字节，极其轻量

③ CA 签名 As：CA 对 Aggr 的 ECDSA 签名，64 字节。这是全局信任锚。

每个节点维护 VF（所有 Er）+ Aggr + As，总存储 < 3KB，覆盖 100 万张证书。满足 R.4。

Forest Prune

每当一个 epoch 过去，最老的那棵 ET 里全是已过期证书，CA 和节点都可以直接丢弃它。这叫 forest prune。

5.2 CA 更新

当撤销或颁发证书时，CA 需要：

更新受影响的 ET（用 Algorithm 4 add_leaf 操作），得到新的 Er
重新计算 Aggr 并签名，生成新的 As
向网络分发：新的 Aggr + As + 受影响的 Er + 更新 PoI 集合

更新 PoI 的作用

节点自己的 PoI 在 ET 发生变化后就失效了，但 CA 不会为每个节点单独生成新 PoI（这样太重了）。CA 的做法是分发所有被更新叶子的 PoI（包括撤销的和新增的），节点收到后用 Algorithm 1 自行更新自己的 PoI。

这里有个重要的设计：原文提到，当更新包含很多 PoI 时，这些 PoI 之间有大量重叠的路径元素，可以聚合压缩，减少分发体积。

Algorithm 1：`update_poi_with_poi`

这是整个方案里最核心的算法，值得仔细理解。

输入：我自己（过期）的叶子哈希 + 我的过期 PoI，以及一个最新叶子的哈希 + 其最新 PoI

关键思路：XOR 两个叶子哈希，找到最左边的不同位，这个位的深度就是两个叶子在 SMT 中分叉的位置。分叉位置之上的路径是共享的，可以用最新 PoI 的对应元素来更新。

步骤：

xor_leaves = my_leaf_hash XOR new_leaf_hash，找到最左边的 1 的位置 target_pos
遍历 target_pos 以上的所有深度，逐一用新 PoI 的对应元素替换我的 PoI 元素
在 target_pos 处，调用 calc_path_root 计算新叶子在该深度的子树根哈希，插入我的 PoI

重要性质：算法是"盲替换"的，不需要关心更新顺序，可以顺序应用多个更新 PoI。而且有时候可以一次性覆盖多个错过的历史更新（因为每次替换都取最新值）。

Epoch Change 时的特殊处理

Epoch 边界时大量新证书同时颁发，此时 CA 不分发一堆 PoI，而是直接分发该 epoch 所有叶子哈希。受影响的节点用这份完整叶子列表自行重建 PoI（O(log n) 计算），其余节点只需要更新对应的 Er。

另一个细节：如果某个 epoch 里没有任何撤销，CA 可以把该 Er 设为 H(∅)，表示"该 epoch 所有证书均有效"，节点直接接受，无需 PoI 验证。

5.3 Aggregator Exchange（Aggr 交换）

节点相遇时，第一步就是交换 Aggr，流程如下（对应原文 Figure 4 步骤①）：

节点 A 和节点 B 相遇：
  ① 互发 Aggr + 自己所属的 epoch 编号 + 是否是 Cacher 的标志
  ② 两边各自比较对方的 Ar 和 At
  ③ 发现自己过期的一方（假设是 B）：
     - 逐一对比 Ac 中的校验和，找出哪些 epoch 的 Er 不一致
     - 向 A 发送不匹配的校验和编号
  ④ A 返回对应的 Er 列表 + As
  ⑤ B 更新自己的 Er，重新计算 Aggr，验证 As 合法性
  ⑥ 如果 B 自己所在 epoch 的 Er 也变了，说明 B 的 PoI 也过期了

示例中，一次完整交换的通信量约 470 字节（Aggr + As + 11 个 Er）。

这个机制的妙处在于：任何节点只要遇到一个最新节点，VF 就能立刻同步。撤销信息像流行病一样在网络里传播，不需要考虑路由和拓扑。满足 R.2 和 R.5。

有一个边界情况：如果对方的 Ac 和我的 Ac 恰好碰撞（不同 Er 产生相同校验和），节点需要请求对方的全部 Er。这种情况极小概率，但方案做了处理。

5.4 分布式 PoI 修复（Distributed Repair）

VF 可以快速同步，但节点自己的 PoI 过期了怎么办？去找 CA 请求新的 PoI 是最后手段，但如果大量节点同时这样做，CA 和网络都会被打垮。

V’CER 提供两种节点间直接修复的策略。

策略一：Direct PoI Repair（直接 PoI 修复）

原文 Figure 4 步骤②。

前提：过期节点遇到了一个最新节点，且两者证书在同一个 epoch。

流程：

完成 Aggr 交换后，过期节点确认对方 VF 是最新的
请求对方的 PoI
验证对方 PoI 对当前 Er 是有效的（防止对方发假数据）
调用 Algorithm 1 用对方 PoI 更新自己的 PoI
检查修复后的 PoI 是否有效
若无效，继续遇到其他最新节点重复此过程

效果分析：一次修复是否成功，取决于两个叶子在 SMT 中的"距离"——分叉越靠近叶子（即两者哈希前缀越接近），能帮助修复的路径元素越少。论文模拟了 10 万叶子的 SMT，结果（Figure 5）：

错过 1 个更新：第一次尝试就能修复的概率超过 80%
错过越多更新：第一次成功率下降，但尝试 10 次后成功率显著回升
错过超过 100 个更新后：失败率（尝试 100 次还没修复）开始明显上升

这个策略的局限是，如果错过的更新很多，需要遇到多个不同位置的节点才能拼齐所有路径元素，效率下降。

策略二：Level-Cache（LC）Repair

原文 Figure 4 步骤③，针对 Direct PoI Repair 效率下降的场景补充。

Cacher Node 额外存储什么：在指定深度 clvl 处，存储 ET 中所有 2^clvl 个节点的哈希，称为 Level-Cache（LC）。这相当于把 ET 在 clvl 深度"横切一刀"，保存这一层所有节点。

为什么有效：SMT 的叶子均匀分布，叶子足够多时，clvl 以上的子树就会被密集填满。对于一个过期节点，它的 PoI 里 clvl 以上的路径元素（靠近根的部分）最可能因为更新而失效，而 LC 恰好覆盖了这部分。

流程（Algorithm 3，update_poi_with_lvl_cache）：

过期节点把自己的过期 PoI 发给 Cacher
Cacher 根据叶子哈希定位 LC 中对应的分区
用 LC 重建 PoI 里 clvl 以上所有路径元素
把修复后的 PoI 发回给过期节点
过期节点验证修复结果

关键参数 clvl 的选择：

LC 修复成功的条件是"过期节点错过的所有更新，没有一个落在该节点叶子所在的 1/2^clvl 分区内"。理论上每个错过的更新有 1/2^clvl 的概率落在同一分区。clvl = 7 时：

分区数 = 128，每个更新落在同分区的概率 ≈ 0.78%
可以容忍约数百次错过更新（<1% 失败率）
存储代价：2^7 × 32B × 52 epoch ≈ 208 KB（Cacher 节点需要）

原文 Figure 6 给出了不同 clvl 下可容忍错过更新数和存储开销的权衡图，直观展示了参数选择空间。

Cacher 自身过期的处理：Cacher 也可能错过更新，这时它可以从其他 Cacher 节点请求最新的 LC，或者用 CA 更新 PoI 来更新自己的 LC（Algorithm 2，update_lvl_cache_with_poi）。

六、安全性分析

伪造更新攻击

攻击者构造一个假的 Er，让某个被撤销的证书看起来还有效。但任何 Er 的变化都会导致 Ar 变化，而 Aggr 有 CA 的签名 As。节点在接受任何 VF 更新时都会验证 As，假数据直接被识别。

阻断更新攻击（孤立节点）

攻击者阻止某节点收到 CA 的撤销更新，让它继续验证已被撤销的证书。这要求攻击者同时阻断该节点与所有其他节点的通信（因为 VF 会在节点相遇时传播）。CA 还会定期发送新的 Aggr（带新 At），即使没有证书变化，孤立节点最终也会发现自己的 VF 过期，拒绝所有 PoI。这个漏洞窗口和 CRL 的有效期、证书有效期类似，业界已有先例。

针对分布式修复的破坏攻击

攻击者向有过期 PoI 的节点发送错误的修复数据，阻止它修复成功（达到拒绝服务效果）。但过期节点在应用修复前会用最新 VF 验证收到的 PoI 是否有效，无效数据直接丢弃。而且只要节点还能遇到正常节点，修复依然会进行。

DoS 攻击全网

强力攻击者直接 DoS 掉整个网络的更新通道。漏洞窗口与其他基于有效期的方案等同，V’CER 没有更差。

七、评估

原型实现与在轨测试

原型用 Python 写（CA 侧），为在 OPS-SAT 卫星上运行转为 Java（NanoSat MO Framework）。测试环境：

地面 A：Raspberry Pi 3B+（1.4 GHz，4GB RAM）
地面 B：Raspberry Pi Zero W（1 GHz，512MB RAM）
太空：OPS-SAT（Altera Cyclone V SoC，800 MHz，1GB RAM，同时运行 ADCS 等系统）

运行时间（1000 次平均）：

操作	RPi 3B+	RPi Zero W	OPS-SAT
签名验证 + Aggr 交换	2.9 ms	6.9 ms	31 ms
PoI 验证	3.8 ms	19.8 ms	228 ms
处理 20 个更新 PoI	76.9 ms	407.7 ms	4545 ms
单次 Direct PoI 修复	7.6 ms	39.4 ms	452 ms
LC (clvl=7) 修复	6.2 ms	29.5 ms	264 ms

“处理 20 个更新 PoI"在 OPS-SAT 上耗时最长（4.5 秒），但作者指出这已经是单个 epoch 里非常高的更新数量，属于极端情况。其余操作基本在 40ms 以内，满足实际需求。

大规模仿真（10K ～ 1M 节点，4 周）

仿真参数：

52 个 epoch（周），年撤销率约 10%（参考 Heartbleed 事件估计值），每日撤销 0.028%
每节点每小时随机遇到 5 个节点
10% 节点是 Cacher（clvl=7）
每次 CA 更新，随机 10% / 30% / 50% 节点错过（分三组跑）
一个节点尝试 30 次分布式修复仍失败，则直接请求 CA

修复成功率（Figure 7）：

错过更新比例	1M 节点下修复成功率	平均需遇几个最新节点
10%	>99%	8.9
30%	>97%	9.3
50%	>93%	10.1

即使在最极端的 50% 错过率 + 100 万节点的场景下，超过 93% 的过期节点能通过节点间协作修复 PoI，不需要联系 CA。满足 R.1 和 R.5。

另一个指标：两个相遇节点都过期的概率（Figure 7 中的 “both outdated” 曲线）。50% 错过率 + 1M 节点下，这个概率不到 5%，说明大多数相遇中至少有一方是最新的，VF 传播效率高。

通信开销（Figure 8）：

指标	10% 错过，1M 节点	50% 错过，1M 节点
节点间每周交换量（每节点）	27.2 KB	81.6 KB
CA 日常更新大小	179.3 KB	179.3 KB（与错过率无关）
每周 Epoch 变更大小	629.8 KB	629.8 KB（与错过率无关）

注意 Epoch 变更不需要发给所有节点，只需发给该 epoch 受影响的节点，实际开销更小。

八、与相关工作的对比

与改进 CRL 方案对比（重点）

方案	存储（1M 证书）	节点错过更新后	设计目标
传统 CRL	>3.6 MB	重新下载全量 CRL	Web PKI
CRLite	~112.5 KB	单独向聚合器请求差量（全网最终 195MB）	Web PKI
Let’s Revoke	~70 KB	同上，~2KB/节点但全网叠加很大	Web PKI
V’CER	<3 KB	节点间协作修复，>93% 无需联系 CA	约束网络

CRLite 和 Let’s Revoke 都是优秀的工作，但它们的设计假设是 Web 场景——聚合器节点可靠可达、网络拓扑稳定。在动态拓扑的约束网络里，精心部署聚合器本身就是难题。

与 CT 等观察者方案对比

CT 和 Enhanced CT 的目标是监控 CA 的行为（防止 CA 误签证书），用的也是 Merkle Tree + PoI，但它们不做端到端的撤销验证，而是让观察者互相监督。V’CER 的目标是节点间的直接认证，两者正交，可以叠加使用。

与区块链方案对比

CertCoin、EthIKS 等方案把信任转移到区块链上，理论上去中心化程度更高，但都要求节点能持续访问链上数据。在卫星网络这种间歇连接的环境里，这个假设不成立。V’CER 不需要维持连接，只需节点间偶尔相遇就能同步。

九、讨论与扩展

原文第 7 节讨论了几个实际问题，都很有价值：

多 CA 场景：可以用 BLS 门限签名让多 CA 委员会共同产生 As；或者每个 CA 维护自己的 VF，节点需要验证哪个 CA 的证书就同步哪个 CA 的 VF。

证书缓存：节点如果频繁与某个固定对端通信，可以缓存对方的证书和 PoI，并用 Algorithm 1 保持缓存的 PoI 最新。这还能提升 Direct PoI Repair 的效率——一个节点可以拿出缓存的多个 PoI 帮助修复，而不只是自己的一个。

动态 LC 大小：不同 epoch 可以用不同的 clvl，越新的 epoch 更新越频繁，用更大的 LC；接近过期的 epoch 几乎不变，用小 LC 甚至不缓存。大 LC 可以直接截断成小 LC，不需要重算。

十、个人总结与思考

这篇论文最打动我的地方

SMT 确定性结构的利用方式。大家知道 SMT 可以做 PoI，但 V’CER 进一步发现：两个 SMT 叶子的 XOR 可以告诉你它们在树中的分叉位置，从而让"用他人 PoI 修复自己 PoI"成为可能。这不是什么复杂的密码学技巧，就是对数据结构性质的深刻理解。

Validation Forest 的分层设计。按 epoch 分树这个决策看似平凡，但它把"频繁变化的"和"稳定的"区分开，大幅降低了 PoI 失效率，是整个方案能在低开销下运作的关键。

一些值得关注的问题

Epoch 边界的冲击：每周 Epoch 变更时，629.8KB 的更新包虽然不发给全网，但受影响节点集中在这一时刻更新，峰值流量可能比均匀的日常撤销更值得关注。

Python/Java 原型的性能代表性：OPS-SAT 上处理 20 个更新 PoI 需要 4.5 秒，主要因为 Java 的 BigInteger 位操作效率低。用 C 重写后性能会大幅提升，但论文没给 C 实现的数据。对于极度受限的设备（比 OPS-SAT 还弱），这个性能是否足够还需要更多验证。

Cacher 的分布与激励：10% 节点是 Cacher 的假设在仿真里是随机分布的。真实网络里 Cacher 可能分布不均，某些区域的节点修复效率会更低。而且谁来担任 Cacher、存储 208KB 额外数据，需要设计激励机制（论文没有讨论）。

时钟同步的依赖：方案依赖"小时级粗粒度时钟同步"来判断证书是否过期。大多数场景里这不是问题，但对完全没有时钟参考的设备（深空探测器？）可能是个约束。

对比读 CRLite 和 Let’s Revoke

这三篇论文解决的是同一个问题（证书撤销），但出发点完全不同。CRLite 和 Let’s Revoke 从"如何压缩存储和更新大小"入手，在 Web PKI 的可靠网络环境里做到了极致；V’CER 则从"如何适应不可靠网络"入手，接受了更高的单节点存储上限（3KB vs 70-112KB 看似差距大，但覆盖 100 万证书只要 3KB 已经很惊人），换来了无需中心依赖的健壮性。设计目标不同，不好简单说谁更好，但放在约束网络里 V’CER 的思路明显更合适。

参考

论文原文：USENIX Security 2022
代码：github.com/vcer4pki/VCER
CRLite：Larisch et al., IEEE S&P 2017
Let’s Revoke：Smith et al., NDSS 2020
Certificate Transparency：Laurie, CACM 2014
Revocation Transparency（SMT 最早应用于撤销的提案）：Laurie & Kasper, Google Research 2012

一、为什么读这篇论文#

二、问题是什么#

约束网络长什么样#

现有方案为什么不行#

论文要解决的核心矛盾#

三、系统模型与设计需求#

三类实体#

敌手模型#

五条设计需求#

四、背景知识：Sparse Merkle Tree#

普通 Merkle Hash Tree（MHT）#

Sparse Merkle Tree（SMT）#

为什么这对 V’CER 关键#

五、V’CER 方案详解#

5.1 Validation Forest（VF）#

为什么要多棵树？#

VF 的三个组成部分#

Forest Prune#

5.2 CA 更新#

更新 PoI 的作用#

Algorithm 1：update_poi_with_poi#

Epoch Change 时的特殊处理#

5.3 Aggregator Exchange（Aggr 交换）#

5.4 分布式 PoI 修复（Distributed Repair）#

策略一：Direct PoI Repair（直接 PoI 修复）#

策略二：Level-Cache（LC）Repair#

六、安全性分析#

伪造更新攻击#

阻断更新攻击（孤立节点）#

针对分布式修复的破坏攻击#

DoS 攻击全网#

七、评估#

原型实现与在轨测试#

大规模仿真（10K ～ 1M 节点，4 周）#

八、与相关工作的对比#

与改进 CRL 方案对比（重点）#

与 CT 等观察者方案对比#

与区块链方案对比#

九、讨论与扩展#

十、个人总结与思考#

这篇论文最打动我的地方#

一些值得关注的问题#

对比读 CRLite 和 Let’s Revoke#

参考#