基于“做市商账户”的区块链跨分片协议 —— BrokerChain

彭肖文,黄华威,2022年5月

论文信息:Huawei Huang, Xiaowen Peng, Jianzhou Zhan, Shenyang Zhang, Yue Lin, Zibin Zheng, Song Guo, “BrokerChain: A Cross-Shard Blockchain Protocol for Account/Balance-based State Sharding”, INFOCOM, May 5, 2022.

一、研究背景与动机

区块链是比特币、以太币等加密数字货币的底层基础技术,它综合利用了点对点(P2P)底层网络、分布式数据存储、密码学、分布式一致性共识机制、以及智能合约等计算机技术,构建出一个分布式存储的链式账本 [1][2]。区块链的底层架构为上层应用提供了存储、传输、计算等服务,具有去中心化、难以篡改、协同操作和匿名隐私等典型特征,有着较大的发展和应用前景。区块链主要应用于金融结算、商品溯源、版权保护、数据确权等业务场景 [3]。

然而,区块链底层技术仍处于初期探索阶段,还面临诸多问题和挑战 [4][5]。具体来讲,现有的区块链技术难以解决共识效率问题。例如,比特币的吞吐量为每秒 7 条交易、以太坊的吞吐量也仅为每秒 14 条交易,远低于商用级别所需的吞吐量要求。只有提高了区块链的可扩展性,才能扩大其适用场景,从而赋能数字经济、金融保险、政务等多个领域与行业。

针对区块链的可扩展性,研究人员提出了多种不同的技术方案,如闪电网络[6]、DAG技术[7]、状态通道[8]和分片机制[9]等。其中,分片(Sharding)是一种可提高区块链可扩展性的链上扩容技术。分片机制将完整的账本数据切分为多个互不相交的子账本,再让不同的区块链节点群(也称为分片)管理不同的子账本,多个分片可以并行验证交易,以此线性提升区块链系统的事务处理能力。

但是,区块链分片技术仍面临诸多挑战。如图1所示,基于账户模型的分片机制存在两个问题:第一个问题是跨分片交易比例过高,几乎所有交易均为跨分片交易。过高的跨分片交易率不仅给系统增加了额外的交易负载,而且会造成大量的跨分片通信开销。第二个问题是分片间的交易负载严重失衡,存在冷热不均的现象。我们分别称需要处理过量和少量交易的分片为热分片(Hot Shard)和冷分片(Cold Shard)。热分片由于被持续注入大量的交易,产生了交易拥挤的现象,这会增加交易的确认延迟。而冷分片内只有少量交易可以处理,所产生的区块的交易填充率不高,造成了算力、带宽等资源的浪费。面对如上两个问题,一个难题是如何保证跨分片交易比例较低的同时保证分片间的交易负载均衡。

(a)跨分片交易比例高
(b) 分片间的交易负载不均衡
图1  区块链分片技术的两大挑战

另一方面,在基于状态分片的区块链系统中,跨分片交易的验证和处理策略是至关重要的。系统需要支持分片间的通信,来保证跨分片交易执行的“原子性”。目前已有的比较高效的跨分片交易方案主要通过如图2所示的消息传递方式进行。首先,交易在源分片上链后,源分片的节点会向目标分片发送一个包含 Merkle Path 证明的中继消息。目标分片的节点接收到中继消息后,通过 Merkle Path 验证对应交易的正确上链情况,再在目标分片将关联交易上链,从而实现对相关区块链状态的更新。因为跨分片验证的存在,跨分片交易的延迟在理论上至少是片内交易时延的两倍。当位于目标分片内的关联交易迟迟无法上链时,跨分片交易的共识延迟有可能无限大。

图2  Monoxide [13] 采用“中继交易”来处理跨分片交易

为了减少跨分片交易比例、实现分片之间的负载均衡、并且保证跨分片交易的原子性,本文旨在提出一种新的跨分片协议来提高分片区块链的吞吐量和降低交易的平均确认延迟。

