BBF: Bloom Filter Variant for Blockchain

doi:10.3778/j.issn.1673-9418.2007029

Abstract

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倍，性能提升显著。

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

FAN Xing, NIU Baoning. BBF: Bloom Filter Variant for Blockchain[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(10): 1921-1929.

樊星, 牛保宁. 区块链应用下的新型区块链布隆过滤器[J]. 计算机科学与探索, 2021, 15(10): 1921-1929.

References

[1] NAKAMOTO S. Bitcoin: a peer-to-peer electronic cash system[EB/OL]. (2008-06-10) [2020-07-09]. https://bitcoin.org/bitcoin.pdf.
[2] BUTERIN V. A next-generation smart contract and de-centralized application platform[EB/OL]. (2020-06-03) [2020-07-09]. https://github.com/ethereum/wiki/wiki/White-Paper.
[3] ANDROULAKI E, BARGER A, BORTNIKOV V, et al. Hyperledger fabric: a distributed operating system for per-missioned blockchains[C]//Proceedings of the 13th EuroSys Conference, Porto, Apr 23-26, 2018. New York: ACM, 2018: 1-15.
[4] ZHAO Y L, NIU B N, LI P, et al. A novel enhanced light-weight node for blockchain[C]//Proceedings of the 1st Inter-national Conference on Blockchain and Trustworthy Systems, Guangzhou, Dec 7-8, 2019. Singapore: Springer, 2020: 137-149.
[5] BLOOM B H. Space/time trade-offs in Hash coding with allowable errors[J]. Journal of Communications of ACM, 1970, 13(7): 422-426.
[6] GERVAIS A, CAPKUN S, KARAME G O, et al. On the privacy provisions of Bloom filters in lightweight bitcoin clients[C]//Proceedings of the 30th Annual Computer Security Applications Conference, New Orleans, Dec 8-12, 2014. New York: ACM, 2014: 326-335.
[7] QIAO Y, LI T, CHEN S G. One memory access Bloom filters and their generalization[C]//Proceedings of the 30th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, Shanghai, Apr 10-15, 2011. Piscataway: IEEE, 2011: 1745-1753.
[8] QIAO Y, LI T, CHEN S G. Fast Bloom filters and their generalization[J]. IEEE Transactions on Parallel and Distri-buted Systems, 2014, 25(1): 93-103.
[9] MITZENMACHER M, REVIRIEGO P, PONTARELLI S. OMASS: one memory access set separation[J]. IEEE Trans-actions on Knowledge and Data Engineering, 2016, 28(7): 1940-1943.
[10] KIRSCH A, MITZENMACHER M. Less Hashing, same per-formance: building a better Bloom filter[J]. Journal of Random Structures and Algorithms, 2008, 33(2): 187-218.
[11] SONG H Y, HAO F, KODIALAM M S, et al. IPv6 lookups using distributed and load balanced Bloom filters for 100Gbps core router line cards[C]//Proceedings of the 28th IEEE International Conference on Computer Communica-tions, Joint Conference of the IEEE Computer and Comm-unications Societies, Rio de Janeiro, Apr 19-25, 2009. Pisca-taway: IEEE, 2009: 2518-2526.
[12] XIAO B, HUA Y. Using parallel Bloom filters for multiattribute representation on network services[J]. IEEE Transactions on Parallel and Distributed Systems, 2010, 21(1): 20-32.
[13] MurmurHash[EB/OL]. (2020-02-12) [2020-03-06]. https://en.wikipedia.org/wiki/MurmurHash.
[14] HashMap[EB/OL]. (2018-06-12) [2020-03-06]. https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html.
[15] SKJEGSTAD M, MASENG T. Low complexity set recon-ciliation using Bloom filters[C]//Proceedings of the 7th ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing, San Jose, Jun 9, 2011. New York: ACM, 2011: 33-41.
[16] LU J Y. Research on high-performance Hashing techniques and their applications[D]. Beijing: Tsinghua University, 2017.
卢建元. 高性能哈希技术及其应用的研究[D]. 北京: 清华大学, 2017.
[17] RAMAKRISHNA M. Practical performance of Bloom filters and parallel free-text searching[J]. Journal of Communica-tions of ACM, 1989, 32(10): 1237-1239.
[18] Coding ASM Intel instruction set codes and cycles[EB/OL].(2012-12-16) [2020-03-06]. http://read.pudn.com/downloads95/ ebook/379824/The Art of Assembly Language Programming/Appendix D.
[19] SIMD[EB/OL]. (2018-01-03)[2020-03-06]. http://simd.sourceforge.net/.