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 bit complexity dramatically such that it grows
logarithmically with the number of nodes. Second, with the adoption of
techniques from Information Dispersal and State Machine Replication, the system
is resilient to Byzantine faults and achieves linear message complexity. Third,
we propose a novel 2-dimensional sharding strategy, which inherently supports
cross-shard transactions, alleviating the need for complicated communication
protocols between shards, while keeping the computation and storage benefits of
sharding.