二、本文贡献

  • 本文提出了一套新的跨分片交易处理协议,通过引入“做市商账户”来减少跨分片交易的数量和加速跨分片交易的上链。而且,通过引入“双Nonce”机制和“部分时间状态锁”机制来防止双花交易,并保证跨分片交易的原子性。
  • 本文还提出了状态划分方案,代替分片区块链原本使用的静态状态划分策略。该分片划分方案根据一定时间内的历史交易信息构建一个账户交易状态图,并对其进行图划分。图划分的目标是平衡各个分片的交易量的同时最小化跨分片交易的数量。通过划分的结果,对每个分片内的账户状态进行动态的调整,从而缓解系统的单分片过热和跨分片交易比例过高的问题。

三、提出的跨分片协议简介

 1. 提出协议的概述

    本文提出的区块链动态分片协议的整体框架如图3所示。和传统的分片协议一样,所提出的动态分片协议以“时期 (Epoch)”为单位来运行。时期的定义为固定的片内交易共识轮次或者固定长度的时间。我们采用BFT类共识协议作为片内共识协议。在所提出的协议中,根据职能的不同,存在两种不同类型的分片:工作分片(Mining shard, M-shard)和划分分片(Partition shard, P-shard)。它们分别负责处理不同的事务,具体分工描述如下:

  • 工作分片。工作分片中的节点负责接收、验证和转发交易,并将通过片内共识协议,将合法的交易进行打包上链。工作分片所产生的包含交易的区块,称为交易区块(Transaction Block)。
  • 划分分片。划分分片中的节点负责同步工作分片中待确认的交易,并根据收集到的交易,执行给定的账户划分算法,并且维护更新后全局的账本状态。划分分片通过产生状态区块(State Block)来引导工作分片安全可靠地进行账户状态的转移和分片账本状态的更新。
图3  区块链动态分片协议整体框架

图3展示了本文所提出的跨分片协议的整体框架,包括4个关键步骤,具体描述如下:

  1. 工作分片持续接收、验证和转发客户端发送的交易信息,维护一个待上链确认的分片交易池。工作分片内的节点会通过共识协议,进行交易的验证和上链确认,产生相应的交易区块。同时,这些交易区块和待确认的交易池会被同步到划分分片中。
  2. 划分分片持续监听所有工作分片中的交易信息,构造账户交易网络并且执行Metis划分算法,对账户进行分片划分。
  3. 划分分片根据账户划分的结果,生成最新全局的分片区块链的状态信息。然后,主分片通过共识协议,记录相应的状态信息到区块中,生成相应的状态区块并且对该区块做上链共识。该状态区块会被同步到所有工作分片中。
  4. 工作分片根据状态区块中所记录的划分结果来更新自身分片的账本状态。区块链分片系统准备进入下一个时期。

2. 保障跨分片交易处理的有效性

    如图4所示,针对跨分片交易延迟高的问题,本文基于状态划分算法拟提出一种新的跨分片协议来缓解跨分片交易处理的效率问题。该协议的基本思路阐述如下:在进行状态划分的过程中,系统会同时招募一些特殊的充当中间人的账户,我们称这些特殊的账户为“做市商账户”。系统允许一部分普通用户通过自愿抵押一定的资产,选择充当做市商账户。做市商账户的状态会被系统分割成两部分或多个部分,分别存储在两个或多个分片中,从而参与到若干个跨分片交易的协调当中。做市商账户的协调机制可以减少基于转账类型的交易的跨分片通信,因此可以减少跨分片交易的延迟,从而提高跨分片交易执行的效率。

图4  基于做市商账户的机制加速跨分片交易的共识

图5展示了本文提出的跨分片协议对跨分片交易的执行原理与流程。本文在交易的数据结构中通过引入“部分状态时间锁”,从而实现跨分片交易的原子性执行。假设处于分片1的账户A给处于分片2的账户B发送一笔交易 $\Theta_raw$(如步骤1所示),中间做市商账户 C 会将原交易打包成另一个交易 $\Theta_1$,并广播到分片1(如步骤2所示)。分片1对交易 $\Theta_1$ 执行“AC转账并锁一定时间”操作并上链(如步骤3所示)。当中间商账户在一定时间内观察到交易 $\Theta_1$ 在分片1成功上链后,会向分片2广播交易 $\Theta_2$(如步骤4所示)。最后,步骤5中,分片2对交易 $\Theta_2$ 执行 “CB转账” 的操作并上链,从而最终实现一笔跨分片交易的执行。如果交易过程中因为某一方作恶或者超时,则执行中断操作:分片2会对 $\Theta_1$ 进行上链,并向分片1发送证明 $\gamma$,从而中断对跨分片交易的执行。

