數據可用性抽樣中 2D 里德-所羅門碼的替代方案

致謝：本研究由 Emanuele Viterbo、Dankrad Feist 與本人共同完成，並獲得名為「DAS 中 2D Reed-Solomon 碼之改進」（編號 ESP Grant FY24-1745）的資助。

在本篇文章中，我們將探討區塊循環（Block Circulant, BC）碼如何作為以太坊 PeerDAS 協議中一維（1D）和二維（2D）Reed-Solomon（RS）碼的替代方案。我們提出了 BC 碼的高效編碼與重建算法，這些算法是在與相應 1D RS 算法相同的實作框架下開發的。所提出的編碼算法還允許與 KZG 承諾方案進行良好整合。我們根據碼率（code rate）、停止率（stopping rate）及其包含的局部碼（local codes）大小，對 BC 碼的性能進行了評估，並與 1D 和 2D RS 碼進行了比較。本篇文章的完整版本可參閱 SVF2026。

區塊循環碼 (Block Circulant Codes)

區塊循環（BC）碼在 SVD2025 中被提出，作為 PeerDAS 中 1D RS 碼（目前使用）和 2D RS 碼（預期未來引入）的可行替代方案。與 2D RS 碼類似，BC 碼包含多個局部碼，每個局部碼可以設計為一個 [(n_0,k_0),D] 堆疊式 1D RS 碼（所謂堆疊式 1D RS 碼，是指一個 [n_0D, k_0D] RS 碼，其碼字堆疊在 D 個水平行中，每行長度為 n_0，且有 k_0 列代表信息符號）。因此，它與 KZG 方案相容。事實證明，BC 碼能達到某些碼率、停止率和局部碼大小的運行區間，而這些區間是 1D 或 2D RS 碼都無法實現的。

在 2D RS 碼中，符號排列在二維方格矩陣中，且有線性約束綁定屬於每一行或每一列的符號。在 BC 碼的情況下，符號排列在一個圓圈上，且圓圈被分成多個重疊的弧（arcs）。假設為順時針方向，每個弧都有兩個相鄰的重疊弧，一個在左側，另一個在右側。屬於每個弧的符號都受一組線性約束的限制。我們將在下一小節中提供更具體的描述。

BC 碼的描述

圖 1： 區塊循環碼示意圖。在此範例中，綠色背景的信息符號與粉紅色背景區域的校驗符號相結合，形成最終排列。封閉曲線內的符號分組表示局部碼。

考慮圖 1 所示由 n=16 個符號組成的範例。共有 \mu=4 個弧（其中兩個由封閉曲線標出），每個弧包含 n_0=6 個符號，在圓圈上等距分佈。共有 k=8 個非約束符號，表示為 d_1, \ldots, d_8。每個局部碼包含 k_0=4 個非約束符號。其餘符號是根據特定的線性約束生成的。在每個弧中，添加了 \rho=n_0-k_0=2 個冗餘符號，使得對應該弧的局部碼成為一個 1D RS 碼。例如，對應單個弧的符號向量 (d_1,d_2,p_{11},p_{12},d_3,d_4) 構成了一個 1D RS 碼的碼字。因此，一個弧與一個局部碼是唯一對應的，我們可以交替使用「弧」和「局部碼」這兩個詞。在兩個相鄰局部碼的重疊區域中正好存在 \omega=2 個符號，因此我們稱 \omega 為重疊寬度（overlap width）。每個非約束符號都是兩個不同局部碼的一部分，我們稱之為重疊因子（overlapping factor），記作 \lambda。在目前的安排中，我們有 \lambda=2。在 SVD2025 提出的通用 BC 碼中，可以使用更高 \lambda 值的安排。其他參數如 \omega 和 \rho 也可以進行適當修改。SVD2025 表明，對於 \lambda=2,3 的 BC 碼，其可恢復的擦除（erasures）總數已被證明為 \lambda\rho。可容忍擦除總數與 n 的比率稱為停止率，記作 S。我們在下表中總結了用於 BC 碼可調參數的符號。

