结合信誉跳跃一致性哈希的区块链分片协议

doi:10.3778/j.issn.1002-8331.2304-0414

摘要/Abstract

摘要： 区块链面临扩展性问题，目前主要的解决方法是采用分片技术提升交易的处理能力，但分片过后单个分片内节点数量降低，容易造成分片内中心化与拜占庭节点聚集，对网络的安全性产生危害。针对此问题，提出了一个结合信誉跳跃一致性哈希的区块链分片协议。设计了一种节点信誉等级模型，通过节点在网络中的行为赋予节点不同的信誉等级，降低拜占庭节点在网络中的话语权；提出了基于信誉的跳跃一致性哈希分片部分重构算法（reputation-based jump consistent hash sharding partial reconstruction，RJSPR），将信誉值作为节点进行分片重配置的重要考量，减少分片迁移的开销，并且有效提升分片后的网络安全性；提出了一种基于信誉的改进Raft共识算法（reputation-enhanced Raft，RERaft）用于片内共识，使其拥有一定程度的拜占庭容错能力。实验结果表明，RERaft算法在具备一定拜占庭容错能力的同时可以有效提升系统的共识效率，相比于常见的拜占庭容错算法，具有更好的可扩展性。

关键词: 区块链, 分片技术, 信誉机制, 跳跃一致性哈希, 共识协议

Abstract: Blockchain faces scalability issues, and the main solution currently is to use sharding to increase transaction processing capacity. However, the reduction in the number of nodes within a single shard after sharding can lead to centralization and gathering of Byzantine nodes within the shard, which can compromise network security. To address this issue, a sharding protocol that combines reputation and jump consistent hash for blockchain is proposed. Firstly, a node reputation level model is designed, which assigns different reputation levels to nodes based on their behavior in the network, thus reducing the influence of Byzantine nodes. Secondly, a reputation-based jump consistent hash sharding partial reconstruction algorithm (RJSPR) is proposed, which uses reputation values as an important consideration for shard reconfiguration, reducing the cost of shard migration and effectively improving the network security after sharding. Finally, a reputation-enhanced Raft consensus algorithm (RERaft) is proposed for in-shard consensus, which has a certain degree of Byzantine fault tolerance. Experimental results show that the RERaft algorithm can effectively improve the consensus efficiency of the system while possessing a certain degree of Byzantine fault tolerance. Compared to common Byzantine fault tolerant algorithms, it has better scalability.

Key words: blockchain, sharding technique, reputation mechanism, jump consistent hash, consensus protocol

宁宇豪, 黄建华, 顾彬, 张文韬, 宫在为. 结合信誉跳跃一致性哈希的区块链分片协议[J]. 计算机工程与应用, 2024, 60(16): 276-287.

NING Yuhao, HUANG Jianhua, GU Bin, ZHANG Wentao, GONG Zaiwei. Combining Reputation and Jump Consistent Hash for Blockchain Sharding Protocol[J]. Computer Engineering and Applications, 2024, 60(16): 276-287.

参考文献

