Block Circulant Codes With Application to Decentralized Systems
Birenjith Sasidharan, Emanuele Viterbo, Son Hoang Dau · IEEE Transactions on Communications · 2025
In this paper, we design a family of [n, k, d] block circulant codes that consist of many [n0≪n, k0≪k, d0d] local codes and that satisfy two properties: (1) the code supports distributed decoding of up to (d− 1) erasures relying only on local codes without a central coordinator, and (2) it is amenable to low complexity verification of code symbols using a cryptographic commitment scheme. These properties make the code ideal for use in protocols that address the data availability problem in blockchain networks. Moreover, the code outperforms the currently used 2D Reed-Solomon (RS) code with a larger relative minimum distance (d/n), as desired in the protocol, for a given rate (k/n) in the high-rate regime. The code is designed in two steps. First, we develop the topology, i.e., the structure of linear dependence relations among code symbols, and define it as the block circulant topologyT[μ,λ,ω](ρ). In this topology, there are μ local codes, each constrained by ρ parity checks. The set of symbols of a local code intersects with another in a uniform pattern, determined by two parameters, namely theoverlap factorλ and theoverlap widthω. Next, we instantiate the topology, i.e., specify the coefficients of the linear dependence relations, to construct the block circulant codesCBC[μ, λ, ω, ρ]. Every local code is a [λω+ρ, λω, ρ+1] generalized RS code. The block circulant code hasn= μ(ρ + ω), k = μω and we show that, under certain conditions,d= λρ + 1. For λ = 2, we prove that d = 2ρ+1 always, and provide an efficient, parallelizable erasure-correcting decoder that fully recovers the codeword when there are ≤ 2ρ erasures. The decoder uses a novel decoding mechanism that iteratively recovers erasures from either local codes or pairs of them.