BC 碼參數表

符號	參數含義
\mu	局部碼數量
\lambda	重疊因子（每個符號屬於 \lambda 個局部碼）
\rho	局部碼中的冗餘符號數
\omega	重疊寬度（兩個相鄰局部碼重疊的符號數）
[n_0,k_0]=[\lambda\omega+\rho,\lambda\omega]	局部碼的碼長與維度
[n,k]=[\mu(\omega+\rho),\mu\omega]	全域碼的碼長與維度
R=\frac{\omega}{\omega+\rho}	碼率
S=\frac{\lambda\rho}{\mu(\omega+\rho)}	停止率
R_0=\frac{\lambda\omega}{\lambda\omega+\rho}	局部碼碼率
S_0=\frac{\rho}{\lambda\omega+\rho}	局部碼停止率

堆疊式 BC 碼 (Stacked BC code)

將 1D RS 碼轉換為堆疊式 1D RS 碼的程序在 WZ2024 中有詳細描述。該程序同樣適用於 BC 碼，因為 (a) BC 碼中的每個局部碼都是 1D RS 碼，(b) 編碼可以通過一系列局部 1D RS 編碼器完成，並為每個局部碼精心選擇一組評估點。我們將藉助一個範例來描述 堆疊式 BC 碼 的編碼程序。

編碼算法

圖 2 編碼前 Blob 0 的結構。

圖 3 BC 碼中擴展（編碼後）Blob 0 的結構。

我們藉助圖 2 和圖 3 所示的範例來描述編碼過程。這裡，重疊因子 \lambda=2，共有 \mu=4 個局部碼。我們選擇堆疊參數 D=64，一個 Blob 由 8192 個有限域符號組成，排列在 k=128 個單元（cells）中。每個 Blob 是 \mathbb{F}_q^{(D \times k)}=\mathbb{F}_q^{(64 \times 128)} 的元素，而每個單元屬於 \mathbb{F}_q^{64}。對有限域大小 q 的要求稍後說明。首先，我們將 Blob 0 的 128 個單元劃分為 \mu=4 個段（segments），每段包含 \omega=32 個單元。這四個段的索引為 \text{Segment}(0,0)、\text{Segment}(0,2)、\text{Segment}(0,4) 和 \text{Segment}(0,6)。在編碼過程中，我們將生成包含冗餘符號的段，並將其放置在兩個連續段之間（考慮循環性，\text{Segment}(0,6) 被視為與 \text{Segment}(0,0) 相鄰）。產生的 8 個段（索引從 \text{Segment}(0,0) 到 \text{Segment}(0,7)）共同構成擴展（編碼後）的 Blob。通常，冗餘段將有 \rho 個單元，但在本例中，由於碼率選擇為 R=0.5，我們有 \rho=\omega=32。因此，擴展 Blob 的每個段都由 32 個單元組成。

圖 2 顯示了具有 128 個單元的 Blob 0。預見到擴展 Blob 的結構，與 Blob 0 關聯的單元第二個索引保持為 0\text{-}31, 64\text{-}95, 128\text{-}159, 192\text{-}223。擴展 Blob 0 中具有上述索引的單元保留與 Blob 0 相同的數據。擴展 Blob 0 中索引為 32\text{-}63, 96\text{-}127, 160\text{-}191, 224\text{-}255 的單元將在編碼期間填充冗餘數據。

我們選擇一個質數域 \mathbb{F}_q，使得 \mathbb{H}_3 \subset \mathbb{H}_2 \subset \mathbb{H}_1 \subset \mathbb{H}_0 \subset \mathbb{F}_q^* 是 \mathbb{F}_q^* 中的一個子群鏈，滿足大小約束：

