突破区块链不可能三角(七)——分片(上)

突破区块链不可能三角(七)——分片(上)

本系列文章:

  1. 扩容,扩展,与无限扩展
  2. 在比特币POW之上的尝试
  3. POS与POW-DAG
  4. 区块链中的BFT及HotStuff BFT(Libra BFT)分析
  5. 闪电网络,链下技术,以及它们的局限性
  6. 吹个关于区块链活性的哨子
  7. 分片(上)
  8. 分片(中)
  9. 分片(下)

自我吐槽一下,这个系列的最后一篇拖了快三年,从公链纷争,共识算法火热的2019年拖到了共识算法已经被当成明日黄花的2021年底。不过还好,反正是科普,技术永远不过时——如果对共识算法没兴趣,那么2019年你也大概率不会看;如果对共识算法有兴趣,那么2022年你也会看一眼不是么?

鉴于大家可能已经忘记了这个系列在说啥,我们来回顾一下——

在这个系列之前,我们介绍了区块链共识算法的分类,区分开“可扩展”和“无限扩展”的概念。

在可扩展的部分,我们介绍了两类可扩展路径——一是从改进PoW开始的,中本聪共识的可扩展方案。二是从改进传统BFT开始的,在区块链中应用的BFT类可扩展方案。

接下来,我们进入无限扩展的范畴,介绍了以闪电网络为代表的链下方案。

而这里就出现了由于系列拖得太久造成的问题——在成文的时候,rollup还不被认为是一个二层网络方案,而是一个“1.5层方案”因为它即不解决前文定义中的,瓶颈在网络传输上的“可扩展性问题”,也不算是我分类中的能达到“无限扩展”的“链下技术”。从分类上,它更适合拿来和比特币的Segwit(隔离见证)对比,它解决的是以太坊中Gas上限的问题。

但在成文的时候,Rollup的支持者们已经成功鸠占鹊巢地占领了“二层网络”这个名词,并且把原来的例如侧链方案的二层网络方案踢出了二层网络行列。因此,我又写了一篇可以说是番外的对于Rollup的介绍:maxdeath:什么是Rollup(上)maxdeath:什么是Rollup(下)

至此为止,区块链扩展的问题只差最后和最复杂的一片拼图——分片(Sharding)。

那么我们进入正题。

(注:当然,本文成文的时间较久,一些文中的共识算法之争对于新来这个领域的人可能已经陌生了,因此,读者们就将此文当作是篇老文看就行了)


再谈无限扩展

在性能上,无限扩展(Scale-out)这个概念本身来自于分布式数据库。在分布式数据库中,有垂直与水平扩展的的说法——一个可以垂直扩展的数据库的性能可以通过提升单个服务器的性能来提升,而一个可水平扩展的数据库的性能,可以通过提升增加服务器的数量来提升性能。前者又被成为scale-up,而后者被成为scale-out。

而由于区块链和分布式数据库的原理完全不同,在区块链中,两者实际上都是很难实现的。

对于分布式数据库而言,本身的原理是将一个人能做的东西分给多个人去做,尽管这其中有协同的问题,同时,也需要加入冗余来防止其中有人做的工作出错或者无法完成工作,但总而言之,还是一个多人协作的问题。那么自然,无论其中有人的能力加强,或者多来一些人进行工作,只要管理者的水平不太差,总归,系统的输出总是增加的。然后,只有当管理者的方式,也就是分布式数据库的算法,能够让输出随着增加的单个服务器性能,或者服务器数量线性增加的时候,我们才会说这个系统是无限扩展的。

但与分布式数据库不同,区块链本身的价值核心——去中心化,原本的意义就在于将本来一个人能够解决的问题让多个人每人都去做一遍,然后通过事先共识算法再汇总出一个大家都同意的结果。因此,实际上我们不是把工作量分摊了,而是出于对于其中任何一个人单独完成工作的不信任,让所有的人都把所有的工作完成一遍。然后,所有人把答案汇总在一起,多数人得出的答案将会成为大家都同意的那个。

