💻 computer science

Split Tallies: A Discrete Certificate Calculus for Auditing Dynamic Ordered Sets in Constant Memory

本文介绍了“分裂计数”（Split Tallies），这是一种常数内存审计方案，通过离散证书演算追踪最大间隙，来验证由不可信方维护的动态有序集合，在实现针对计算无界对手的高概率安全性的同时，证明了若没有隐藏的随机性或时间戳，实现此类效率是不可能的。

原作者： Faruk Alpay, Levent Sarioglu

发布于 2026-06-12

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Faruk Alpay, Levent Sarioglu

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你有一位非常聪明但可能并不诚实的图书管理员（维护者），他管理着一个排列得极其完美的图书馆。你（用户）会问类似“书 X 在这里吗？”或“Y 前面的一本书是什么？”之类的问题。图书管理员会瞬间给出答案。然而，你不信任图书管理员的内部记忆，而且你不能每次提问时都去检查他们的书架，因为那样太慢了。

你需要一种方法，在稍后验证他给出的每一个答案是否确实正确，而无需你自己记住整个图书馆。

这篇论文介绍了一个名为 Split Tallies 的系统来解决这个问题。它巧妙地结合了古代会计历史与现代数学，创造了一个“证书”，用以证明图书管理员说的是实话，而几乎不需要在你这边占用任何内存。

以下是其工作原理的拆解，分为几个简单的概念：

1. 古代隐喻：裂开的木棍 (The Split Stick)

这个想法的灵感来自 600 年前英国的“计数木棍”（tally sticks）。

故事： 如果一名商人借钱给农民，他们会在木棍上刻下代表金额的缺口。然后，他们会将木棍纵向劈开。商人保留一半（Stock，即“库存”），农民保留另一半（Foil，即“箔片”）。
神奇之处： 当需要还钱时，他们会将两半拼在一起。只有真正的木棍才能完美契合，因为木纹和缺口会完全对齐。假木棍永远无法匹配。
在本文中：
- 图书管理员持有“箔片”（他们对图书馆的内部记忆）。
- 审计员（你）持有“库存”（你的一份由 5 个数字组成的秘密列表）。
- 公开计数 (Public Tally) 是图书管理员在每一次操作后必须记录下的“缺口”列表。
- 审计 (Audit) 是你检查图书管理员的故事是否与你的秘密列表相符的时刻。

2. 核心技巧：追踪“间隙”而非书籍

大多数人认为图书馆是一个书籍列表。但这篇论文说：“不，请思考书籍之间的空白空间。”

想象图书馆的书架有一个起点 (0) 和一个终点 (U)。
如果书架是空的，则从起点到终点有一个巨大的间隙。
如果你添加一本书，你就将这个大间隙分割 (split) 成两个较小的间隙。
如果你移除一本书，你就将两个间隙合并 (merge) 回一个。

论文证明，如果你确切知道这些间隙是如何连接的，你就确切知道每本书在哪里。图书管理员不仅仅是说“书 X 在这里”；他们必须指向证明这一点的特定间隙。

3. 游戏规则（“契约”）

为了防止图书管理员撒谎，该系统迫使他们遵循严格的规则，就像一场带有严格计时机制的音乐椅游戏：

公开时钟： 每当创建一个新间隙（添加一本书）时，它都会获得一个唯一的、连续的 ID 数字（类似于时间戳）。
引用规则： 当图书管理员回答问题时，他们必须引用他们正在使用的间隙 ID。
- 关键规则： 你只能引用在当前时刻之前创建的间隙 ID。你不能引用“未来”的 ID。
秘密数学： 审计员（你）持有一个秘密数字。每当一个间隙诞生或被使用时，审计员都会将自己的秘密数字乘以一个涉及该间隙 ID 的数学公式。
- 如果图书管理员是诚实的，数学运算在最后会完美吻合。
- 如果图书管理员撒谎（例如，声称某本书在那里但实际上不在），他们就必须伪造一个间隙 ID。由于他们不知道你的秘密数字，数学运算几乎肯定会在最后失败。

4. 为什么它如此高效

论文声称这个系统非常轻量化：

对于你（审计员）： 你只需要记住 5 个数字和一个“标志”（一个是/否开关）。你不需要存储图书馆、书籍或历史记录。你只需要观察“缺口”的流向。
对于图书管理员： 他们需要极小的额外空间（每个书籍对应一个额外的数字）来存储间隙 ID。
成本： 如果图书管理员试图作弊，成功的概率微乎其微（在一百万次操作中，成功率低于一万亿分之一）。

