本文研究动态有序集合（支持插入、删除、成员查询、前驱后继、最小值最大值等操作）的回顾性审计问题。集合由不可信方维护，被动审计者（auditor）仅需存储 5 个机器字和 1 个标志位，并在每次操作时接收一个常量大小的公开 tally 记录。审计阶段，维护者披露声称的活跃空区间（live vacant intervals）。方法的核心是利用最大间隙（maximal gaps）表示顺序语义：间隙有出生、引用、消费、时间戳等状态，同时两个隐藏域累加器分别对出生账本和消费账本进行相等性测试。诚实执行以概率 1 被接受；若包含 T 次操作的会话中存在错误回答，接受概率至多为 (4T+1)/p（p 为秘密域元素大小，对计算能力无限制的维护者有效）。论文证明确定性或可见硬币审计器需要线性状态，并发现移除时间戳规则会导致精确重放伪造。实现方面，采用叶导向的 (2,4)-树作为维护者数据结构，每个操作最坏情况 O(log n) 时间，每个元素额外存储一个字，且再平衡事件在 m 次更新上具有可审计的 O(m) 包络。检查点审计可通过加法误差组合。本文适合研究可验证计算、数据完整性审计及信任最小化系统的研究人员阅读。

本文研究持续观察下私有化发布k维向量更新的问题。初始向量为零向量，在时间点t_i上通过添加x^{(i)}进行更新，其中t_i∈[T]，x^{(i)}在k维单位球B_k内。两个数据集被认为是相邻的，如果它们的对称差大小不超过1。持续发布需要在每个时间步t=1,...,T输出累加和A^{(t)} = ∑_{i: t_i ≤ t} x^{(i)}。经典方法可以O(kT)时间、polylog(T)噪声幅度释放近似值。本文考虑每个时间步仅需发布A^{(t)}的子集，提出一种快速高斯机制，能够在常数时间内采样噪声向量中任意指定条目，同时精确复制二叉树机制下高斯噪声的分布。该改进基于布朗桥构建的新数据结构，突破了已知O(log T)时间界限。文章展示了两个数据管理应用：1) 正交范围计数查询的动态数据结构，在隐私/准确性/空间权衡上优于先前结构；2) 连接大小估计，同时改进了高概率界。本文适合对差分隐私、数据流算法和数据结构设计感兴趣的研究者。

本文提出并分析了 Parent-Hash 有向无环图（PHDAG），这是一种用于链上注册表的追加型数据结构，其中每次追加操作只需对之前未触及的存储槽进行恒定数量的写入操作。此前，PHDAG 从未被作为独立原语进行形式化分析，也未被明确边界常数，更未与标准的增量 Merkle 树（IMT）进行基准比较。作者形式化证明 PHDAG 的追加操作在 gas 成本上为 O(1)，与注册表大小和树深度无关，而 IMT 的每次插入成本则是关于叶子索引的随机变量，作者推导出其均值和方差的闭式表达式。通过在 Base Sepolia 测试网上对 1 至 25 层树深度进行实验验证，观察到 PHDAG 的 gas 消耗恒定在约 76,276 gas（标准差约 6 gas），而 IMT 成本随深度线性增长。交叉点（IMT 更便宜）远低于所有已调查生产注册表的深度。此外，本文还建立了从公共事件日志中无需信任地重建注册表的方法，时间复杂度为线性，且无需链下依赖。该研究首次将 PHDAG 与 IMT 进行了系统的理论和实证对比，为链上数据结构的成本优化提供了重要参考。