所以说,由于两个场景面临的问题和方案都是迥然相异的,因此直接将分布式数据库采用的方法套在区块链上是无法达到无限扩展的。甚至说,无限扩展这个概念其实在区块链里都是不适用的——因为分布式数据库相当于分配工作,而区块链则像是民主表决。对于工作而言,自然,工作完成得越快越好——越快,则说明管理水平越高。如果一个10人的公司在扩大10倍之后的效率是10倍的话,扩大100倍效率就是100倍,这管理水平就可媲美韩信当年的“多多益善”了。但区块链相当于民主表决,这个时候你说参与表决的人数多了100倍但是表决速度不仅没有减少而且还增加了,这个时候都不用了解采用了什么新技术,但用常理推断这个表决结果都相当可疑。而且,追求无限扩展,相当于说表决速度不仅仅增加了,还快了100倍,这件事本身不仅不现实,而且毫无意义。因为如果真是这样,那么它不可能是民主表决,而只能是任务分派。也就是说,这个系统不可能是个区块链,而只是个分布式数据库。

然而,从始作俑者号称“百万TPS”的EOS开始,在很长的一段时间内,区块链们都乐此不疲地追求着“无限扩展”,直至今日,关于无限扩展的论文和技术还是层出不穷。

实际上,这仍旧是一个在区块链领域常见的,项目噱头先行,媒体推波助澜,然后挟裹着技术发展的情境。

前文中,我们已经介绍了“可扩展”这个概念的发展历程,而同样的混乱在“无限扩展”这个概念上又发生了一次。

由于当时“可扩展”本身的概念就比较模糊,几乎任何一条区块链都可以说自己是可扩展的,因为他们至少相比于比特币更“可扩展”一些。于是,从宣传的角度而言,可扩展已经不是什么值得吹嘘的特性了,这个时候“无限扩展”的概念就被从分布式数据库的场景里拿了过来。毕竟,对于用户而言,比特币的7TPS实在上不了台面,而对于不理解区块链的用户而言,TPS肯定是越高越好,甚至,几千到几万的TPS都可能不够用,如果能有如同传统分布式数据库或者分布式系统一样,有上百万的TPS,那样才符合移动互联网时代人们对于TPS的预期。而这里面最大的牛,莫过于明星项目EOS吹起的通过分片达到的百万TPS。当然,后来我们知道EOS从理论和实现上都从来没有兑现过“百万TPS”的宣传,但作为一个划时代的明星项目,它毫无疑问引领了整个区块链领域通过一切办法追求“百万TPS”和“无限扩展”的风潮。

无限扩展的本质

实际上,无限扩展的本质在前文中分布式数据库和区块链的对比中已经很明显了——

无限扩展是分布式数据库的概念,而从根本上是和区块链相悖的。因此,实际上无限扩展就是让系统更像分布式数据库而不是区块链,让参与的人更多地像是在合作而不是互相监督。于是,我们其实很容易看出来实际上“无限扩展”和“区块链”本身其实是一条线上的两头——想要无限扩展,就需要如同分布式数据库一样将工作分散给所有节点,也就是相信每个节点的工作结果而不做验证;而想要去中心,就需要每个人都不相信其他人的工作结果,都去重复一边其他人的工作来进行验证。这就构成了“去中心”与“无限扩展”的二元对立。于是,想要将扩展性提高到“无限扩展”,那么自然没有“去中心”可言,也就完全失去了区块链的意义。

那么,我们已经很清楚地知道了去中心这一端的样子,就是每个人都必须去重复所有人的工作。然后,如果我们想要追求可扩展性,就没法让每个人都去重复一遍所有的工作。但想要这么做,除了分布式数据库的方法,还有另一个维度——

假设网络里有100个人,要么我们说每个工作不需要所有人都验证了,只要10个人验证就可以了——这样,效率提高了10倍,因为每个人的工作量都只是原来的1/10,但是安全性变成了原来的10分之一,因为原本如果用了能够容忍1/3恶意节点的算法的话,那么现在,如果10个人中有4个恶意节点,最终的结果就可能有错。另一种做法是,我们从10个人中选出10个我们认为最可靠同时工作效率最高的人,然后由这10个人负责验算所有的结果,而其他人就只要相信他们的结果就行。这样,整体的工作量也降低了10倍,然后如果这10个人的工作效率够高,整体的工作效率还是会提升。但这里,其实我们认为这个系统更“中心化”了,因为原来是100个人做决定的事情,现在做决定的只有10个人了。

于是,我们得到了这个很有名的“无限扩展不可能三角”。

不可能三角之谜

“不可能三角”可以算是区块链领域里的一个最大的迷思了,它的前身可能是分布式系统中的CAP原则,即分布式系统无法同时达到一致,可用和分区容错性。CAP原则有理论严谨的证明版本,也即前文中介绍过的FLP不可能,即:“在异步的分布式系统中,即便只有一个故障节点的存在,也不存在一个算法可以使所有正常节点达成共识。”而这里,达成共识的要求就包含了“一致性”和“可用性”,换言之,就是说,在异步系统中,如果有故障节点的存在(分区容错),即不可能同时达到一致和可用。但两者的区别在于,FLP定理是经过严格证明的,而CAP原则则更多是一个来源于经验的通俗说法,因为其实CAP原则中并没有严格地定义CAP原则适用的网络模型和成立的具体条件。

