致谢：这是与 Emanuele Viterbo 和 Dankrad Feist 的合作成果，并得到了 ESP 拨款 FY24-1745“DAS 中二维里德-所罗门码的改进”的支持。
本文阐述了如何在以太坊 PeerDAS 协议中使用区块循环码 (BC 码) 来替代一维 (1D) 和二维 (2D) Reed-Solomon (RS) 码。我们提出了一种高效的编码和重构方法。
在与 BC 代码相同的实现框架内开发的算法
相应的 1D RS 算法。所提出的编码算法也允许
KZG承诺方案的优雅集成。我们对其进行了评估和比较。
本文从码率、停止率以及局部码的大小等方面比较了BC码与一维和二维RS码的性能。更详细的版本发表于SVF2026 。
区块循环码
SVD2025引入了块循环 (BC) 码，作为 PeerDAS 中一维（目前使用）和二维 RS 码（预计稍后集成）的可行替代方案。与二维 RS 码类似，BC 码包含多个局部码，每个局部码都可以设计为[(n_0,k_0),D] [ ( n 0 , k 0 ) , D ]堆叠的一维 RS 码。所谓堆叠的一维 RS 码，是指码字堆叠成 D 行（每行长度为n_0 n 0 ， k_0 k 0列，表示信息符号）的[n_0D ,k_0D] [ n 0 D , k 0 D ] RS 码。因此，它与 KZG 方案兼容。事实证明，BC 码能够实现某些速率、停止速率和局部码大小的运行状态，而这些状态是 1D 或 2D RS 码都无法实现的。
在二维RS码中，符号排列在一个二维正方形网格中，每一行或每一列的符号都受到线性约束。在BC码中，符号排列在一个圆上，该圆被分割成多个重叠的弧。每个弧都有两个相邻的重叠弧，一个在其左侧，另一个在其右侧（顺时针方向）。每个弧上的符号都受到一组线性约束。我们将在下一小节中给出更具体的描述。
BC法规简介
图 1：块循环码示意图。在本例中，绿色背景的信息符号与粉色背景区域的奇偶校验符号组合，形成最终排列。闭合曲线内的符号组表示局部码。
考虑图 1 所示的包含n= 16个符号的示例。圆上有μ = 4个弧（其中两个用闭合曲线标记），每个弧包含n₀=6个符号，这些符号均匀分布在圆上。总共有k= 8个不受约束的符号，记为 d₁ , … , d₈ 。每个局部码包含k₀= 4个不受约束的符号。其余符号的生成受到某些线性约束。在每个弧中，以某种方式添加 ρ =n₀-k₀= 2个冗余符号，使得与该弧对应的局部码成为一个一维 RS 码。例如，对应于单个弧的符号向量(d_1, d_2, p_{11}, p_{12}, d_3, d_4) ( d1 , d2 , p11 , p12 , d3 , d4 )构成一维RS码的一个码字。因此，一个弧与一个局部码唯一对应，我们可以互换使用弧和局部码这两个词。两个相邻局部码的重叠区域恰好包含ω = 2ω = 2个符号，因此我们将ω称为重叠宽度。每个未约束的符号都属于两个不同的局部码，我们称之为重叠因子，记为λ 。在本例中，λ = 2λ = 2。在SVD2025中提出的通用 BC 码中， λ值可以更大。其他参数，例如 ω和ρ ，也可以进行适当的修改。SVD2025指出，对于λ=2,3 的BC码，其可恢复的总擦除次数为λρ 。可容忍的总擦除次数与n的比值称为停止率，记为S。下表总结了 BC 码可调参数的符号。
BC代码的参数
| 符号 | 参数的含义 |
|---|---|
| \mu μ | 本地代码数量 |
| λ | 重叠因子（每个符号都是λ局部码的一部分） |
| ρ | 本地代码中冗余符号的数量 |
| ω | 重叠宽度（两个相邻本地码重叠的符号数） |
| [n_0,k_0]=[\lambda\omega+\rho,\lambda\omega] [ n 0 , k 0 ] = [ λ ω + ρ , λ ω ] | 本地代码块长度和维度 |
| [n,k]=[\mu(\omega+\rho),\mu\omega] [ n , k ] = [ μ ( ω + ρ ) , μ ω ] | 全局代码块长度和维度 |
| R=\frac{\omega}{\omega+\rho} R = ω ω + ρ | 速度 |
| S=\frac{\lambda\rho}{\mu(\omega+\rho)} S = λ ρ μ ( ω + ρ ) | 停止率 |
| R_0=\frac{\lambda\omega}{\lambda\omega+\rho} R 0 = λ ω λ ω + ρ | 本地代码率 |
| S_0=\frac{\rho}{\lambda\omega+\rho} S 0 = ρ λ ω + ρ | 本地代码停止率 |
堆叠式 BC 代码
WZ2024详细描述了将一维 RS 码转换为堆叠一维 RS 码的过程。该过程同样适用于 BC 码，因为 (a) BC 码中的每个局部码都是一维 RS 码，(b) 编码可以通过一系列局部一维 RS 编码器完成，每个局部码的评估点都经过精心选择。我们将通过一个示例来描述堆叠 BC 码的编码过程。
编码算法
图 2编码前 blob 0 的结构。
图 3 BC 码中扩展（编码）blob 0 的结构。
我们借助图 2 和图 3 所示的示例来描述编码。这里，重叠因子λ = 2 ，且有μ = 4 个局部码。我们选择堆叠参数D = 64 ，一个blob由8192个有限域符号组成，这些符号排列在k = 128个单元格中。每个 blob 都是 \ mathbb {F}_q^{(D \times k)} = \mathbb{F}_q^{(64 \times 128)} F ( D × k ) q = F ( 64 × 128 ) q的一个元素，而每个单元格属于\mathbb{F}_q^{64} F 64 q 。有限域q的大小要求将在下文中简要描述。首先，我们将 Blob 0 的128个单元格分割成μ = 4个段，每个段包含ω= 32个单元格。这四个段分别索引为 Segment(0,0)、Segment(0,2)、Segment(0,4)和Segment ( 0,6 ) 。在编码过程中，我们将在两个连续的段之间生成并放置包含冗余符号的段（循环地， Segment ( 0,6 )被视为与Segment ( 0,0 )相邻） 。由此得到的8个片段，索引为Segment ( 0,0 )到Segment ( 0,7) ，共同构成扩展（编码）blob。通常，冗余片段将包含ρ个单元格，但在本例中，由于编码率选择为R=0.5，因此ρ = ω= 32 。所以，扩展blob 的每个片段都包含32 个单元格。
图 2 显示了具有128 128 个细胞的 blob 0。为了预测扩展 blob 的结构，与 Blob 0 0关联的细胞的第二个索引保持为0\text{-}31,64\text{-}95,128\text{-}159,192\text{-}223 0 - 31 , 64 - 95 , 128 - 159 , 192 - 223 。扩展 blob 0 中具有上述索引的单元格将保留与 blob 0相同的数据。扩展blob 0中索引为32-63、96-127、160-191、224-255的单元格将在编码期间填充冗余数据。
我们选择一个素域\mathbb{F}_q F q ，使得\mathbb{H}_3 \subset \mathbb{H}_2 \subset \mathbb{H}_1 \subset \mathbb{H}_0 \subset \mathbb{F}_q^* H 3 ⊂ H 2 ⊂ H 1 ⊂ H 0 ⊂ F ∗ q是\mathbb{F}_q^* F ∗ q中满足大小约束的子群链。
可以观察到，与椭圆曲线bls12-381相关的素数q满足2^{32} \mid (q-1) 2 32 ∣ ( q − 1 ) ，因此适合寻找上述子群链。子群树如图 4 所示。接下来，我们将描述如何构造扩展的 blob 0 0 。
该编码由4个局部码组成，索引为0-3 ，编码过程是逐个对每个局部码进行单独编码。图 3 清晰地标示出构成每个局部码的单元格。
前3ω=96 3ω = 96个单元\text{单元}(0,0-95)单元( 0,0-95 )由3ωD = 96 ×64=6144 3ωD = 96 × 64 = 6144个有限域符号组成，形成一个([n_0=96,k_0=64],D=64) ( [ n0 = 96 , k0 = 64 ] , D = 64 )堆叠的一维 RS 码字。利用 blob 0 0 数据中位于 \text{Cells}(0,0-31) 和 \text{Cells } ( 0,64-95 )的符号，可以构造次数至多为2\omega D = 4096 2 ω D = 4096的多项式f_0(X) \in \mathbb{F}_q[X] f 0 ( X ) ∈ F q [ X ] 。扩展blob中的每个单元格都与\mathbb{H}_3 H 3的一个陪集相关联，如下所示：
\begin{aligned}\text{Cells}(0,0-31) &\Leftrightarrow \mathbb{H}_3, \beta^{64}\mathbb{H}_3, \beta^{32}\mathbb{H}_3, \ldots, \beta^{124}\mathbb{H}_3 \\\text{Cells}(0,64-95) &\Leftrightarrow \beta^{2}\mathbb{H}_3, \beta^{66}\mathbb{H}_3, \beta^{34}\mathbb{H}_3, \ldots, \beta^{126}\mathbb{H}_3 \\\text{Cells}(0,32-63) &\Leftrightarrow \beta\mathbb{H}_3, \beta^{65}\mathbb{H}_3, \beta^{33}\mathbb{H}_3, \ldots, \beta^{125}\mathbb{H}_3\end{aligned}细胞（ 0，0-31 ） ⇔ H 3 , β 64 H 3 , β 32 H 3 , … , β 124 H 3细胞（ 0，64-95 ） ⇔ β 2 H 3 , β 66 H 3 , β 34 H 3 , … , β 126 H 3细胞（ 0，32-63 ） ⇔ β H 3 , β 65 H 3 , β 33 H 3 , … , β 125 H 3在96个单元格中的每一个单元格中， f_0(X) f 0 ( X )在相应的陪集上进行求值，求值结果成为该单元格的内容。这产生了一个堆叠的局部码0 0的RS码字。多项式f_0(X) f 0 ( X )的构造方式使得扩展块中单元格( 0,0-31 )和单元格(0,32-63)的求值结果与块中对应的值完全相同。这是通过将数据值作为求值结果，并根据这些数据值插值多项式来实现的。
对局部代码1、2和3重复相同的步骤。相应的多项式分别表示为f_1(X)、f_2(X ) 、 f_3 ( X ) 。用于构建每个f_i ( X )的blob数据（i=1,2,3 ） 、与每个局部代码关联的单元格以及用作评估点的陪集如下所示。
（a）本地代码1 1 : \text{单元格}(0,64\text{-}159)单元格( 0 , 64 - 159 )
\begin{aligned}f_1(X) &\Leftrightarrow \text{Blob 的单元格}(0,64\text{-}95) \text{和} \text{Blob 的单元格}(0,128\text{-}159) \\\text{单元格}(0,64\text{-}95) &\Leftrightarrow \beta^2 \mathbb{H}_3, \beta^{66} \mathbb{H}_3, \beta^{34} \mathbb{H}_3, \ldots, \beta^{126} \mathbb{H}_3 \\\text{单元格}(0,96\text{-}127) &\Leftrightarrow \beta^3 \mathbb{H}_3, \beta^{67} \mathbb{H}_3, \beta^{35} \mathbb{H}_3, \ldots, \beta^{127} \mathbb{H}_3 \\\text{Cells}(0,128\text{-}159) &\Leftrightarrow \mathbb{H}_3, \beta^{64} \mathbb{H}_3, \beta^{32} \mathbb{H}_3, \ldots, \beta^{124} \mathbb{H}_3\end{aligned}f 1 ( X ) ⇔斑点0的细胞( 0 , 64 - 95 )和细胞( 0 , 128 - 159 ) 。细胞（ 0，64-95 ） ⇔ β 2 H 3 , β 66 H 3 , β 34 H 3 , … , β 126 H 3细胞（ 0，96-127 ） ⇔ β 3 H 3 , β 67 H 3 , β 35 H 3 , … , β 127 H 3细胞（ 0，128-159 ） ⇔ H 3 , β 64 H 3 , β 32 H 3 , … , β 124 H 3（b）本地代码2 2 : \text{单元格}(0,128\text{-}223)单元格( 0 , 128 - 223 )
\begin{aligned}f_2(X) &\Leftrightarrow \text{Blob 0 的单元格}(0,64-95) 和 } \text{Blob 0 的单元格}(0,128-159) \\\text{Blob 0 的单元格}(0,128-159) &\Leftrightarrow \mathbb{H}_3, \beta^{64} \mathbb{H}_3, \beta^{32} \mathbb{H}_3, \ldots, \beta^{124} \mathbb{H}_3 的单元格}(0,160-191) &\Leftrightarrow \beta \mathbb{H}_3, \beta^{65} \mathbb{H}_3, \beta^{33} \mathbb{H}_3, \ldots, \beta^{125} \mathbb{H}_3 \\\text{Cells}(0,192\text{-}223) &\Leftrightarrow \beta^2 \mathbb{H}_3, \beta^{66} \mathbb{H}_3, \beta^{34} \mathbb{H}_3, \ldots, \beta^{126} \mathbb{H}_3\end{aligned}f 2 ( X ) ⇔斑点0的细胞( 0 , 64 - 95 )和细胞( 0 , 128 - 159 ) 。细胞（ 0，128-159 ） ⇔ H 3 , β 64 H 3 , β 32 H 3 , … , β 124 H 3细胞（ 0，160-191 ） ⇔ β H 3 , β 65 H 3 , β 33 H 3 , … , β 125 H 3细胞（ 0，192-223 ） ⇔ β 2 H 3 , β 66 H 3 , β 34 H 3 , … , β 126 H 3（c）本地代码3 3 : \text{单元格}(0,192\text{-}255)单元格( 0 , 192 - 255 )和\text{单元格}(0,0\text{-}31)单元格( 0 , 0 - 31 )
\begin{aligned}f_3(X) &\Leftrightarrow \text{Blob 的单元格}(0,64\text{-}95) \text{和} \text{Blob 的单元格}(0,128\text{-}159) \\\text{单元格}(0,192\text{-}223) &\Leftrightarrow \beta^2 \mathbb{H}_3, \beta^{66} \mathbb{H}_3, \beta^{34} \mathbb{H}_3, \ldots, \beta^{126} \mathbb{H}_3 \\\text{单元格}(0,224\text{-}255) &\Leftrightarrow \beta^3 \mathbb{H}_3, \beta^{67} \mathbb{H}_3, \beta^{35} \mathbb{H}_3, \ldots, \beta^{127} \mathbb{H}_3 \\\text{Cells}(0,0\text{-}31) &\Leftrightarrow \mathbb{H}_3, \beta^{64} \mathbb{H}_3, \beta^{32} \mathbb{H}_3, \ldots, \beta^{124} \mathbb{H}_3\end{aligned}f 3 ( X ) ⇔斑点0的细胞( 0 , 64 - 95 )和细胞( 0 , 128 - 159 ) 。细胞（ 0，192-223 ） ⇔ β 2 H 3 , β 66 H 3 , β 34 H 3 , … , β 126 H 3细胞（ 0，224-255 ） ⇔ β 3 H 3 , β 67 H 3 , β 35 H 3 , … , β 127 H 3细胞（ 0，0-31 ） ⇔ H 3 , β 64 H 3 , β 32 H 3 , … , β 124 H 3观察可知，本地代码3 3呈循环式，即将右端单元格中的数据与左端起始单元格中的数据绑定在一起。如图 1.0 所示。值得注意的是，这种编码方式是系统性的，也就是说，blob 中的数据在扩展的 blob 中可以原样访问。
图 2 BC 码的子群树。这里， \beta β是\mathbb{H}_0 H 0的生成元。
接下来介绍使用 FFT 的精确算法。我们用{\bf u} \in \mathbb{F}_q^{64 \times 128} u ∈ F 64 × 128 q表示 blob 0。我们用{\bf u}[\textsf{start}\text{-}\textsf{end}] u [ start - end ]表示单元格\text{Cell}(0,\textsf{start}) Cell ( 0 , start )到\text{Cell}(0,\textsf{end}) Cell ( 0 , end )处的数据。我们定义四个(D\times \omega) = (64 \times 32) ( D × ω ) = ( 64 × 32 )的 blob 数据数组，它们以向量化的形式表示，即长度为2048 × 2048 的向量：
扩展的团块表示为{\bf \hat{x}} \in \mathbb{F}_q^{64 \times 256} ^ x ∈ F 64 × 256 q ，并且我们有
