Journal of Frontiers of Computer Science and Technology ›› 2021, Vol. 15 ›› Issue (10): 1921-1929.DOI: 10.3778/j.issn.1673-9418.2007029

• Network and Information Security • Previous Articles     Next Articles

BBF: Bloom Filter Variant for Blockchain

FAN Xing, NIU Baoning   

  1. School of Information and Computer Science, Taiyuan University of Technology, Jinzhong, Shanxi 030600, China
  • Online:2021-10-01 Published:2021-09-30



  1. 太原理工大学 信息与计算机学院,山西 晋中 030600


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.

Key words: bloom filter, blockchain, membership query



关键词: 布隆过滤器, 区块链, 成员查询