An Optimal Stability Matching Algorithm for DAG Blockchain Based on Matching Theory

XIA Xu; HUANG Jianhua; ZHENG Hong; TANG Ruicong

doi:10.1049/cje.2021.01.010

Volume 30 Issue 2

Apr. 2021

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2021 > 30(2): 367-377

XIA Xu, HUANG Jianhua, ZHENG Hong, et al., “An Optimal Stability Matching Algorithm for DAG Blockchain Based on Matching Theory,” Chinese Journal of Electronics, vol. 30, no. 2, pp. 367-377, 2021, doi: 10.1049/cje.2021.01.010

Citation:

XIA Xu, HUANG Jianhua, ZHENG Hong, et al., “An Optimal Stability Matching Algorithm for DAG Blockchain Based on Matching Theory,” Chinese Journal of Electronics, vol. 30, no. 2, pp. 367-377, 2021, doi: 10.1049/cje.2021.01.010

Citation:

PDF( 7268 KB)

An Optimal Stability Matching Algorithm for DAG Blockchain Based on Matching Theory

doi: 10.1049/cje.2021.01.010

XIA Xu^1
,,
HUANG Jianhua^{1
,
,},
ZHENG Hong^1
,,
TANG Ruicong^2
,

1.
East China University of Science and Technology, Shanghai 200237, China
2.
Hong Kong DAEX Blockchain Limited, Hong Kong 999077, China

Funds:

the National Science Foundation of China 61472139

the Shanghai Science and Technology Commission 11511504403

More Information

Author Bio:
XIA Xu   was born in Jiangsu, China. He is working on his master degree with the School of Information Science and Engineering of East China University of Science and Technology, Shanghai, China. His research interests are in the general area of distributed system and blockchain.(Email: skj865@outlook.com)

HONG Zheng   received her Ph.D. degree in computer software and theory from Chinese Academy of Science, China in 2003. She joined East China University of Science and Technology, China in 2003, where she is currently an Associate Professor in the Department of the Computer Science and Engineering. Her research interests include pervasive computing, system modelling and analysis, blockchains.(Email: zhenghong@ecust.edu.cn)

TANG Ruicong   received the M.E. degree in software engineering from Zhejiang University. His research interests include fintech and blockchain technology, focusing on supply chain finance, sharding and cross-chain tech-nology, distributed network. He has held several blockchain patents.(Email: ruicongtang@zju.edu.cn)
Corresponding author: HUANG Jianhua (corresponding author) was born in Guizhou, China. He had received the B.S., M.S., and Ph.D. degrees from East China University of Science and Technology. He has served as Associate Professor of computer science and engineering at East China University of Science and Technology since 1998. His research interests include computer networks, IoTs, blockchains, and data mining. He is a member of blockchain branch of Chinese Institute of Electronics. (Email: jhhuang@ecust.edu.cn)
Received Date: 2019-11-04
Accepted Date: 2020-06-20
Publish Date: 2021-03-01

Abstract

Abstract

IOTA is a typical blockchain designed for IoT applications. The Markov chain monte carlo algorithm (MCMC) used in IOTA may lead to a large number of unverified blocks, which increases transaction delay to a certain extent. We propose a Stable matching algorithm (SMA) based on matching theory to stimulate nodes to verify blocks, thereby reducing the number of unverified blocks and the consensus delay. The structure of our IoT blockchain uses the Directed acyc1ic graph (DAG) to improve the transaction processing capability. The nodes in the network are abstracted as transaction issuers and transaction verifiers. A verification service scheduling system is used to assign transactions to the verifiers and achieve the optimal matching. We designed a trust evaluation mechanism which offers verifiers references and awards to check transactions. The simulation results show that SMA can significantly reduce the number of orphan blocks and improve the transaction throughput, which helps to improve the reliability of the IoT blockchain.
- Blockchain,
- Consensus algorithm,
- Game theory,
- Directed acyc1ic graph (DAG)

FullText(HTML)

References(26)

References

