A Bloom filter variant for Blockchain

【Author】 Fan, Xing; Niu, Baoning

【Source】CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE

【影响因子】1.831

【Abstract】Blockchain is a single linked list of blocks consisting of transactions identified by their hash value. Querying Blockchain, primarily searching blocks/transactions, can be treated as membership queries and efficiently evaluated by a Bloom filter (BF). The existing BFs for Blockchain, however, do not exploit the data characteristics of Blockchain and the features of modern processors, which otherwise have the potential to greatly improve their performance. This article proposes a novel Bloom filter variant for Blockchain, called Blockchain Bloom Filter (BBF), with three alternatives to improve BF. First, we reorganize BF structure to make use of Single Instruction Multiple Data provided by modern processors, which parallelize the bit-map and bit-test processes of BBF and accelerate element insertion and membership querying. On that basis, hash computation of BBF is parallelized, which reduce the hashing time to 1/k that of the BF in theory, where k is the number of hash functions. Second, hash functions derived from block/transaction hash are developed to reduce the complexity of hash computation and accelerate the element insertion and membership query processes of BBF. Finally, we further refine BBF structure to limit the mapping range of an element within a cache-line in the on-chip cache in order to increase cache efficiency. With the improvements, both theoretical analysis and extensive simulations show that the performance of BBF membership queries greatly exceeds the three state-of-the-art Bloom filter variants, which enables efficient data queries and application specific analysis over Blockchain.

【Keywords】Blockchain; Bloom filter; element insertion; membership query

【发表时间】

【收录时间】2022-01-01

【文献类型】

【主题类别】

--