Scaling Blockchains Using Coding Theory and Verifiable Computing

Abstract

The issue of scalability has been restricting blockchain from its widespread adoption. The current transaction rate of bitcoin is around seven transactions/second while its size has crossed the 300 GB mark. Although many approaches propose different ways to scale blockchain, e.g., sharding, lightning network, etc., we focus our analysis on methods utilizing ideas from coding theory. We first consider SeF, a blockchain archiving architecture utilizing LT codes to reduce storage constraints per node up to 1000x. SeF enables full nodes to store only a small number of encoded blocks or droplets instead of an entire blockchain. Although efficient in the average case, the architecture sometimes requires large bandwidth (many droplets) to reconstruct blockchain. While other rate-less coding strategies utilizing two encoding levels are proven better than LT codes, we investigate their suitability in the proposed architecture. We propose and simulate three techniques about how to incorporate these coding strategies. The results show that precode-based rate-less coding schemes provide similar storage savings with reduced bandwidth variance for recovery. The other work we examine is PolyShard, which introduces the notion of coded-sharding. Coded sharding exports block verification of sub-ledger to the whole network instead of nodes handling that sub-ledger, making sharding resilient even to an adaptive adversary, i.e., adversary having the power to corrupt nodes after their assignment to shards. However innovative, PolyShard requires decoding of Reed-Solomon codes over large fields for block verification in real-world settings, making it computationally intensive and less practical. We propose replacing the decoding phase with verifiable computing, which reduces the bottleneck and makes the system practical for light verification functions.