Thesis Defence: Erasure-Coded Sampling for Data Recoverability in Nakamoto Consensus

Tianyu Shi, supervised by Dr. Chen Feng, will defend their thesis titled “Erasure-Coded Sampling for Data Recoverability in Nakamoto Consensus” in partial fulfillment of the requirements for the degree of Master of Applied Science in Electrical Engineering.

An abstract for Tianyu Shi’s thesis is included below.

Defences are open to all members of the campus community as well as the general public. Please email chen.feng@ubc.ca to receive the Zoom link for this defence.

Abstract

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 simulations validate the analytical bounds, and numerical results illustrate the tradeoff between recovery communication overhead and confirmation latency.