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

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.

Key words: bloom filter, blockchain, membership query

摘要:

布隆过滤器(BF)可以高效查询元素是否在指定集合中,广泛应用于区块链成员查询中。针对现有的通用布隆过滤器无法充分利用区块链数据特性及通用设备计算资源的问题,提出一种新型区块链布隆过滤器(BBF)。首先,改进布隆过滤器数据结构,对BBF以组为单位进行细分,从而将元素的映射范围限制在一个组内,减少访存失败次数,提高访存效率。其次,利用区块链数据的特性,提出一种简化的三阶段哈希映射函数,减少计算开销。在此基础上,使用单指令多数据流(SIMD)技术实现元素插入和查询操作的并行处理,提高BBF构建及查询速度,最终实现区块链上数据的高效查询和分析。实验结果显示,BBF与BF、OMBF两个主流布隆过滤器相比,其正向查询时的成员查询速度分别提高4倍、3倍,性能提升显著。

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