5. “不可能”的部分

作者还证明了，如果不破坏系统，你无法让这个系统变得更简单：

没有随机性？ 如果不使用秘密随机数，聪明的骗子总能欺骗你。
没有秘密？ 如果图书管理员知道你的秘密数字，他们就可以伪造数学结果。
没有时间限制？ 如果图书管理员被允许引用“未来”的 ID（穿越时空），他们就可以创建一个看起来真实的完美假图书馆。这种“时钟”规则对于阻止此类行为至关重要。

6. “重平衡”奖励

图书馆有时需要重新组织书架（将一个满的架子拆分为两个，或将两个空的架子合并）。论文显示，即使是这些混乱的重组步骤也可以被审计。他们证明了无论图书管理员进行多少次重组，总的“移动”次数都是可以预测的。审计员只需通过计算图书管理员的“收据”数量，即可确保他们没有进行额外的操作来掩盖谎言。

总结

这篇论文构建了一个针对动态列表的数学谎言检测器。

图书管理员负责执行工作。
审计员几乎不做任何事（仅需 5 个数字）。
计数 (Tally) 是关于“缺口”的公开记录。
结果： 即使图书管理员是一个试图欺骗你的超级计算机，即使你几乎没有任何内存来存储数据，你也能以近乎 100% 的确定性来验证所给出的每一个答案是否正确。

这就像是通过看一张证明数学逻辑成立的单一收据，来检查银行账户余额，而不是去清点金库里的每一枚硬币。

技术摘要：分裂刻痕（Split Tallies）：一种用于审计动态有序集合的离散证书微积分，具备常数内存特性

问题陈述

本文研究了对由对手方（“维护者”）维护并由消费者查询的动态有序集合进行验证的问题。在许多现代计算场景中，数据结构存在于不可信的环境中（例如，远程服务、不透明的硬件加速器或采购的库）。消费者发出操作（插入、删除、成员测试、前驱/后继查询以及极值查询），并立即接收答案并据此执行操作，且无延迟。

核心挑战在于，如何在不要求消费者（“审计员”）存储数据结构本身或重新执行操作的情况下，为整个操作历史提供一份正确性证书。审计员必须是被动的，仅存储常数量的状态（具体为五个机器字和一个标志位），而维护者则需为每一次操作向一个被称为“刻痕”（tally）的公开、只增序列追加一条简短的“刻痕”（记录）。目标是高概率地检测出维护者是否曾提供过错误答案，即使维护者拥有无限的计算能力并能根据可见的历史调整其策略。

方法论

提出的解决方案被称为分裂刻痕（Split Tallies），其灵感源自历史上的木制刻痕计数棒（tally sticks）：通过在木棒上刻下记号来记录债务，然后将木棒纵向劈开。债权人持有“存货”（stock），债务人持有“箔片”（foil）；在结算时，将两半对齐以验证真实性。在此数字语境下：

刻痕（The Tally）： 由维护者追加的公开刻痕流。
存货（The Stock）： 审计员的私有状态（五个字和一个标志位）。
箔片（The Foil）： 维护者内部的数据结构簿记。
审计（The Audit）： 将“存货”与“箔片”进行“对齐”（meshing）的过程（在会话结束时披露）。

间隙微积分（The Gap Calculus）

该方案的技术核心是离散间隙微积分。系统并非直接审计集合 $S$ ，而是审计划分有序全集的极大真空区间（间隙）族。

表示法： 一个位于全集 $\{1, \dots, U\}$ 上的集合 $S$ 被唯一地表示为连接哨兵 $0 $和$ U+1 $的一组**连锁间隙**$ \langle a, b \rangle$。
标准型： 本文证明了这种间隙族对应于区间无环图中从 $0 $到$ U+1$ 的唯一单位路径。
重写： 操作被建模为该路径的局部重写：
- 插入： 将一个间隙 $\langle a, b \rangle$ 分裂为两个间隙 $\langle a, x \rangle, \langle x, b \rangle$ 。
- 删除： 将两个相邻的间隙 $\langle a, x \rangle, \langle x, b \rangle$ 合并为一个间隙 $\langle a, b \rangle$ 。
- 查询： 通过展示特定的间隙来回答（例如，包含 $x$ 的间隙用于成员测试，或以 $x$ 为起点的间隙用于前驱查询）。

契约纪律（The Indenture Discipline）

为了在不存储状态的情况下审计这些重写，审计员采用了基于有限域 $\mathbb{F}_p$ 上多项式恒等测试的指纹机制：