图5  保证跨分片交易原子性的流程

四、实验结果

实验设置:本文使用 python 搭建了一个分片区块链的仿真实验环境,实现了基于Metis图划分的分片调整和“做市商账户”跨分片交易机制。关于数据集,本文使用了以太坊从2015年8月7日至2016年2月13日的1,600,000条真实历史交易。在实验过程中,交易以一定的交易到达率被注入到各个分片中。每个分片的出块时间间隔设置为8秒,每个区块打包交易数量上限为2000条,分片数量为32个。实验测试了不同交易到达率和不同分片数量下的系统吞吐量和平均交易延迟。

主要实验结果:如图6所示,本文提出的分片协议与 Monoxide [13] 采取的分片机制相比,吞吐量最大提升150%,平均交易延迟降低70%;与基于负载均衡优先(Load Balance First,LBF)的动态分片调整协议相比,吞吐量最大提升10%,平均交易延迟降低40%。可见,与 Monoxide [13]提出的“中继交易”协议相比,本文提出的 BrokerChain 协议能够保证跨分片交易在较短的时间内完成,从而降低跨分片交易的交易延迟。

图6  吞吐量和平均交易延迟随交易到达率的变化

如图7所示,与基于Metis图划分方法相比,本文提出的机制可以将跨分片交易的比例进一步降低10%。

图7  跨分片交易比例 (分片数量为64)

五、提出的机制应用到工业界的前景分析

1. 块链分片机制的用前景

如今,区块链技术已经被诸多国家认可,各国加大了对区块链产业发展的布局,并争抢产业的制高点。我国也不断布局推动区块链产业的发展,2021 年我国发布了《指导意见》,进一步明确了区块链的发展目标,推动相关应用落地。近年来,国内头部企业纷纷推出自己的联盟链平台,如国产开源联盟链底层平台 FISCO BCOS [10]、蚂蚁链(AntChain)[11] 和华为云区块链 [12] 等。

联盟链的底层基础设施平台为上层应用提供了分布式存储、高效价值传输、分布式计算等服务,其发展状况已经成为推动区块链业务是否繁荣的关键因素。虽然联盟链技术已经有相关的落地场景,但大多局限于小规模的共识场景。现有的联盟链技术难以解决大规模共识节点和拥有大量交易的场景下的共识问题。只有提高了联盟链的可扩展性,才能更好地支撑其适用的大规模应用场景,从而赋能数字经济、数字政务等领域与行业。

本文提出的机制,针对面向广域网的大规模联盟链基础设施,采用分片技术实现提升区块链的可扩展性能。基于分片机制的联盟区块链是一个充满潜力的研究与应用方向。

2. 块链跨分片协议用前景分析

2021年初国家发布“十四五规划纲要”,指出区块链是赋能数字经济的重要基础设施。目前国内区块链领域是多链共存的现状,因此跨区块链平台实现数据与业务的高效交互十分必要。本文提出的基于做市商账户的跨分片协议,理论上可以扩展为跨链协议,它能为多个链之间提供一种简单、高效的跨链交易的服务。在跨链交易能够执行成功的情况下,可以大大减少跨链通信;在跨链交易执行失败的情况下,通过生成交易的失败证明,并执行资产回滚操作,来维护跨链交易的原子性和数字资产的全局状态一致性。

参考文献

[1] Nakamoto S. Bitcoin: A peer-to-peer electronic cash system[J]. Decentralized Business Review, 2008: 21260

[2] Wood G. Ethereum: A secure decentralised generalised transaction ledger[J]. Ethereum project yellow paper, 2014, 151(2014): 1-32

