Erasure-coded sampling for data recoverability in Nakamoto consensus

Abstract

Blockchain systems provide a decentralized and fault-tolerant infrastructure for maintaining a shared transaction ledger without relying on a trusted central authority. Nakamoto consensus, in particular, enables open participation and robust agreement in permissionless environments. However, these benefits typically rely on broad data replication, which requires participants to download and propagate large volumes of transaction data and can therefore impose substantial communication overhead. This thesis proposes and analyzes a bandwidth-efficient data recoverability protocol for Nakamoto consensus using erasure-coded sampling. Instead of requiring every participant to download a full transaction batch, the protocol allows an operator to encode a large transaction batch, called a mega transaction, into coded chunks and publish a compact cryptographic commitment on chain. Participants verify sampled coded chunks and cast PoW-bound votes on their validity. The Nakamoto consensus layer then determines whether the mega transaction should be accepted as recoverable, so that it can be reconstructed and verified later if a dispute arises. The main focus of this thesis is to formalize the recoverability failure event: the event that the protocol incorrectly accepts a mega transaction as recoverable even though honest participants do not collectively hold enough valid coded chunks for reconstruction. We derive conservative analytical bounds on the probability of this event and use these bounds to formulate a utility-based parameter-selection problem under a target security requirement. Monte Carlo estimates validate the analytical bounds, and numerical results illustrate the tradeoff between recovery communication overhead and confirmation latency.