University of British Columbia
Erasure-coded sampling for data recoverability in Nakamoto consensus
Abstract
dc:descriptionBlockchain 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.
Degree
thesis:*- Name thesis:degree_name
- Master of Applied Science - MASc
- Level thesis:degree_level
- master's
- Discipline thesis:degree_discipline
- Electrical Engineering
- Grantor dc:publisher
- University of British Columbia
- Year dc:date
- 2026
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Shi, Tianyu
- Contributors dc:contributor
-
- Feng, Chen
Rights
dc:rights- Statement dc:rights
-
- Attribution-NonCommercial-NoDerivatives 4.0 International
- Language dc:language
- eng
Identifiers
dc:identifier.*- Handle dc:identifier
- http://hdl.handle.net/2429/95128