\begin{aligned}
|\mathbb{H}_3| &= D = 64,\
|\mathbb{H}_2| &= \omega D = 2048,\
|\mathbb{H}_1| &= 2\omega D = 4096,\
|\mathbb{H}_0| &= 2\lambda\omega D = 8192 .
\end{aligned}

可以觀察到，與橢圓曲線 bls12-381 相關聯的質數 q 滿足 2^{32} \mid (q-1)，因此適合尋找上述子群鏈。子群樹如圖 4 所示。接下來，我們描述如何構建擴展 Blob 0。

• 該代碼由 4 個局部碼（索引為 0\text{-}3）組成，編碼是通過逐一分別對每個局部碼進行編碼來完成的。在圖 3 中，清楚地標示了構成每個局部碼的單元。
• 前 3\omega=96 個單元 \text{Cells}(0,0\text{-}95) 由 3\omega D = 96 \times 64=6144 個有限域符號組成，構成一個 ([n_0=96,k_0=64],D=64) 堆疊式 1D RS 碼字。可以使用 Blob 0 在 \text{Cells}(0,0\text{-}31) 和 \text{Cells}(0,64\text{-}95) 處的數據符號形成一個次數最多為 2\omega D = 4096 的多項式 f_0(X) \in \mathbb{F}_q[X]。擴展 Blob 中的每個單元都與 \mathbb{H}_3 的陪集（coset）關聯如下：

