技术摘要：链上注册表常数时间追加操作的成本分析

问题陈述

溯源树（Provenance Trees, PTs）是用于算子门控溯源基础设施的数据底层，属于追加式有向无环图（DAG）。尽管此前的研究声称 PT 的底层追加操作在 Gas 成本上为 $O(1)$——即与注册表大小和树深度无关——但这一主张缺乏作为独立原语的形式化隔离、明确的常数界限，以及针对行业标准：增量默克尔树（Incremental Merkle Tree, IMT）的实证基准测试。

IMT 在零知识协议（如 Tornado Cash、Semaphore）和 Rollup 状态承诺中占据主导地位，它提供了简洁的 $O(\log N)$ 成员证明，但其追加成本随树深度呈对数级增长（$\Theta(\log N)$）。对于那些成员证明并非主要查询需求的应用场景（例如溯源注册表），IMT 的成本权衡并不理想，然而，另一种方案在何时变得更具优势的交叉点尚未得到严格建立。

研究方法

本文将 父哈希有向无环图（Parent-Hash Directed Acyclic Graph, PHDAG） 隔离为一个独立的原语，并通过三个维度将其与 增量默克尔树（IMT） 进行对比：

1. 形式化复杂度分析： 作者将 PHDAG 的追加操作形式化，证明其执行的 EVM 操作数量与注册表大小 ($n$) 或深度无关。他们将此与 IMT 的前沿更新循环（frontier-update loop）进行了对比，后者随深度 ($d$) 线性缩放。
2. 随机成本建模： 考虑到 IMT 的追加成本会根据叶子索引的二进制表示（汉明重量）而变化，作者将单次插入的 Gas 成本建模为一个随机变量。他们在均匀分布的叶子索引下，推导出了 IM 成本均值和方差的闭式表达式，并区分了“写入层”（更新前沿）与“读取层”（仅遍历而不写入）。
3. 实证验证： 论文在 Base Sepolia 测试网上部署了两种原语的独立合约。实验覆盖了从 1 到 25 的树深度。
   • IMT： 通过执行 $\max(d, 2)$ 次追加的“比例深度扫描”进行测试，以捕捉方差。
   • PHDAG： 通过 200 次追加运行来表征成本分布和方差。
   • 指标： Gas 消耗通过交易收据进行测量，排除了初始冷存储初始化成本，以专注于稳态性能。

核心贡献

1. PHDAG 的形式化复杂度

论文确立了 PHDAG 的追加操作在 Gas 成本上严格为 $O(1)$。

• 机制： 每次追加都会向三个此前未触及的存储槽（由唯一标识符键入的冷 SSTOREs）写入数据，外加一个对计数器的热写入（warm write）。
• 不变性： 成本对于全局注册表大小 $n$ 以及任何关于树深度的概念都是不变的。由于交易的访问列表在每笔交易开始时都会重置，且 PHDAG 每次都写入新的存储槽，因此其成本仅取决于固定的操作数量，而非合约的状态。
• 重构： 论文证明，完整的注册表可以通过公开事件日志在 $O(|V|)$ 时间内完成重构，且不依赖于链下数据，因为事件流携带了规范的历史记录。

2. IMT 的随机模型

作者推导出 IMT 的单次插入成本是一个依赖于叶子索引 $i$ 的随机变量 $g$：

• 均值： $E[g] = c_0 + \frac{d}{2}(c_L + c_R)$，其中 $c_L$ 和 $c_R$ 分别是写入层和读取层的边际成本。
• 方差： $Var[g] = (c_L - c_R)^2 \frac{d}{4}$。
• 启示： 虽然相对方差（变异系数）随深度增加而减小，但绝对标准差随 $\Theta(\sqrt{d})$ 增长，这为高深度注册表引入了操作上的不可预测性。

3. 实证交叉点与验证

• PHDAG 性能： 测得每次追加的成本恒定为 76,276 Gas（标准差 $\approx 6$ Gas），证实了深度不变性。
• IMT 性能： 成本随深度线性增长。
• 交叉点： PHDAG 比 IMT 更便宜的深度被确定在 $d \approx 6$ 至 $7.2$ 之间。
  • 在 $d=6$ 时，测得的 IMT 成本（$\approx 78,000$ Gas）超过了 PHDAG 成本。
  • 计算得出，基于均匀索引分布的终身平均交叉点为 $d^* \approx 7.2$。

结果

实证数据验证了理论模型：

• PHDKG 在所有测试深度下均表现出极低的方差和恒定的成本。
• IMT 表现出线性成本增长和随深度增加而增长的绝对方差。
• 生产环境背景： 调查的每个生产级注册表（Tornado Cash, Semaphore, zkSync, Scroll, Linea）都运行在深度 $d \ge 20$ 的环境下。因此，所有此类系统目前都处于 PHDAG 严格更便宜 且提供可预测成本的区间，前提是应用不需要简洁的成员证明。

意义与主张

论文声称，对于满足以下条件的追加式溯源注册表，PHDAG 原理是更优的选择：

1. 不需要简洁的成员证明： 溯源查询通常涉及父链遍历或通过唯一 ID 进行存在性检查，这些可以通过 $O(|V|)$ 基于日志的重构来支持，而非 $O(\log N)$ 的默克尔证明。
2. 成本可预测性至关重要： 对于管理高吞量追加服务的算子而言，PHDAG 近乎为零的方差消除了为最坏情况 Gas 尾部进行预算的需求，相比于在高深度下的 IMT，这具有显著的操作优势。
3. 鲁棒性是首要考量： PHDAG 的对数规范设计确保了注册表历史的不可毁灭性和可重构性，仅凭公开事件日志即可完成，而不依赖于任何链下索引服务或当前的合约存储状态。

作者总结道，PHDAG 是作为以太坊溯源基础设施统一接口的有力竞争者，为非 ZK 应用提供了一种相对于依赖深度的 IMT 而言、具有常数成本且深度不变的替代方案。