🔢 mathematics

Monotone Erasure Codes

本文引入单调擦除码以支持分布式系统中的任意信任假设，为线性变体提供高效的构造算法，并展示了其在构建通信高效的通用异步可验证信息分散（AVID）协议以用于区块链共识中的应用。

原作者： Vivien Bammert, Annalisa Cimatti, Orestis Alpos, Giuliano Losa, Christian Cachin

发布于 2026-05-22

📖 1 分钟阅读🧠 深度阅读

原作者： Vivien Bammert, Annalisa Cimatti, Orestis Alpos, Giuliano Losa, Christian Cachin

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

想象一下，你拥有一份制作世界上最美妙蛋糕的珍贵秘密食谱。你希望以某种方式存储这份食谱，使得即使部分朋友遗忘了笔记或丢失了记录，你仍能凭借剩余的朋友重建完整的食谱。

旧方法：“一刀切”方案
传统上，系统采用一种称为纠删码（Erasure Coding，如 Reed-Solomon 码）的方法。这好比将你的食谱切成 10 等份，分给 10 位朋友每人一份。规则很简单：“只要你有任意 6 位朋友，就能拼凑出切片并烤出蛋糕。”

如果你假设任意 4 位朋友都可能消失，这种方法效果极佳。但如果你的朋友们并非完全相同呢？

朋友 Alice 居住在风暴频发地区，经常丢失邮件。
朋友 Bob 非常可靠，但邮箱很小。
朋友 Charlie 超级可靠，且拥有巨大的邮箱。

旧的"10 份切片，需要 6 份”规则在此处效率低下。它将经常出错的 Alice 与 Bob 等同对待。如果 Alice 丢失了她的切片，即使你拥有许多可靠的朋友，也可能因切片不足而无法烤出蛋糕。你或许会为了保险起见给 Alice 分配巨大的切片，从而浪费空间；或者给 Bob 分配过小的切片，导致不够用。

新构想：“单调纠删码”
本文提出了一种更聪明的食谱切割与分发方式，称为单调纠删码（Monotone Erasure Codes）。该系统不再遵循“需要 6 人”这类僵化规则，而是尊重信任图谱（或称访问结构）。

将信任图谱想象成一份定制操作手册，其中说明：

“如果你拥有 Alice，则必须同时拥有 Bob 和 Charlie 才能生效。”
“但如果你仅拥有 Bob 和 Charlie，那就足够了！”
“如果你拥有 David 和 Eve，则需要第三人，但具体是谁无关紧要。”

系统根据此图谱为不同朋友分配不同大小的食谱片段：

Alice（不可靠）可能获得非常小的片段（甚至完全没有片段），因为系统知道无法单独依赖她。
Bob 和 Charlie（可靠）获得更大、更关键的片段。
David 和 Eve 获得中等大小的片段。

其神奇之处在于：无论哪群朋友出现，只要他们根据信任图谱构成一个“有效团队”，他们就拥有足以重建整个蛋糕的总信息量。如果他们不是有效团队（例如仅 Alice 加一个随机陌生人），则无法完成重建。

构建方法
本文提供了两种构建这些定制码的主要方法：

快速构建器：该方法将你的信任图谱（描述为包含“与”和“或”的逻辑树）作为输入，快速将食谱切割成片段。它速度快且适用于任何图谱，但有时会略微浪费空间（例如为了保险起见将切片切得稍大）。
完美构建器：该方法利用一点数学（线性规划），为你的特定信任图谱寻找精确的最小片段。这就像一位主厨计算每位朋友所需面团的精确毫米数以最小化浪费。这是最高效的，但需要更多的计算时间。

他们还发现了一种特殊情况，称为分区访问结构（Partitioned Access Structures，类似于 Stellar 网络，其中节点被分组到组织中）。针对这些情况，他们构建了一种超高效算法，能极快地找到完美的片段大小。

实际应用："GAVID"协议
本文不仅止步于存储食谱，还展示了如何利用这些代码在混乱、异步的互联网中发送消息，其中人们可能会撒谎或反应迟缓。

