RaptorCast：设计一个消息传递层
在权益证明区块链中，预先确定的领导者通常在每一轮中提议一个交易区块。将此区块传播给所有验证者是共识协议中最具挑战性和耗时的步骤之一。在这篇博文中，我们将研究 RaptorCast，这是一种旨在解决以下考虑因素的解决方案：
- 性能 - 需要快速将区块提议发送到网络的其余节点
- 安全性 - 区块（或其片段）的每个接收者都需要能够验证它是否来自正确的领导者并且完好无损
- 鲁棒性 - 诚实验证者需要保证，在存在数据包丢失和拜占庭少数派的情况下，他们可以重建区块提议
背景
领导者如何将其区块提议发送给其他验证者？
有许多策略可以应对这一挑战。领导者可以简单地将提议区块逐个发送给每个验证者。然而，这种方法无法扩展。例如，如果有 1,000 个验证者，区块大小为 2MB，那么领导者需要上传大约 2GB 的数据。假设网络延迟为零，带宽为 1 Gbps，这仍然需要大约 16 秒，这对于高性能区块链来说显然是不切实际的。
在我们的系统中，我们需要做出一些关键决策，以确保与区块链约束的兼容性，同时优化速度和可靠性。具体来说，我们需要选择：
- 数据传输协议
- 一种编码系统
- 一种广播策略
下面，我们将描述每个设计参数并解释我们为什么这样设计。
数据传输协议
在为我们的系统选择数据传输协议时，我们主要考虑两个选项：TCP（传输控制协议）和 UDP（用户数据报协议）。每种协议都提供独特的优势和权衡，我们的决策应与我们的性能、可靠性和安全性要求相符。
TCP 是一种面向连接的协议，可确保可靠的数据传输。它提供诸如错误检查、丢失数据包的重传和数据排序等功能。这使得 TCP 非常适合数据完整性和可靠性至关重要的环境——尤其是在涉及潜在数据包丢失或网络不稳定的情况下。但是，这种可靠性是有代价的：当数据包重新排序或丢失时，延迟会增加，这会降低实时或高吞吐量应用程序的性能。
另一方面，UDP 是一种无连接协议，强调速度和效率。它传输数据时无需建立连接的开销，非常适合需要低延迟并且可以容忍偶尔的数据包丢失的应用程序。但是，我们需要调整我们的设计，以补偿 UDP 上的数据包丢失，并确保验证者收到目标数量的编码符号，尽管可能存在丢失。
也就是说，UDP 本身不提供身份验证或数据包传递保证机制，这是我们在上下文中主要关注的两个问题。但是，如果我们可以解决其他层中的这些限制，那么 UDP 将成为一个引人注目的选择。
因此，在我们的提案区块传播设计中，我们选择使用 UDP 而不是 TCP，以利用其速度优势，并且我们尝试通过我们的设计和编码系统来解决数据包丢失、数据完整性和消息认证问题。
QUIC 是另一种传输层协议，它结合了安全会话和流控制策略（类似于 TCP），并提高了效率。相对于 UDP，QUIC 引入了额外握手和加密的开销，这超过了更好的可靠性保证所带来的好处。
编码系统
由于我们选择 UDP 而不是 TCP，因此集成一个编码系统来处理数据包丢失变得至关重要。通过选择 UDP，我们固有地接受了数据包丢失的可能性，因此我们必须有效地弥补它。最有效的方法是采用强大的前向纠错 (FEC) 方案。例如，如果我们预计有 10% 的数据包丢失，我们可以简单地发送 10% 的额外编码数据包。这样，只要接收器收到足够数量的数据包，无论哪些特定数据包到达，它都可以成功解码源数据。
有几种著名的编码方案，包括 LT 码、R10、RaptorQ 和 Reed-Solomon。每种方案都具有独特的优势：有些方案（如 Reed-Solomon (Reed & Solomon, 1960)）对损坏的数据具有鲁棒性，而另一些方案（如 R10 和 RaptorQ）则旨在有效地处理丢失的数据。
对于我们的系统，我们选择了 R10，它是 Raptor 码 (Shokrollahi, 2006) 的一种实现，因为它具有高性能和可扩展性。但是，R10 本身并不能防止符号损坏（即，修改后的数据）。为了解决这个问题，我们将加入符号级别的身份验证，以确保数据完整性并检测传输过程中的任何篡改。
广播策略
此设计层定义了数据包如何从领导者分发和转发到其他验证器。存在几种策略，每种策略在速度、可靠性和可扩展性方面都有不同的权衡。
一种广为人知的方法是 Gossip 协议，其中每个验证器将接收到的数据包的子集转发给几个随机选择的对等方。这种方法简单而稳健，但由于冗余传输，效率可能不高。
我们采用的方法是结构化广播，其中每个验证器被分配特定的数据部分，以重新广播到预定义的对等节点组。这种两跳方法更节省带宽且更具可预测性。
还有一种半结构化方法，它将随机性与结构相结合。在这种模型中，数据包转发目标是随机选择的，但在定义的结构内，类似于 Solana 的 Turbine (Anza, n.d.) 协议。
1. 数据传输层
当领导者广播他们的提议时，如何防止恶意节点在转发过程中修改数据包（中间人攻击）？接收者如何验证接收数据的完整性，并确保数据包确实是由正确的领导者生成的？
在我们的设计中，每个编码符号（每个块）都适合一个 UDP 数据包，并且每个数据包都是可以独立验证的。为了理解这是如何工作的，我们首先描述每个数据包的结构。每个数据包由四个关键组件组成：
- Merkle Proofs
- Header
- Chunk Header
- Data
什么是块（chunk）？
数据块是由纠删码产生的较小的数据单元（在第 2 节中进一步讨论），可用于重建原始有效负载。单个数据块对应于下面图示的 UDP 数据包的数据或有效负载。
让我们逐步了解每个组件。
Merkle Proofs (100 字节)
为了验证消息的真实性，发送者需要使用其私钥对消息进行签名，而接收者使用发送者的公钥进行验证。 如前所述，我们计划将一个块转换为多个块并独立传输每个块； 因此，每个块都需要由发送者进行身份验证。 理论上，领导者可以对每个块进行签名，这足以防止篡改或数据损坏。 但是，当对数百或数千个块执行签名操作时，计算成本很高。
借助 RaptorCast，签名数量减少了 32 倍:主节点对每组 32 个数据块（包括各自的chunk headers）生成一棵 Merkle 树。主节点随后只对“header”（定义见下文）与 Merkle 根哈希的拼接内容进行签名，而不是对每个数据块单独签名。由于每个哈希为 20 字节，且 Merkle 树深度为 5（对应 32 个叶子节点），因此 Merkle 证明仅需 100 字节。
通过 Merkle 树方法，我们以每个块增加 100 字节额外数据的代价，将签名数量减少了 32 倍。
这种方法也有利于验证。因为每 32 个块共享同一个签名，所以验证者可以缓存签名并执行快速的 Merkle 证明验证，而不是验证数千个单独的签名。
Header (108 字节)
上述签名不仅为接收者提供了关于 Merkle 根的保证，而且还将其与下面定义的所有元数据相关联。 事实上，签名占据了大部分头部空间（65 字节）。
- 65 字节 => 发送者对哈希（header剩余部分与 Merkle 根的连接）的签名。此签名将与 31 个其他 UDP 数据包共享（相同的 Merkle 根）。
- 2 字节 => 版本，在协议更新时递增
- 1 位 => 广播标志
- 7 位 => Merkle 树深度
- 8 字节 (u64) => Epoch #
- 8 字节 (u64) => 毫秒级的 Unix 时间戳
- 20 字节 => 区块提议哈希的前 20 个字节
- 4 字节 (u32) => 序列化的区块提议长度（字节） 头部总大小为 108 字节：
Chunk Header (24 字节)
Chunk Header包含特定于每个数据块的元数据，并包含有关编码索引的信息。结构如下图所示： 
数据
为了计算表示给定区块提议所需的最小 UDP 数据包数量，我们采用 ~1500 字节的 MTU（最大传输单元）大小，并减去header, chunk header, 和 Merkle proof使用的固定 232 字节。这为实际数据留下了 1268 字节。
然后，我们将消息的总大小除以这个有效载荷容量，以确定需要多少个数据包。
有了这些，我们就解决了数据完整性和消息认证的问题。每个块都包含 Merkle 根的签名，因此如果恶意节点修改任何数据包，更改后的版本的哈希值将与 Merkle 树不匹配，并且完整性检查将失败。
2. 编码系统
我们已经通过 Merkle 证明和数字签名解决了消息完整性和身份验证问题。现在我们转向第二个主要挑战：确保消息在不可靠的传递情况下仍然可用。为了应对这一挑战，我们使用一种编码系统，该系统可确保消息在数据包丢失的情况下也能传递。
数据包丢失可能由于多种原因发生，包括网络不稳定、拥塞，甚至节点故意丢弃数据包或未能转发数据包的恶意行为。我们的目标是确保每个诚实节点都收到足够多的编码数据包，以重建原始提案消息，而不管具体传递了哪些数据包。
最后一点至关重要：我们不能依赖数据包索引，因为我们无法控制哪些数据包丢失。相反，我们依赖于一种编码系统，即纠删码，它将原始消息转换为更长的派生版本。原始消息可以从新消息的任何足够大的子集中恢复。
为了实现这一点，我们必须选择适当数量的编码块（编码符号）来传输。例如，如果我们将提案分成 1000 个源块（源符号），我们可能会估计 1100 个编码块足以成功重建。但是，如果我们还预计有 10% 的数据包丢失，并考虑到高达 33% 的节点是恶意的（例如，不转发数据），我们必须引入额外的冗余，以确保诚实节点至少收到 1100 个块。
确定确切的冗余度取决于广播策略，我们将在下一节中解释。一旦确定了策略，我们将返回来解释如何以高置信度选择冗余级别。接下来，我们将解释我们正在使用的编码系统。
我们使用 R10 作为我们编码-解码系统的基础。R10 是 RFC 5053 (Luby et al., 2007) 中规定的标准化喷泉码。它专为高效且稳健的前向纠错 (FEC) 而设计，尤其是在像 UDP 这样不可靠或有损的网络上。
对于那些不熟悉的人来说，R10 与 Luby Transform (LT) 码（Luby, 2002）密切相关，它是在此基础上构建和扩展的。为了提供适当的背景，我们首先简要解释 LT 编码和解码，然后再过渡到 R10 如何增强这些方法。
LT 编码 (Luby Transform)
在 LT 码中，核心思想是从一组固定的源块（比如， N 个块，它们也被称为源符号）中产生任意数量的编码符号。每个编码符号的生成方式如下：
- 从一个度分布中选择一个度 d （这决定了要组合多少个源块）。
- 随机从原始集合中选择 d 个不同的源块。
- 将这些源块进行异或运算，形成编码符号。
请注意，编码器根据输入（ N 和编码符号索引）确定性地选择源块。
度分布示例
degree 1 : 10%
degree 2 : 45%
degree 3 : 5%
degree 4 : 5%
degree 5 : 10%
degree 8 : 10%
degree 40: 15%
这意味着：
- 45% 的情况下，编码器选择 2 个源块进行异或运算。
- 15% 的情况下，它选择 40 个源块进行异或运算。
- 以此类推..
编码过程是无状态且简单的，这使得 LT 码非常适应于动态生成或流式传输符号的系统。
LT 解码
LT 系统中的解码基于剥离的思想，这是一种递增的方法，用于降低接收到的编码块的度数，直到所有 N 度为 1 的块都被推导出来。
- 找到一个度为 1 的编码符号。
- 这个符号只包含一个未知的源块，因此可以立即恢复。
- 将已知的源块代入所有包含它的其他编码符号中（即，异或运算）。
- 重复这个过程——每次替换都可能创建新的度为 1 的符号。
如果在任何时候，当解码尚未完成时，没有剩余的度数为 1 的符号，则过程失败。
LT Decoding Example LT 解码示例
假设源块是 c1 到 c5 ，并且我们收到以下编码符号：
s1 = c1 # degree 1 DONE
s2 = c1 + c2 + c3 # degree 3
s3 = c2 + c1 # degree 2
s4 = c5 + c3 # degree 2
s5 = c4 + c5 + c2 + c1 # degree 4Step-by-step decoding: 逐步解码：
- s1 的度为 1 → 恢复 c1
- 将 c1 代入所有包含 c1 的其他符号： s2 、 s3 和 s5
s1 = c1 # degree 1 DONE
s2 = c1 + c2 + c3 => c2 + c3 # degree 2
s3 = c2 + c1 => c2 # degree 1 DONE
s4 = c5 + c3 # degree 2
s5 = c4 + c5 + c2 + c1 => c4 + c5 + c2 # degree 3- s3 现在度为 1 → 恢复 c2
- 将 c2 代入所有包含 c2 的其他符号： s2 和 s5
s1 = c1 # degree 1 DONE
s2 = c2 + c3 => c3 # degree 1 DONE
s3 = c2 # degree 1 DONE
s4 = c5 + c3 # degree 2
s5 = c4 + c5 + c2 => c4 + c5 # degree 2- s2 现在是 1 度 → 恢复 c3
- 将 c3 代入 s4 ： 求出 c5
s1 = c1 # degree 1 DONE
s2 = c3 # degree 1 DONE
s3 = c2 # degree 1 DONE
s4 = c5 + c3 => c5 # degree 1 DONE
s5 = c4 + c5 # degree 2- 恢复 c5 ，然后在 s5 中使用它： s5 变为 c4
- 最后，恢复 c4
s1 = c1 # degree 1 DONE
s2 = c3 # degree 1 DONE
s3 = c2 # degree 1 DONE
s4 = c5 # degree 1 DONE
s5 = c4 + c5 => c4 # degree 1 DONE✅ 所有源块已成功恢复。
LT 码的局限性
然而，并非所有解码会话都如此顺利。考虑一组没有出现度为 1 的符号的编码符号：
s1 = c2 + c1 # degree 2
s2 = c3 + c5 + c2 # degree 3
s3 = c1 + c5 # degree 2
s4 = c1 + c4 # degree 2
s5 = c4 + c3 + c2 # degree 3
s6 = c1 + c3 # degree 2在这里，没有符号的度数为 1，因此 LT 解码器会卡住——它无法通过剥离取得任何进展。尽管如此，该系统包含 6 个具有 5 个变量的线性方程，这在代数上是可解的。
这里是另一个例子，表明即使存在一个度为 1 的符号，LT 解码器也可能卡住并最终失败。这与上面第一个成功的例子几乎相同，除了 s1 = c3 而不是 s1 = c1 。
s1 = c3 # degree 1 DONE
s2 = c1 + c2 + c3 # degree 3
s3 = c2 + c1 # degree 2
s4 = c5 + c3 # degree 2
s5 = c4 + c5 + c2 + c1 # degree 4尽管取得了一些进展，我们还是陷入了困境。
s1 = c3 # degree 1 DONE
s2 = c1 + c2 # degree 2
s3 = c2 + c1 # degree 2
s4 = c5 # degree 1 DONE
s5 = c4 + c2 + c1 # degree 3R10：优于 LT 的改进
R10 代码通过在 LT 编码之前添加预编码阶段并在剥离解码器失败时支持基于矩阵的解码来扩展 LT。
- 预编码阶段通过在 LT 编码之前添加结构化冗余来提高解码成功率。
- 如果剥离失败，R10 会退回到使用高斯消元法求解方程组。
- 与原始 LT 码相比，R10 码需要更少的额外编码符号才能成功解码，这归功于预编码阶段和高斯消元回退。然而，解码仍然需要略多于原始源符号的数量，因为一些编码符号可能是线性相关的。一个小的冗余因子可以解决这个需求。
因此，在上面的第一个失败案例中，即使 LT 解码器放弃，R10 也会求解整个系统以恢复源块。
3. 广播策略
我们的设计基于一个 两级结构的广播模型。每个验证者（validator）会接收与其质押量成比例数量的数据包，并负责将这些数据包再次广播给网络中的其他节点。
设定验证者之间的质押分布为：
其中 表示第 个验证者的质押量， 为 总质押量（total stake）。
假设总共编码出了 个符号块（chunks），则每个验证者 分配到的块数量为：
这些块用于再次广播。
使用向上取整（ceiling function）确保即使存在高达三分之一的拜占庭节点，每个诚实的验证者也能接收到足够的块以完成解码。
领导者如何决定编码符号的数量 ？
假设原始提案消息可以被分成 个数据块（chunks）。领导者（leader）需要确保诚实验证者（honest validators）最终能够集体接收足够数量的块，以成功解码原始消息，即便存在以下情况：
- ：从领导者到验证者的丢包率（第一跳）
- ：验证者之间的丢包率（第二跳）
- 拜占庭行为的验证者（可能拒绝转发他们分配的块）——假设其总质押权重低于 1/3
我们还定义了以下变量：
- ：全网总质押量
- ：领导者的质押量
接下来定义冗余因子如下：
Packet Loss（丢包冗余系数）
其中分母中的 和 表示数据在每一跳中成功传输的概率。
例如：
- 若 （即丢包率为 66.66%），则只有 的包会被成功传送。
- 在这种情况下，为了成功交付 个块，需要发送 个块 ⇒ 需要约 3 倍的冗余因子来补偿。
因此，丢包率出现在分母中，用来适当地放大冗余因子。
拜占庭行为（最多占网络的 1/3）
对于最多 1/3 的拜占庭节点（可能会恶意拒绝转发），我们定义了以下冗余因子：
该冗余因子确保了在 1/3 验证者为拜占庭节点 的假设下系统仍可容错，同时根据领导者的质押量 动态调整。
特殊情况：
如果领导者的质押为 0（即 ），公式简化为：
表示基础冗余率为 1.5，符合应对 1/3 拜占庭节点容错 的需求。
例如：如果需要 10 个块，则发送 15 个块。即使有 5 个被丢弃，剩下的 10 个也足够解码。当领导者的质押量接近总质押量的 时，分母 ，此时 ，表示需要无限冗余，几乎不现实。
将之前的所有冗余因子相乘，再额外乘以一个 1.1 的常数项（用于解码开销补偿），最终冗余因子为：
此公式确保：
- 考虑了两跳的丢包损耗
- 领导者的质押不会影响冗余判断（从计算中剔除）
- 假设拜占庭节点（最多 1/3）不参与转发
- 诚实节点将至少接收到 1.1 倍于解码所需的数据块，确保解码成功
在当前的实现中，冗余值是硬编码的。当较低的冗余度就足够时，这可能会导致效率低下，并且在需要较高冗余度的场景中，也可能会引入拜占庭容错问题。因此，采用动态冗余方案（上述公式）可以显著提高系统的鲁棒性。
一些示例，假设总权益 。
| SL | L | L' | 有 BFT 保证的冗余度 | 无 BFT 保证的冗余度 |
|---|---|---|---|---|
| 1 | 1% | 1% | 1.69 | 1.12 |
| 5 | 1% | 1% | 1.72 | 1.12 |
| 10 | 1% | 1% | 1.78 | 1.12 |
| 20 | 1% | 1% | 1.92 | 1.12 |
| 1 | 5% | 5% | 1.83 | 1.22 |
| 5 | 5% | 5% | 1.87 | 1.22 |
| 10 | 5% | 5% | 1.93 | 1.22 |
| 20 | 5% | 5% | 2.08 | 1.22 |
因此，领导者将生成 个块并设置：
并根据 将块分发给各个验证者。
示例
考虑一个权益向量：
这里，总权益为 。
假设提案区块适合放入 4 个数据块，冗余因子设置为 2。这总共得到 。为了考虑上述公式中的舍入，领导者会为每个验证者预先生成额外的 4 个备份块，因此创建了 个块。
阶段 1：分配
领导者根据验证者的权益和 方程式将块分配给他们：
- 验证者 1 拥有 权益 收到 2 个块
- 验证者 2 拥有 权益 收到 3 个块
- 验证者 3 拥有 权益 收到 2 个块
- 验证者 4 拥有 权益 收到 1 个块
阶段 2：重新广播
在领导者将分配的区块发送给第一阶段的每个验证者之后，验证者负责将其分配的区块重新广播给所有其他验证者
下图说明了区块的分配和重新广播： 
在之前的示例中，分配给每个验证者的块数量恰好是整数，因此不需要舍入。因此，没有使用任何备份块 (c9 - c12)。然而，在大多数实际场景中，会出现小数值，并且向上舍入是必要的。
例如，考虑一个新的总权益为 12 的权益分布：
假设原始块数量为 2，冗余因子为 4，这意味着 。现在，我们计算每个验证者应该收到的块数量：
- 验证者 1 拥有 权益 收到 2 个块
- 验证者 2 拥有 权益 收到 4 个块
- 验证者 3 拥有 权益 收到 2 个块
- 验证者 4 拥有 权益 收到 2 个块
这导致总共分配了 个块，即使原始块数量是 8。需要额外的 2 个块来解释舍入效应。这正是领导者预先生成 个额外块的原因，其中 是验证者的数量。
下图说明了在第二个示例中从领导者到验证者的块分布情况。
结论与未来方向：
高性能区块链要求技术栈的每个部分都针对吞吐量和低延迟进行优化。RaptorCast 是我们目前解决以可扩展和高效的方式向全球节点运营商网络共享区块提议的方案。简单概括来说，RaptorCast：
- 使用 UDP 作为其数据传输协议，接受缺乏交付保证以支持性能。通过数字签名，每个单独的块可以直接归因于给定的领导者和区块提案。
- 使用编码系统解决不可避免的丢包问题。特别是，我们选择了 R10（Raptor 代码的一种实现）。R10 通过添加预编码阶段来扩展 Luby Transforms (LT)，并在剥离解码器失败时回退到基于矩阵的解码。
- 实现一个两跳广播树，其中块最初按权益权重分配，接收者将其块重新广播到网络的其余部分。冗余是预期数据包丢失、领导者的权益价值、潜在的拜占庭行为以及少量解码开销的函数。
我们已经描述了当前的设计，但正在积极研究改进领域。未来的工作可能包括以下高级想法：
乐观设计与回退机制
如果拜占庭少数派拒绝参与区块传播，网络将丢失一轮。通过放宽拜占庭容错保证，冗余需求会显著降低。为了实现性能和活跃性安全之间的平衡，可以设计一个配备回退机制的乐观（低冗余）提案广播系统。如果观察到连续或有规律的故障，可以激活更高的冗余以适应拜占庭容错。在一系列成功的轮次之后，可以自动放宽这些参数以提高性能。
更快的编码器/解码器
如果我们只有少量源块，Reed-Solomon 码可能是一个不错的选择，但随着块数量的增加，它们的速度会显著降低。一种管理方法是将数据分成更小的段，并分别对每个段进行编码。这使得 Reed-Solomon 码的使用更加实用。然而，为了保持拜占庭容错性，每个段所需的冗余可能会导致大量的带宽开销。
参考文献
Anza. (n.d.). Turbine Block Propagation. Agave Validator Documentation. Retrieved April 29, 2025, from https://docs.anza.xyz/consensus/turbine-block-propagation
Luby, M. (2002). LT codes. Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, 271–282. https://doi.org/10.1109/SFCS.2002.1181950
Luby, M., Shokrollahi, A., Watson, M., & Stockhammer, T. (2007). Raptor forward error correction scheme for object delivery (RFC 5053). IETF. https://datatracker.ietf.org/doc/html/rfc5053
Reed, I. S., & Solomon, G. (1960). Polynomial codes over certain finite fields. Journal of the Society for Industrial and Applied Mathematics, 8(2), 300–304. https://doi.org/10.1137/0108018
Shokrollahi, A. (2006). Raptor codes. IEEE Transactions on Information Theory, 52(6), 2551–2567. https://doi.org/10.1109/TIT.2006.874390
https://www.category.xyz/blogs/raptorcast-designing-a-messaging-layer