\begin{aligned}
\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 \
\text{Cells}(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{Cells}(0,32\text{-}63) &\Leftrightarrow \beta\mathbb{H}_3, \beta^{65}\mathbb{H}_3, \beta^{33}\mathbb{H}_3, \ldots, \beta^{125}\mathbb{H}_3
\end{aligned}

在 96 個單元的每一個中，f_0(X) 在相應的陪集上進行求值，求值結果成為該單元的內容。這產生了局部碼 0 的堆疊式 RS 碼字。多項式 f_0(X) 的構造方式使得擴展 Blob 中 \text{Cells}(0,0\text{-}31) 和 \text{Cells}(0,32\text{-}63) 的求值結果與 Blob 中的相應值完全相同。這是通過將數據值作為求值結果並從這些數據值插值出多項式來實現的。

• 對局部碼 1、2 和 3 重複相同的程序。相應的多項式表示為 f_1(X)、f_2(X) 和 f_3(X)。用於構建每個 f_i(X) (i=1,2,3) 的 Blob 數據、與每個局部碼關聯的單元以及用作評估點的陪集列於下方。

(a) 局部碼 1: \text{Cells}(0,64\text{-}159)
\begin{aligned}
f_1(X) &\Leftrightarrow \text{Blob 0 的 Cells}(0,64\text{-}95) \text{ 和 Cells}(0,128\text{-}159) \
\text{Cells}(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{Cells}(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}

(b) 局部碼 2: \text{Cells}(0,128\text{-}223)
\begin{aligned}
f_2(X) &\Leftrightarrow \text{Blob 0 的 Cells}(0,64\text{-}95) \text{ 和 Cells}(0,128\text{-}159) \
\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 \
\text{Cells}(0,160\text{-}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}

(c) 局部碼 3: \text{Cells}(0,192\text{-}255) 和 \text{Cells}(0,0\text{-}31)
\begin{aligned}
f_3(X) &\Leftrightarrow \text{Blob 0 的 Cells}(0,64\text{-}95) \text{ 和 Cells}(0,128\text{-}159) \
\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 \
\text{Cells}(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}

觀察到局部碼 3 以循環方式繞回，即它將右端的單元數據與起始左端的單元數據綁定在一起。這在圖 3 中有所指示。我們注意到編碼是系統性的，即 Blob 中的數據在擴展 Blob 中原樣可用。

圖 4 BC 碼的子群樹。這裡，\beta 是 \mathbb{H}_0 的生成元。

接下來介紹使用 FFT 的具體算法。讓我們用 {\bf u} \in \mathbb{F}_q^{64 \times 128} 表示 Blob 0。我們使用 {\bf u}[\textsf{start}\text{-}\textsf{end}] 表示從 \text{Cell}(0,\textsf{start}) 到 \text{Cell}(0,\textsf{end}) 的數據。讓我們定義四個 (D\times \omega) = (64 \times 32) 的 Blob 數據數組，以其向量化形式表示，即作為 2048 長度的向量：

\begin{aligned}
\mathbf{u}_0 &= \mathbf{u}[0\text{-}31], \
\mathbf{u}_2 &= \mathbf{u}[64\text{-}95], \
\mathbf{u}_4 &= \mathbf{u}[128\text{-}159], \
\mathbf{u}_6 &= \mathbf{u}[192\text{-}223].
\end{aligned}

擴展 Blob 表示為 {\bf \hat{x}} \in \mathbb{F}_q^{64 \times 256}，我們有向量化形式的：

\hat{\mathbf{x}}_i = \hat{\mathbf{x}}[32i\text{-}(32i+31)], \quad i=0,1,\ldots,7.

我們使用 || 來串聯兩個向量以形成更長的向量。算法如下：

對於 i=0,1,2,3，執行：

• 如果 i 是偶數，設置 \mathbb{G} = \beta \mathbb{H}_2, j=2i, \ell = (2i+2)\bmod 8。
• 如果 i 是奇數，設置 \mathbb{G} = \beta^3 \mathbb{H}_2, j=(2i+2)\bmod 8, \ell = 2i。
• 設置 ((\hat{\mathbf{x}}j | \hat{\mathbf{x}}\ell)(\alpha), \alpha \in \mathbb{H}_1) = \mathbf{u}j | \mathbf{u}\ell。
• 計算 \mathbf{x}j | \mathbf{x}\ell = \mathrm{IFFT}_{\mathbb{H}_1}(\hat{\mathbf{x}}j | \hat{\mathbf{x}}\ell)。
• 計算 \hat{\mathbf{x}}{2i+1} = \mathrm{FFT}{\beta\mathbb{H}_1}(\mathbf{x}j | \mathbf{x}\ell, \mathbb{G})。

\hat{\mathbf{x}}_{2i+1} 的條目佔據符合每個單元陪集分配的單元。

上述 BC 編碼器需要四次在 \mathbb{H}_1 上的 IFFT 計算和四次在 \beta\mathbb{H}_1 上受限於 \mathbb{H}_2 陪集的受限 FFT 計算。再次注意 |\mathbb{H}_1|=k_0D 且 |\mathbb{H}_2|=k_0D/2。所謂受限 FFT，是指在一個群（陪集）上計算 FFT，但僅限於屬於子群（子陪集）的一組值。SVF2026 提供了一種計算受限 FFT/IFFT 的高效方法。

重建算法

SVF2026 中描述了一種高效的重建算法。

堆疊式 BC 碼的 KZG 承諾

在堆疊式 BC 碼的每一列中，我們都有在子群或子群陪集上的求值。因此，適用於 1D RS 碼的 KZG 多重證明 WZ2024 在這裡也同樣適用。為每個局部 RS 碼提供 KZG 承諾就足夠了，其碼長遠小於整個 BC 碼的碼長。通過這種方式，我們降低了 KZG 相關計算的複雜度。

與 1D 和 2D RS 碼的比較

考慮參數為 \mu, \omega 和 \rho 的 BC 碼。在整個討論中，我們固定重疊因子 \lambda=2。回想一下，\mu 代表局部碼的數量，\rho D 代表每個局部碼中的冗餘符號數，而 \omega D 代表兩個相鄰局部碼相交的符號數。BC 碼的碼率 R、停止率 S 和局部碼大小 L 由以下公式給出：

\begin{aligned}
L &= (2\omega+\rho)D \
R &= \frac{\mu \omega D}{\mu(\omega+\rho)D}
= \frac{\omega}{\omega + \rho} \
S &= \frac{2\rho D}{\mu(\omega+\rho)D}
= \frac{2\rho}{\mu(\omega + \rho)}
= \frac{2(1-R)}{\mu}.
\end{aligned}

圖 3 顯示了不同 \mu 值的 BC 碼在 S 和 R 之間的權衡。圖中還包含了 1D 和 2D RS 碼的權衡。因此，BC 碼實現了介於 1D 和 2D RS 碼之間的區域。

圖 3 1D RS、2D RS 和不同 \mu=2,4,6（從左至右）值的 BC 碼在停止率 (S) 和碼率 (R) 之間的權衡。

在擴展 Blob 內可以重建的缺失符號絕對最大數量 E 由下式給出：

E=nDS

其中 nD 是擴展 Blob 中存在的符號總數，S 是停止率。我們考慮三種不同的 Blob 大小：1 MB、8 MB 和 32 MB，每一種都對應於 Blob 內一定數量的有限域符號 kD。映射取決於有限域 \mathbb{F}_q 的選擇，因為 \mathbb{F}_q 中的一個符號使用 \lceil\log_2(q)\rceil 位元表示。例如，當有限域選擇為與 \texttt{bls12-381} 相關聯的域時，1 MB 的 Blob 與 2^{15} 個有限域符號相關聯，其中 \lceil\log_2(q)\rceil = 32\times 2^8 = 32 字節。對於各種文件大小，我們在圖 4 和圖 5 中繪製了 E 與 R 的關係圖。在圖 4 中，將 \mu=4 的 BC 碼與 1D 和 2D RS 碼進行比較，而在圖 5 中，選擇 \mu=6 的 BC 碼進行比較。BC 碼遜於 1D RS 碼並不令人意外，因為 1D RS 碼在給定碼率下對於 E 是最優的。有趣的是，在相同的文件大小和碼率下，\mu=4 和 \mu=6 的 BC 碼性能都顯著優於相應的 2D RS 碼。

圖 4 1D RS、2D RS 和 \mu=4 的 BC 碼在可容忍擦除數 (E) 和碼率 (R) 之間的權衡，文件大小分別為 F=1 MB, 8 MB 和 32 MB（從左至右）。

圖 5 1D RS、2D RS 和 \mu=6 的 BC 碼在可容忍擦除數 (E) 和碼率 (R) 之間的權衡，文件大小分別為 F=1 MB, 8 MB 和 32 MB（從左至右）。

在圖 6 中，比較了 BC、1DRS 和 2DRS 碼中的局部碼大小。由於 1D RS 碼不包含任何局部碼，因此整個代碼被視為其局部碼。可以觀察到，2D RS 碼在局部碼的絕對大小方面顯著優於 BC 碼。總之，與 2D RS 碼相比，BC 碼在增加可容忍擦除數量方面具有顯著優勢。然而，BC 碼的局部碼大小與 2D RS 碼相比非常大。無論如何，BC 碼提供了一種不同於 1DRS 和 2DRS 碼的運行區間，並為設計在 1D 和 2D RS 碼中間區間運行的代碼開闢了可能性。

圖 6 1D RS、2D RS 和 \mu=6 的 BC 碼在局部碼大小 (L) 和碼率 (R) 之間的權衡，文件大小分別為 F=1 MB, 8 MB 和 32 MB（從左至右）。對於 1D RS，沒有局部碼，因此我們取 L=nD。

參考文獻

[SVD2025] Theory of Block Circulant Codes

[SVF2026] Block Circulant Codes for PeerDAS

[WZ2024] A Documentation of Ethereum’s PeerDAS

        1 則貼文 - 1 位參與者

        [閱讀完整主題](https://ethresear.ch/t/alternatives-to-2d-reed-solomon-codes-in-das/24639)