New Codes that Improve upon the 2D Reed-Solomon Codes in Data Availability Sampling Protocols

We have designed a new family of block circulant (BC) codes stitching together many copies of generalized Reed-Solomon (GRS) code as its component codes. The BC code is equipped enough to replace 2D Reed-Solomon (2D RS) codes used in existing protocols to ensure data availability (DA) in Ethereum. Since every component code is a Reed-Solomon code, KZG commitment scheme works for the BC code as well. Since the blocklength of the component codes are much smaller than blocklength of the whole code, it supports distributed reconstruction and encoding without requiring any super-node. We have also designed a low-complexity decoding of erasures for the BC code that requires only RS decoder as a major subroutine. The BC code offers the following advantages in comparison to 2D RS code:
1) Reduced number of samples to be queried per light node for a fixed low storage overhead of the code.
2) Reduced number of KZG digests to be computed.

For example, let us compare a [1444,1024,49] 2D RS code with a [1416,1024,65] shortened BC code both having a low storage overhead of about 1.4x. To achieve the same target performance in tackling the DA problem in a network of 1000 light nodes, the 2D RS code would require querying 72 samples per light node, while the BC code requires only 53 samples. Furthermore, the number of local codes in the BC code is 12 instead of 76 in the 2D RS code, yielding a proportionate reduction in the complexity of realizing the KZG commitment scheme. In this project, we plan to assess the performance of the BC code via a prototype implementation.