8BTCCI: 16031.87 +5.89% 8BTCVI: 11365.38 +2.71% 24H成交额: ¥4901.90亿 +4.39% 总市值: ¥20091.04亿 +5.56%
突破区块链不可能三角(二)——在比特币POW之上的尝试

突破区块链不可能三角(二)——在比特币POW之上的尝试

maxdeath 发布在 比特币 海盗号 40679

最近比特币的上涨似乎是在提醒着大家,比特币在十年之后似乎还是有着蓬勃的生命力。这一点,无论从软件还是从信息技术的角度来看都是一件无比神奇的事情——同样是来自2009年的产品,windows 7已经进入了最后的时光,iphone 3早就已经不见踪影,而许多我们现在习以为常,仿佛从很早以前就一直存在的东西,例如小米,例如ipad,甚至,例如微信,其实都还尚未诞生。

但是,实际上,无论是ipad还是微信,都早已经不是当初的样子。但比特币却不然,从性能到功能,相比于最初的版本仅仅是在功能上有些许审慎的改进。这其中的缘由,固然有区块链本身去中心化的特性,也有之前在专栏第一系列分叉的部分提到的政治和路线之争,但归根结底的原因是——

比特币的POW设计,实际上是十分精妙的。

我个人并不认为这是中本聪有意为之,或者说,中本聪对于POW的设计的是非常巧妙的,但是,由于他非科班出身的背景(参见我对于他身份的分析的答案)

https://www.zhihu.com/question/305973025/answer/628460658

https://www.zhihu.com/question/67192203/answer/251020050

他无法去用严格的数学来证明这种算法的有效性,然而,他却需要最简单的逻辑来说服自己以及其他人这个算法确实是有效的,因此,他给了算法足够多的冗余,例如十分钟的区块间隔,来让读者从直觉上相信“这个时间足够所有人同步这个区块了”,而不去纠结如果这个假设不成立会出现什么结果。

于是,这就是比特币POW巧妙的地方——它的算法极简单,简单到不需要严密地推论和证明就能令人信服它的可行性。但另一方面,却也让人不禁去想——这里似乎有这么多可以改进的空间,只要稍加修改,就能……

然而,大部分拍脑袋的对于比特币的改进方案实际上都引入了额外的机制,而这些机制在最终都被证明了引入了额外的安全隐患——因为实际上,比特币的机制尽管简单,却恰恰符合了信息安全的基本原则——越复杂的机制,就越容易出错。

对于这点,张韧同学的这篇论文有非常精彩的论述。

https://www.esat.kuleuven.be/cosic/publications/article-3005.pdf 

当然,这并不代表比特币的POW完全没有改进的空间,而正相反,POW的改动空间相当大,只不过,做出改动的人需要知道自己到底在改什么,又或者说,很微小的改动都会造成一些连锁反应,于是需要相应的机制去修复,因此,如果一个改动看起来还和原版POW一样简洁,那么它多半是有问题的。于是,这里其实留给非专业人事操作的地方就不多了——想要改进比特币POW,需要从更深入的角度去理解POW和分布式系统。

这里,我们从可扩展的角度介绍一些经典的POW扩展方案。

在前文已经说过了,区块链比特币可扩展性的瓶颈在于——任何一笔交易需要发给所有节点。

而这其中,比特币POW有一个额外的限制,就是POW的有效性是建立在所有人都在同一条最长链上挖矿的,于是,大致上说,只有上一个区块被挖出来并且同步到整个网络之后,共识算法,即挖矿,才能开始进行。

这里,大家已经看出来了——这基本上是个同步系统。

而这个时候有人可能会提出异议——众所周知比特币POW是个异步拜占庭容错算法,我们现实所处的也是个异步环境,为什么你说比特币POW是个同步算法?

这是对于比特币POW的一个常见的误区。实际上,POW只有在基本同步的网络中才有效。然而,比特币POW用激励的方法鼓励1,节点不做恶意的行为;2,节点尽量去和其他节点保持同步,来保证这个系统基本上是同步的。之所以说是“基本上”,是因为确实我们不需要绝对同步,我们的要求是——POW的时间,即区块间隔,需要远大于同步所需要的时间,才可以认为这个系统是基本同步的。换句话说,

比特币的共识算法必须需要一定时间来进行,而且必须在所有节点同步,即传输和验证完所有交易之后才能开始。

换句话说,比特币的共识算法是这样的:

然而,我们希望所有的带宽*时间都用来在网络中传输交易,而不希望先做一个时间t1的同步,确保所有人都对于最长链有共识之后再开始进行一段时间t2的POW计算达成共识。而在t2的这段时间是无法做同步的,因为在没有共识的前提下,我们并不知道哪个区块是正确的,于是,这时候的带宽就被浪费了。

理想状态是,我们能够一边做共识一边同步?那需要做的第一步就是,我们需要把比特币POW中的共识和交易(区块内容)脱钩。

