基于“做市商账户”的区块链跨分片协议 —— 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

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

Web3、DAO、与区块链 | Apr27话题

By 黄华威,2022年4月27日

早上起床翻看朋友圈,读到一篇最新的关于 Web3 的文章,题目为《Web3革命:逃离、信仰、大迁徙》,发表在虎嗅网。然后冲泡咖啡时,找了一些 Web3 的播客,听了几个音频。又把我一年前发表的一篇关于 DAO 的综述论文打印出来。阅读之后,我决定撰写一篇 Web3 感想的文章。于是就有了这篇 blog。

我们先简要过一下这篇文章。这里仅仅挑选一些 highlights,具体内容还请自行前往阅读。

文章提到 “国内至少六家互联网大厂的高级管理者或高级技术人才,放弃了稳定的高薪和可观的期权,主动探索Web3世界。” 紧接着,文章列举了几个有代表性的践行者在这个新兴赛道的早期探索与尝试。其中美团联合创始人王慧文对 Web3 学习之后,提出如下观点:“区块链撕裂了中国互联网,中国互联网的主要矛盾从巨头与创业公司的矛盾转变成古典互联网与区块链之间的矛盾”。2020年他从美团退休,开始探索新的赛道。另一个有代表性的 Web3 的从业者是前字节跳动90后程序员郭宇。2020年他从字节离职后,开始专心研究区块链技术与应用,后来全身投入 Web3 赛道。可见,从大厂高管到大厂年轻人,Web3 正在吸引源源不断的互联网人加入这个行业。

那说到这里, Web3 究竟是什么?继续引用这篇文章的说法:“Web3是指基于区块链技术的去中心化在线生态系统,许多人认为它代表了互联网的下一个阶段”。一名传统投资机构合伙人认为“目前Web3行业,很像2000年的互联网”。在目前的 Web3 行业,也逐渐有一些雏形产品问世,比如被视为去中心化的支付宝 MetaMask,被视为去中心化的QQ音乐 Audius,以及全球最大 NFT 交易平台 Opensea,等等,这些去中心化的应用已经在全球范围内吸引了千百万的用户,这些公司也逐渐成为全球最具影响力的公司。

接下来,咱们粗略地概括一下 Web3 与 区块链、还有 DAO 之间的关系。继续借用刚才文章中的观点:“区块链是一种技术,DAO是一种制度,Web3则是一种文化”。

大家已经很熟悉区块链了,我们不再赘述。我们看一下什么是 DAO。DAO的字面意思是“去中心化 自主治理的 组织”,它是一种去中心化组织形态,当然也可以通俗地理解为“去中心化的公司”,是建立在区块链基础之上的 一个自治系统。其实 DAO 不一定必需区块链技术才能建立。具有相同理念和共识的一帮人即可形成一个DAO。而且人们未必需要区块链才能形成共识。比如,文章举了一个例子:在互联网世界,当人们强烈认同一个视频或者文章时,即使不断被中心化机构删除,人们可以通过自发存储和不停地转载,将其尽力保留在网络上。这样的自发行为其实就是 DAO 的思想和 Web3 文化的一种体现。进一步来讲,如果借助区块链的技术,这些人们产生的共识,会更加容易地被记录、被分享,从而更好地践行 DAO 与 Web3 的理念与文化。

好,关于这篇文章的内容,我就为大家分享到这里。接下来的一段时间,我会通过几篇文章来逐步谈一下 Web3 行业 与 区块链、DAO 之间的关联。这里我们稍微展望一下 Web3 与 DAO 的未来。目前来看,虽然互联网人是最具有创新精神的一个群体,但是能突破 旧思维 去 拥抱新的变化,去参与新赛道,仍然是逆人性的行为,是充满挑战的。不管如何,这个世界唯一不变的真理就是这个世界在一直变化着。任何人都阻挡不了新趋势的发展。总有一个时刻你会觉得:如果不去主动拥抱变化,就会被趋势所碾压。

目前,Web3 与 DAO 已经被应用到了 互联网、金融、艺术 等等具有代表性的 为数不多的几个行业,但是这场变局已经悄悄铺开了10年时间。不用焦虑,因为社会大众对 DAO 的认识 还有 Web3 文化的了解, 远远尚未成熟。因此,这个赛道未来是一片蓝海。

然后,我再稍微提一下一年前发表在 IEEE OJ-CS 期刊上关于 DAO 的综述论文。我们论文题目是 “From Technology to Society: An Overview of Blockchain-Based DAO”,翻译过来就是“从技术到社会:对基于区块链技术的 DAO 的概览”,于2021年4月13日正式发表在 IEEE 计算机协会旗下的一个新刊 IEEE Open Journal of the Computer Society (OJ-CS)。

这篇论文主要梳理与讨论了 基于区块链技术的 DAO 的概念术语、发展历史、当前最新的研究与应用,以及对未来发展的一些展望。我在 google scholar 上看了一下我们这篇综述论文的引用情况,目前已经有4个引用,其中一个引用是来自荷兰乌得勒支大学的硕士毕业论文,作者在文中提到我们这篇论文介绍了三个比较流行的 DAO 项目: Aragon,Colony,与 DAOStack。看到我们的论文为他人带来启发,我还是很欣慰的,这也是作为一名从事学术研究的 researcher 最开心的事情了。话题有点扯远了。感兴趣的朋友们,欢迎阅读我们这篇论文,有任何问题欢迎给我留言或者发邮件给我。

最后提一下,我已经跟我的一个学生讨论了近期要做一个关于 DAO 的详细调研,后续我会陆续分享给大家,期待您的关注。

PS: 这篇 blog 的音频记录请前往“小宇宙”平台收听:https://www.xiaoyuzhoufm.com/episodes/6269030bbf39836fd02b7795