Gauze: enabling communication-friendly block synchronization with cuckoo filter

doi:10.1007/s11704-022-1685-5

Front. Comput. Sci.

2023, Vol. 17

Issue (3) : 173403 https://doi.org/10.1007/s11704-022-1685-5

RESEARCH ARTICLE

Gauze: enabling communication-friendly block synchronization with cuckoo filter

Xiaoqiang DING¹, Liushun ZHAO², Lailong LUO³, Junjie XIE⁴, Deke GUO^1,³(

), Jinxi LI¹

¹. College of Intelligence and Computing, Tianjin University, Tianjin 300350, China
². School of Computer Science and Technology, Xidian University, Xi’an 710071, China
³. Science and Technology on Information Systems Engineering Laboratory, National University of Defense Technology, Changsha 410073, China
⁴. Institute of Systems Engineering, AMS, PLA, Beijing 100141, China

Download: PDF(14695 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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 ×$ lower than Graphene) and the total synchronization space cost (about $10 ×$ lower than Compact Blocks) in different scenarios.

Keywords block synchronization cuckoo filter probabilistic data structure

Corresponding Author(s): Deke GUO

About author: Tongcan Cui and Yizhe Hou contributed equally to this work.

Just Accepted Date: 18 March 2022 Issue Date: 16 September 2022

Cite this article:

Xiaoqiang DING,Liushun ZHAO,Lailong LUO, et al. Gauze: enabling communication-friendly block synchronization with cuckoo filter[J]. Front. Comput. Sci., 2023, 17(3): 173403.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-022-1685-5
https://academic.hep.com.cn/fcs/EN/Y2023/V17/I3/173403

Fig.1 Block synchronization in the blockchain. (Since node 4 is disconnected, new transactions and blocks are not saved to this node’s mempool during the second synchronization round.)

Fig.2 Scenario 1: the receiver’s mempool contains the entire block

Fig.3 The propagation process of blocks in the blockchain

Fig.4 Scenario 2: the receiver’s mempool does not contain the entire block

Fig.5 An illustrative example of Protocol 1 for propagating a block that is a subset of the mempool

Protocol 1 Gauze

1: Sender: The sender sends the transaction IDs as the content of an inventory (inv) for the block to the receiver.2: Receiver: The receiver requests the unknown block. 3: Sender: The sender creates

C F S

from the transaction IDs of the block (blue area in Fig.2-left) and sends it to the receiver. 4: Receiver: The receiver creates a candidate set

S 1

of transaction IDs, queries the

C F S

received from the sender, and adds the transactions contained in the

C F S

S 1

from her mempool. Based on the result of

S 1

, she validates the Merkle root in the block header and decodes the block.

Tab.1

Fig.6 If Protocol 1 fails (the block is not a subset of the mempool), Protocol 2 begins

Protocol 2 Gauze Enhanced

1: Receiver: The receiver creates

C F R

from the transaction IDs of the mempool (blue and green areas in Fig.4-right) and sends it to the sender. 2: Sender: The sender queries

C F R

and confirms the receiver’s missing transactions (red area in Fig.4-right) according to the transactions contained in its block and adds them to the miss_txn.3: Sender: The sender sends miss_txn containing all transactions that are not in

C F R

directly to the receiver. 4: Receiver: The receiver creates a candidate set

S 2

of transaction IDs that pass through

C F S

sent by the sender in Protocol 1. Based on the results of

S 2

and miss_txn, she validates the Merkle root in the block header and decodes the block.

Tab.2

Fig.7 Average processing latency (s) of Gauze VS. Graphene. Each facet is a block size: (200, 2000, and 10000 transactions)

Fig.8 Average space cost of Gauze VS. Compact Blocks and Graphene. Each facet is a block size: (200, 2000, and 10000 transactions)

Fig.9 Average false positive rate of Gauze VS. Graphene. Each facet is a block size: (200, 2000, and 10000 transactions)

Fig.10 Average processing latency (s) of Gauze VS. Graphene (

f = 16

). Each facet is a block size: (200, 2000, and 10000 transactions)

Fig.11 Average space cost of Gauze VS. Compact Blocks and Graphene (

f = 16

). Each facet is a block size: (200, 2000, and 10000 transactions)

Fig.12 Average false positive rate of Gauze VS. Graphene (

f = 16

). Each facet is a block size: (200, 2000, and 10000 transactions)

Fig.13 Average processing latency (s) of Gauze Enhanced VS. Graphene Extended as the fraction of the block owned by the receiver increases

Fig.14 Average space cost of Gauze Enhanced VS. Compact Blocks and Graphene Extended as the fraction of the block owned by the receiver increases

