Back to search

University of British Columbia

Erasure-coded sampling for data recoverability in Nakamoto consensus

Abstract

dc:description

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.

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

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Shi, Tianyu. Erasure-coded sampling for data recoverability in Nakamoto consensus. master's thesis, University of British Columbia, 2026. http://hdl.handle.net/2429/95128