Block Circulant Codes with Application to Decentralized Systems

In this paper, we design a family of [n, k, d] block circulant codes that consist of many [n₀ ≪ n, k₀ ≪ k, d₀ < d] 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 topology T[_μ,λ,ω](ρ). 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 the overlap factor λ and the overlap width ω. Next, we instantiate the topology, i.e., specify the coefficients of the linear dependence relations, to construct the block circulant codes C_BC[μ, λ, ω, ρ]. Every local code is a [λω+ρ, λω, ρ+1] generalized RS code. The block circulant code has n = μ(ρ + ω), 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.