但也许是受到CAP原则的影响,“不可能三角”这个概念被频频引入区块链领域,我所知的最早最著名的一个版本大约是“区块链不可能同时达到去中心(Decentralization),安全(Security),和可扩展(Scalability)”。而这大约也是区块链不可能三角最著名的版本——通常,用来说明的是比特币和EOS,其中,比特币就是一个无法扩展但是去中心和安全的区块链,而EOS则是一个可以扩展并且安全的不去中心的区块链。这两个例子确实相对于一般大众而言更好理解,然而,这两个例子本身以及用来证明的这个不可能三角从各个角度都是错误的——如果以EOS的可扩展标准,那么前文中可扩展PoW类的大部分算法都能够在维持不弱于比特币的去中心化程度的前提下达到可扩展,比如Algorand就打破了这个不可能三角。因此,通过比特币和EOS来定义的不可能三角不仅不准确,而且结论也是错误的。

另一个著名的不可能三角来自以太坊创始人Vitalik Buterin,同样是“区块链不可能同时达到去中心,安全,和可扩展”,但对于这三个概念做了一个和以上这个不可能三角截然不同的定义——其中,去中心被定义为“每个节点能够仅处理O(c)的交易”,而可扩展则被定义为“整个网络能够处理O(N)的交易”。但Buterin实际上是在以太坊分片的文章中提出这个“不可能三角”的,于是,其实文章的结论是“通过分片技术我们可以同时达成不可能三角”,于是,实际上这个不可能三角的结论本身还是错误的,因为这其实是个“可能三角”。

第三个不可能三角来自于分片论文Omniledger,在论文中,Omniledger中给出了他们对无限扩展的定义——区块链的输出可以随着验证节点的增加而线性增长。然后,如同以太坊分片的论文,他们先提出了不可能三角的结论,即“区块链不可能同时达到去中心(Decentralization),安全(Security),和无限扩展(Scale-out)”,然后证明了Omniledger可以同时达到三者,于是,这仍旧是一个“可能三角”。

这也是区块链领域这个“不可能三角”迷思的来源——因为这三种不可能三角的提出,实际上都是为了某个“打破不可能三角”的技术方案的铺垫。而我认为,区块链真正的“不可能三角”,是同时达到这三者:

  • 无限扩展:系统的输出能够随着节点数量的增加而增加。
  • 去中心:所有节点的地位都是一致的,不假设某个或者某些节点比其他节点更有能力或者更为可信。
  • 安全:对于中本聪共识,能够有1/2的容错;对于BFT共识,能有1/3的容错

目前,这个定义下的区块链不可能三角是正确的,至少,前文中“打破不可能三角”的几种方式并没有打破这个不可能三角——打破第一个不可能三角的Algorand其实是一个严格的“可扩展”共识算法而没有达到无限扩展,打破第二个不可能的以太坊分片和打破第三个不可能的Omniledger,实际上都牺牲了安全性。

而实际上,其实这才是提出“不可能三角”的目的——我们需要一个共识算法可行性的边界,而不是仅仅指出某些算法的局限性然后用“我们打破了不可能三角!”来做噱头。在下文中,我会介绍实际上这个“不可能三角”也并不是严格成立,也是可以打破的,但那就需要引入另一个维度“功能性”并且做出牺牲。所以,总体而言,我们需要明确的问题是——本章中介绍的所有分片方案,以及之前介绍的二层网络方案,实际上都需要做出安全性或者去中心化上牺牲。

几类基本的分片技术

我们先从最直观的角度来理解分片技术——这也是区块链“分片”这个概念的由来。

前文中我们已经说了,如果每个人都需要验证每笔交易,那么区块链一定不可能是“无限扩展”的,于是,我们需要某种方法,让每个人不需要验证每笔交易,又或者说,每笔交易并不需要发给所有人验证。

这里面其实有两个半问题——一个是“获取”交易,一个是“验证”交易,半个是“储存”交易。也就是说,你首先得接收到这笔交易的信息,然后按照规则进行验证,最后,之所以是“半个”问题,是因为你可以把这个交易存起来,但其实对于有最终性的共识算法而言,储存过去的交易和状态并不是必须的。

