Gauze: enabling communication-friendly block synchronization with cuckoo filter

Abstract

Block synchronization is an essential component of blockchain systems. Traditionally, blockchain systems tend to send all the transactions from one node to another for synchronization. However, such a method may lead to an extremely high network bandwidth overhead and significant transmission latency. It is crucial to speed up such a block synchronization process and save bandwidth consumption. A feasible solution is to reduce the amount of data transmission in the block synchronization process between any pair of peers. However, existing methods based on the Bloom filter or its variants still suffer from multiple roundtrips of communications and significant synchronization delay. In this paper, we propose a novel protocol named Gauze for fast block synchronization. It utilizes the Cuckoo filter (CF) to discern the transactions in the receiver’s mempool and the block to verify, providing an efficient solution to the problem of set reconciliation in the P2P (Peer-to-Peer Network) network. By up to two rounds of exchanging and querying the CFs, the sending node can acknowledge whether the transactions in a block are contained by the receiver’s mempool or not. Based on this message, the sender only needs to transfer the missed transactions to the receiver, which speeds up the block synchronization and saves precious bandwidth resources. The evaluation results show that Gauze outperforms existing methods in terms of the average processing latency (about 10\times lower than Graphene) and the total synchronization space cost (about 10\times lower than Compact Blocks) in different scenarios.

Graphical abstract

Keywords

block synchronization / cuckoo filter / probabilistic data structure

Xiaoqiang Ding is currently pursuing his MS degree from the College of Intelligence and Computing, Tianjin University, China. His research interests include data structure, distributed networking systems, and blockchain

Liushun Zhao received his BE degree in communications engineering from Harbin Engineering University, China in 2018. From 2018, He continues to pursue his PhD degree in the School of Computer Science and Technology, Xidian University, China. His research interest focuses on security supervision in the operation process of blockchain

Lailong Luo received the BS, MS, and PhD degrees from the College of Systems Engineering, National University of Defense Technology, China in 2013, 2015 and 2019, respectively. He is currently a lecturer in the College of Systems Engineering, National University of Defense Technology, China. His research interests include data structure and distributed networking systems

Junjie Xie received the BE degree in computer science and technology from the Beijing Institute of Technology, China in 2013. He received the MS and PhD degrees in management science and engineering from the National University of Defense Technology, China in 2015 and 2020, respectively. He is currently an engineer with the Institute of Systems Engineering, AMS, PLA, Beijing, China. His research interests include distributed systems, software-defined networking, and mobile edge computing

Deke Guo received the BS degree in industry engineering from the Beihang University, China in 2001, and the PhD degree in management science and engineering from the National University of Defense Technology, China, in 2008. He is currently a professor with the College of Systems Engineering, National University of Defense Technology, China. His research interests include distributed systems, software-defined networking, data center networking, wireless and mobile systems, and interconnection networks. He is a senior member of the IEEE and a member of the ACM

Jinxi Li is currently pursuing his MS degree from the College of Intelligence and Computing, Tianjin University, China. His research interests include edge computing and network function virtualization

References

[1] Van Renesse R, Dumitriu D, Gough V, Thomas C. Efficient reconciliation and flow control for anti-entropy protocols. In: Proceedings of the 2nd Workshop on Large-Scale Distributed Systems and Middleware. 2008, 1− 7

[2] Kokoris-Kogias E, Jovanovic P, Gailly N, Khoffi I, Gasser L, Ford B. Enhancing bitcoin security and performance with strong consistency via collective signing. In: Proceedings of the 25th USENIX Conference on Security Symposium. 2016, 279– 296

[3] Gilad Y, Hemo R, Micali S, Vlachos G, Zeldovich N. Algorand: scaling byzantine agreements for cryptocurrencies. In: Proceedings of the 26th Symposium on Operating Systems Principles. 2017, 51– 68

[4] Buterin V, Griffith V. Casper the friendly finality gadget. 2017, arXiv preprint arXiv: 1710.09437

[5] Ayinala K, Choi B Y, Song S. PiChu: accelerating block broadcasting in blockchain networks with pipelining and chunking. In: Proceedings of the 2020 IEEE International Conference on Blockchain (Blockchain). 2020, 221– 228

[6] Chawla N, Behrens H W, Tapp D, Boscovic D, Candan K S. Velocity: scalability improvements in block propagation through rateless erasure coding. In: Proceedings of the 2019 IEEE International Conference on Blockchain and Cryptocurrency (ICBC). 2019, 447– 454