Fig.15 Average false positive rate of Gauze Enhanced VS. Graphene Extended as the fraction of the block owned by the receiver increases

1	Renesse R, Van D, Dumitriu V, Gough C Thomas. 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	E, Kokoris-Kogias P, Jovanovic N, Gailly I, Khoffi L, Gasser B Ford. 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	Y, Gilad R, Hemo S, Micali G, Vlachos N Zeldovich. Algorand: scaling byzantine agreements for cryptocurrencies. In: Proceedings of the 26th Symposium on Operating Systems Principles. 2017, 51– 68
4	V, Buterin V Griffith. Casper the friendly finality gadget. 2017, arXiv preprint arXiv: 1710.09437
5	K, Ayinala B Y, Choi S Song. 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	N, Chawla H W, Behrens D, Tapp D, Boscovic K S Candan. 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	L, Zhang T, Wang S C Liew . Speeding up block propagation in bitcoin network: uncoded and coded designs. Computer Networks, 2022, 206: 108791
8	M A, Imtiaz D, Starobinski A, Trachtenberg N Younis. 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	K, Croman C, Decker I, Eyal A E, Gencer A, Juels A, Kosba A, Miller P, Saxena E, Shi E G, Sirer D, Song R Wattenhofer. On scaling decentralized blockchains. In: Proceedings of the 2016 International Conference on Financial Cryptography and Data Security. 2016, 106– 125
10	L, Luo D, Guo W, Li T, Zhang J, Xie X Zhou . Compound graph based hybrid data center topologies. Frontiers of Computer Science, 2015, 9( 6): 860– 1874
11	C, Decker R Wattenhofer. Information propagation in the bitcoin network. In: Proceedings of the IEEE P2P 2013 Proceedings. 2013, 1– 10
12	D, Eppstein M T, Goodrich F, Uyeda G Varghese . What’s the difference?: Efficient set reconciliation without prior context. ACM SIGCOMM Computer Communication Review, 2011, 41( 4): 218– 229
13	P Tschipper. Buip010: xtreme thinblocks. See Bitco.in/forum/threads/buip010-passed-xtreme-thinblocks774 website, 2016
14	B H Bloom . Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 1970, 13( 7): 422– 426
15	M Corallo. Bip152: Compact block relay, See Github/bitcoin/bips/blob/master/bip-0152.mediawiki website, 2016
16	A P, Ozisik G, Andresen B N, Levine D, Tapp G, Bissias S Katkuri. Graphene: efficient interactive set reconciliation applied to blockchain propagation. In: Proceedings of the ACM Special Interest Group on Data Communication. 2019, 303– 317
17	M T, Goodrich M Mitzenmacher. Invertible bloom lookup tables. In: Proceedings of the 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton). 2011, 792– 799
18	B, Fan D G, Andersen M, Kaminsky M D Mitzenmacher. 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	J Toomim. 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	G, Naumenko G, Maxwell P, Wuille A, Fedorova I Beschastnikh. Erlay: efficient transaction relay for bitcoin. In: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. 2019, 817– 831
21	S, Shafeeq S, Zeadally M, Alam A Khan . Curbing address reuse in the iota distributed ledger: a cuckoo-filter-based approach. IEEE Transactions on Engineering Management, 2020, 67( 4): 1244– 1255
22	B, Fan D G, Andersen M Kaminsky. 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	O Rottenstreich. Sketches for blockchains. In: Proceedings of the 13th International Conference on COMmunication Systems & NETworkS (COMSNETS). 2021, 254– 262
24	D, Guo M Li . Set reconciliation via counting bloom filters. IEEE Transactions on Knowledge and Data Engineering, 2013, 25( 10): 2367– 2380
25	D, Chen C, Konrad K, Yi W, Yu Q Zhang . Robust set reconciliation. In: Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, 2014, 135– 146
26	L, Luo D, Guo Y, Zhao O, Rottenstreich R T B, Ma X Luo . 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	M, Ruan T, Titcheu E, Zhai Z, Li Y, Liu E, Jinlong Y, Cui H Xu . On the synchronization bottleneck of openstack swift-like cloud storage systems. IEEE Transactions on Parallel and Distributed Systems, 2018, 29( 9): 2059– 2074
28	D Eppstein. Cuckoo filter: simplification and analysis. In: Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). 2016, 8

[1]

FCS-21685-OF-XD_suppl_1

Download

[1]	Jingsong SHAN,Yinjin FU,Guiqiang NI,Jianxin LUO,Zhaofeng WU. Fast counting the cardinality of flows for big traffic over sliding windows[J]. Front. Comput. Sci., 2017, 11(1): 119-129.

Viewed

Full text

Abstract

Cited

Shared

Discussed