致謝：這是與 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 ，並且我們有