代码与时间戳： 每个间隙的诞生都通过公开计数器 $\kappa$ 分配一个唯一的代码（时间戳）。
引用： 每次操作必须引用所消耗（重写）的间隙代码。
累加器： 审计员维护两个累加器， $A$ $A$ （用于诞生）和 $R$ $R$ （用于消耗）。对于具有代码 $c$ $c$ 和端点 $a, b$ $a, b$ 的间隙，将其映射到域中的值 $\nu(a, b, c)$ $ν (a, b, c)$ 。
- 诞生时： $A \leftarrow A \cdot (z - \nu(a, b, c))$
- 消耗时： $R \leftarrow R \cdot (z - \nu(a, b, c))$
- 这里， $z$ 是审计员在会话开始前选择的一个秘密域元素。
验证： 在审计时，维护者披露当前所有间隙及其代码。审计员检查披露的间隙是否能够对齐（形成有效链），并验证是否 $A = R$ 。

关键机制

时间规则： 被引用的代码必须严格小于事件开始时的计数器值。这防止了维护者“借用”未来的代码来伪造平衡的账本。
强制性（Forcing）： 由于间隙路径的唯一性，任何查询的正确答案都是被引用的间隙的强制函数。如果维护者引用了一个不存在或不再活跃的间隙，其答案将与间隙属性不一致，或者账本将变得不平衡。

关键贡献与结果

1. 审计定理（完备性与可靠性）

本文确立了该方案具有完全完备性（诚实的维护者总会被接受）和 $\epsilon$ -可靠性。

可靠性误差： 如果维护者在 $T$ 次操作中提供哪怕一次错误答案，其被接受的概率至多为 $(4T + 1)/p$ 。
参数： 使用 61 位素数 $p$ （例如 $2^{61}-1$ ），对于高达一百万次操作的会话，误差概率低于 $2^{-38}$ 。
假设： 不需要任何计算硬度假设；其安全性相对于无限制对手是信息论安全的。

2. 不可能性与必要性结果

本文证明了特定的设计选择是不可或缺的：

确定性底限： 任何具有会话结束可靠性的确定性审计员，对于大小为 $n$ 的集合，必须至少存储 $2n - \log_2(2n+1)$ 比特的状态。这证明了随机性是一个必要条件，而非仅仅是便利工具。
秘密随机性： 如果审计员的随机币（random coins）对维护者可见，则可靠性误差变为 1（维护者总能伪造一份记录）。因此，评估点 $z$ 的隐秘性是必要的。
时间规则的必要性： 若没有防止引用未来代码的规则，则存在一个显式的三操作伪造案例，能够实现精确平衡并以概率 1 被接受。

3. 维护者实现

本文提供了一个使用叶向（leaf-oriented）(2, 4)-树的具体实现：

复杂度： 操作在最坏情况下运行时间为 $O(\log n)$ 。
开销： 该结构每个元素仅需额外存储一个字（用于存储间隙代码）。
审计重平衡： 本文引入了一个证明包络（attestation envelope），证明在 $m$ 次更新过程中，结构性事件（分裂、融合、共享）的数量至多为 $2m$ 。这一界限通过审计员统计维护者追加的一个字大小的证明来完成，从而将摊还分析转化为可公开验证的声明。

4. 检查点与纪元

该协议支持任意检查点。审计可以在任何时间进行，且被接受的纪元可以带有加性误差界限进行链接。这允许调节检测延迟（例如，为了高安全性在每次操作后进行审计，或为了效率降低审计频率）。

意义与范围

本文声称提供了一个关于动态有序集合常数内存审计的封闭账户。其意义在于：

范式转移： 从“孤立测试”转向“随执行过程传递的认证”。
信息论保证： 在不依赖密码学假设（如 Merkle 树或数字签名）的情况下实现验证，转而利用多项式的代数性质和有序集合的组合结构。
紧凑下界： 通过证明任何确定性方案都需要线性空间且随机性必须隐藏，证明了所提方案是接近最优的常数内存解。
明确的常数： 所有参数（素数大小、字计数、误差界限）都是明确的，并经过校准（例如，适配 64 位字）。

其范围严格限于七操作接口（插入、删除、成员、前驱、后继、最小值、最大值）。本文明确指出，间隙微积分认证的是排列（相邻性、括号化、极值性），但不扩展到诸如秩（rank）之类的聚合属性，因为后者对于单个间隙而言不是局部的。检测是回顾性的；本文承认，在这种信息论设置下，实现在线检测（即立即拒绝错误答案）是一个已知的研究前沿，且与单向函数的存在相关，因此所提方案在其定义的回顾性模型内是最优的。