Scaling permissionless blockchains via sharding

This thesis systematically analyses blockchain sharding, a promising approach for scaling blockchain protocols. Based on the systematic analysis, we formalised and improved two over-looked primitives in blockchain sharding protocols, namely shard allocation and decentralised randomness beacon (DRB), and suggested countermeasures against security issues in cross-chain 51% attacks and atomic swaps. We provided formal security proofs and experimental evaluations on the proposed constructions and countermeasures, demonstrating their security and practicality.