基于树形结构构造的联盟链主从多链共识算法

doi:10.12263/DZXB.20201212

摘要/Abstract

摘要：

区块链构建了一种价值互联的去中心化网络，是继互联网之后的最具革命性和颠覆性的创新技术.但现有区块链存在性能低下，隐私保护不足，单层链式结构难以支持多种场景下数字资产的分类并发处理，单链共识算法难以实现多链乃至全局的一致性等问题.为解决上述问题，本文基于树形结构设计一种适用于联盟链场景的主从多链架构，可实现不同数字资产的分类、并发处理和达到数据隔离的隐私需求.针对该树形主从多链架构，进一步提出一个基于门限签名的改进拜占庭容错共识算法，可解决多样化数字资产分类并发处理带来的一致性问题.性能分析和仿真结果表明：所提方案在实现隐私数据隔离保护的同时，兼具高并发交易性能，通信复杂度由O（n²）降为O（n），可满足企业多样化业务需求.

长摘要
区块链构建了一种价值互联的去中心化网络，是继互联网之后的最具革命性和颠覆性的创新技术。但现有区块链存在性能低下、隐私保护不足，单层链式结构难以支持多种场景下数字资产的分类并发处理，单链共识算法难以实现多链乃至全局的一致性等问题。为解决上述问题，首先，本文设计一种适用于联盟链场景的主从多链架构，该架构基于树形结构对群组进行切分，并利用通道技术达到数据隔离的隐私需求；通过每个通道维护一条从链，所有通道共同维护一条主链，实现不同数字资产的分类处理；通过从链存储多样化交易内容，主链存储交易摘要，主从链通过哈希锁定的方式达到不可篡改和便于审计的目的；利用多个通道并行处理交易，解决现有区块链吞吐量低下和交易延迟过高等问题。然后，针对该树形结构的主从多链架构，设计基于门限签名的拜占庭容错共识算法解决多样化数字资产分类并发处理带来的一致性问题，以及设计视图转换协议将失效或作恶的父节点向底层叶子节点位置调动，并将底层叶子节点替换到父节点位置，以实现强有力的系统活性保障。最后，性能分析和仿真结果表明：所提方案具有良好的高并发交易性能，同时兼顾隐私数据的隔离保护，满足了企业多样化业务需求。

关键词: 联盟链, 主从多链, 树形结构, 拜占庭容错共识算法

Abstract:

Blockchain constructs a decentralized network of value interconnection, which is the most revolutionary and subversive innovation technology after the Internet. However, the existing blockchain has some problems, such as low performance, insufficient privacy protection, single-layer chain structure being difficult to support the classification and concurrent processing of digital assets in multiple scenarios, and single-chain consensus algorithm being difficult to achieve multi-chain and even global consistency. In order to solve the above problems, this paper first designs a master-slave multi-chain architecture based on tree structure, which can realize the classification and concurrent processing of different digital assets, and meet the privacy requirement of data isolation. Secondly, a Byzantine fault-tolerant consensus algorithm is designed based on threshold signature to solve the consistency problem in the tree-based master-slave multi-chains. Performance analysis and experimental results show that the the proposed scheme has high concurrency performance and good privacy protection for data isolation, and the communication complexity is reduced from O( $n 2$ ) to O(n) which can meet the diversified business needs of enterprises.

