Patterned Erasure Correcting Codes for improved Storage and Communication Efficiency in Blockchain Systems
- Author(s): Mitra, Debarnab
- Advisor(s): Dolecek, Lara
- et al.
Blockchains are decentralized ledgers which store the sequence of transactions in the form of a hash chain. However, this decentralization requires each node in the network to store the entire blockchain, an operation which incurs significant storage costs. Erasure coding and network coding techniques were previously introduced to mitigate this storage burden. In this thesis, we introduce a technique that leverages the patterned nature of node failures in blockchain systems to design a coding scheme called PARE (Pattern Aware Redundancy for Erasures), which minimally corrects only a predefined set of node failure patterns (called a patterned set), in the sense that the code guarantees to correct only the erasures present in the patterned set and gives no guarantees about erasure patterns that are not present in the patterned set. PARE is able to significantly reduce storage costs in blockchain systems compared to previous erasure coding techniques. We then modify PARE to a locally recoverable coding scheme called PARE-LRC which corrects all single node failures locally while still minimally correcting only a predefined set of node failure patterns. In situations where single node failures are more prone to occur, this approach lowers communication cost and provides a better trade off between communication cost and storage cost compared to other techniques used for blockchain systems.