他们创建了一个新协议，称为GAVID（通用异步可验证信息分散）。

旧方法：仅在你确切知道可能有多少人失败时有效（例如“最多 3 个骗子”）。
新方法（GAVID）：配合复杂的信任图谱运作。它允许发送者将食谱片段散布到网络中。即使部分朋友撒谎或反应迟缓，只要一个由诚实朋友组成的“有效团队”（即内核）收集了这些片段，他们就能验证食谱的真实性并重建它。

为何重要
在区块链和分布式系统的世界中，并非所有计算机都生而平等。有些比其他更值得信赖。本文提供了数学工具，以停止将所有人一视同仁。它允许系统通过根据每个节点的具体可靠性定制数据分发，从而实现更高的效率（存储更少数据）和更强的鲁棒性（处理复杂的信任关系）。

总结：

旧代码：“无论这些人是谁，都需要 10 人中的 6 人。”
新代码（单调）：“基于你信任谁，需要特定的人员组合。将更多数据分配给可靠者，较少的数据分配给不可靠者。”
结果：在信任程度各异的环境中，一种更智能、更高效的数据存储与共享方式。

技术摘要：单调擦除码

1. 问题陈述

传统的擦除码（如 Reed-Solomon (MDS) 码）基于阈值故障假设运行。在这些系统中，数据被划分为 $k$ 份，并编码为 $n$ 个片段，使得任意 $k$ 个片段都足以进行重构。该模型假设任意 $k$ 个节点的子集具有相同的可用性或故障概率，而与节点的具体身份无关。

然而，现代分布式系统，特别是在区块链和加密货币领域（例如 Stellar、XRP 账本），利用广义故障假设或拜占庭容错（Byzantine）共识系统。在这些情境中，信任并非均匀分布；某些节点比其他节点更值得信任，且故障模式并非纯粹随机，而是取决于特定的节点子集。现有的基于阈值的代码无法在不产生显著开销或结构不匹配的情况下，有效地适应这些任意的信任假设。本文旨在解决对尊重任意单调访问结构的擦除码的需求，即确保特定的节点子集（访问集）能够重构数据，而其他子集则可能无法做到。

2. 方法论

本文介绍了单调擦除码，这是对经典擦除码的推广，旨在处理任意的访问结构 $\mathcal{A} \subseteq 2^{\mathcal{P}}$ ，其中 $\mathcal{P}$ 是节点集合。

2.1 定义与形式化

单调擦除码：一种由 Encode（编码）和 Decode（解码）算法组成的方案。Encode 将文件 $f$ 映射为片段向量 $(g_1, \dots, g_n)$ ，其中片段的大小可以不同。Decode 从对应于访问集 $A \in \mathcal{A}$ 的任意片段子集中重构 $f$ 。
效率：通过开销 $\beta = (\mu - \kappa) / \kappa$ 来衡量，其中 $\kappa$ 是输入文件大小， $\mu$ 是所有片段的总大小。目标是 minimize $\beta$ 。
线性单调擦除码：一类特定的码，其编码和解码是在有限域 $\mathbb{F}_q$ 上的线性运算。编码由生成矩阵 $G$ 和将 $G$ 的列映射到节点的标记函数 $\phi$ 定义。如果对应于这些节点的 $G$ 的子矩阵具有满秩（ $k$ ），则该节点集合是充分的。

2.2 构建方法

本文提出了三种构建这些码的不同方法：