Extended Abstract
Blockchain constructs a decentralized network of value interconnection, which is the most revolutionary and subversive innovation technology after the Internet. However, the existing blockchain has some problems, such as low performance, insufficient privacy protection, single-layer chain structure is difficult to support the classification and concurrent processing of digital assets in multiple scenarios, and single-chain consensus algorithm is difficult to achieve multi-chain and even global consistency. In order to solve the above problems, this paper first designs a master-slave multi-chain architecture based on tree structure, which can meet the privacy requirements of data isolation by group segmentation and channel technology, can achieve classification and concurrent processing of different digital assets by the cooperation of master chain and slave chains to improve the system throughput, and can achieve the purpose of being tamper proof and easy to audit by means of hash locking of master chain and slave chains. Secondly, for the master-slave multi chain architecture of the tree structure, a Byzantine fault-tolerant consensus algorithm based on threshold signature is designed to solve the consistency problem caused by the concurrent processing of diversified digital asset classification, and then a view conversion protocol is proposed to transfer the invalid or evil parent node to the bottom leaf node location, and replace the bottom leaf node to the parent node location, so as to achieve a strong system activity guarantee. Performance analysis and experimental results show that the the proposed scheme has high concurrency performance and good privacy protection for data isolation, which can meet the diversified business needs of enterprises.

Key words: consortium chain, master-slave multi-chain, tree structure, Byzantine fault-tolerant consensus algorithm

中图分类号:

TP311

张文芳, 孙海锋, 张晏端, 唐荣骏, 王小敏, 马征, 李暄, 黄路非. 基于树形结构构造的联盟链主从多链共识算法[J]. 电子学报, 2022, 50(2): 257-266.

ZHANG Wen-fang, SUN Hai-feng, ZHANG Yan-duan, TANG Rong-jun, WANG Xiao-min, MA Zheng, LI Xuan, HUANG Lu-fei. A Consensus Algorithm for Consortium Chain with Tree Based Master-Slave Multi-Chain Architecture[J]. Acta Electronica Sinica, 2022, 50(2): 257-266.

图/表 6

参考文献 23

1	邵奇峰, 金澈清, 张召, 等. 区块链技术: 架构及进展[J]. 计算机学报, 2018, 41(5): 969-988.
	SHAO Q F, JIN C Q, ZHANG Z, et al. Blockchain: Architecture and research progress[J]. Chinese Journal of Computers, 2018, 41(5): 969-988. (in Chinese)
2	EFANOV D, ROSCHIN P. The all-pervasiveness of the blockchain technology[J]. Procedia Computer Science, 2018, 123: 116-121.
3	NAKAMOTO S. Bitcoin: A peer-to-peer electronic cash system[EB/OL]. (2008-11-01)[2022-01-17]. .
4	蔡维德, 郁莲, 王荣, 等. 基于区块链的应用系统开发方法研究[J]. 软件学报, 2017, 28(6): 1474-1487.
	TSAI W D, YU L, WANG R, et al. Blockchain application development techniques[J]. Journal of Software, 2017, 28(6): 1474-1487. (in Chinese)