对于分布式系统专家们来说,最顺利成章的事情就是把拜占庭容错的state-of-the-art,也就是PBFT套进去。为什么要套PBFT呢?因为从传统分布式系统来看的话,比特币最不能容忍的地方并不是他的输出或者说是可扩展性,而是a)长达6个区块(一小时)的延迟;b)没有最终性(finality),即永远无法确认达成共识。然后,才轮得到一个小问题,即c)输出太低。但同时,分布式系统专家们也看到了POW的一个明显的好处,就是非许可。于是,自然而然以及不约而同地,Hybrid consensus和Byzcoin两篇论文做了一种简单地将用POW作为一种准入机制然后进行(类)PBFT的方法。

两个算法的原理基本上都是保留比特币POW的一切特性,例如区块奖励,例如出块时间等等。但是,POW不再决定交易,而只做委员会选举——例如,我们规定,最近的100个出块者是当前的委员会,然后由他们进行BFT决定交易,这里的交易是最终的也就是绝对的,不存在分叉的问题,然后把广播给全网。然后我们可以认为这样决定的交易就是最终结果,于是解决了(a)(b)两个问题,然后顺带的,因为POW的共识只决定出块者,所以交易的输出不再受限于POW,而只受限于BFT的输出。而无论是在做BFT还是做完BFT把交易广播到全网的时间里,都不影响POW继续进行下一轮共识。

通过这种方法,我们相当于对比特币POW进行了这样的改动:

这里,委员会的验证是和共识差不多同时进行的(BFT算法),而委员会达成共识的结果将直接广播给全网,这个过程和下一轮委员会的选举也是脱钩的。

和这两种思路从扩展的角度近似,但是路线不同的是Bitcoin-NG。

Bitcoin-NG其实更好理解——首先还是照常用比特币POW,只不过,这个时候出来的区块里面不用包含所有交易,只是宣布——我是竞争胜出的合法出块者。然后,在十分钟之内,这个出块者可以以更快的速度(更短的区块间隔)发“微区块”,其中只包含交易而不需要再做POW,因为他已经竞争得了这一次的出块权。这样的话,我们达到了和Hybrid Consensus以及Byzcoin一样的效果——用POW选取出块者而不是区块,于是交易本身就和共识脱钩了。

但是这里有个问题——如果微区块有非法交易怎么办?乍看上去我们可以直接用POW的方法解决问题——“如果发现了微区块有问题就忽略掉出问题的区块,然后让下一个算出POW的人出块”。然而,这种方法等于又把交易同步速度和共识挂钩了,于是又会出现和比特币POW一样的问题——即,来不及接收和验证所有交易的节点有可能把算力浪费在最终被废弃的链上。

于是,Bitcoin-NG需要一个不去替换出块者或者交易块(以防算力被浪费),但是能够无效话非法交易和惩罚出块人的机制。这个机制被称为“有毒交易”,简单说就是当非法交易被发现的时候,后面的节点可以将这个交易注明无效,然后拿走提交非法交易的出块者之前获得的区块奖励。

这样的话,我们可以比较一下Hybrid Consensus(Byzcoin)和Bitcoin-NG的异同:

相同点:两者都通过用POW选取出块者而非区块(交易)本身的方式把共识和交易脱钩。

不同点:Hybrid Consensus(Byzcoin)中,通过BFT决定交易,于是我们认为交易已经是可信的。而Bitcoin-NG中出块者发出来的交易仍旧未经验证,于是可能是非法的。于是,Bitcoin-NG中所有节点需要在同步交易之后验证交易的有效性,然后Bitcoin-NG根据博弈论设计了另一套激励(惩罚)模型,来保证微区块中交易的安全性。

所以说,实际上Bitcoin-NG可以表述为:

这里,共识0指的是某种初步的共识,然后,最终形成的共识是在传输之后。如果最终共识总是和初步共识不一致的话,这个算法实际上就会退回成比特币POW。然而,只要大部分时间最终共识和初步共识一致,这个算法就可扩展了。

但是,虽然两者看起来只是POW的简单变体,但需要注意的是:

两者都改变了比特币的安全模型——后者我们已经说过了微区块中的交易需要通过“有毒交易”来惩罚,而前者由于需要进行BFT,所以安全性假设需要改成“不超过1/3的算力被恶意节点掌握”,这点和比特币假设中不超过50%算力安全是不一样的。而且,尽管从理论上来讲,Hybrid Consensus并没改变最近100个出块的人,只不过是把轮流出块变成大家一起商量着出块了而已。然而,这种改变仍旧会给人中心化的感觉,尤其当90%以上的算力都集中在大矿工的手中的时候——在比特币POW里,小矿工还能出块,但是如果在委员会之中,小矿工的意见就会淹没在90%的大矿工之中。而且,委员会选举会陷入这样的两难——比如,如果委员会大小过小,那么了解概率的人都知道,这10个节点中超过3个是恶意的概率是不小的,因此安全性保证不了。而如果这个委员会过大,那么BFT本身的复杂度和延时又会变得很大,使得算法失去了扩容的意义。

