Although blockchain, the supporting technology of various cryptocurrencies, has offered a potentially effective framework for numerous decentralized trust management systems, its performance is still sub-optimal in real-world networks. With limited bandwidth, the communication complexity for nodes to process a block scales with the growing network size and hence becomes the limiting factor of blockchain’s performance.In this paper, we suggest a re-design of existing blockchain systems, which addresses the issue of the communication burden. First, by employing techniques from Coded Computation, our scheme guarantees correct verification of transactions while reducing the communication complexity dramatically such that it grows logarithmically with network size. Second, by adopting techniques from Information Dispersal and State Machine Replication, our design is provably resilient to Byzantine faults under standard cryptographic assumptions. 1