BBF: Bloom Filter Variant for Blockchain

Abstract

Bloom filter (BF) is highly efficient for membership queries, which is widely used in blockchain mem-bership queries. Aiming at the existing BFs do not exploit the data characteristics of blockchain and the features of modern processors, this paper proposes a novel bloom filter variant named blockchain bloom filter (BBF). Firstly, this paper modifies data structure which divides BBF into groups, so that the mapping range of an element is limited into a group to reduce the number of cache misses and improve cache efficiency. Secondly, a simplified three-stage Hash process is presented to eliminate computing overhead by taking advantage of blockchain data characteristics. On this basis, BBF uses single instruction multiple data (SIMD) to parallelize element insertion and query, and accelerate BBF construction and query speed, which can realize efficient query and analysis of blockchain data ultimately. The experimental result shows that BBF??s membership query speed under positive query can improve 4 times and 3 times over the other two state-of-the-art bloom filter variants, i.e., BF, OMBF（one-memory bloom filter）, which enables significant performance improvement.

Keywords

• bloom filter
• blockchain
• membership query