A Theoretical Treatment of Blockchain Scaling Protocols

Abstract

Scaling decentralized blockchains has been in the spotlight of the blockchain research community due to the immediate consequences on the widespread adoption of cryptocurrencies. In this thesis, we examine different scaling solutions of blockchain protocols mainly from a theoretical perspective. We first present a formalization of sharding protocols, the most promising on-chain scaling solution. Our goal is to provide formal “common grounds” for systematically evaluating the security and efficiency of sharding systems. To that end, we define the necessary properties sharding protocols should satisfy. To demonstrate the power of our framework, we evaluate the most prominent sharding systems found in literature, and further provide bounds and limitations of what sharding protocols can achieve in general. We conclude by identifying the critical components of sharding. We then focus on off-chain scaling solutions, and in particular, payment channels. We highlight and address security concerns on the fundamental construction of payment channels. Specifically, previous payment channel designs demand participants to be online monitoring the blockchain, while the blockchain should be live and the network synchronous. We alleviate the first assumption for Bitcoin-compatible constructions by presenting Cerberus channels. Cerberus channels enable participants to go securely offline for an extended period of time as monitoring the blockchain is outsourced to third-parties that are financially incentivized to faithfully follow the protocol. Assuming smart contracts we later present Brick, the first incentive-compatible asynchronous payment channel construction, effectively eliminating both security assumptions. Brick remains secure with offline participants under network asynchrony, and concurrently provides correct incentives. Finally, we study the creation of payment channel networks under the lens of theory. On the one hand, we investigate the design of capital-efficient payment channel networks assuming a central coordinator. For this purpose, we introduce an algorithmic framework and present numerous results, either efficient (approximation) algorithms or hardness results. On the other hand, we model payment channel networks as network creation games, where participants act selfishly. We analyze prominent topologies for Nash equilibria, determine the social optima, and bound the price of anarchy when possible. Our objective is to determine the optimal topologies for payment channel networks, both under central coordination and when the network is decentralized.