Journal Home > Volume 27 , Issue 5
Tsinghua Science and Technology 2022, 27(5): 817-831 https://doi.org/10.26599/TST.2021.9010065
Open Access | Issue | Published: 17 March 2022

Distributed Consensus for Blockchains in Internet-of-Things Networks

Show Author's Information Li Yang( ),  Yifei Zou( ),  Minghui Xu,  Yicheng Xu,  Dongxiao Yu,  Xiuzhen Cheng
School of Computer Science and Technology, Shandong University, Qingdao 266237, China
Shenzhen Institute of Advanced Technology, Chinese Academy of Sciences, Shenzhen 518055, China
Keywords:
Internet-of-Things (IoT), distributed algorithm, consensus in blockchain, SINR model
Cite this article:
Yang L, Zou Y, Xu M, et al. Distributed Consensus for Blockchains in Internet-of-Things Networks. Tsinghua Science and Technology, 2022, 27(5): 817-831. https://doi.org/10.26599/TST.2021.9010065
Download citation
EndNote(RIS)
BibTeX

673

Views

100

Downloads

Citations

21

Crossref

16

WoS

21

Scopus

2

CSCD

Abstract Full text About this article

In recent years, due to the wide implementation of mobile agents, the Internet-of-Things (IoT) networks have been applied in several real-life scenarios, servicing applications in the areas of public safety, proximity-based services, and fog computing. Meanwhile, when more complex tasks are processed in IoT networks, demands on identity authentication, certifiable traceability, and privacy protection for services in IoT networks increase. Building a blockchain system in IoT networks can greatly satisfy such demands. However, the blockchain building in IoT brings about new challenges compared with that in the traditional full-blown Internet with reliable transmissions, especially in terms of achieving consensus on each block in complex wireless environments, which directly motivates our work. In this study, we fully considered the challenges of achieving a consensus in a blockchain system in IoT networks, including the negative impacts caused by contention and interference in wireless channel, and the lack of reliable transmissions and prior network organizations. By proposing a distributed consensus algorithm for blockchains on multi-hop IoT networks, we showed that it is possible to directly reach a consensus for blockchains in IoT networks, without relying on any additional network layers or protocols to provide reliable and ordered communications. In our theoretical analysis, we showed that our consensus algorithm is asymptotically optimal on time complexity and is energy saving. The extensive simulation results also validate our conclusions in the theoretical analysis.


menu
Abstract
Full text
Outline
About this article

Distributed Consensus for Blockchains in Internet-of-Things Networks

Show Author's information Li Yang( ), Yifei Zou( ), Minghui Xu, Yicheng Xu, Dongxiao Yu, Xiuzhen Cheng
School of Computer Science and Technology, Shandong University, Qingdao 266237, China
Shenzhen Institute of Advanced Technology, Chinese Academy of Sciences, Shenzhen 518055, China

Abstract

In recent years, due to the wide implementation of mobile agents, the Internet-of-Things (IoT) networks have been applied in several real-life scenarios, servicing applications in the areas of public safety, proximity-based services, and fog computing. Meanwhile, when more complex tasks are processed in IoT networks, demands on identity authentication, certifiable traceability, and privacy protection for services in IoT networks increase. Building a blockchain system in IoT networks can greatly satisfy such demands. However, the blockchain building in IoT brings about new challenges compared with that in the traditional full-blown Internet with reliable transmissions, especially in terms of achieving consensus on each block in complex wireless environments, which directly motivates our work. In this study, we fully considered the challenges of achieving a consensus in a blockchain system in IoT networks, including the negative impacts caused by contention and interference in wireless channel, and the lack of reliable transmissions and prior network organizations. By proposing a distributed consensus algorithm for blockchains on multi-hop IoT networks, we showed that it is possible to directly reach a consensus for blockchains in IoT networks, without relying on any additional network layers or protocols to provide reliable and ordered communications. In our theoretical analysis, we showed that our consensus algorithm is asymptotically optimal on time complexity and is energy saving. The extensive simulation results also validate our conclusions in the theoretical analysis.