在目前的区块链领域里,“获取”是最大的瓶颈——因为获取交易的能力受限于传输能力,而传输能力则受限于网络的物理带宽,这是目前制约TPS的主要因素;“验证”随着以太坊类区块链的崛起和智能合约的发展,也开始逐渐限制区块链的性能,尤其是以太坊EVM的一些固有局限实际上限制了交易处理的速度,但这些更多的是工程上如何实现以及推广上如何取代以太坊的问题,而不是理论上的障碍;而与这两者相比,“储存”上的瓶颈则要更加往后排了——因为储存设备毕竟相对便宜而且容易提高,只有前两个问题得以解决之后,TPS显著上升,那么储存上的问题才会凸显出来。

于是,我们首先来讨论如何在“获取”交易上动手脚——如何让每个节点不需要接收每一笔交易。

根据网络分片

那么自然而然地,我们得到了第一种最直观的思路。

如果小红和小明都是中国人,那么他们之间的交易,为什么要发给美国的Mike去验证?

所以,为什么不根据地域(网络)来对网络进行分片呢?这样,中国的交易就只在中国验证,然后美国的交易就只在美国验证?

首先,我们先从结果看——结果是,乍看上去,每个节点确实需要接收的交易变少了。中国的节点只需要维持一个包含中国节点交易的账本,而美国节点只需要维持一个包含美国交易的账本。

但前提是,如果没有“跨分片交易(Cross-shard Tx)的话。

小明挖出了一个币,然后给了小红,小红验证了这个币明确无误,这确实不关Mike的事。但如果小红接着想要从Mike那里买东西,问题就来了:

Mike如果说:“你这个是在中国分片交易的钱,我不收。”那实际上这个币就不再是一个通用的货币了,这分片也就不是分片而是分裂了。

那Mike怎么验证这笔钱呢?

第一种方案,Mike就只能去把中国交易的账本下载下来自己按照这种币的规则从头验证一遍,然后确认这笔钱是真的再接收。

这样乍看上去好像可行,因为虽然Mike的确需要维持中国和美国的账本,但是他并不需要维持其他国家比如欧洲的账本,而其他的美国节点也不需要这样做。

但问题是,如果Mike想要在美国花掉这笔钱,比如将这笔钱发给Alice,那么Alice自然不会听Mike说“这是笔真钱,我亲自验证过”就相信,所以她也得下载一个中国的账本去验证一遍这笔钱。于是,就算其他美国节点不需要和中国节点做交易,只要Mike的这笔钱能花,那么所有美国节点还是得去接收一次中国的账本——他们倒是可能不需要验证其中的每一笔交易,但是前面已经说了——接收这件事才是最大的瓶颈所在。

同理,只要有人和欧洲做交易,那么所有人还得再去接收一遍欧洲的账本。最终,我们回到了原点——所有人都得再收一遍所有人的账本,于是分片就没有意义了。

因此,就有了另一种方案。

在每个国家各找出那么一些较为可信并且网络条件较好的节点,这些节点负责所有跨分片交易的验证。

也就是说,小红如果想要发一笔交易给Mike的话,小红需要通过一个Mike可以信任的中间机构,这个机构负责下载中国的账本并验证中国的所有交易,当这个机构验证通过了这笔交易之后,它告知Mike这笔交易是可靠的,于是Mike接收这笔交易。

很显然,这又回到了中心化交易的老路上。

但这本身也是无奈之举——因为我们已经说过了,不牺牲去中心化或者安全性是不可能实现无限扩展的,而这就是一种牺牲去中心化的方式。这里,所有的“片内交易”还是可以去中心地进行验证,而所有的分片交易则需要通过选出来的节点。一般节点只需要获取片内的交易数据,而这些选出来的跨片节点需要获取所有交易数据。当然,我们可以选出多个跨片节点来进行拜占庭容错来防止完全的中心化,但是中心化和安全性还是一脉相承的——更少的跨片节点代表更少的人需要下载全部交易,代表更高的效率,但带来的后果是,如果想要进行跨分片的双重支付攻击的话,只需要和超过半数的“跨片节点”合谋就够了,而不需要收买所有节点中的半数。

