Reed规范或更好的前缀认证（2023）

# Reed 规范 来源：https://worm-blossom.github.io/reed/ 前缀认证方案\(Meyer, 2023bb\) (https://worm-blossom.github.io/reed/assets/references/meyer2023sok.pdf)——通常称为*追加日志*或*透明日志*——是一种高效认证事件之间全序关系的密码学方案。对于来自同一事件流的任意两个事件，你可以提供一段短的摘录来证明一个事件发生在另一个事件之前（而非同时发生）。Reed (https://worm-blossom.github.io/reed/#name) 是一个轻量级规范，用于实现该方案\(Meyer, 2023aa\) (https://worm-blossom.github.io/reed/assets/references/meyer2023better.pdf)，该方案比传统的证书透明日志\(Laurie et al., 2021\) (https://www.rfc-editor.org/info/rfc9162) 生成更短的证明。 Reed (https://worm-blossom.github.io/reed/#name) 取代了之前的 Bamboo (https://github.com/AljoschaMeyer/bamboo) 规范。Reed (https://worm-blossom.github.io/reed/#name) 比 Bamboo 更高效，功能集更极简，并且可泛化至任意特定的密码学原语。Bamboo 最初是为高效数据复制设计的，但后来我倾向于更灵活的复制技术 (https://willowprotocol.org/)，因此 Reed (https://worm-blossom.github.io/reed/#name) 去掉了它的数据复制起源。 后面会有图表。 ## 概述 (https://worm-blossom.github.io/reed/#overview) 先来一段密集的单段总结，再用图片逐步解释，如何？ Reed (https://worm-blossom.github.io/reed/#name) 是一种传递前缀认证方案\(Meyer, 2023bb\) (https://worm-blossom.github.io/reed/assets/references/meyer2023sok.pdf)：给定一个事件序列，我们构造一个无环有向图（DAG），其边对应一个对象包含另一个对象的密码学哈希（即一个 Merkle-DAG）。对于每个事件，我们分配一个承诺顶点，该顶点有一条通向该事件的路径，以及通向所有更早事件承诺顶点的路径。给定两个事件的承诺顶点以及它们之间路径的出邻域，我们可以重建路径上所有顶点的哈希，从而证明第一个事件确实发生在另一个事件之前。Reed (https://worm-blossom.github.io/reed/#name) 保证这些路径的出邻域很小，即验证是高效的。 让我们逐步分解。我们从一组有序的事件序列开始，下面例子中有九个事件： 图1 (https://worm-blossom.github.io/reed/#fig_events) 一个包含九个事件的序列。目前没什么有趣的。 这些事件将构成图的基础。为了确保*高效*的前缀认证，我们首先需要添加一些额外的顶点。你暂时不需要关心我们*如何*确定这些顶点，我们只是在这里感受一下总体概念。 图2 (https://worm-blossom.github.io/reed/#fig_vertices) 我们根据后面要介绍的规则，添加了一些额外的顶点。 接下来，我们添加边，使这些顶点成为一个有用的图。我们正在构建一个 Merkle-DAG，这意味着每个顶点都标有其出邻域标签串联的密码学哈希\(^1\)。我们不需要可视化这些标签，因为它们由图的结构确定性地产生。 图3 (https://worm-blossom.github.io/reed/#fig_edges) 我们添加了一些边。这些边遵循一种有用的模式，我保证。你已经能嗅到三进制类跳表的气息了吗？ 每个事件都有一个关联的承诺顶点。 图4 (https://worm-blossom.github.io/reed/#fig_commitments) 事件及其专用的承诺顶点，分组在一起。注意到每个事件（平凡地）可以从其承诺顶点到达，并且每个承诺顶点可以从所有更晚事件的承诺顶点到达。 为了说明前缀认证，我们现在任意选择两个事件，并突出显示它们承诺顶点之间的路径。 图5 (https://worm-blossom.github.io/reed/#fig_path) 事件 和 的承诺顶点之间的最短路径。 给定该路径的出邻域的（标签），我们可以重建路径顶点的标签。特别地，我们可以重建事件 和 的承诺顶点的标签。 ``` 1let label_2_0 := hash(concat(label(), label())) 2let label_3_0 := hash(concat(label_2_0, label())) 3let label_3_1 := hash(concat(label(), label_3_0)) 4let label_6_1 := hash(concat(label_3_1, label())) 5let label_7_0 := hash(concat(label_6_1, label())) 6let label_8_0 := hash(concat(label_7_0, label())) ``` 如果哈希函数是安全的，那么在计算上不可行去*伪造*能够重建两个顶点之间路径的标签。因此，这些标签不可伪造地证明两个顶点之间存在一条路径。换句话说，事件 必须发生在事件 之前。简洁吧！ \(^1\) 这是一个轻微的简化，Reed (https://worm-blossom.github.io/reed/#name) 的正式版本还会在标签中串联一些元数据。 ## 规范 (https://worm-blossom.github.io/reed/#spec) 我们假设 hash (https://worm-blossom.github.io/reed/#hash) 是一个安全的哈希函数，将任意字节串映射为固定宽度的字节串。我们称 hash (https://worm-blossom.github.io/reed/#hash) 的一个输出为 digest (https://worm-blossom.github.io/reed/#digest)。 我们以事件序列 events (https://worm-blossom.github.io/reed/#events) 来定义一切，其中 event (https://worm-blossom.github.io/reed/#event) 是一个任意的字节串。事件序列 events (https://worm-blossom.github.io/reed/#events) 的长度 length (https://worm-blossom.github.io/reed/#length) 必须在 1 到 二者之间（含）。我们对 events 从 开始编号，因为这样数学上会更优美。 集合 InnerVertices (https://worm-blossom.github.io/reed/#InnerVertices) 是所有对 的集合，其中 且 能整除 而无余数。我们称 为事件 的承诺顶点 (https://worm-blossom.github.io/reed/#commitment)。 令 属于 InnerVertices (https://worm-blossom.github.io/reed/#InnerVertices)。 的前驱顶点 (https://worm-blossom.github.io/reed/#predecessor) 是事件 如果 ，否则是内部顶点 。 令 属于 InnerVertices (https://worm-blossom.github.io/reed/#InnerVertices) 且 不*属于* InnerVertices (https://worm-blossom.github.io/reed/#InnerVertices)。那么我们称 为事件 的最高顶点 (https://worm-blossom.github.io/reed/#topmost)。 令 属于 InnerVertices (https://worm-blossom.github.io/reed/#InnerVertices)，且 。 的跳跃顶点 (https://worm-blossom.github.io/reed/#jump) 是事件 的最高顶点 (https://worm-blossom.github.io/reed/#topmost)。 图6 (https://worm-blossom.github.io/reed/#fig_slls) 一个图，描绘了一个长事件序列的前几个顶点。浅色垂直边连接每个顶点到其前驱顶点，较暗的边连接每个顶点到其跳跃顶点。 事件 e (https://worm-blossom.github.io/reed/#label_event) 的标签 (https://worm-blossom.github.io/reed/#label) 是以下串联的 hash (https://worm-blossom.github.io/reed/#hash)： - 字节 `0x00`，以及 - e (https://worm-blossom.github.io/reed/#label_event)。 内部顶点 的标签 (https://worm-blossom.github.io/reed/#label) 是以下串联的 hash (https://worm-blossom.github.io/reed/#hash)： - 字节 `0x01`， - 的 前驱顶点 (https://worm-blossom.github.io/reed/#predecessor) 的标签， - 的 跳跃顶点 (https://worm-blossom.github.io/reed/#jump) 的标签——如果 不存在则为空字符串的 hash (https://worm-blossom.github.io/reed/#hash)， - 的大端编码作为一个无符号64位整数，以及 - 的编码作为一个无符号8位整数。 在标签中包含 和 并非方案安全所必需，但有实际好处：给定某个内部顶点的标签，你可以通过提供其前驱顶点和跳跃顶点的标签来证明它在图中的位置。 你可以通过一个贪心的逐步算法找到从一个顶点到另一个顶点的最短路径。从某个顶点开始，跳到它的跳跃顶点。如果跳过了，则改为跳到前驱顶点。反复迭代，直到到达目标顶点。形式上： 令 和 属于 InnerVertices (https://worm-blossom.github.io/reed/#InnerVertices)，且 。从 到 的 最短路径 (https://worm-blossom.github.io/reed/#shortest) 是唯一的序列 ，满足 - ，且 - 对于每个 ，有： - 如果 的跳跃顶点的 x 坐标严格小于 ，那么 是 的前驱顶点， - 否则 是 的跳跃顶点。 图7 (https://worm-blossom.github.io/reed/#fig_large_path): 一个示例路径 从 到 的 最短路径 (https://worm-blossom.github.io/reed/#shortest) 是序列 两个 承诺顶点 (https://worm-blossom.github.io/reed/#commitment) 之间的 最短路径 (https://worm-blossom.github.io/reed/#shortest) 的封闭出邻域的标签用作证明一个事件发生在另一个事件之前的证书。更精确些：证书是通过从较大事件的承诺顶点沿着最短路径走到较小事件的承诺顶点，每一步添加一个不在路径上的出邻域\(^2\)，最后反转得到的序列而获得的。形式上： 令 和 属于 InnerVertices (https://worm-blossom.github.io/reed/#InnerVertices)，且 。 和 的 前缀证书 (https://worm-blossom.github.io/reed/#certificate) 是序列，它 - 以 的跳跃顶点的 标签 (https://worm-blossom.github.io/reed/#label) 开头——如果 不存在则用空字符串的 hash (https://worm-blossom.github.io/reed/#hash)，然后 - 对于从 到 的 最短路径 (https://worm-blossom.github.io/reed/#shortest) 中的每个元素，按逆序连续地包含恰好一个 digest (https://worm-blossom.github.io/reed/#digest)：跳跃顶点的 digest 或前驱顶点的 digest，两者中哪一个*不*是逆序最短路径中的前一个顶点（对于第一个顶点，总是使用前驱顶点的 digest）。 继续图7 (https://worm-blossom.github.io/reed/#fig_large_path) 中的例子： 和 的 前缀证书 (https://worm-blossom.github.io/reed/#certificate) 是以下顶点的 digest 序列： 注意，同一个 digest 可能在 前缀证书 (https://worm-blossom.github.io/reed/#certificate) 中出现多次。我们可以很容易地定义一个压缩版本的证书，去除重复哈希除第一次出现外的所有出现，但验证时会更复杂。副本足够罕见（只有当某个跳跃顶点的 坐标严格减少时才会发生，而这仅在图的“左上角”附近），因此我们选择了更简单的验证过程，而不是追求证书大小在最佳情况下的微小缩减。 给定一个 digest 序列 以及一个声明： 是两个标签分别为 和 的承诺顶点之间的前缀证书，你可以迭代验证该声明。为了验证，利用 中的信息依次逆序计算从 到 的最短路径上的顶点的标签。如果你这样算出的 和 的标签分别匹配 和 ，那么你就成功验证了前缀证书。假设没有哈希碰撞，这证明直到事件 的事件序列是直到事件 的事件序列的前缀。因此，特别地，事件 发生在事件 之前。 这就是别人如何高效地向你证明某个事件发生在另一个事件之前。对于透明日志的使用场景，日志管理机构会对承诺顶点签名。签名后的承诺顶点将扮演该场景中签名树头 (https://www.rfc-editor.org/rfc/rfc9162.html#name-signed-tree-head-sth) 的角色。 关于 Reed (https://worm-blossom.github.io/reed/#name) 使用的链接方案的详细复杂度分析，请参阅论文\(Meyer, 2023aa\) (https://worm-blossom.github.io/reed/assets/references/meyer2023better.pdf)。 \(^2\) 对于最后一个顶点，两个出邻域都在路径之外——先添加前驱顶点，再添加跳跃顶点。 ## 参考文献 (https://worm-blossom.github.io/reed/#bibliography)