Keywords: Internet-of-Things (IoT), distributed algorithm, consensus in blockchain, SINR model

References(40)

[1]
A. Zanella, N. Bui, A. Castellani, L. Vangelista, and M. Zorzi, Internet of things for smart cities, IEEE Internet Things J., vol. 1, no. 1, pp. 22–32, 2014.
DOI Google Scholar
[2]
S. Huckle, R. Bhattacharya, M. White, and N. Beloff, Internet of things, blockchain and shared economy applications, Procedia Comput. Sci., vol. 98, pp. 461–466, 2016.
DOI Google Scholar
[3]
O. Novo, Blockchain meets IoT: An architecture for scalable access management in IoT, IEEE Internet Things J., vol. 5, no. 2, pp. 1184–1195, 2018.
DOI Google Scholar
[4]
Q. Xu, Y. F. Zou, D. X. Yu, M. H. Xu, S. K. Shen, and F. Li, Consensus in wireless blockchain system, in Proc. 15th Int. Conf. Wireless Algorithms, Systems, and Applications, Qingdao, China, 2020, pp. 568–579.
DOI
[5]
Z. P. Cai and Q. Chen, Latency-and-coverage aware data aggregation scheduling for multihop battery-free wireless networks, IEEE Trans. Wirel. Commun., vol. 20, no. 3, pp. 1770–1784, 2021.
DOI Google Scholar
[6]
J. W. T. Chan, F. Y. L. Chin, D. S. Ye, and Y. Zhang, Online frequency allocation in cellular networks, in Proc. 19th Annu. ACM Symp. Parallel Algorithms and Architectures, San Diego, CA, USA, 2007, pp. 241–249.
DOI
[7]
W. T. Chan, Y. Zhang, S. P. Y. Fung, D. S. Ye, and H. Zhu, Efficient algorithms for finding a longest common increasing subsequence, in Proc. 16th Int. Symp. Algorithms and Computation, Sanya, China, 2005, pp. 665–674.
DOI
[8]
D. X. Yu, Q. S. Hua, Y. X. Wang, and F. C. M. Lau, An O(log n) distributed approximation algorithm for local broadcasting in unstructured wireless networks, presented at the 2012 IEEE 8th Int. Conf. Distributed Computing in Sensor Systems, Hangzhou, China, 2012, pp. 132–139.
DOI
[9]
Q. Chen, Z. P. Cai, L. L. Cheng, and H. Gao, Structure-free general data aggregation scheduling for multihop battery-free wireless networks, IEEE Trans. Mob. Comput., .
DOI Google Scholar
[10]
J. Li, A. M. V. V. Sai, X. Z. Cheng, W. Cheng, Z. Tian, and Y. S. Li, Sampling-based approximate skyline query in sensor equipped IoT networks, Tsinghua Science and Technology, vol. 26, no. 2, pp. 219–229, 2021.
DOI Google Scholar
[11]
J. Li, M. Siddula, X. Z. Cheng, W. Cheng, Z. Tian, and Y. S. Li, Approximate data aggregation in sensor equipped IoT networks, Tsinghua Science and Technology, vol. 25, no. 1, pp. 44–55, 2020.
DOI Google Scholar
[12]
D. X. Yu, Y. F. Zou, Y. X. Wang, J. G. Yu, X. Z. Cheng, and F. C. M. Lau, Implementing the abstract MAC layer via inductive coloring under the Rayleigh-fading model, IEEE Trans. Wirel. Commun., vol. 20, no. 9, pp. 6167–6178, 2021.
DOI Google Scholar
[13]
D. X. Yu, Y. F. Zou, M. H. Xu, Y. C. Xu, Y. Zhang, B. Gong, and X. S. Xing, Competitive age of information in dynamic IoT networks, IEEE Internet Things J., vol. 8, no. 20, pp. 15160–15169, 2021.
DOI Google Scholar
[14]
Y. Zhang, J. C. Chen, F. Y. L. Chin, X. Han, H. F. Ting, and Y. H. Tsin, Improved online algorithms for 1-space bounded 2-dimensional bin packing, in Proc. 21st Int. Symp. Algorithms and Computation, Jeju, Korea, 2010, pp. 242–253.
DOI
[15]
S. King and S. Nadal, PPcoin: Peer-to-peer crypto-currency with proof-of-stake, https://decred.org/ research/king2012.pdf, 2012.
[16]
Bitcoinwiki, Proof of stake, https://en.bitcoin.it/wiki/Proof_of_Stake, 2014.
[17]
S. Dziembowski, S. Faust, V. Kolmogorov, and K. Pietrzak, Proofs of space, in Proc. 35th Annu. Cryptology Conf., Santa Barbara, CA, USA, 2015, pp. 585–605.
DOI
[18]
W. T. Chan, Y. Zhang, S. P. Y. Fung, D. S. Ye, and H. Zhu, Efficient algorithms for finding a longest common increasing subsequence, J. Comb. Optim., vol. 13, no. 3, pp. 277–288, 2007.
DOI Google Scholar
[19]
D. X. Yu, L. Ning, Y. F. Zou, J. G. Yu, X. Z. Cheng, and F. C. M. Lau, Distributed spanner construction with physical interference: constant stretch and linear sparseness, IEEE/ACM Trans. Netw., vol. 25, no. 4, pp. 2138–2151, 2017.
DOI Google Scholar
[20]
Y. Xiao, N. Zhang, W. J. Luo, and Y. T. Hou, Modeling the impact of network connectivity on consensus security of proof-of-work blockchain, presented at the IEEE INFOCOM 2020—IEEE Conf. Computer Communications, Toronto, Canada, 2020, pp. 1648–1657.
DOI
[21]
I. Bentov, C. Lee, A. Mizrahi, and M. Rosenfeld, Proof of activity: Extending Bitcoin’s proof of work via proof of stake [extended abstract] y, ACM SIGMETRICS Performance Evaluation Review, vol. 42, no. 3, pp. 34–37, 2014.
DOI Google Scholar
[22]
S. Nakamoto, Bitcoin: A peer-to-peer electronic cash system, https://bitcoin.org/bitcoin.pdf, 2008.
[23]
K. J. O’Dwyer and D. Malone, Bitcoin mining and its energy footprint, presented at the 25th IET Irish Signals & Systems Conf. 2014 and 2014 China-Ireland Int. Conf. Information and Communications Technologies (ISSC 2014/CIICT 2014), Limerick, Ireland, 2014, pp. 280–285.
DOI
[24]
J. Bonneau, A. Miller, J. Clark, A. Narayanan, J. A. Kroll, and E. W. Felten, SoK: Research perspectives and challenges for Bitcoin and Cryptocurrencies, presented at the 2015 IEEE Symp. Security and Privacy, San Jose, CA, USA, 2015, pp. 104–121.
DOI
[25]
A. Kiayias, A. Russell, B. David, and R. Oliynykov, Ouroboros: A provably secure proof-of-stake blockchain protocol, in Proc. 37th Annu. Int. Cryptology Conf., Santa Barbara, CA, USA, 2017, pp. 357–388.
DOI
[26]
P. Gaži, A. Kiayias, and A. Russell, Stake-bleeding attacks on proof-of-stake blockchains, presented at the 2018 Crypto Valley Conf. Blockchain Technology (CVCBT), Zug, Switzerland, 2018, pp. 85–92.
DOI
[27]
M. F. Yin, D. Malkhi, M. K. Reiter, G. G. Gueta, and I. Abraham, HotStuff: BFT consensus with linearity and responsiveness, in Proc. 2019 ACM Symp. Principles of Distributed Computing, Toronto, Canada, 2019, pp. 347–356.
DOI
[28]
M. Castro and B. Liskov, Practical byzantine fault tolerance, in Proc. 3rd Symp. Operating Systems Design and Implementation, New Orleans, LA, USA, 1999, pp. 173–186.
[29]
W. T. Chan, F. Y. L. Chin, D. S. Ye, G. C. Zhang, and Y. Zhang, On-line scheduling of parallel jobs on two machines, J. Discrete Algorithms, vol. 6, no. 1, pp. 3–10, 2008.
DOI Google Scholar
[30]
F. Y. L. Chin, B. Fu, J. L. Guo, S. G. Han, J. L. Hu, M. H. Jiang. G. H. Lin, H. F. Ting, L. P. Zhang, Y. Zhang, et al., Competitive algorithms for unbounded one-way trading, Theor. Comput. Sci., vol. 607, pp. 35–48, 2015.
DOI Google Scholar
[31]
X. Y. Fan, M. Z. Dai, C. X. Liu, F. Wu, X. D. Yan, Y. Feng, Y. Q. Feng, and B. Q. Su, Effect of image noise on the classification of skin lesions using deep convolutional neural networks, Tsinghua Science and Technology, vol. 25, no. 3, pp. 425–434, 2020.
DOI Google Scholar
[32]
Z. Y. Hu, D. S. Li, and D. K. Guo, Balance resource allocation for spark jobs based on prediction of the optimal resource, Tsinghua Science and Technology, vol. 25, no. 4, pp. 487–497, 2020.
DOI Google Scholar
[33]
D. X. Yu, Y. F. Zou, J. G. Yu, X. Z. Cheng, Q. S. Hua, H. Jin, and F. C. M. Lau, Stable local broadcast in multihop wireless networks under SINR, IEEE/ACM Trans. Netw., vol. 26, no. 3, pp. 1278–1291, 2018.
DOI Google Scholar
[34]
D. X. Yu, Y. F. Zou, J. G. Yu, Y. Zhang, F. Li, X. Z. Cheng, F. Dressler, and F. C. M. Lau, Implementing the abstract MAC layer in dynamic networks, IEEE Trans. Mob. Comput., vol. 20, no. 5, pp. 1832–1845, 2021.
DOI Google Scholar
[35]
D. X. Yu, Y. F. Zou, Y. Zhang, F. Li, J. G. Yu, Y. Wu, X. Z. Cheng, and F. C. M. Lau, Distributed dominating set and connected dominating set construction under the dynamic SINR model, presented at the 2019 IEEE Int. Parallel and Distributed Processing Symp. (IPDPS), Rio de Janeiro, Brazil, 2019, pp. 835–844.
DOI
[36]
D. X. Yu, Y. F. Zou, Y. Zhang, H. Sheng, W. F. Lv, and X. Z. Cheng, An exact implementation of the abstract MAC layer via carrier sensing in dynamic networks, IEEE/ACM Trans. Netw., vol. 29, no. 3, pp. 994–1007, 2021.
DOI Google Scholar
[37]
Y. F. Zou, M. H. Xu, H. Sheng, X. S. Xing, Y. C. Xu, and Y. Zhang, Crowd density computation and diffusion via internet of things, IEEE Internet Things J., vol. 7, no. 9, pp. 8111–8121, 2020.
DOI Google Scholar
[38]
Y. F. Zou, D. X. Yu, L. B. Wu, J. G. Yu, Y. Wu, Q. S. Hua, and F. C. M. Lau, Fast distributed backbone construction despite strong adversarial jamming, presented at the IEEE INFOCOM 2019—IEEE Conf. Computer Communications, Paris, France, 2019, pp. 1027–1035.
DOI
[39]
C. Dwork, N. Lynch, and L. Stockmeyer, Consensus in the presence of partial synchrony (preliminary version), in Proc. 3rd Annu. ACM Symp. Principles of Distributed Computing, Vancouver, Canada, 1984, pp. 103–118.
[40]
J. Schneider and R. Wattenhofer, What is the use of collision detection (in wireless networks), in Proc. 24th Int. Symp. Distributed Computing, Cambridge, MA, USA, 2010, pp. 133–147.
DOI
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 14 June 2021
Revised: 25 July 2021
Accepted: 18 August 2021
Published: 17 March 2022
Issue date: October 2022

Copyright

© The author(s) 2022.

Acknowledgements

This work was partially supported by the National Key Research and Development Program of China (No. 2020YFB1005900) and the National Natural Science Foundation of China (NSFC) (Nos. 6212200494, 61971269, and 6210070740).

Rights and permissions

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Return