5	POON J, DRYJA T. The bitcoin lightning network: Scalable off-chain instant payments[R/OL]. (2016-01-14)[2022-01-17]. .
6	EYAL I, GENER A E, SIRER E G . et al . Bitcoin-NG: A scalable blockchain protocol[C]//13th USENIX Symposium on Networked Systems Design and Implementation. Santa Clara, USA: USENIX, 2016: 45-59.
7	JAE K. Tendermint: Consensus without mining[R/OL]. (2014)[2022-01-17]. .
8	PASS, RAFAEL, ELAINE S. Hybrid consensus: Efficient consensus in the permissionless model[C]//31st International Symposium on Distributed Computing(DISC 2017). Vienna, Austria: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017: 39-55.
9	KOGIAS E K, JOVANOVIC P, GAILLY N, et al. Enhancing bitcoin security and performance with strong consistency via collective signing[C]//25th USENIX Security Symposium(USENIX Security 16). Austin, USA: USENIX ASSOC, 2016: 279-296.
10	PASS R, SHI E. Thunderella: Blockchains with optimistic instant confirmation[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. New York, USA: Springer, 2018: 3-33.
11	VASIN P. Blackcoin's proof-of-stake protocol v2[R/OL]. (2014-07-01)[2022-01-17]. .
12	FENG L B, ZHANG H, CHEN Y, et al. Scalable dynamic multi-agent practical Byzantine fault-tolerant consensus in permissioned blockchain[J]. Applied Sciences, 2018, 8(10): 1919.
13	GAO S, YU T Y, ZHU J M, et al. T-PBFT: An EigenTrust-based practical Byzantine fault tolerance consensus algorithm[J]. China Communications, 2019, 16(12): 111-123.
14	DU M X, CHEN Q J, MA X F. MBFT: A new consensus algorithm for consortium blockchain[J]. IEEE Access, 2020, 8: 87665-87675.
15	包振山, 王凯旋, 张文博. 基于树形拓扑网络的实用拜占庭容错共识算法[J]. 应用科学学报, 2020, 38(1): 34-50.
	BAO Z S, WANG K X, ZHANG W B. A practical Byzantine fault tolerance consensus algorithm based on tree topological network[J]. Journal of Applied Sciences, 2020, 38(1): 34-50. (in Chinese)
16	TSAI W T, BLOWER R, ZHU Y, et al. A system view of financial blockchains[C]//2016 IEEE Symposium on Service-Oriented System Engineering(SOSE). Oxford, UK: IEEE, 2016: 450-457.
17	BACKA A, CORALLO M, DASHJRET L, et al. Enabling blockchain innovations with pegged sidechains[R/OL]. (2014-10-22)[2022-01-17]. .
18	ROOTSTOCK. Sidechains, drivechains and RSK 2-way peg designs[EB/OL]. (2015)[2022-01-17]. .
19	SOUSA J, BESSANI A, VUKOLIC M. A Byzantine fault-tolerant ordering service for the hyperledger fabric blockchain platform[C]//Proceedings of the 1st Workshop on Scalable and Resilient Infrastructures for Distributed Ledgers. Las Vegas, Nevada, USA: ACM, 2017, 6: 1-2.
20	闵新平, 李庆忠, 孔兰菊, 等. 许可链多中心动态共识机制[J]. 计算机学报, 2018, 41(5): 1005-1020.
	MIN X P, LI Q Z, KONG L J, et al. Permissioned blockchain dynamic consensus mechanism based multi-centers[J]. Chinese Journal of Computers, 2018, 41(5):1005-1020. (in Chinese)
21	PARK C, KUROSAWA K. New Elgamal type threshold digital signature scheme[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 1996, 79(1): 86-93.
22	LESLIE L, ROBERT S, MARSHALL P. The Byzantine generals problem[J]. ACM Transactions on Programming Languages and Systems(TOPLAS), 1982, 4(3): 382-401.
23	WOOD GAVIN. Ethereum: A secure decentralised generalised transaction ledger[EB/OL]. (2014-01-14)[2022-01-17]. .

方案	架构	共识机制	容错率	去中心化程度	分叉	数据隔离	跨链处理	抗双花	通信复杂度
Bitcoin^［3］	单链	PoW	50%	完全	有	×	×	√
Bitcoin-NG^［6］	单链	PoW	50%	完全	有	×	×	√
Ethereum^［23］	单链	PoW	50%	完全	有	×	×	√
T-PBFT^［13］	单链	PBFT	50%	半去中心化	无	×	×	×	O（n²）
MBFT^［14］	单链	MBFT	33%	半去中心化	无	×	×	√	O（n）
文献［15］	单链	TTNPBFT	33%	半去中心化	无	×	×	√	O（n^k ）
Fabric^［19］	多链	PBFT	33%	半去中心化	无	√	×	√	O（n²）
文献［20］	多链	PBFT	33%	半去中心化	无	√	√	×	O（n²）
本方案	多链	*	33%	半去中心化	无	√	√	√	O（n）

方案	架构	共识机制	容错率	去中心化程度	分叉	数据隔离	跨链处理	抗双花	通信复杂度
Bitcoin^［3］	单链	PoW	50%	完全	有	×	×	√
Bitcoin-NG^［6］	单链	PoW	50%	完全	有	×	×	√
Ethereum^［23］	单链	PoW	50%	完全	有	×	×	√
T-PBFT^［13］	单链	PBFT	50%	半去中心化	无	×	×	×	O（n²）
MBFT^［14］	单链	MBFT	33%	半去中心化	无	×	×	√	O（n）
文献［15］	单链	TTNPBFT	33%	半去中心化	无	×	×	√	O（n^k ）
Fabric^［19］	多链	PBFT	33%	半去中心化	无	√	×	√	O（n²）
文献［20］	多链	PBFT	33%	半去中心化	无	√	√	×	O（n²）
本方案	多链	*	33%	半去中心化	无	√	√	√	O（n）

SDK接口名	接口功能	接口接收参数
open	开户	账户名、金额
transfer	转账	账户名、账户名、金额
delete	销户	账户名

SDK接口名	接口功能	接口接收参数
open	开户	账户名、金额
transfer	转账	账户名、账户名、金额
delete	销户	账户名

[1]	张帅, 高旻, 文俊浩, 熊庆宇, 唐旭. 基于自监督学习的去流行度偏差推荐方法[J]. 电子学报, 2022, 50(10): 2361-2371.
[2]	李雪莹, 王田路, 梁鹏, 王翀. 基于系统模型的用户评论中非功能需求的自动分类[J]. 电子学报, 2022, 50(9): 2079-2089.
[3]	王飞扬, 冀鹏欣, 孙笠, 危倩, 李根, 张忠宝. 一种基于深度学习的动态社交网络用户对齐方法[J]. 电子学报, 2022, 50(8): 1925-1936.
[4]	李辉, 张建朋, 陈福才. 基于流式分析的大规模网络重叠社区发现算法[J]. 电子学报, 2022, 50(8): 1951-1958.
[5]	钱忠胜, 宋佳, 俞情媛, 成轶伟, 孙志旺. 利用函数影响力的相似程序间测试用例重用与生成[J]. 电子学报, 2022, 50(7): 1696-1707.
[6]	曹阳, 高旻, 余俊良, 范琪琳, 荣文戈, 文俊浩. 基于双图混合随机游走的社会化推荐模型[J]. 电子学报, 2022, (): 1-11.
[7]	王飞扬, 冀鹏欣, 孙笠, 危倩, 李根, 张忠宝. 一种基于深度学习的动态社交网络用户对齐方法[J]. 电子学报, 0, (): 1-12.
[8]	刘杰, 游品鸿, 田明, 刘金凤. 基于局部投影的视差图像拼接平滑优化[J]. 电子学报, 2022, 50(6): 1451-1456.
[9]	李志博, 李清宝, 兰明敬, 孙剑帆. 基于镜像选择序优化的MART算法[J]. 电子学报, 2022, 50(2): 314-325.
[10]	范书平, 万里, 姚念民, 张岩, 马宝英. 基于关键用例获取的测试用例排序方法[J]. 电子学报, 2022, 50(1): 149-156.
[11]	柳菁, 李琪. DisHAP：基于层次亲和聚类的分布式大图划分算法[J]. 电子学报, 2021, 49(10): 2002-2011.
[12]	史先进, 曹爽, 张重生, 陶月锋, 吕灵灵, 沈夏炯. 基于锚点的字符级甲骨图像自动标注算法研究[J]. 电子学报, 2021, 49(10): 2020-2031.
[13]	王森, 王煜, 宁德军. 复杂软件系统健康状态智能感知与诊断模型[J]. 电子学报, 2021, 49(9): 1799-1808.
[14]	黄名选. 关联模式挖掘与词向量学习融合的伪相关反馈查询扩展[J]. 电子学报, 2021, 49(7): 1305-1313.
[15]	钱忠胜, 俞情媛, 宋涛, 朱懿敏, 祝洁, 赵畅. 基于支持向量机回归模型的测试用例生成与重用[J]. 电子学报, 2021, 49(7): 1386-1391.