Scaling blockchains

Blockchains are a new type of state machine replication that have raised interesting challenges. A replicated state machine (RSM) is a well-established approach to building fault-tolerant systems. Because each replica needs to execute the same set of instructions to transition through the same state changes, adding more replicas does not translate directly to an increase in performance. On top of that, RSM can be made to tolerate Byzantine failures, i.e., nodes in the system can have arbitrary behavior. Blockchains distinguish themselves from traditional RSM mainly for having an open membership, being decentralized, and involving economic aspects as a means to counter adversarial attacks. Yet, despite their increasing popularity, current blockchain systems scale poorly and are constrained to exist in isolation, unable to communicate with each other. In this thesis, we explore techniques to make blockchains scale in two angles: (a) scaling blockchain transaction throughput; and (b) making the state synchronization faster and robust for incoming peers. For (a), we analyze the effects of partitioning a real blockchain state in several shards and how to minimize communication within shards, while keeping the shards balanced. We then propose a protocol that can be applied to increase the throughput of a sharded blockchain or by which blockchains can communicate with each other. For (b), we propose a data structure that can be used by blockchains to enhance scalability by easing the synchronization process and allowing the blockchain’s state to be reconstructed without requiring additional trust. The claims in this thesis are sustained by extensive experimental evaluation using real applications from public blockchains, developing new protocols and algorithms, and performing tests in geo-replicated environments