This thesis presents the design, implementation and evaluation of techniques toscale the base layers of decentralised blockchain networks—where transactions aredirectly posted on the chain. The key challenge is to scale the base layer withoutsacrificing properties such as decentralisation, security and public verifiability.It proposes Chainspace, a blockchain sharding system where nodes processand reach consensus on transactions in parallel, thereby scaling block productionand increasing on-chain throughput. In order to make the actions of consensus-participating nodes efficiently verifiable despite the increase of on-chain data, asystem of fraud and data availability proofs is proposed so that invalid blocks canbe efficiently challenged and rejected without the need for all users to download alltransactions, thereby scaling block verification.It then explores blockchain and application design paradigms that enable on-chain scalability on the outset. This is in contrast to sharding, which scalesblockchains designed under the traditional state machine replication paradigmwhere consensus and transaction execution are coupled. LazyLedger, a blockchaindesign where the consensus layer separated from the execution layer is proposed,where the consensus is only responsible for checking the availability of the datain blocks via data availability proofs. Transactions are instead executed off-chain,eliminating the need for nodes to execute on-chain transactions in order to verifyblocks. Finally, as an example of a blockchain use case that does not require anexecution layer, Contour, a scalable design for software binary transparency is pro-posed on top of the existing Bitcoin blockchain, where all software binary recordsdo not need to be posted on-chain.