但其实,以上的这些,是一些理论上需要注意的问题,但并不是缺陷。从安全性来讲,虽然两者改变了安全性假设,但是并不是就不安全了,也并不是说两者就一定比比特币POW要不安全,毕竟比特币POW也有例如自私挖矿这种问题。然而,无论是比特币特有的政治因素,还是整个比特币的社区意愿和对安全性的担忧,再者就是比特币硬分叉的难度,都不会允许比特币对算法进行如此之大的改变。而再之后,POW在学术界中的热度也迅速降温(参见之前文章中BFT的发展历史),于是,仅有非常少的系统最终采用了这两种POW算法(有某个知名项目用了Bitcoin-NG)。但两者的思路——先选取委员会再进行BFT和先选取区块发布者的这种思路,完完整整地被例如Algorand和Snow-white或Ouroboros这种POS算法继承了,这几个我们下次讲。

此外,还有第三种方法。

让我们把自己带入比特币的矿工来重新思考一下为什么分叉会导致比特币的安全性下降。

当你收到一个区块的时候,你开始对这个区块进行验证,确认区块的合法性之后,你开始在这上面挖矿。然而,在收到第一个区块10秒钟之后,你收到了另一个区块,然后,在通过验证之后,你发现它也是合法的……

这个时候,你将面临一个两难选择——你可以选择继续在第一个区块上挖矿,因为你觉得既然你先收到了它,也许很多其他的节点也一样。但是,你也知道有另一种可能性,就是也许你只是收到第二个区块的时间比较晚,而网络中其他的节点实际上最早收到的是第二个……但无论如何,你都只能选一个,选错的后果就是你挖的那个块最终没有出现在最长链上,而你的这些算力浪费了。

而与此同时,网络中所有的节点都在做这样的选择,也同样面临着算力被浪费的风险,这就是分叉导致比特币安全性下降的原因。

而这个时候,我们会想到一幅图——为什么我们不能两个都要呢?

201904151356206_副本

于是,我们得到了GHOST,也就是后来被用于以太坊的算法。在这种算法中,允许将看到的几个同高度的区块同时标记为前一个区块,然后其中一个为主,是“父块”,而其他几个为“叔块”。父块中的交易和比特币POW的父块同样对待,而叔块则只记录区块头,剩下的交易部分验证之后就丢弃。然后,最重要的部分是,将比特币POW的最长链共识改为最重链共识,即把分叉的深度也计入最长链的统计之中,于是,我们得到了这样的计算方法。

本图引自Ghost论文,链接见下。

https://link.springer.com/chapter/10.1007%2F978-3-662-47854-7_32

这样,即便在分叉很多的网络中,恶意节点也不会因此获得优势,因为深度为1的分叉的算力也会贡献给系统的安全,而不是被浪费掉。

通过这种方法,我们可以稍微地提高比特币POW的输出,因为我们对于同步的要求没有之前那么高了,只要区块中的所有交易能够在下个共识阶段开始之前完成同步,依旧不影响系统的安全性。

然而,这种做法仍旧是有局限的——我们仍旧达不到真正的可扩展,因为我们不能无限制地提高区块大小或者减小区块间隔,问题就在于,深度>1的分叉仍旧不能被纳入共识之中,于是仍旧会造成算力的浪费。或者说,我们从某种程度上并行了共识和传输,但并不是完全并行。

而如果把GHOST按照这种思路扩展下去,把深度>1的分叉也包含进来,也就是说,当挖出新区块的时候,并不一定要指向上一高度的区块,指向之前的区块也可以。换句话说,交易同步不再有时间限制。甚至,我们也可以考虑不去丢弃叔块中的交易,而是让它们都作为账本的一部分,然后在采用一个一致的算法去判定冲突的交易和重复的交易,这样,我们就会得到Inclusive Blockchain Protocol,Spectre,乃至Phantom和Conflux。换句话说,比特币POW就转化成了现在大家趋之若鹜的DAG了。

而在一个理想状态的DAG里,矿工不需要再去管在哪个区块后面挖矿才能不浪费算力,也不用管自己的区块是不是包含了已经出现或者冲突的交易——只需要随便连上几个你知道的最近的区块然后做个POW把区块发出去就行了。而最终,系统会自行达成一个共识,而这个共识能够利用网络中所有矿工的算力,保证恶意节点想要进行双重支付的成本仍旧是全网算力的50%。

也就是说,我们得到了如下图的系统——带宽可以都用来传输数据,而共识可以与之并行进行——这是可扩展POW的另一个思路。

这次,我们主要介绍了比特币POW之所以不可扩展的原因和两个可扩展POW的思路。

我们将在下期中沿着这个思路,从可扩展的角度介绍POS和DAG的基本原理和挑战,顺带介绍一些明星项目,例如POS类的Ouroboros,Algorand,Dfinity,以及DAG类的Phantom和Conflux.

文章标签: 区块链 POW
评论(1)
登录 账号发表你的看法,还没有账号?立即免费 注册
  • 3ec9a86ae5 2019-04-16
    如果用户需要保存"叔叔块"们才能验证历史交易数据,那么和直接扩容区块有何区别?最长区块链式客观存在,所以能防止双花和作弊,你说的这几个方案都是直接给矿工仲裁权,简直是法币央行的翻版。社区要是能同意这几种更新,那比特币真的到了该归零的时候了。