[3]中国工商银行金融科技研究院. 区块链金融应用发展白皮书[R/OL]. 2020. http://pdf.dfcfw.com/pdf/H3_AP202004261378665796_1.pdf

[4] Zheng Z, Xie S, Dai H N, et al. Blockchain challenges and opportunities: A survey[J]. International Journal of Web and Grid Services, 2018, 14(4):352-375

[5] 韩璇, 袁勇, 王飞跃, 等. 区块链安全问题: 研究现状与展望[J]. 自动化学报, 2019, 45(1):206-225

[6] Poon J, Dryja T. The bitcoin lightning network: Scalable off-chain instant payments[EB/OL].2022. https://www.bitcoinlightning.com/wp-content/uploads/2018/03/lightning-network-paper.pdf

[7] Pervez H, Muneeb M, Irfan M U, et al. A comparative analysis of dag-based blockchain architectures[C]//2018 12th International conference on open source systems and technologies(ICOSST). IEEE, 2018:27-34

[8] Dziembowski S, Faust S, Hostáková K. General state channel networks[C]//Proceedings of the2018 ACM SIGSAC Conference on Computer and Communications Security (CCS’18). ACM,2018:949-966

[9] Luu L, Narayanan V, Zheng C, et al. A secure sharding protocol for open blockchains[C]//Proc.of ACM SIGSAC Conference on Computer and Communications Security (CCS’16). ACM,2016:17-30

[10] Li H, Li C, Li H, et al. An overview on practice of fisco bcos technology and application[J].Information and Communications Technology and Policy, 2020, 46(1):52-60

[11] 蚂蚁链. https://antchain.antgroup.com/docs/11/101801

[12] 华为区块链白皮书2021,建设融合开放的数字经济基础设施 [R/OL]. 2021. https:// res-static.hc-cdn.cn/cloudbu-site/china/zh-cn/BCS/BCS__2.0.pdf

[13] J. Wang and H. Wang, “Monoxide: Scale-out blockchains with asynchronous consensus zones,” in Proc. of 16th USENIX Symposium on Networked Systems Design and Implementation (NSDI’19). Boston, MA: USENIX Association, Feb. 2019, pp. 95–112

(版权声明,转载请标明出处。)

联邦学习设备调度的论文被 ICDCS 2022 接收

黄华威,李瑞新,2022年4月6日

近日,HuangLab 在联邦学习设备调度方面的研究取得进展,论文《ContexFL: Context-aware Federated Learning by Estimating the Training and Reporting Phases of Mobile Clients》被分布式计算系统领域顶级学术会议 The 42nd IEEE International Conference on Distributed Computing Systems (ICDCS 2022) 录用为长文。

会议介绍

ICDCS 是分布式计算系统领域享有盛誉和具有重要学术影响力的顶级国际学术会议,本届 ICDCS 会议 Research Track 论文全球投稿共573篇,仅有114篇被录用,录用率为19.9%。

论文介绍

Huawei Huang, Ruixin Li, Jialiang Liu, Sicong Zhou, Kangying Lin, and Zibin Zheng, “ContextFL: Context-aware Federated Learning by Estimating the Training and Reporting Phases of Mobile Clients”, ICDCS, 2022.

在边缘计算的环境中,由于边缘网络的情况和各种物联设备的可用算力是频繁变化、波动较大的,跨设备的横向联邦学习的训练效果往往较大程度上受到设备的网络情况和可用计算资源的影响。传统的横向联邦学习设备调度方法着重考量当前设备的状态(网络、算力等),但面对网络和算力频繁变化、波动较大的环境之时,便难以维持联邦学习训练的稳定性与可靠性,从而造成联邦学习所训练的模型性能浮动较大的现象。

论文提出的 ContextFL 框架

本文针对上述现象,提供了一种可行的解决思路:为充分考虑边缘计算环境的不稳定性因素影响,本研究通过结合各设备当前以及预测的未来一段时间内的网络与算力状态进行设备调度,从而确保参与联邦学习的设备都是可靠的有效设备,以此提高边缘计算环境中联邦学习训练效果的稳定性与可靠性。