从效率的角度看,在假设每个分片都能找出一些性能更好并且可靠的节点的前提下,这种分片方式的确提高了效率——对于一般节点而言,它们只需要维护一个自己分片的账本,而对于所有的跨片节点,它们得负责维护所有交易的总帐本。这是个不轻的任务,但是我们有办法来降低他们的负担——如果这个区块链的共识算法有“最终性”的话,那么验证一笔跨片交易在片内账本的真实性可能不需要通过提交整个账本,而只需要提供一个远小于整个账本大小的“证据”就行了。于是,维护跨片交易的节点可以不需要保存每个分片的账本,而仅仅需要维护一个记录所有跨片交易的跨片账本,和每个跨片交易对应的它们在各自分片真实性的“证据”。

这里的“最终性”,是相对于中本聪共识里的概率共识的。换言之,如果采用比特币的PoW算法,那么账本就不具有最终性,那么跨片节点的负担就会很重。从另一个侧面来聊这个问题的话,就是ETH2.0的路线图——为什么一定要有一条PoS的“信标链”?因为实际上这条信标链通过同步拜占庭容错算法达到了“最终性”,这样才有了后面的分片路线。

实际上,这种分片方式也的确出现在早期的以太坊的分片文件中,成为了最早的分片提案之一——以至于,在“区块链分片”概念最早出现的时候,一说到这个词,大家立刻能够想到的,就是这种以国家或者地域进行划分的分片方案。


这种分片方案的有效性是非常直观的——首先从生活经验来看,的确片内交易应该占大头而跨片交易是少数。其次,现实社会中的交易系统里,我们的确也需要依赖于一些性能好、更可靠的中心来处理跨国转账的交易。再次,从物理世界的规则来看,片内的节点互相之间的网络连接也更好,所以单个分片应该可以达到更好的性能。总之,这种分片的逻辑实际上和现实世界的逻辑是一致的。

但相对的,正如前文中说的,这种方案牺牲了去中心化——我们得做出信任一些节点的假设;也牺牲了安全性——原本,你需要和整个系统的大多数节点合谋才能进行一次双重支付,而现在,你只需要和任何一个分片的大多数,或者所有跨片节点的大多数合谋,就可以进行一次双重支付攻击。

但这种分片最致命的一个问题恰恰也出在直观上——

正因为它和现实世界的逻辑太相近了,我们不需要将它实现出来也能看出来,发生在现实中的问题同样会反映在这种方案中——

比如,在这个方案里,美国节点需要相信中国节点的验证结果。而在现实中,我们已经知道了,无论中国验证的形式和结果再正确,美国节点也不会和不愿相信这个结果。这种方案中天然地包含了这种地域、国家和意识形态的分歧,因此如果采用了这种方案,几乎可以肯定的是,用不了多久这种分歧就会爆发,最后的结果就是——分片变成了分裂。原本区块链的思想是用一致的算法和数学来代替社会中“人”和信任的作用,现在反倒把现实社会中的问题重新引回了区块链:比如,分片里的交易相当于一个国家的经济活动,那么应不应该透明?需不需要监督?谁来监督?跨片节点成了国际事务的处理者,那么谁来担任?每个分片应该有几个节点?这些节点,是不是又成了国家角色的代表者?

随机分片

于是,在这种分片方案结构的基础上,人们提出改变分片的方式——不按照地域,而采用随机的方法。

随机数产生的方法,在前面的PoW和PoS部分已经多次提及了。而这里,我们可以采用同样的随机数,然后,将节点根据节点的id进行随机划分。比如,在比特币中,我们可以将交易按照地址进行划分——比如,从尾号为1的地址出来的交易,我们记为分片1,从尾号为2的地址出来的交易,记为分片2。那么,如果是一个尾号为1的地址转钱给另一个尾号为1的地址,那么这就是分片1的片内交易。如果是给一个尾号为2的地址转的钱,那么这就是一个跨片交易。

那么,跨片交易要谁来负责呢?其实也好办——还是用随机的方法,随机选出一些节点作为每个片区的代表负责跨片交易。

我们可以将这种方式和根据地域划分的方式进行对比。

从性能上,随机分片一定是变差了——对于分片的账本而言,原来同一个分片的节点地理位置上都接近,互相之间网络链接的物理性能上肯定也更好;对于跨链的账本而言,原来选出来的跨链节点一定是网络能力更好的机构,而现在跨链机构是随机选出来的,因此,跨链账本维护上,效率自然就会受限于所选出来的性能不那么好的节点。

那么优势是什么呢?实际上优势就在于它的安全性是成立的——我们作为参与者,能够接受也愿意相信身份未知,互相不认识,没有什么关系的和我们一样的参与者中的大部分节点都是诚实的,因为大部分区块链都是做的这样的假设;但如果说要求一个国家或者一个地区的人去完全相信另一个国家的节点得出的结果而完全不做验证,这件事是违背现实社会规则的。这种担忧是合理的,同时也是有现实意义的——因为同一个国际和地区的节点就是会有利益上的相关性,而选出的代表整个分片利益的节点,在整个系统中,也的确有为了保证自己分片利益而作恶的动机。

