AdaptiveShard: Enhancing Throughput and Security of Sharded Blockchain With Adaptive Verifiable Coding

The blockchain technology provides a revolutionary solution for information exchange through its decentralized, tamper-proof, and highly secure characteristics. It has wide application in many industries, with the potential to improve efficiency, reduce costs, and promote innovation. However, the full replication mechanism of blockchain results in the need for each device to store complete blockchain data, leading to inefficient storage. Additionally, as the scale of the blockchain network expands, the increasing data volume and frequent transactions can cause network congestion and latency, posing scalability issues for blockchain. Coded sharding blockchain has been proposed to address these issues. However, the current solutions face challenges such as dealing with malicious nodes and low computational efficiency, which hinder the enhancement of their scalability and computational performance. To resolve these problems, we propose AdaptiveShard by combining coded sharding blockchain with adaptive verifiable coded computing (AVCC). This solution is designed based on the Unspent Transaction Output (UTXO) model and is suitable for cryptocurrency transaction scenarios. Compared to traditional coded sharding blockchain solutions, AdaptiveShard can: 1) enhance the computational performance of coded sharding blockchain during block validation by combining AVCC with Gaussian variant of Freivalds algorithm (GVFA), reducing the decoding complexity to <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O</i>(<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</i><sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> log<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</i>); 2) validate the computation results of each shard using GVFA and replace balance check verification functions with matrix multiplication, reducing the computational complexity of verification to <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O</i>(√<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i>); 3) reduce the additional number of nodes required to resolve malicious nodes from two to one using verifiable computation; 4) balance the system in the presence of straggler or malicious nodes through dynamic coding techniques, eliminating their impact and improving system reliability. Experiments demonstrate that at t=1000, the throughput is 25.6% higher compared to Polyshard. Compared to the solution without dynamic coding, the solution with dynamic coding can reduce the running time by 9.7% at t=50.