[1] NAKAMOTO S. Bitcoin: a peer-to-peer electronic cash system[EB/OL]. (2008) [2022-04-02]. https://bitcoin.org/bitcoin.pdf.
[2] LAMPORT L, SHOSTAK R, PEASE M. The Byzantine generals problem[J]. ACM Transactions on Programming Languages and Systems, 1982, 4(3): 382-401.
[3] XIE J, TANG H, HUANG T, et al. A survey of blockchain technology applied to smart cities: research issues and challenges[J]. IEEE Communications Surveys & Tutorials, 2019, 21(3): 2794-2830.
[4] AZARIA A, EKBLAW A, VIEIRA T, et al. MedRec: using blockchain for medical data access and permission management[C]//Proceedings of the 2016 2nd International Conference on Open and Big Data, 2016: 25-30.
[5] ALI M S, VECCHIO M, PINCHEIRA M, et al. Applications of blockchains in the Internet of things: a comprehensive survey[J]. IEEE Communications Surveys & Tutorials, 2018, 21(2): 1676-1717.
[6] KORPELA K, HALLIKAS J, DAHLBERG T. Digital supply chain transformation toward blockchain integration[EB/OL]. (2017-01-04)[2022-04-02] http://hdl.handle.net/10125/41666.
[7] LUU L, NARAYANAN V, ZHENG C D, et al. A secure sharding protocol for open blockchains[C]//Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, 2016: 17-30.
[8] CORBETT J C, DEAN J, EPSTEIN M, et al. Spanner: Google’s globally distributed database[J]. ACM Transactions on Computer Systems, 2013, 31(3): 1-22.
[9] CHAUHAN A, MALVIYA O P, VERMA M, et al. Blockchain and scalability[C]//Proceedings of the 2018 IEEE International Conference on Software Quality, Reliability and Security Companion, 2018: 122-128.
[10] ZAMANI M，MOVAHEDI M，RAYKOVA M. RapidChain: scaling blockchain via full sharding[C]//Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, 2018: 931-948.
[11] SEN S，FREEDMAN M. Commensal cuckoo：secure group partitioning for large-scale services[J]. ACM SIGOPS Operating Systems Review, 2012, 46(1): 33-39.
[12] KOKORIS-KOGIAS E, JOVANOVIC P, GAS-SER L, et al. OmniLedger: a secure, scale-out, decentralized ledger via sharding[C]//Proceedings of the 2018 IEEE Symposium on Security and Privacy, 2018: 583-598.
[13] SZYDLO M. Merkle tree traversal in log space and time[C]//LNCS 3027: Proceedings of the 2004 International Conference on the Theory and Applications of Cryptographic Techniques, 2004: 541-554.
[14] WANG J, WANG H. Monoxide: scale out blockchains with asynchronous consensus zones[C]//Proceedings of the 16th USENIX Symposium on Networked Systems Design and Implementation, 2019: 95-112.
[15] 黄建华, 夏旭, 李忠诚, 等. 基于动态授权的信任度证明机制[J]. 软件学报, 2019, 30(9): 2593-2607.
HUANG J H, XIA X, LI Z C, et al. Proof of trust: mechanism of trust degree based on dynamic authorization[J]. Journal of Software, 2019, 30(9): 2593-2607.
[16] BUGDAY A, OZSOY A, OZTANER S M, et al. Creating consensus group using online learning based reputation in blockchain networks[J]. Pervasive and Mobile Computing, 2019, 59: 101056.
[17] 王梦楠, 黄建华, 邵兴辉, 等. 基于信誉的区块链分片共识方案[J]. 计算机科学, 2022, 49(10): 297-309.
WANG M N, HUANG J H, SHAO X H, et al. Reputation-based blockchain sharding consensus scheme[J]. Computer Science, 2022, 49(10): 297-309.
[18] HUANG B H, QU X, ZHENG H Y, et al. A credit-based Byzantine fault tolerance consensus algorithm[J]. Netinfo Security, 2022, 22(4): 86-92.
[19] ONGARO D, OUSTERHOUT J. In search of an understandable consensus algorithm[C]//Proceedings of the 2014 USENIX Annual Technical Conference, 2014: 305-319.
[20] LAMPORT L. Paxos made simple[J]. ACM SIGACT News, 2001, 32(4): 18-25.
[21] SABT M, ACHEMLAL M, BOUABDALLAH A. Trusted execution environment: what it is, and what it is not[C]//Proceedings of the 2015 IEEE Trustcom/BigDataSE/ISPA, 2015: 57-64.
[22] MARSH S P. Formalising trust as a computational concept [D]. Scotland: University of Stirling, 1994.
[23] LEE B, JEONG Y, SONG H, et al. A scalable and highly available network management architecture on consistent hashing[C]//Proceedings of the 2010 IEEE Globecom, 2010.
[24] MARSAGLIA G. Random numbers fall mainly in the planes[J]. Proceedings of the National Academy of Sciences, 1968, 61(1): 25-28.
[25] AMIRI M J, AGRAWAL D, El ABBADI A. Sharper: sharding permissioned blockchains over network clusters[C]//Proceedings of the 2021 International Conference on Management of Data, 2021: 76-88.