基础构建（非最优）：
- 基于表示访问结构的单调布尔公式（MBF）。
- 该算法递归遍历访问树。对于 AND 节点，文件被分割成块；对于 OR 节点，文件被复制。
- 结果：保证完整性，但由于树结构中的冗余复制，通常导致高开销。
高效线性构建（次优）：
- 使用递归算法构建分块 MDS 矩阵。
- 它通过结合范德蒙德矩阵（用于阈值操作符），并使用克罗内克积和单位矩阵来对齐维度，从而构建编码矩阵。
- 结果：计算高效（关于访问树规模的多项式时间），但不保证最小开销。
最优线性构建（通过线性规划）：
- 一般情况：将寻找最优片段分布的问题表述为线性规划问题（LPP）。目标是最小化分配给节点的片段权重之和，受限于每个访问集至少持有 $k$ 个“基础”片段（源自底层 MDS 码）的约束。
- 分区访问结构：对于特定类别的结构（分层结构，其中每个节点在 MBF 中恰好出现一次，例如 Stellar 的信任模型），本文提供了一种专门的递归算法（算法 2）。该算法通过识别包含或排除哪些子树以最小化开销，从而高效地（ $O(n^2)$ ）求解 LPP，实际上确定了基础片段的最优分配。

2.3 协议应用：GAVID

本文将这些码集成到一个名为**通用异步可验证信息分散（GAVID）**的分布式协议中。

推广：将经典的 AVID 协议（Cachin 和 Tessaro）从阈值系统扩展到通用拜占庭共识系统。
机制：使用共识系统的核系统（kernel system）作为单调擦除码的访问结构。
关键概念：引入可靠集（包含与任何故障集不相交的核的集合），以确保异步环境下的可用性和一致性。
优化：提出GAVID-H，用 Merkle 树根替换完整的验证向量，从而降低通信复杂度。

3. 主要贡献

单调擦除码的定义：本文正式定义了一种新的编码原语，将经典擦除码推广到任意单调访问结构，允许非均匀的信任假设。
构建算法：
- 提供了一种计算高效的方法，用于为任意访问结构构建线性单调擦除码（尽管在开销方面并不总是最优）。
- 提供了一种通过求解从访问结构导出的线性规划问题来构建最优线性单调擦除码的方法。
分区访问结构：分析了分区访问结构（在实践中很常见）的具体情况，并提出了一种高效算法来为它们构建最优码，并刻画了其开销。
GAVID 协议：制定了一种通用异步可验证信息分散协议（GAVID），利用单调擦除码为任意共识系统实现通信高效的拜占庭可靠广播。

4. 结果与分析

开销界限：对于最小访问集大小为 $\tau$ 的通用访问结构，最优线性单调擦除码的开销 $\beta$ 在大 $k$ 时受限于 $\beta \le (n - \tau)/\tau$ 。这意味着如果最小访问集接近节点总数，开销将趋近于零。
分区构建的效率：针对分区访问结构的专用算法运行时间为 $O(n^2)$ ，当访问集数量呈指数级增长时，这比直接求解通用 LPP 要快得多。
协议复杂度：
- GAVID Disperse：消息复杂度 $O(n^2)$ ；通信复杂度 $O(n(1+\beta)|f| + n^3|H|)$ 。
- GAVID-H（Merkle 优化）：将通信复杂度降低至 $O(n(1+\beta)|f| + n^2(\log n)|H|)$ ，将存储复杂度降低至 $O((1+\beta)|f| + n(\log n)|H|)$ 。
正确性：本文证明了只要系统的核结构存在单调擦除码，GAVID 即满足任意拜占庭共识系统的终止性、一致性、可用性和正确性属性。

5. 意义与主张

本文主张，单调擦除码是感知信任的分布式系统的关键赋能者。通过超越僵化的“任意 $k$ 个出 $n$ 个”阈值模型，这些代码允许系统：

减少冗余：通过将更多数据分配给值得信任的节点，而将较少数据分配给风险较高的节点，而不是同等对待所有节点，从而优化存储和通信开销。
支持复杂的信任模型：直接实现现实世界区块链网络（如 Stellar）中发现的信任假设，其中信任是分层且非均匀的。
推广协议：提供一种基础原语（GAVID），使现有的高效广播和共识协议能够在通用拜占庭共识系统下运行，而不仅仅局限于简单的阈值模型。

作者指出，虽然他们为分区结构提供了一种高效的构建方法，但为任意访问结构（以具有指数级数量集合的 MBF 形式给出）构建最优单调擦除码的问题仍然是一个未解之谜。他们还建议未来的工作方向包括动态码以及将其他编码理论技术（如无速率码）应用于此场景。