链闻ChainNews
公众号ID:chainnewscom
计算机顶级学术会议 NSDI 2019 收录的唯一区块链论文究竟如何实现 TPS 过万?
链闻曾在去年 12 月份独家报道了顶级计算机学术会议「NSDI 2019」收录了由华人分布式系统专家王嘉平和汪浩撰写的区块链扩容论文,二人提出的「Monoxide」方案在一个由 4.8 万个全球节点组成的测试环境中,实现了比比特币网络高出 1000 倍的每秒事务处理量、1000 倍的状态内存容量,有望打破不可能三角瓶颈。
最近,链闻和该方案的提出者王嘉平进行了深入交流,请他详细介绍了该方案原理以及测试的具体细节。
NSDI 2019 大会联合主席接受链闻采访,表示王嘉平和汪浩的论文是本届大会唯一一篇专攻区块链领域的论文,「评审委员会成员对这篇论文提出的想法非常兴奋,认为这个想法值得讨论并且将引发相应的后续工作。」
链闻相信,区块链技术出现突破性发展离不开计算机科学、密码学等基础学科研究的推进,也离不开工程学上的实现。区块链领域的创新性研究在 NSDI、OSDI 、SOSP 这样的学术会议上通过严格的同行评语,对整个行业的发展意义重大。我们可以查到的信息是,最近一次顶级学术会议接受区块链公链方案的论文,是 2017 年 SOSP 大会,接受了 MIT 研究团队提出的「Algorand」方案。
王嘉平清楚的记得,那是去年 11 月 30 日,一个周五的晚上。他突然接到了俄亥俄州立大学计算机及工程学系研究科学家汪浩打来的电话。
「快看下邮件,NSDI 论文委员会给我们发来了邮件…」汪浩在电话中说。
就在那一瞬间,王嘉平的心突然咯噔一下,悬在了半空。
NSDI 的全称是「 Networked Systems Design and Implementation」,是一个行业内备受尊敬的独立机构「USENIX」所组织的旗舰会议。该机构由计算机系统大型用户、开发者和研究者组成,其组织的这个大会是计算机网络系统领域久负盛名的顶级学术会议。
王嘉平和汪浩二人在两个月前曾向 NSDI 2019 大会提交了一份论文,提出了一个可以将现有区块链单链共识算法横向扩展 1000 倍以上的方法。
此时,他们此时正在焦急地等待评论文审委员会的回应,期待论文能够通过以严苛而闻名的同行审阅流程,被大会接受。
NSDI 2019 大会官方此前已经多次申明,会在 12 月 3 日周一论文委员会开会讨论之后,统一发出录用通知。而在在论文委员会开会讨论之前提前收到通知,通常只会是两种情况:论文毫无争议地被录用,或者毫无争议地被拒收。
汪浩带来的是个好消息:他们的论文入选了。
与组委会通知邮件同时抵达的,是请他们在 NSDI 2019 大会第一天的上午环节宣讲论文的邀请。
NSDI 2019
大会收录王嘉平和汪浩撰写的区块链扩容论文,「Monoxide」方案有望打破不可能三角瓶颈
在接下来几天里,王嘉平和汪浩认真研读了 NSDI 2019 大会接受的所有论文。今年 NSDI 接受的49 篇文章中,有超一半来自麻省理工学院、加州大学伯克利分校、斯坦福大学等美国顶尖高校,另外近一半则来自微软、谷歌、因特尔等大型云计算相关企业,国内高校仅有清华大学有三篇文章被录用,分别是关于网络系统建模、超算系统监控以及 RFID 无线技术。
NSDI 2019 大会的联合主席Jay Lorch告诉链闻,王嘉平和汪浩的论文,是本届大会唯一一篇专攻区块链领域的论文。「评审委员会的成员对这篇论文提出的想法非常兴奋,认为这个想法值得讨论并且将引发相应的后续工作」,Jay Lorch 说。
NSDI 是与 OSDI、SOSP 等会议同列为全球计算系系统顶级学术会议的大会,不过,NSDI 更加侧重于网络系统的设计与实现,注重计算机系统的性能和伸缩性等方向。由于该会议采用严格的双盲评审,每篇文章都要经过两轮总计六到八个审稿人审阅,之后还需要经过程序委员会的讨论筛选,众所周知的关于大数据系统 Spark 的研究论文,就由其主要研究者 Matei Zaharia 发表在 2012 年的 NSDI 大会上。
「一氧化物」的威力
面对链闻记者,王嘉平对 11 月末听到自己论文入选 NSDI 大会时的心情记忆犹新。尽管对他来说,论文发表在顶级学术期刊、被学术会议认可并不是什么新鲜事。
毕业于中科院计算技术研究所的王嘉平曾在微软研究院工作多年,专注分布式系统、计算机图形学和视觉,以及用于机器学习的 GPU 集群等领域的研究工作。在微软研究院,他师从微软全球执行副总裁、微软研究院负责人沈向洋,被沈称为「最喜欢的学生」,曾有数十项研究成果发表在 ACM SIGGRAPH/ToG 等顶级国际期刊上,获得十余项美国专利。2016 年底,他加入创新工场,主导区块链和人工智能方向的投资,在那里,他主导了对比特大陆的首轮机构投资,成为其首轮三大主要投资方之一。
王嘉平多年从事分布式系统研究工作
王嘉平向链闻介绍,在「NSDI 2019」大会上入选的这篇论文中,他和自己的团队提出了一个名为「一氧化物 Monoxide」的方案,实现了「异步共识组」模型,可以将一个现有区块链单链的共识算法横向扩展 1000 倍以上。
更准确地说,这种扩展方法「将使得吞吐量(TPS)提升 1000 倍以上,同时也将全网计算能力(CPU)提升 2000 倍以上,将状态表达的内存空间(RAM)提升 2000 倍以上」。
「一氧化物 Monoxide」是项目名。王嘉平说,「一氧化物」这个项目中最关键的设计在于利用「异步共识组 Asynchronous Consensus Zones」实现分布式系统性能的提升。其中,核心又是「共识组 Consensus Zone」。
「一氧化物」通过异步共识组实现分布式系统性能的提升
据王嘉平介绍,所谓「共识组」,实际上由多个同质的、功能上完全一致、地位上也完全平等,并且逻辑上尽量隔离的独立共识系统的实例所构成,「他们并行工作,分摊全网的吞吐、计算、存储的压力,分摊全网状态的维护工作」。
具体而言,他指出这些「共识组」具有如下特征:
具备独立且相对稳定的节点集合,逻辑上不要求一个节点参与到多个共识组
具备独立的账簿,承载全网的一部分用户,即组内用户,各个共识组的组内用户没有交集
具备独立的 Chain of Blocks,仅记录已经确认的和组内用户相关的交易
具备独立的非阻塞的出块过程,各个组之间没有任何同步的需要,比如需要互斥锁定特定资源
具备独立的未确认交易集合,仅有和组内用户相关的未确认交易会被暂存
具备独立的出块候选或竞争机制,矿工仅限于组内竞争,和其他组的矿工无直接竞争关系
具备独立的 Gossip 网络,完成区块和未确认交易的广播,不波及其他共识组的节点
王嘉平和汪浩的论文,就是设计了这样的一个可以实现如上「共识组」的系统和协议。
王嘉平说,这个系统可以实现协议上的跨分片交易,可以正确、高效地完成,保证攻击单个共识组的代价与攻击整个网络代价相当,同时还可以保证单个运行中的全节点需要承担的系统压力不会随着全网性能的提升而变大。
至于具体在单个共识组内部采用的共识算法,王嘉平称,可以是 PoW,也可以是类 BFT 或者 VRF 算法,「我们的基础实现,基于最朴素的 PoW 算法。」
区块链伸缩性大幅改善,吞吐量达到 11694 TPS
区块链的伸缩性,或者称为区块链的性能,一直是制约区块链技术走向实际应用的瓶颈。
在公链领域,一个普遍流行的说法为「不可能三角」,即系统的安全性、去中心化和性能,三者只能取其中之二。无论是最早的比特币区块链,还是以太坊区块链,甚至过去一两年中涌现出的自称为「区块链 3.0」的新型公链项目,全世界最聪明的计算机系统科学研究者、密码学家、计算机工程开发者,纷纷进入这个领域,试图解决这个难题。
据王嘉平的介绍,「一氧化物」这个解决方案与传统研究方式多数关注于用新的共识算法来实现性能提升的设计大有不同。
这是一个采用了「异步共识组」的分片系统。对于采用了「异步共识组」这样的分片系统来说,系统的性能不是一个定值,是一个和系统资源配置相关,并且可以被调整的值。他解释说,就好像一个多个稳定转速的发动机,不同的油耗就有不同的推力,「在异步共识组中,这个油耗就是全网有多少全节点,有多少矿工节点。」
他也向链闻展示了一张在一个最高有 4.8 万个节点组成的测试网络中的实测吞吐量图表。这张图表显示出,不同的共识组数量这个「油耗」,可以实现怎样的不同的「推力」,即区块链的吞吐量。
图 1,测试网络中不同的共识组数量与性能提升的关系
在这张图表中,横轴代表的是测试网络中的节点被划分成了多少个共识组,而纵轴则是平均每秒处理的交易量。
在王嘉平和汪浩进行的测试中,最大的共识组数量为 2048,此时吞吐量达到了 11694 TPS。让他们兴奋的是,这个数字已经远超现今所有公开发表的运行于互联网上的公链项目。
「测试网上实现的这个结果让我们非常激动。」王嘉平用半开玩笑的语气说,「当然了,这个结果不能和那些只在机房里面跑、单节点、并且采用了怪兽一样的服务器的项目去比较,因为后者根本无法部署成为开放的公链。」
更让他们激动的是,除了区块链吞吐量绝对值数字超越了目前已有公链项目之外,这个方案在测试网络中表现出来的线性伸缩性,显示了利用「异步共识组」的分片系统的巨大潜能:随着共识组数量的增加,全网的吞吐量将获得线性地提升,于此同时,全网的状态内存空间、交易处理的计算力、归档历史交易的存储空间也将同时得到线性的提升。
「在我看来,只有同步实现了所有方面的提升,才能避免某一个资源成为瓶颈,这才是真正的伸缩性。」王嘉平向链闻表示。
一场横跨 15 个城市、4.8 万节点的测试
为了证明理论的可行性,王嘉平和俄亥俄州立大学的分布式系统研究者汪浩、PPLive 前技术合伙人张小兵、OCaml 编译器的核心开发成员张宏波一同组建了一个研究与实验小组,进行了一系列实验和测试。
其中,汪浩是 NSDI 2019 所收录的论文的第二作者,也是王嘉平的博士同班同学。他们曾经都曾就读于中科院计算技术研究所,获得博士学位。
俄亥俄州立大学计算机及工程学系研究科学家汪浩,「Monoxide」方案论文的第二作者
这个实验小组部署了一个遍布全球不同国家、由 1200 台主机组成的物理网络,这些主机平均分布在全球 15 个不同国家的城市中,这样做的目的是希望让测试网络尽量接近真实的互联网延迟。该网络的实测平均延迟为 102 毫秒。而主机的配置也尽量接近实际情况,他们选择了 8 核 CPU、32G 内存的配置,避免使用过高配置的机器。
在这 1200 台主机上,实验小组最多运行了 4.8 万个全节点实例,每个节点限定最高带宽 30Mbps,然后,从几十个共识组进行实验,直到几千个共识组。测试首先显示出,即便在几千个共识组的情况下,单节点的压力始终不大,可以轻松运行在如此配置的主机上。甚至在最极端的情况下,一个主机运行了 40 个实例。
为了测试这个网络处理一对一支付交易的性能,他们进行了工作集测试。王嘉平和团队选择了截止高度到 5867279 的以太坊上所有 ERC20 代币支付的历史记录,作为测试用工作集,而不是随机构造一堆交易。
「这样是为了让测试更为真实,尤其是想测试跨片的发生概率的真实情况。」王嘉平说,「这个工作集中包含了 1600 万个地址、7600 万条交易记录,每一个交易还有支付源和宿的地址,以及和源地址对应的签名,还有支付金额,总共百来个字节。我们把这个工作集在全网重放,来获得测试结果。」
他介绍说,在单个共识组中,采用了类 GHOST 的 PoW 算法,目标出块间隔 15 秒,测试结果显示,单个共识组的吞吐量达到了 15.6 TPS。
「这是一个非常保守的设定,完全可以简单地通过扩大块尺寸来获得额外几十倍的提升。不过我认为,通过这种方式获得的提升并不能体现我们自身的技术价值。」王嘉平说。
在实验中,他们测试了最大共识组数量为 2048 的场景,此时整个网络的吞吐量达到了 11694 TPS。
「细心人可能会发现,单个共识组的吞吐量可以达到 15.6 TPS,我们测试的最大共识组数量为 2048 个,如果 15.6 TPS 乘以 2048 个共识组,整个系统理论上应该实现 31948.8 TPS 才对,这个理论值应该远大于我们实测的 11694.9 TPS。其中原因也很简单。事实上,每一次共识组数量翻倍,其性能提升并不是 2 倍,而是一个稍低的数字。」王嘉平解释说,「处理跨片交易是会有额外的开销的,好在我们的算法使得这个开销是个常数,和共识组的数量无关。这样,就可以让整个网络的性能实现与共识组数量的增长呈现线性的正相关增高。」
具体而言,据王嘉平的观察,进行共识组数量翻倍之后,首先会出现「额外开销」较大的情况,然后,这种「额外开销」会逐渐减少具体见上文图一。据他的统计,进行共识组翻倍之后,第一段可以将 TPS 提升 1.6 倍,继续进行翻倍,第二段可以将 TPS 提升 1.6 倍,之后,「额外开销」逐渐收窄,系统性能的提升基本可以稳定在随着共识组数量增长一倍而提高至原性能的 1.9 倍左右。
「把不可能三角撕开一个巨大的口子」
王嘉平介绍,在这个异步共识组组成的系统中,进行非跨片交易时,交易确认时间和单链系统无异,而跨片交易的确认时间会最大延长到原来的 2 倍,平均达到 1.5 倍,即 22.5 秒左右。
他和团队还在实验中测试了在以太坊历史交易记录的测试集中,跨共识组交易占到的比例。
他向链闻展示了一张图表,其中显示,当在分片达到 128 个共识组的时候,跨共识组交易的比例就几乎已经是 100% 了。
「很显然,分片越多,用户会被切得更细,就会有更大的概率使得交易双方处于不同分片上。我们的算法并不回避这个状况,而是给出了高效的跨片处理方案,从而使得全网的伸缩性继续保持线性提升,而不受跨片交易的制约。」王嘉平说平。
不过,王嘉平也毫无保留的指出了这个系统的局限性。
他说,理论上随着共识组的规模的不断扩大,这个系统的伸缩性会线性提升,但是最终还是会有一个「止步」的边界,而最主要会受制于当前互联网带宽的限制。
「应该让大家知道特定的技术边界。我们设计的这个系统中,为了使得跨片交易得以正确安全地完成,共识组之间需要传递成链的块头信息,这部分信息在共识组数量达到一定规模之后,会占据相当的带宽消耗。」王嘉平说。
他说,具体来说,共识组之间需要传递成链的块头信息大约为每个共识组每块 256 个字节左右,在其实验中,当系统达到 11694.9 TPS 的时候,该部分消耗的带宽是 279.6Kbps 左右,与之相关的存储和计算代价可以忽略不计,在 30Mbps 的单节点带宽约束之下,「共识组数量的天花板在 20 万左右」。
如果实现 20 万个共识组的情况下,据该团队测算,全网吞吐量在理论上可以达到百万 TPS,此时,全网状态内存容量将超过 1PB 左右。
「这个代价和出块尺寸无关,因为需要传播的仅为块头,这和单位时间出块个数有关。我们想到的解决办法是扩大出块尺寸,同时等比提高出块间隔,来降低这个部分的开销,并且保持吞吐量不变,同时也不增加单节点压力。付出的代价是,这样做会使得交易确认时间变长。」王嘉平说。
此外,影响共识组数量的另一个因素是社区的规模,即全网矿工节点和全节点的总和。
王嘉平说,对于单个共识组来说,参与其中的节点不能太少,至少应该过百,否则会容易暴露出块节点即矿工的物理 IP 地址,也会增大全节点被隔离欺骗与全节点连接的其他对等节点全部是恶意节点的概率。「在我们设计的异步共识组中,我们鼓励一个全节点参与多个共识组,而矿工节点参与多个共识组更是有利可图,这在一定程度上缓解了这个问题。」
此外,他向链闻强调,对于分片系统来说,吞吐量和容量从来都不是一个单一的数字,而是一个根据具体应用场景、安全约束、延迟敏感程度、社区发展阶段、交易活跃度等多方面考虑的权衡设计,是一个可以调整的东西。
而不论怎样,让他兴奋的是,无论具体应用场景是什么,他和汪浩在论文中提出的异步共识组将现有区块链网络性能提升 1000 倍这个最基本底线是可以轻松获得的。
「你说这个技术算是突破了区块链所谓的不可能三角吗? 我认为是,虽然还不算彻底,但是,可以说撕开了一个巨大的口子。」王嘉平说。
现在,他正等待 2 月 26 日在波士顿举办的「NDSI 2019」大会上讲解自己的论文。
他说,在一个全球顶级的学术评审团队对他的论文进行了同行审阅之后,他更期待在论文正式在大会上发表之后,行业中更多广泛的研究者和开发者可以共同审阅并提出意见,更期待共同合作,「我们的工作重点在于有效地横向扩容,在技术上和很多研究新型共识机制的工作是正交的。我们乐于与现有的或未来继续涌现的公链团队展开合作和交流,为现有的单链系统作横向的扩容,在不增加单节点压力的前提下,轻松获得至少百倍吞吐量和性能的提升。」
加密行业 TOP 100 最活跃的投资机构
领取专属 10元无门槛券
私享最新 技术干货