那么,实际上同样的问题,也并不会因为随机分片而解决——如果随机分片之后就固定下来,那么每个分片在时间久了之后也会形成自己的团体,有自己的利益。因此,随机的分片还需要定期重新划分,跨片节点也需要重新选择,才能防止分片形成自己的利益共同体而危害安全性。

然而,这里面又出现了交易历史的问题——在一段时间内,由于每个节点都有可能被划分进多个分片,也可能成为跨片节点,于是它还是得获取所有的这些账本,那么分片的意义又不存在了。

所以,重新分片不能过于频繁,同时节点被划分到新的分片之后,新的验证节点也不应该需要再获取和验证之前的全部账本,而只需要获取账本的最终状态,然后这个最终状态由当时负责维护账本安全性的节点签名。

以上,就是随机分片的方式。最早的一篇“分片”论文(Elastico,Loi Luu et. al)就采用了这样的一种方式。但由于机制较为复杂,比如拜占庭容错采用的是不可扩展的PBFT,导致了即便在理论上,也得到10000个节点这样的量级才能表现出些许对于非分片系统的优势。但如果采用了更好具可扩展性的BFT算法,分片在输出上的优越性立即就体现出来了,这种方法代表性的论文是Omniledger,也是最早的提出可以“无限扩展”,并且定义了“无限扩展”的论文之一。在Omniledger中,片内的BFT算法采用了树状结构和聚合签名的方式来减少消息复杂度。使得最终系统的消息复杂度为o(N),也就是可以随着系统节点数量的增加而增加,这点是非常好的。但相对而言,安全性是下降了,这体现在容错可能会从原本的1/3,下降为1/10(举例,并非一定是这个数)。这也是为了提高输出所需要付出的代价。

关于这两个随机分片算法的具体细节其实已经无需多言,因为其实大部分其中构成的元素都已经在前文中介绍过了,例如如何将BFT套进非许可的网络里,如何提高BFT的可扩展性,如何计算公开可计算的随机数等等……而分片中最核心的思路,结构,和交易验证的方式,也在上一节之中介绍了。

跨片交易的安全性

需要注意的是,随机分片方案还是严格在“不可能三角”的约束之内的——因为随机选取的验证者终究不是全体验证者。这个安全性的下降有多少呢?我们不妨列一些数据:

如果有100个验证者,在不分片的情况下,我们可以容忍33个恶意节点。

这个时候,如果我们把网络分成3片,每片33个或者是34个节点,分别容错10,10和11个恶意节点,加起来等于31。于是,原本一个安全可用的区块链,在分片之后至少有一个分片是不安全的,这显然没法称之为一个“可用的分片方案”。而这个方案,只有当恶意节点数量每那么多,比如只有20个或者更少的情况下,才能保证大概率是有用的。于是,分片是会降低安全性的。

但即便如此,我们也只能保证“大概率不出现恶意分片”,但是万一出现了恶意分片了会怎么样呢?比如,如果分片A中有超过10个恶意节点,他们就可以造成分片内账本的不一致,于是,他们可以用两个不一致的账本分别把同一笔钱转给分片B和分片C中的节点,而两边都会接收。

如果把一个分片看成一个人,那么这就是最典型的双重支付问题,而这个问题的症结也很清楚——我们需要一个所有跨片交易的统一账本,也就是之前所说的,所有跨片节点需要维护一个跨片交易账本。但这么做的代价是非常高昂的——假设我们随机把网络分成了10片,那么即便我们假设所有的交易都是一对一的交易,那么按概率10笔交易中也会有9笔是跨片交易。于是,实际上跨片账本的大小是未分片前的总帐本的大小的90%。但这么大的账本实际上只是为了防止很低概率出现的分片不安全的情况,这看起来有点得不偿失。

因此,很多新的分片算法摒弃了Elastico和Omniledger中的跨片账本,取而代之的是一个看上去不那么完美,但是在实际中经常被使用的“经济学”保证,即,要求所有验证节点抵押,并且如果发现作弊者就进行事后追责,比如NEAR就采用了经典的抵押的方案——验证者需要抵押一部分钱在链上,如果作弊被发现,那么发现者可以提交证据来取走作弊者的部分押金。但经济学上早就指出了这么做的局限性——如果作弊的概率很低的话,那么这种极小概率才能获得的奖励是不足以维持诚实节点持续去检查别的节点是否作弊的。因此用这种押金+罚没的机制代替一个跨链账本毫无疑问地会再次削弱安全性。

