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

4492 软件学报 2025 年第 36 卷第 10 期

言, 当状态更新发生时, DFORC 只需要对当前状态变更涉及的那条哈希链进行更新操作, 而无需频繁读取和写入
磁盘. 通过避免大量无关节点的读写操作, DFORC 有效地降低了磁盘 I/O 瓶颈问题. 这不仅显著提高了更新效率,
还减轻了全节点的存储压力.
4.2 初始化
md 及其在 DFORC 中的相应索引, 以便稍后用于生成承诺和证明, 具体过
′
首先计算随机生成器 R, 消息摘要
程参见算法 2. 生成 EQAS 的 SK.seed、PK.seed、SK.prf 需要调用 3 次随机数生成器 (算法 2 第 1 行). 然后, 基于
key 和 SK.prf 生成 R, 定义为:

R = PRF(SK.prf,Optrand.key) (6)
其中, Optrand 是 n 字节字符串, 初始化为 0, 可以选择性地用 1 随机覆盖来进行设置. 通过添加额外的随机性, R
具有非确定性, 这有助于抵御侧信道攻击. 然后, 我们推导出使用的索引 idx, 以及 md:

(md||idx) = H msg (R,PK.seed,PK.root,key) (7)
其中, H msg 详见第 2.2 节, PK.root 来源于超树的顶层根节点 (见 ht_sig 算法中第 1–14 行), md 的长度为 m = ⌊(ka+7)⌋+
⌊(h−h/d +7)⌋+⌊(h/d +7)⌋ bits. 根据选择的参数 (算法 2 的第 5–7 行) 将 (md||idx) 拆分为 md 、树地址 idx_tree 和
′
′ m 3 字节用于叶子节点索
叶子索引 idx_lea f , 其中需要 m 1 字节用于 key 的消息摘要 md , 需要 m 2 字节用于树地址和
k
′ k 是
引, 使 m = m 1 +m 2 +m 3 . 接着将 md 拆分成 个 log(t) 位的字符来生成索引数组 idx[k], 其中 DFORC 树的数量,
k 个索引中的每个都对应 DFORC sk. 具体来说, 第 1 个索引
t 是叶子节点数量. 例如 idx[k] = [2,5,7,...], 这 中每个
选择第 1 个树中的第 2 个 sk; 第 2 个选择第 2 棵树中的第 5 个 sk; 以此类推, 最后一个索引选择最后一棵树中的
第 idx[k −1] 个 sk. 随后, 将与 key 对应的索引添加到 ID 中.
算法 2. 初始化.

输入: key;
′
输出: md , idx_tree, idx_lea f .
1. SK.seed, SK.prf, PK.seed ← Random(n);
2. PK.root ← ht_sig() (见 ht_sig 算法中第 1–14 行);
3. 根据公式 (6) 生成 R;
4. 根据公式 (7) 生成 (md||idx);
5. md 为 (md||idx) 中前 ⌊ka+7⌋ bits;
′
6. idx_tree 为 (md||idx) 中接下来的 ⌊(h−h/d +7)⌋ bits;
7. idx_leaf 为 (md||idx) 后面的 ⌊h/d +7⌋ bits;
′
8. return md , idx_tree, idx_lea f
4.3 承诺和证明
ADRS 方案
4.3.1
ADRS 方案采用一组操作地址的方法, 具体的所有操作方法见文献 [30], 所有节点在每次哈希调用后更新地
址. 对于不同的用例, 有 5 种类型的地址: 第 1 种类型用于平衡 WOTS+ (BW) 方案中的哈希函数, 另一种用于压
缩 BW 公钥, 第 3 种类型用于超树中 Merkle 树的哈希函数, 以及另一种用于 DFORC 中每棵树的哈希, 最后一种
类型用于压缩 DFORC 的根节点. 如图 5 所示, layer address 表示节点在超树中的高度, 对于底层的树, layer address
为 0; tree address 表示从最左边的树索引 0 开始, 节点在超树中的位置; type 表示地址的类型: BW 哈希地址为 0,
BW 公钥压缩为 1, 哈希树地址为 2, DFORC 地址为 3, DFORC 树的根节点压缩为 4; hash address 表示键值对的地
址; tree height 表示节点在 DFORC 中的高度; tree index 的计算方式在第 4.3.2 节.