ErlangShen: Efficient Transaction Execution Mechanism for Graphical Blockchain Based on Pipeline with Low Access Cost

XIAO Jiang; WU Enping; ZHANG Shijie; FU Zihao; JIN Hai

doi:10.11999/JEIT230874

Volume 46 Issue 5

May 2024

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2024 > 46(5): 2111-2121

XIAO Jiang, WU Enping, ZHANG Shijie, FU Zihao, JIN Hai. ErlangShen: Efficient Transaction Execution Mechanism for Graphical Blockchain Based on Pipeline with Low Access Cost[J]. Journal of Electronics & Information Technology, 2024, 46(5): 2111-2121. doi: 10.11999/JEIT230874

Citation:

XIAO Jiang, WU Enping, ZHANG Shijie, FU Zihao, JIN Hai. ErlangShen: Efficient Transaction Execution Mechanism for Graphical Blockchain Based on Pipeline with Low Access Cost[J]. Journal of Electronics & Information Technology, 2024, 46(5): 2111-2121. doi: 10.11999/JEIT230874

Citation:

XIAO Jiang, WU Enping, ZHANG Shijie, FU Zihao, JIN Hai. ErlangShen: Efficient Transaction Execution Mechanism for Graphical Blockchain Based on Pipeline with Low Access Cost[J]. Journal of Electronics & Information Technology, 2024, 46(5): 2111-2121. doi: 10.11999/JEIT230874

PDF( 3884 KB)

ErlangShen: Efficient Transaction Execution Mechanism for Graphical Blockchain Based on Pipeline with Low Access Cost

doi: 10.11999/JEIT230874

1.
National Engineering Research Center for Big Data Technology and System, Wuhan 430074, China
2.
Services Computing Technology and System Laboratory, Wuhan 430074, China
3.
Cluster and Grid Computing Laboratory, Wuhan 430074, China
4.
School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China

Funds: The National Key Research and Development Program of China (2021YFB2700700), The Key Research and Development Program of Hubei (2021BEA164)

Received Date: 2023-08-09
Rev Recd Date: 2023-11-03

Available Online: 2023-11-13

Publish Date: 2024-05-30

Abstract

Abstract

Directed Acyclic Graph(DAG)-based blockchain can significantly improve system performance and have become a research topic in both academia and industry. Compared with the traditional chain-based blockchains with serialization, DAG-based blockchains can process multiple blocks concurrently to package significant transactions into the chain. With the surge in transaction throughput, DAG-based blockchain faces the issue of low transaction execution efficiency, i.e., the demand for state data access for massive transaction execution increases dramatically, resulting in high Input/Output(I/O) overhead. Enabling low I/O state access mainly encounters two new challenges. On the one hand, if DAG-based blockchain directly adopts the traditional state prefetch mechanism, it will introduce a large number of stale reads due to inconsistent execution logic. On the other hand, state access for different accounts causes duplicate I/O overhead in the upper nodes of the Merkle tree. To this end, an efficient transaction execution mechanism based on pipelining—ErlangShen is designed, including the epoch granularity state prefetch mechanism and Merkle high-level path buffer mechanism to reduce the number of stale reads and duplicate I/O overhead, respectively. Specifically, ErlangShen leverages the complicated logic and severe conflicts of transactions accessing hotspot states to parallelize the execution of hotspot transactions and the prefetch of states accessed by cold transactions, to avoid the implication of the state prefetching on the transaction execution. Furthermore, the customized concurrency control methods is designed according to the data access pattern of hotspot and cold states to further improve the system throughput. Experimental results show that ErlangShen can reduce the number of stale reads by about 90% and improve transaction processing performance by 3～4 times compared to Nezha, the state-of-the-art DAG-based blockchain transaction processing solution.
- Blockchain,
- Directed Acyclic Graph (DAG)-based blockchain,
- Input/Output (I/O) optimization,
- Concurrency control,
- State trie

FullText(HTML)

References(32)

References