随机分片的输出提升

到此为止,随机分片的思路和安全性已经明确了,但问题可能才刚刚开始。

因为其实我们在之前都悄悄地做了一个隐含的假设,但这个假设却未必是对的——

原本,所有人都需要维护一个全量的账本;而现在,分片内的节点只需要维护片内的账本,而跨片节点负责维护跨片账本,乍看上去,两者都要比全量的账本小了,所以我们得到了一个更高效,无限扩展的区块链。

然而,片内账本和跨片账本它们本身,真的一定比全部的账本小吗?

有人可能觉得,这不是理所当然的事情吗?

那么我们来看看按照以上的分片结构,多少人需要获知一笔跨片交易,比如小红发给Mike的这笔交易。

首先,小红和Mike本人是需要知道的。

接着,小红所在的分片A和Mike所在的分片B也是需要知道的,但细节可能有所区别,比如,小红所在的分片需要知道:“这笔钱已经被转出了分片A,因此不能再在这个分片中使用了。”而Mike所在的分片需要知道:“我们收到了一笔来在分片A的合法的钱,现在这笔钱可以在这个分片使用。”

再次,所有的跨片节点需要知道:“一笔来自分片A的小红的UTXO的钱转给了分片B,这笔钱不能再被用来转给其他分片了。”

除此之外,其他的节点就不需要知道这笔交易了,从这个角度讲,的确,每个分别的账本是要比全部的账本小的。

但是,一笔交易是有可能有多个输入和多个输出的。

如果恰好这些输入分别处于所有不同的分片中,那么这笔交易就需要所有人都知道了。

那么,如果恰好所有交易都是这样的跨片交易,那么这个分片实际上不仅没有起到任何提高输出的效果,还白白增加了大量的冗余。

当然,你可能会说,怎么可能所有交易都是这样的?

但其实这事真的不好说,而是视情况和区块链的性质而定。

比如,我们把以太坊类的区块链纳入考量——比如最简单的在线足球菠菜的智能合约,参与的人可能来自各个分片,于是无论这个智能合约在哪个分片,我们都会得到和上文中一样的情况——即所有调用这个智能合约的交易都需要被所有分片所获知。如果一个区块链上面都是这种交易类型,那么分片技术就完全起不到提高输出的作用。

而事实上,其实追根溯源,我们之所以天然地想到“根据网络分片”这种方案,也是因为交易这个场景的特性中就天然包含了地域性,所以我们可以直观地联想到分片的合理性以及所带来的便利性,比如,“国内交易肯定远远多于跨国交易”并且“中国发生的确实没有必要让美国的节点知道啊。”

但对于别的场景而言,这件事就没那么理所当然了。而推而广之,像是类似于以太坊这样的图灵完备,应该可以支持任何场景的区块链,随机分片的效果就非常难说了,而且,在实际操作上也更加复杂——

以太坊中,在前文中已经介绍过了,所有的交易会共同维护一个一致的状态,这个状态就相当于是一个“账户”类的账本,记录着所有人的账户和余额。而后面的交易会在这个状态上做修改,比如,哪些余额增加,哪些余额降低。而且,由于智能合约的存在,许多交易会同时调用和更改多个“账户”中所记录的数值。而作为图灵完备的基础,以太坊对于如何调用状态,一次能调用多少个,谁能调用哪些状态,都是不做限定的。

于是,既然不知道状态中的哪些变量在未来的交易中被调用,自然也就没法对于状态进行分片,也就是说,节点还是要维持一个完整的状态,而想要维持完整的状态,则必须得接收全量的交易对于状态进行更新。

打个比方,数字货币的分片就如同一群负责某个美食街的外卖小哥,为了防止高峰期忙不过来,大家自发地分配任务——一人蹲守一家餐馆,免得在交通人流拥挤的时候在美食街反复穿行。但以太坊类的分片就如同一群负责一家大超市的外卖小哥,他们如果也分片说“你负责冷冻区,然后我负责生鲜区,他负责饮料区……然后如果来了买冻品的单子,就你去送,来了买生鲜的单子就我去送”,结果就不会有多少效果,因为相比于订餐基本上都只会从一家餐馆订,来超市买东西的单子都是好几个区一起买的,于是外卖小哥们还是免不了要在超市里的所有区跑一趟。

