Page 94 - 《软件学报》2025年第10期

张川 等: 抗量子的高效区块链认证存储方案 4491

∗
Succ EU-CMA (A) = Pr[vf(pk, M ,σ ) = 1∧ M < {M i } |(sk, pk) ← kg();(M ,σ ) ← A sign(sk;) ] (4)
q s
∗
∗
∗
∗
SIGN i=1
其中, M 1 ,..., M q s 是 A 提交给签名 Oracle 的消息. 本文将 SIGN 的 PQ-EU-CMA 不安全性定义为: 计算时间为 ξ,
查询复杂度为 q s 的所有量子对手的最大成功概率为:

InSec PQ-EU-CMA (SIGN;ξ;q s ) = max{Succ EU-CMA (A)} (5)
SIGN
A
4 抗量子的高效区块链认证存储方案 EQAS
在本节中, EQAS 利用键值对数据库作为后端, 并维护一个键值映射元组 (KV,VM,ID), 其中 KV 存储键值对,
VM 存储键的版本号, ID 存储键对应的索引. 当区块链处理一个区块时, 该区块包含键值对 (key,value), 其中每个
键值对都具有一个版本号, 起始值为 0. 接下来, 首先介绍 FORC 的变体 DFORC, 然后介绍 EQAS 的设计细节. EQAS
框架如图 4 所示.

公钥

读写操作 查询键对应的值
全节点 键值数据库

验证
承诺
区块链 轻节点
DFORC 结构

存入区块头
证明 承诺
返回键对应的证明 超树结构

图 4 EQAS 框架

4.1 动态随机森林链 (DFORC)

典型的 FORC 结构是静态的. 一旦 FORC 构造完成, 私钥在未达到签名限制前不会进行更新, FORC 结构也不
会被修改. 此外, 由于 FORC 结构依赖于私钥的构建, 若私钥保持不变, 则该结构也将始终保持不变. 然而, 在公有
区块链中, 这种静态 FORC 结构无法用于生成承诺, 因为承诺会随着键值对的更新而改变. 因此, 如何动态地产生
FORC 承诺成为一个挑战. 为了解决这个问题, 本文提出了 DFORC (动态随机森林链). 在 DFORC 中, 我们只更改
树上的节点, 而哈希链上存储的私钥保持不变. 当新键值对选择同一棵树上相同索引时, 我们需要处理与该索引对
应的叶子节点, 然后对叶子节点执行哈希操作, 哈希迭代的次数取决于选择该索引的次数. 然后更新从该叶子节点
到根节点路径上的节点, 逐步生成一个新的根节点, 即承诺.
在传统区块链认证存储中, MPT 是一种常用的数据结构, 用于生成交易的存在性证明和状态承诺. 然而, MPT
结构的一个关键瓶颈在于每次状态更新时, 不仅需要更新涉及的路径节点的哈希值, 还需要进行大量的磁盘 I/O
操作. 这是因为 MPT 的数据存储通常会涉及磁盘读写, 而读取路径上各个节点进行更新会导致 I/O 操作的频繁发
生. 本文提出的动态随机森林链 (DFORC) 依然需要更新路径上的节点, 但与传统的 MPT 结构不同的是, DFORC
在设计上避免了额外的磁盘读写操作. DFORC 将状态存储结构优化为多条独立的哈希链, 这些哈希链构成一个随
机森林结构, 允许每次状态更新仅限于相关的哈希链, 而不涉及其他无关链上的节点. 这种设计虽然仍需对哈希路
径上的节点进行更新, 但通过缓存机制或内存中的节点管理, DFORC 大幅减少了对磁盘的频繁读写需求. 具体而