Acknowledgement: This is a joint work with Emanuele Viterbo and Dankrad Feist and is supported by ESP Grant FY24-1745 titled “Improvements to 2D Reed-Solomon Codes in DAS”.
In this post, we describe how block circulant (BC) codes can serve as an alternative to one-dimensional (1D) and two-dimensional (2D) Reed–Solomon (RS) codes in the Ethereum PeerDAS protocol. We present efficient encoding and reconstruction
algorithms for BC codes, developed within the same implementation framework as
the respective 1D RS algorithms. The proposed encoding algorithm also permits a
graceful integration of KZG commitment scheme. We evaluate and compare
the performance of BC codes in terms of code rate, stopping rate, and the size of the local codes they contain, against both 1D and 2D RS codes. A longer version of this post is available in SVF2026.
Block Circulant Codes
Block circulant (BC) codes are introduced in SVD2025 as a viable alternative to both 1D (currently used) and 2D RS codes (expected to be incorporated later) in PeerDAS. Similar to the 2D RS code, the BC code contains multiple local codes, and each local code can be designed as a [(n_0,k_0),D][(n0,k0),D] stacked 1D RS code. By stacked 1D RS code, we mean a [n_0D ,k_0D][n0D,k0D] RS code whose codewords are stacked in D horizontal rows each row of length n_0n0, and k_0k0 columns representing information symbols). Therefore, it is compatible with the KZG scheme. It turns out that BC codes achieve certain operating regimes of rate, stopping rate and local code size that are not feasible with either a 1D or a 2D RS code.
In a 2D RS code, the symbols are arranged in a two-dimensional square grid and there are linear constraints binding symbols belonging to every row or column. In the case of a BC code, symbols are arranged on a circle and the circle is divided into multiple overlapping arcs. Every arc has two neighbouring overlapping arcs, one on the left and the other on the right assuming a clockwise direction. Symbols belong to every arc are subject to a set of linear constraints. We present a more concrete description in the next subsection.
A Description of the BC Code
Figure 1: Illustration of the block circulant code. In this example, information symbols in the green background color are combined with parity symbols in the pink background color region resulting in the final arrangement. The groupings of symbols within the closed curves indicate local codes.
Consider the example consisting of n=16n=16 symbols as given in Figure 1. There are \mu=4μ=4 arcs (two of them marked by closed curves) each containing n_0=6n0=6 symbols, equally spaced on the circle. There are a total of k=8k=8 unconstrained symbols denoted as d_1, \ldots, d_8d1,…,d8. Each local code contains k_0=4k0=4 unconstrained symbols. The remaining symbols are generated subject to certain linear constraints. In every arc, \rho=n_0-k_0=2ρ=n0−k0=2 redundant symbols are added in such a manner that the local code corresponding to the arc becomes a 1D RS code. For example, the vector of symbols (d_1,d_2,p_{11},p_{12},d_3,d_4)(d1,d2,p11,p12,d3,d4) corresponding to a single arc forms a codeword of an 1D RS code. Thus an arc is uniquely identified with a local code, and we may write arc and local code interchangeably. There lies exactly \omega=2ω=2 symbols at the overlapping region of two adjacent local codes and therefore we call \omegaω as the overlap width. Every unconstrained symbol is part of two distinct local codes and we call it the overlapping factor, denoted by \lambdaλ. In the present arrangement, we have \lambda=2λ=2. In the general BC code presented in SVD2025, arrangements with higher values of \lambdaλ are possible. Other parameters like \omegaω and \rhoρ can also be modified suitably. It is shown in SVD2025 that a BC code with \lambda=2,3λ=2,3, the total number of erasures that can recovered by the BC code has been shown to be \lambda\rhoλρ. The ratio of total number of tolerable erasures to nn is called the stopping rate and is denoted by SS. We summarize the notations used for adjustable parameters of the BC code in the table below.
Parameters of BC code
| Notation | Meaning of the parameter(s) |
|---|---|
| \muμ | Number of local codes |
| \lambdaλ | Overlap factor (Every symbol is part of \lambdaλ local codes) |
| \rhoρ | Number of redundant symbols in a local code |
| \omegaω | Overlap width (Number of symbols two adjacent local codes overlap on) |
| [n_0,k_0]=[\lambda\omega+\rho,\lambda\omega][n0,k0]=[λω+ρ,λω] | Local code blocklength and dimension |
| [n,k]=[\mu(\omega+\rho),\mu\omega][n,k]=[μ(ω+ρ),μω] | Global code blocklength and dimension |
| R=\frac{\omega}{\omega+\rho}R=ωω+ρ | Rate |
| S=\frac{\lambda\rho}{\mu(\omega+\rho)}S=λρμ(ω+ρ) | Stopping rate |
| R_0=\frac{\lambda\omega}{\lambda\omega+\rho}R0=λωλω+ρ | Local code rate |
| S_0=\frac{\rho}{\lambda\omega+\rho}S0=ρλω+ρ | Local code stopping rate |
Stacked BC code
The procedure to convert an 1D RS code to stacked 1D RS code is described in detail in WZ2024. The exact procedure is applicable to the BC code as well because (a) each of the local code in the BC code is an 1D RS code, (b) the encoding can be performed by a series of local 1D RS encoders with carefully chosen set of evaluation points for each of the local code. We will describe the encoding procedure for a stacked BC code with the help of an example.
Encoding Algorithm
Figure 2 Structure of blob 0 before encoding.
Figure 3 Structure of extended (encoded) blob 0 in BC code.
We describe the encoding with the help of an example illustrated in Figure 2 and 3. Here, overlap factor \lambda=2λ=2 and there are \mu=4μ=4 local codes. We pick the stacking parameter D=64D=64 and a blob consists of 81928192 finite field symbols arranged in k=128k=128 cells. Each blob is an element of \mathbb{F}_q^{(D \times k)}=\mathbb{F}_q^{(64 \times 128)}F(D×k)q=F(64×128)q, whereas each cell belongs to \mathbb{F}_q^{64}F64q. The requirement on size of finite field qq will be shortly described. First we partition 128128 cells of Blob 0 into \mu=4μ=4 segments each containing \omega=32ω=32 cells. These four segments are indexed as \text{Segment}(0,0), \text{Segment}(0,2), \text{Segment}(0,4)Segment(0,0),Segment(0,2),Segment(0,4), and \text{Segment}(0,6)Segment(0,6). During the encoding procedure, we shall generate and place segments containing redundant symbols in between two successive (\text{Segment}(0,6)Segment(0,6) is considered to be adjacent to \text{Segment}(0,0)Segment(0,0), viewing them cyclically) segments. The resultant 88 segments indexed as \text{Segment}(0,0)Segment(0,0) to \text{Segment}(0,7)Segment(0,7) jointly form the extended (encoded) blob. In general, the redundant segments will have \rhoρ cells, but in this example, we have \rho=\omega=32ρ=ω=32 since the rate is chosen to be R=0.5R=0.5. Therefore, every segment of the extended blob consists of 3232 cells.
In Figure 2, the blob 0 with 128128 cells are shown. Anticipating the structure of extended blob, the second index of cells associated to Blob 00 are kept as 0\text{-}31,64\text{-}95,128\text{-}159,192\text{-}2230-31,64-95,128-159,192-223. Cells within extended blob 0 with the above indices are retained with the same data as blob 0. The cells indexed as 32\text{-}63,96\text{-}127,160\text{-}191,224\text{-}25532-63,96-127,160-191,224-255 in the extended blob 00 will be populated with redundant data during encoding.
We choose a prime field \mathbb{F}_qFq such that \mathbb{H}_3 \subset \mathbb{H}_2 \subset \mathbb{H}_1 \subset \mathbb{H}_0 \subset \mathbb{F}_q^*H3⊂H2⊂H1⊂H0⊂F∗q is a chain of subgroups in \mathbb{F}_q^*F∗q satisfying size constraints
It may be observed that the prime number qq associated to the elliptic curve bls12-381 satisfies that 2^{32} \mid (q-1)232∣(q−1) and is therefore suitable to find the above subgroup chain. The tree of subgroups is given in Figure 4. Next, we describe how the extended blob 00 is constructed.
The code consists of 44 local codes indexed as 0\text{-}30-3, and encoding is carried out by separately encoding each of the local code one by one. In Figure 3, cells forming each of the local codes are clearly indicated.
The first 3\omega=963ω=96 cells \text{Cells}(0,0\text{-}95)Cells(0,0-95) comprising of 3\omega D = 96 \times 64=61443ωD=96×64=6144 finite field symbols form a ([n_0=96,k_0=64],D=64)([n0=96,k0=64],D=64) stacked 1D RS codeword. A polynomial f_0(X) \in \mathbb{F}_q[X]f0(X)∈Fq[X] of degree at most 2\omega D = 40962ωD=4096 may be formed using symbols in blob 00 data at \text{Cells}(0,0\text{-}31)Cells(0,0-31) and \text{Cells}(0,64\text{-}95)Cells(0,64-95). Each cell in the extended blob is associated to a coset of \mathbb{H}_3H3 as follows:
\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}Cells(0,0-31)⇔H3,β64H3,β32H3,…,β124H3Cells(0,64-95)⇔β2H3,β66H3,β34H3,…,β126H3Cells(0,32-63)⇔βH3,β65H3,β33H3,…,β125H3In each of 9696 cells, f_0(X)f0(X) is evaluated at the corresponding coset and the evaluations become the contents of that cell. This yields a stacked RS codeword of the Local code 00. The polynomial f_0(X)f0(X) is constructed in such a manner that the evaluations at \text{Cells}(0,0\text{-}31)Cells(0,0-31) and \text{Cells}(0,32\text{-}63)Cells(0,32-63) in the extended blob are exactly same as the corresponding values in the blob. This is achieved by taking the data values as evaluations and interpolating a polynomial from these data values.
The same procedure is repeated for Local code 1, 21,2 and 33. The corresponding polynomials are denoted by f_1(X), f_2(X)f1(X),f2(X) and f_3(X)f3(X). The blob data used to construct each f_i(X),i=1,2,3fi(X),i=1,2,3, cells associated to each local code, and the cosets used as evaluation points are listed below.
(a) Local code 11: \text{Cells}(0,64\text{-}159)Cells(0,64-159)
\begin{aligned}f_1(X) &\Leftrightarrow \text{Cells}(0,64\text{-}95) \text{ and } \text{Cells}(0,128\text{-}159) \text{ of blob } 0 \\\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}f1(X)⇔Cells(0,64-95) and Cells(0,128-159) of blob 0Cells(0,64-95)⇔β2H3,β66H3,β34H3,…,β126H3Cells(0,96-127)⇔β3H3,β67H3,β35H3,…,β127H3Cells(0,128-159)⇔H3,β64H3,β32H3,…,β124H3(b) Local code 22: \text{Cells}(0,128\text{-}223)Cells(0,128-223)
\begin{aligned}f_2(X) &\Leftrightarrow \text{Cells}(0,64\text{-}95) \text{ and } \text{Cells}(0,128\text{-}159) \text{ of blob } 0 \\\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}f2(X)⇔Cells(0,64-95) and Cells(0,128-159) of blob 0Cells(0,128-159)⇔H3,β64H3,β32H3,…,β124H3Cells(0,160-191)⇔βH3,β65H3,β33H3,…,β125H3Cells(0,192-223)⇔β2H3,β66H3,β34H3,…,β126H3(c) Local code 33: \text{Cells}(0,192\text{-}255)Cells(0,192-255) and \text{Cells}(0,0\text{-}31)Cells(0,0-31)
\begin{aligned}f_3(X) &\Leftrightarrow \text{Cells}(0,64\text{-}95) \text{ and } \text{Cells}(0,128\text{-}159) \text{ of blob } 0 \\\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}f3(X)⇔Cells(0,64-95) and Cells(0,128-159) of blob 0Cells(0,192-223)⇔β2H3,β66H3,β34H3,…,β126H3Cells(0,224-255)⇔β3H3,β67H3,β35H3,…,β127H3Cells(0,0-31)⇔H3,β64H3,β32H3,…,β124H3Observe that local code 33 wraps around cyclically in the sense that it binds together the data in cells in the right end to the ones on the starting left. This is indicated in Fig.\ref{fig:bcexblob}. We remark that the encoding is systematic i.e., data in the blob is available as such in the extended blob.
Figure 2 Tree of subgroups for BC code. Here, \betaβ is a generator of \mathbb{H}_0H0.
The exact algorithm using FFT is presented next. Let us use {\bf u} \in \mathbb{F}_q^{64 \times 128}u∈F64×128q to denote blob 0. We use {\bf u}[\textsf{start}\text{-}\textsf{end}]u[start-end] to denote the data at the cells \text{Cell}(0,\textsf{start})Cell(0,start) to \text{Cell}(0,\textsf{end})Cell(0,end). Let us define four (D\times \omega) = (64 \times 32)(D×ω)=(64×32) blob data arrays in their vectorized form, i.e., as 20482048 long vectors:
The extended blob is denoted by {\bf \hat{x}} \in \mathbb{F}_q^{64 \times 256}^x∈F64×256q and we have