[1]	ZETZSCHE D A, ARNER D W, and BUCKLEY R P. Decentralized finance[J]. Journal of Financial Regulation, 2020, 6(2): 172–203. doi: 10.1093/jfr/fjaa010.
[2]	郝敏, 叶东东, 余荣, 等. 区块链赋能的6G零信任车联网可信接入方案[J]. 电子与信息学报, 2022, 44(9): 3004–3013. doi: 10.11999/JEIT220370. HAO Min, YE Dongdong, YU Rong, et al. Blockchain empowered trustworthy access scheme for 6G zero-trust vehicular networks[J]. Journal of Electronics & Information Technology, 2022, 44(9): 3004–3013. doi: 10.11999/JEIT220370.
[3]	张海波, 徐蓬勃, 王汝言, 等. 区块链下基于蛛网模型的新能源汽车能源交易机制研究[J]. 电子与信息学报. doi: 10.11999/JEIT221386. ZHANG Haibo, XU Pengbo, WANG Ruyan, et al. Research on energy trading mechanism of new energy vehicles based on cobweb model under blockchain[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT221386.
[4]	潘晨, 刘志强, 刘振, 等. 区块链可扩展性研究: 问题与方法[J]. 计算机研究与发展, 2018, 55(10): 2099–2110. doi: 10.7544/issn1000-1239.2018.20180440. PAN Chen, LIU Zhiqiang, LIU Zhen, et al. Research on scalability of blockchain technology: Problems and methods[J]. Journal of Computer Research and Development, 2018, 55(10): 2099–2110. doi: 10.7544/issn1000-1239.2018.20180440.
[5]	NAKAMOTO S. Bitcoin: A peer-to-peer electronic cash system[EB/OL]. https://bitcoin.org/bitcoin.pdf, 2023.
[6]	BAIRD L. The swirlds hashgraph consensus algorithm: Fair, fast, byzantine fault tolerance[EB/OL]. https://www.swirlds.com/downloads/SWIRLDS-TR-2016-01.pdf, 2016.
[7]	LEMAHIEU C. Nano: A feeless distributed cryptocurrency network[EB/OL]. https://content.nano.org/whitepaper/Nano_Whitepaper_en.pdf, 2018.
[8]	Taraxa whitepaper[EB/OL]. https://docs.taraxa.io/tech-whitepaper/abstract, 2023.
[9]	Aleph zero whitepaper[EB/OL]. https://docs.alephzero.org/aleph-zero/explore/whitepapers, 2023.
[10]	CHOI S M, PARK J, NGUYEN Q, et al. Fantom: A scalable framework for asynchronous distributed systems[EB/OL]. https://doi.org/10.48550/arXiv.1810.10360, 2018.
[11]	LI Chenxing, LI Peilun, ZHOU Dong, et al. A decentralized blockchain with high throughput and fast confirmation[C]. 2020 USENIX Annual Technical Conference, 2020: 515–528. https://www.usenix.org/conference/atc20/presentation/li-chenxing.
[12]	YU Haifeng, NIKOLIĆ I, HOU Ruomu, et al. OHIE: Blockchain scaling made simple[C]. 2020 IEEE Symposium on Security and Privacy, San Francisco, USA, 2020: 90–105. doi: 10.1109/SP40000.2020.00008.
[13]	XU Jie, CHENG Yingying, WANG Cong, et al. Occam: A secure and adaptive scaling scheme for permissionless blockchain[C]. 2021 IEEE 41st International Conference on Distributed Computing Systems, Washington, USA, 2021: 618–628. doi: 10.1109/ICDCS51616.2021.00065.
[14]	高政风, 郑继来, 汤舒扬, 等. 基于DAG的分布式账本共识机制研究[J]. 软件学报, 2020, 31(4): 1124–1142. doi: 10.3969/j.issn.1000-9825.2020.04.018. GAO Zhengfeng, ZHENG Jilai, TANG Shuyang, et al. State-of-the-art survey of consensus mechanisms on DAG-based distributed ledger[J]. Journal of Software, 2020, 31(4): 1124–1142. doi: 10.3969/j.issn.1000-9825.2020.04.018.
[15]	KEIDAR I, KOKORIS-KOGIAS E, NAOR O, et al. All you need is DAG[C]. 2021 ACM Symposium on Principles of Distributed Computing, Italy, 2021: 165–175. doi: 10.1145/3465084.3467905.
[16]	SPIEGELMAN A, GIRIDHARAN N, SONNINO A, et al. Bullshark: DAG BFT protocols made practical[C]. 2022 ACM SIGSAC Conference on Computer and Communications Security, Los Angeles, USA, 2022: 2705–2718. doi: 10.1145/3548606.3559361.
[17]	DANEZIS G, KOKORIS-KOGIAS L, SONNINO A, et al. Narwhal and tusk: A DAG-based mempool and efficient BFT consensus[C]. 17th European Conference on Computer Systems, Rennes, France, 2022: 34–50. doi: 10.1145/3492321.3519594.
[18]	陈友荣, 章阳, 陈浩, 等. 面向车联网异构节点的区块链高效一致性共识算法研究[J]. 电子与信息学报, 2022, 44(1): 314–323. doi: 10.11999/JEIT201065. CHEN Yourong, ZHANG Yang, CHEN Hao, et al. Efficient consistency consensus algorithm of blockchain for heterogeneous nodes in the internet of vehicles[J]. Journal of Electronics & Information Technology, 2022, 44(1): 314–323. doi: 10.11999/JEIT201065.
[19]	POPOV S. The tangle[EB/OL]. http://cryptoverze.s3.us-east-2.amazonaws.com/wp-content/uploads/2018/11/10012054/IOTA-MIOTA-Whitepaper.pdf, 2017.
[20]	SOMPOLINSKY V, LEWENBERG Y, and ZOHAR A. SPECTRE: A fast and scalable cryptocurrency protocol[J]. IACR Cryptology ePrint Archive, 2016, 2016: 1159.
[21]	BAGARIA V, KANNAN S, TSE D, et al. Prism: Deconstructing the blockchain to approach physical limits[C]. 2019 ACM SIGSAC Conference on Computer and Communications Security, London, UK, 2019: 585–602. doi: 10.1145/3319535.3363213.
[22]	WOOD G. Ethereum Yellow Paper: A formal specification of Ethereum, a programmable blockchain[EB/OL]. https://ethereum.github.io/yellowpaper/paper.pdf, 2023.
[23]	ANDROULAKI E, BARGER A, BORTNIKOV V, et al. Hyperledger fabric: A distributed operating system for permissioned blockchains[C]. 13th European Conference on Computer Systems, Porto, Portugal, 2018: 30. doi: 10.1145/3190508.3190538.
[24]	PENG Zeshun, ZHANG Yanfeng, XU Qian, et al. NeuChain: A fast permissioned blockchain system with deterministic ordering[J]. Proceedings of the VLDB Endowment, 2022, 15(11): 2585–2598. doi: 10.14778/35517 93.3551816.
[25]	KIM J Y, LEE J, KOO Y, et al. Ethanos: Efficient bootstrapping for full nodes on account-based blockchain[C]. 16th European Conference on Computer Systems, UK, 2021: 99–113. doi: 10.1145/3447786.3456231.
[26]	LI Chenxing, BEILLAHI S M, YANG Guang, et al. LVMT: An efficient authenticated storage for blockchain[C]. 17th USENIX Symposium on Operating Systems Design and Implementation, Boston, USA, 2023: 135–153.
[27]	PONNAPALLI S, SHAH A, BANERJEE S, et al. RainBlock: Faster transaction processing in public blockchains[C]. 2021 USENIX Annual Technical Conference, 2021: 333–347. https://www.usenix.org/conference/atc21/presentation/ponnapalli.
[28]	TAFT R, MANSOUR E, SERAFINI M, et al. E-store: Fine-grained elastic partitioning for distributed transaction processing systems[J]. Proceedings of the VLDB Endowment, 2014, 8(3): 245–256. doi: 10.14778/2735508.2735514.
[29]	XIAO Jiang, ZHANG Shijie, ZHANG Zhiwei, et al. Nezha: Exploiting concurrency for transaction processing in DAG-based blockchains[C]. IEEE 42nd International Conference on Distributed Computing Systems, Bologna, Italy, 2022: 269–279. doi: 10.1109/ICDCS54860.2022.00034.
[30]	THOMSON A, DIAMOND T, WENG Shuchun, et al. Calvin: Fast distributed transactions for partitioned database systems[C]. 2012 ACM SIGMOD International Conference on Management of Data, Scottsdale, USA, 2012: 1–12. doi: 10.1145/2213836.2213838.
[31]	CHEN Zhihao, QI Xiaodong, DU Xiaofan, et al. PEEP: A parallel execution engine for permissioned blockchain systems[C]. 26th International Conference on Database Systems for Advanced Applications, Taipei, China, 2021: 341–357. doi: 10.1007/978-3-030-73200-4_24.
[32]	Ethereum browser[EB/OL]. https://etherscan.io/chart/address, 2023.