Research On Efficient High-frequency Algorithms And Scalable Storage For Blockchain

Blockchain is believed to be able to build trust among multiple parties and improve the operational efficiency of economy and society.Improving the computing efficiency of Blockchain system and enhancing its storage scalability can not only improve the performance of Blockchain system,but also reduce the threshold of node participation and maintain the decentralized characteristics of Blockchain,which is a key supporting technology for the application and promotion of Blockchain.From the perspective of computation,Blockchain technology is composed of technologies from encryption,peer-to-peer（P2P）networking and distributed consensus.All the technologies involve hash operations,especially Secure Hash Algorithm 256（SHA256）and Bloom Filter（BF）are frequently used in encryption operations and Blockchain on-chain data query,which are known as high-frequency operations.With the increase of Blockchain applications and data volume,the high-frequency operations have become a major computing pressure for common devices.From the perspective of storage,the append-only data structure means that Blockchain has to maintain its endlessly growing data.Accordingly,the growing storage and computing resources are needed for a node to store Blockchain data and verify transactions.The full nodes with a limited storage and computing resources are forced to exit the Blockchain system or switch roles to non-full nodes,i.e.,lightweight nodes,which raises the scalability issue of Blockchain storage systems.The full node refers to the node that stores the entire Blockchain data and has basic node functions.While the lightweight nodes are those that only store the block headers and have the payment verification function.This thesis focuses on the improvement of Blockchain computing efficiency and the optimization of the storage scalability.In terms of the improvement of computing efficiency,SHA256 and Bloom filter are taken as examples to make full use of the hash-native characteristics of Blockchain data as well as the computing resources of general-purpose equipments,and develop a general method of improving the high-frequency computing efficiency of Blockchain,and consequently improving the overall computing efficiency of Blockchain:（1）the direct utilization of block/transaction hash value;（2）the data-level parallelism based on Single Instruction Multiple Data（SIMD）;（3）the thread-level parallelism based on CPU multi-core;as well as（4）the range of data access scope and cache-line adaptation strategy to reduce the probability of cache misses.In terms of the optimization of the storage scalability,this thesis targetes at resolving the contradiction between data redundancy and decentralization,by finding the quantitative indexes for evaluating scalable storage of Blockchain system,and putting forward the Scalable Model of Blockchain Storage Systems（SMBSS）.The main work and innovations are as follows:（1）In the aspect of improving the computational efficiency of high-frequency operations for hash-native data,this thesis proposes SHA256_ASM for a single message and SHA256^*_MIM for multiple independent messages by utilizing SIMD and CPU multi-core supported by general equipments,as well as the hash-native features of Blockchain data.SHA256_ASM adopts the Interleaved Multi-Vectorizing Message Scheduling（IMV-MS）method to achieve computational acceleration by interleaved executing SIMD vectorization and prefetching for a single message.While SHA256^*_MIM employs both data-level parallelism and thread-level parallelism to accelerate computation.As experimental results show,SHA256_ASMand SHA256^*_MIM achieve up to 5.91 times,60.38 times better performance compared with SHA256,and the computing performance is roughly the same at all levels of cache.（2）In terms of improving the computing efficiency of high-frequency operations for Blockchain data query,an optimization method of Blockchain Bloom Filter（BBF）is proposed by taking Bloom Filter as an example.First,BBF is divided into multiple groups to take the advantage of SIMD,which realize the element insertion and membership query within the inter-group.Then,a simplified three-stage mapping method is proposed by using the hash native feature of Blockchain data to reduce computational overhead.Finally,we limit the mapping range of an element within a cache-line in order to reduce the number of cache misses.The experimental results show that BBF is approximately 3.0 times to 5.2 times,and 1.5 times to 2.3 times faster than a BF in positive membership query and negative membership query,respectively.（3）In quantitative research of storage scalability of Blockchain systems,aiming at the issue of the functional inequivalence among the different types of nodes in various schemes of Blockchain storage systems,which erodes the decentralization characteristic,this thesis surveys the schemes of Blockchain storage systems and proposes the quantitative indicators for scalable storage of Blockchain systems,including the degree of decentralization,storage cost of nodes and data reliability.The experiments are conduced on the representative storage schemes according to the quantitative indicators for scalable storage of Blockchain systems,which lays a foundation for the construction of the scalable model of Blockchain storage systems.（4）In terms of the construction of scalable model of Blockchain storage systems,this paper takes the quantitative indicators for scalable storage of Blockchain systems as the key parameters,combines the characteristic that the transactions can be verified by referring to the most recent blocks of UTXO-based Blockchain,as well as the current state of all accounts are maintained in the state trie of Account-based Blockchain,and proposes the Scalable Model for Blockchain Storage Systems（SMBSS）.The key factors of SMBSS are sharding,guaranteed data availability,and decentralization.Experimental analysis on the prototypes of the SMBSS is carried out to verify its validity.