*当 Chuck Norris 使用纠删码时，他不仅仅是保护数据冗余；他创建了一个坚不可摧的冗余堡垒，即使丢失一个字节都感觉像是在向他道歉。*

使用多项式插值的纠删码

:::info 定义

纠删码是一种前向纠错 (FEC) 码，它假设存在比特 擦除（而不是比特 错误），它将 `k` 个符号的消息转换为具有 `n` 个符号的更长消息（码字），以便可以从 `n` 个符号的子集中恢复原始消息。 :::

我们现在将看到一个使用多项式的纠删码的例子。

:::warning 警告

本节缺少许多数学形式，并隐藏了许多关于实际实现的细节（例如，实际上我们将在有限域上的多项式上进行运算，而本节在实数上的多项式上进行运算）。

但是，本节让读者掌握使用多项式插值的纠删码的思想。 :::

问题设置

Alice 有以下 4 字节的消息 `0x160C0B0D`，她想将其传输给 Bob。为此，她使用了一个不可靠的网络（互联网），该网络具有糟糕的、非常容易丢失连接的连接。

Alice 将把消息编码为 6 字节的编码消息，如果 Bob 仅收到编码的 6 字节消息的 任何 75%，他将能够重建初始的 4 字节消息。

任何 这个词在这里非常重要。如果 Bob 收到以下消息，则他必须能够重建初始数据，例如：

• 仅编码消息的前 75%，或者
• 仅编码消息的后 75%，或者
• 任何组合，只要 Bob 收到至少 75%（6 字节）的编码消息

:::info 注意

在本节中，我们将使用 3/4 (75%) 的码率，这意味着初始消息大小将增加 50%。 因此，只需要编码消息的 3/4 (75%) 即可重建初始消息。 :::

编码

让我们将 Alice 的 4 字节消息分成 4 个字节：`[0x16, 0x0C, 0x0B, 0x0D]`。 每个字节将代表一个多项式约束。 我们有 4 个约束。

让我们定义一个多项式 `P`，它具有以下约束：

• `P(0) = 22` (`0x16`)
• `P(1) = 12` (`0x0C`)
• `P(2) = 11` (`0x0B`)
• `P(3) = 13` (`0x0D`)

`x` 的计算值为整数 (0, 1, 2, 3)。 `P(x)` 的计算值是 Alice 想要编码的消息的字节。

使用拉格朗日多项式插值，Alice 找到唯一的次数最多为 `4-1 = 3` 的多项式，该多项式符合这 4 个约束。 她得到：

$$ P(x) =-x^3 + \frac{15}{2}x^2 - \frac{33}{2}x + 22 $$

扩展

Alice 添加了 2 个扩展点。 她选择 2 个对应于 `x=3` 和 `x=4` 的点。

在这些点处计算 `P` 得到：

• `P(4) = 12` (`0x0C`)
• `P(5) = 2` (`0x02`)

通讯

Alice 将不会向 Bob 发送 `0x160C0B0D`，而是：

• 与 Bob 约定她将向他发送 6 个 `(x, P(x))` 数据点，其中 `P` 是一个次数最多为 `3` 的多项式。
• 向 Bob 发送：`[(0x00, 0x16), (0x01, 0x0C), (0x02, 0x0B), (0x03, 0x0D), (0x04, 0x0C), (0x05, 0x02)]`，对应于 6 个 `(x, P(x))` 元组。
• 与 Bob 约定初始数据为：`[P(0), P(1), P(2), P(3)]`。

由于 Alice 和 Bob 之间的连接容易丢失，因此 Bob 仅收到 6 个元组中的 4 个：

• `(0x00, 0x16)`，
• `(0x02, 0x0B)`，
• `(0x04, 0x0C)`，以及
• `(0x05, 0x02)`

重建

从收到的字节中，Bob 推断出：

• `P(0) = 22` (`0x16`)
• `P(2) = 11` (`0x0B`)
• `P(4) = 12` (`0x0C`)
• `P(5) = 2` (`0x02`)

Bob 知道原始消息是 `[P(0), P(1), P(2), P(3)]`。 但是，`P(1)` 和 `P(3)` 丢失了。

Bob 知道这 4 个点属于次数最多为 `3` 的唯一多项式，因此他可以使用拉格朗日插值法重建该多项式（就像 Alice 之前所做的那样，但是使用与 4 字节初始消息相对应的 `4` 个点）。

Bob 最终得到这个多项式（这与 Alice 之前计算的完全相同）：

$$ P(x) =-x^3 + \frac{15}{2}x^2 - \frac{33}{2}x + 22 $$

Bob 现在在 `x=1` 和 `x=3` 处计算 `P`。 他发现：

• `P(1) = 12` (`0x0C`)
• `P(3) = 13` (`0x0D`)

Bob 现在能够重建前 4 个元组： `[(0x00, 0x16), (0x01, 0x0C), (0x02, 0x0B), (0x03, 0x0D)]` 和初始消息：`0x160C0B0D`。

:::info 注意

如果 Bob 收到的点少于 4 个，那么他将无法重建相应的次数最多为 `3` 的唯一多项式。

实际上，他将能够重建无穷多个次数最多为 `3` 的多项式，包括原始多项式。

但是，他不会确切地知道哪个是好的多项式。 :::

:::info 注意

使用这种纠删码技术的优势可能乍看并不明显：

• 如果没有纠删码，Alice 会向 Bob 发送 4 个字节的数据。
• 如果有纠删码，Alice 会向 Bob 发送 6 个字节的数据（+ `x` 坐标）。

纠删码会消耗更多数据。

但是，这里的重要一点是：

• 如果没有纠删码，Bob 必须接收 Alice 发送的 4 个字节中的 正好 4 个字节 (100%)。
• 如果有纠删码，Bob 可能会收到 Alice 发送的 6 个字节中的 任何 4 个字节 (75%)。 :::

一些纠删码的现实生活用法

二维码

此二维码嵌入了 offchainlabs.com 链接。

如果我们损坏此二维码的某些部分，仍然可以检索嵌入在其中的（纠删码）信息。

光盘

一张划痕损坏的光盘（在一定程度上...）可能仍然可读，因为存储在其中的数据经过了纠删码。

以太坊 - 信标链 blobs peer DAS

这个精确的案例将被详细研究。

• 原文链接： hackmd.io/uImjdfxFT2-xA7...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～