[1]	D. Lund, C. MacGillivray, V. Turner, et al., "Worldwide and regional internet of things (IoT) 2014-2020 forecast: A virtuous circle of proven value and demand", https://www.business.att.com/, 2014-5-1.
[2]	Z. Zheng, S. Xie and H.N. Dai, "Blockchain challenges and opportunities: A survey", International Journal of Web and Grid Services, Vol. 14, No. 4, pp. 352-375, 2018. doi: 10.1504/IJWGS.2018.095647
[3]	I.C. Lin and T.C. Liao, "A survey of blockchain security issues and challenges", International Journal of Network Security, Vol. 19, No. 5, pp. 653-659, 2017.
[4]	A. Dorri, S.S. Kanhere and R. Jurdak, "LSB: A lightweight scalable blockchain for IoT security and anonymity". Journal of Parallel and Distributed Computing, Vol. 134, pp. 180-197, 2019. doi: 10.1016/j.jpdc.2019.08.005
[5]	S. Huh, S. Cho and S. Kim, "Managing IoT devices using blockchain platform", In: Proceedings of the IEEE 19th International Conference on Advanced Communication Technology (ICACT), Bongpyeong, Korea, pp. 464-467, 2017.
[6]	X.T. Ma, W.P. Ma and X.X. Liu, "A cross domain authentication scheme based on blockchain technology", Acta Electronica Sinica, Vol. 46, No. 11, pp. 2571-2579, 2018. http://en.cnki.com.cn/Article_en/CJFDTOTAL-JSJY201802005.htm
[7]	J. Sun and G. Xiong, "Credit payment for radio resources transactions based on consortium blockchain in SCMA mMTC", Acta Electronica Sinica, Vol. 47, No. 8, pp. 1677-1684, 2019. (in Chinese) http://en.cnki.com.cn/Article_en/CJFDTotal-DZXU201908010.htm
[8]	I. Makhdoom, M. Abolhasan, H. Abbas, et al., "Blockchain's adoption in IoT: The challenges, and a way forward", Journal of Network and Computer Applications, Vol. 125, pp. 251-279, 2019. doi: 10.1016/j.jnca.2018.10.019
[9]	K. Karlsson, W. Jiang, S. Wicker, et al., "Vegvisir: A partition-tolerant blockchain for the internet-of-things", 2018 IEEE 38th International Conference on Distributed Computing Systems (ICDCS), Vienna, Austria, pp. 1150-1158, 2018.
[10]	S. Nakamoto, "Bitcoin: A peer-to-peer electronic cash system", Self-published Paper, Vol. 1, No. 1, 2008. http://www.researchgate.net/publication/235927522_Bitcoin_A_Peer-to-Peer_Electronic_Cash_System
[11]	I. Eyal, A.E. Gencer, E.G. Sirer, et al., "Bitcoin-ng: A scalable blockchain protocol", 13th symposium on Networked Systems Design and Implementation (NSDI'16), Santa Clara, CA, USA, pp. 45-59, 2016.
[12]	S. King and S. Nadal, "Ppcoin: Peer-to-peer crypto-currency with proof-of-stake", Self-published Paper, Vol. 1, No. 1, 2012. http://www.researchgate.net/publication/265116876_PPCoin_Peer-to-Peer_Crypto-Currency_with_Proof-of-Stake
[13]	M. Castro, "A correctness proof for a practical byzantine-fault-tolerant replication algorithm", Ph. D. Thesis, Massachusetts Institute of Technology, Cambridge, MA, USA, 1999.
[14]	Z.W. Zhang, "A byzantine fault-tolerant algorithm for blockchains", http://docs.neo.org/zh-cn/basic/consensus/whitepaper.html, 2019-8-15.
[15]	A. Miller, Y. Xia, K. Croman, et al., "The honey badger of BFT protocols", Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, pp. 31-42, 2016.
[16]	E. Buchman, "Tendermint: Byzantine fault tolerance in the age of blockchains", https://tendermint.com/static/docs/tendermint.pdf, 2019-8-1.
[17]	J.L. Gross, J. Yellen and P. Zhang, Handbook of Graph Theory, CRC Press, Boca Raton, USA, pp. 180-195, 2013.
[18]	M. Zander, T. Waite, D. Harz, et al., "DAGsim: Simulation of DAG-based distributed ledger protocols", Measurement and Modeling of Computer Systems, Vol. 46, No. 3, pp. 118-121, 2019. http://www.researchgate.net/publication/330693364_DAGsim_Simulation_of_DAG-based_distributed_ledger_protocols
[19]	S. D. Lerner, "DagCoin: A cryptocurrency without blocks", White Paper, DagCoin-v4, https://dagcoin.org/wp-content/uploads/2019/07/Dagcoin_White_Paper.pdf, 2018-05-14.
[20]	S. Popov, "The tangle", https://www.iota.org/foundation/research-papers, 2019-8-1.
[21]	E. Heilman, N. Narula, T. Dryja, et al., "Cryptanalysis of Curl-P and Other Attacks on the IOTA Cryptocurrency", https://eprint.iacr.org/2019/344.pdf, 2019-8-31.
[22]	A. Churyumov, "Byteball: A decentralized system for storage and transfer of value", https://byteball.org/Byteball.pdf, 2019-8-31.
[23]	D. Gale and L.S. Shapley, "College admissions and the stability of marriage", The American Mathematical Monthly, Vol. 69, No. 1, pp. 9-15, 1962. doi: 10.1080/00029890.1962.11989827
[24]	Z. Zhang, T. Zeng, X. Yu, et al., "Social-aware D2D pairing for cooperative video transmission using matching theory", Mobile Networks & Applications, Vol. 23, No. 3, pp. 639-649, 2018. http://smartsearch.nstl.gov.cn/paper_detail.html?id=2b85288c9b191d7fc956c8c8acdaacf1
[25]	A. Zappone, L. Sanguinetti, G. Bacci, et al., "Energy-efficient power control: A look at 5G wireless technologies", IEEE Transactions on Signal Processing, Vol. 64, No. 7, pp. 1668-1683, 2015. http://ieeexplore.ieee.org/document/7328326/
[26]	M. Zeng, S. Leng and Y. Zhang, "Power charging and discharging scheduling for V2G networks in the smart grid", 2013 IEEE International Conference on Communications Workshops (ICC), Budapest, Hungary, pp. 1052-1056, 2013.