[7] Zhang L, Wang T, Liew S C . Speeding up block propagation in bitcoin network: uncoded and coded designs. Computer Networks, 2022, 206: 108791

[8] Imtiaz M A, Starobinski D, Trachtenberg A, Younis N. Churn in the bitcoin network: characterization and impact. In: Proceedings of the 2019 IEEE International Conference on Blockchain and Cryptocurrency (ICBC). 2019, 431– 439

[9] Croman K, Decker C, Eyal I, Gencer A E, Juels A, Kosba A, Miller A, Saxena P, Shi E, Sirer E G, Song D, Wattenhofer R. On scaling decentralized blockchains. In: Proceedings of the 2016 International Conference on Financial Cryptography and Data Security. 2016, 106– 125

[10] Luo L, Guo D, Li W, Zhang T, Xie J, Zhou X . Compound graph based hybrid data center topologies. Frontiers of Computer Science, 2015, 9( 6): 860– 1874

[11] Decker C, Wattenhofer R. Information propagation in the bitcoin network. In: Proceedings of the IEEE P2P 2013 Proceedings. 2013, 1– 10

[12] Eppstein D, Goodrich M T, Uyeda F, Varghese G . What’s the difference?: Efficient set reconciliation without prior context. ACM SIGCOMM Computer Communication Review, 2011, 41( 4): 218– 229

[13] Tschipper P. Buip010: xtreme thinblocks. See Bitco.in/forum/threads/buip010-passed-xtreme-thinblocks774 website, 2016

[14] Bloom B H . Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 1970, 13( 7): 422– 426

[15] Corallo M. Bip152: Compact block relay, See Github/bitcoin/bips/blob/master/bip-0152.mediawiki website, 2016

[16] Ozisik A P, Andresen G, Levine B N, Tapp D, Bissias G, Katkuri S. Graphene: efficient interactive set reconciliation applied to blockchain propagation. In: Proceedings of the ACM Special Interest Group on Data Communication. 2019, 303– 317

[17] Goodrich M T, Mitzenmacher M. Invertible bloom lookup tables. In: Proceedings of the 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton). 2011, 792– 799

[18] Fan B, Andersen D G, Kaminsky M, Mitzenmacher M D. Cuckoo filter: practically better than bloom. In: Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies. 2014, 75– 88

[19] Toomim J. Benefits of ltor in block entropy encoding, or: ISPs hate him! Learn how to make your block 75% Xthinner with this one weird trick. See Jtoomim.medium/benefits-of-ltor-in-block-entropy-encoding-or-8d5b77cc2ab0 website, 2018

[20] Naumenko G, Maxwell G, Wuille P, Fedorova A, Beschastnikh I. Erlay: efficient transaction relay for bitcoin. In: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. 2019, 817– 831

[21] Shafeeq S, Zeadally S, Alam M, Khan A . Curbing address reuse in the iota distributed ledger: a cuckoo-filter-based approach. IEEE Transactions on Engineering Management, 2020, 67( 4): 1244– 1255

[22] Fan B, Andersen D G, Kaminsky M. MemC3: compact and concurrent MemCache with dumber caching and smarter hashing. In: Proceedings of the 10th USENIX Conference on Networked Systems Design and Implementation. 2013, 371– 384

[23] Rottenstreich O. Sketches for blockchains. In: Proceedings of the 13th International Conference on COMmunication Systems & NETworkS (COMSNETS). 2021, 254– 262

[24] Guo D, Li M . Set reconciliation via counting bloom filters. IEEE Transactions on Knowledge and Data Engineering, 2013, 25( 10): 2367– 2380

[25] Chen D, Konrad C, Yi K, Yu W, Zhang Q . Robust set reconciliation. In: Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, 2014, 135– 146

[26] Luo L, Guo D, Zhao Y, Rottenstreich O, Ma R T B, Luo X . MCFsyn: a multi-party set reconciliation protocol with the marked cuckoo filter. IEEE Transactions on Parallel and Distributed Systems, 2021, 32( 11): 2705– 2718

[27] Ruan M, Titcheu T, Zhai E, Li Z, Liu Y, Jinlong E, Cui Y, Xu H . On the synchronization bottleneck of openstack swift-like cloud storage systems. IEEE Transactions on Parallel and Distributed Systems, 2018, 29( 9): 2059– 2074

[28] Eppstein D. Cuckoo filter: simplification and analysis. In: Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). 2016, 8

Acknowledgements

This work was supported in part by the National Natural Science Foundation of China (Grant No. 62032017).

RIGHTS & PERMISSIONS

2023 Higher Education Press