以太坊也一样,假设里面有一万个账户,节点们的确可以互相商量一下,说一人负责1000个账户。但是谁都不知道接下来的交易要操作哪些账户,从哪些账户读取数据,又更改哪些账户。如果最终交易总是这样同时读取和操作多个账户,那么分片的意义就失去了。

那这样的话,类似以太坊的区块链就无法进行分片了吗?

也未必,只不过,随机分片和网络分片就不适用了。

根据应用分片

实际上,在讨论菠菜的智能合约的时候,我们已经可以感觉出来了——如果是菠菜交易,我们这些不参与菠菜人有什么必要知道吗?

这实际上和之前的“中国发生的确实没有必要让美国的节点知道啊”的逻辑是一致的,也就是说,其实之前我们在做的,与其说是根据网络或者地区进行分片,实际上就是根据应用进行分片——网络和地域已经天然地将“交易”这个应用根据交易活跃程度划分了片,换句话说,如果我们要把一个数字货币的区块链按照它应用的逻辑,也就是交易频率进行划分的话,那么大概率最终划分的结果和网络分片是一致的。

于是,对于交易之外的应用,想要分片真正达到最好的提高输出的效果,也应该根据交易的类型和频率分布进行,让互相频繁交易的节点尽量都在一个分片内,让跨片区的交易尽量少——毕竟,一笔片内交易只需要片内的节点收到就行,而跨片交易则至少需要两个分片和跨片节点收到,如果牵涉的片更多,则需要知道的节点更多。

同时,由于这种根据应用分片的方式从逻辑上也更容易理解,而能够理解的逻辑其实就是状态分片的前提——就如同刚才的比方,虽然乍看上去来超市的单子很多都会买各个区域的东西,但是如果能够找出其中的规律,比如很多单子只有生鲜和蔬菜,而有的单子只有酒水和饮料,那么我们就能够根据我们所知的“超市购物”这种特殊应用的特性来进行分片——原本,快递员不知道每单都会要买什么东西,迫不得已,只好在超市里做好什么都要买的准备。但是,如果他知道生鲜和蔬菜的单子多,那么他就可以只做好买这两种东西的准备,而不用去跑其他的区了。

而甚至于,如果这个超市买这两样东西的人都非常多,这个超市甚至可以单独开一个柜台,单独给这个部分搞一排收银。而这个买生鲜和蔬菜的区域,实际上就根据应用的特点,形成了一个单独的分片,这个分片只保存关于特定应用需要使用的状态,也就是只进生鲜和蔬菜。如果想买别的东西行不行呢?可以,那么这笔交易自然就成了一笔“跨链交易”,因为负责处理这笔交易的节点都不在自己这个分片中。于是,收到这笔交易的矿工,也就是收银员,将启用上文中提过的跨链交易的方法来处理这笔交易。

同时,这种方法实际上鼓励参与应用的使用者去主动加入应用所在的分片,例如,如果你是一个某个DeFi合约的频繁使用者,为了避免每次都用跨片交易调用这个合约,可以在这个合约的分片创建一个地址然后用这个地址去专门负责调用这个合约,然后再定期去和原地址进行一笔跨片交易。

于是,实际上即便是随机分片,只要时间足够久,最后也会出现这种按照应用分片的情况出现。但另一方面,前文中也说了,如果时间太久,这种根据应用的分片实际上还是会出现和根据网络分片同样的问题——美国的节点可以不相信中国分片的验证结果,那么交易的分片也可以不相信菠菜分片的验证结果。但如果我们定期打乱重新随机分片的话,这种自发形成的根据应用分片又没有了。

因此,一个被以太坊2.0和NEAR采用的方式是让分片固定,而随机选取每个分片的验证者,并定期进行轮换。而一个更好的思路是——这些验证者不仅是随机的,还是隐藏的,即可以采用可验证随机数(VRF)的机制,让攻击者没法知道一个分片的当前验证者是谁,直到他们完成验证并且对结果签名之后。这样,既保证分片对交易分割的有效性,又能够保证每个分片的安全性。


以上,基本上就是目前随机分片这种主流思路和分片机制的问题了。

但如果我们能跳出“分片”这个词带来的先入为主的印象和分布式数据库或者随机分片的窠臼,我们是不是有更好的方案呢?

本文首发于:https://zhuanlan.zhihu.com/p/448862074

本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
maxdeath
maxdeath

上海唯链科技信息科技有限公司 高级区块链研究顾问

40 篇文章, 1121 学分