文章标题:《LibraBFT算法简述》文章来源:知乎专栏作者:任之劼
首先,不熟悉BFT的人可以看看我之前的三篇文章:
《区块链时代的拜占庭将军们》《区块链时代的拜占庭将军们》《区块链时代的拜占庭将军——区块链共识算法的发展趋势》
其实我是在发完第三篇之后就看到了Hotstuff,当时非常犹豫要不要把这个算法加进共识算法的发展趋势里面,后来放弃了,因为我觉得新算法层出不穷是加不完的,当然,我现在有点后悔这个决定——要不然现在就可以拿出来吹一吹了。另外一点,也是好巧不巧的,用BLS来降低BFT的消息复杂度这个事,正好是我扩容那一系列下一篇的内容。不过那些内容在这里我准备简述一下,然后细节可以继续关注我的专栏。
HotstuffBFT
Hotstuff这篇论文我记得是年初的时候发在arxiv上的,一作是一位康奈尔的中国博士,然后论文会正式发表在今年的PODC上。不过,在正式发表之前,就已经被LibraBFT用了而大火了一把。
这篇我们不具体说Hotstuff的细节,而是更说一些Hotstuff的思路和贡献。当然,我觉得对于许多区块链的从业者而言,具体的细节可能并没有这些来的有趣,同时,直接看论文的时候,其实不如这样的思路来的清晰。
大网络中的BFT
BTC 24小时资金净流出186.34亿元人民币:金色财经监测数据显示,加密货币市场24小时资金净流出排名前三分别为[2021/2/1 18:38:43]
这个其实不算是Hotstuff的贡献,而是其实就像我在BFT第一篇就说的,是区块链为BFT算法这个问题带来的一个新的场景和挑战。而这其中的第一个挑战,就是把O(n^2)的消息复杂度降到O(n)。但是,本身这件事并不是Hotstuff的创新,因为基本上所有目前的BFT都有了O(n)的消息复杂度。
Hotstuff达到O(n)消息复杂度的方法其实已经是一个比较经典的方法了,就是采用聚合签名,然后假定leader是诚实的让leader去收集签名。采用聚合签名的方法其实从Byzcoin就有了,然后其实很多共识算法,不仅限于BFT算法,例如Dfinity,也在采用这类方法。这个方法我在后面的一篇扩容的部分会详细写到,在这里就不赘述了。
BFT与链的结合
传统BFT达成共识的方法是两轮共识,其中第一轮定序,第二轮commit。很多将BFT用于区块链的项目仍旧采取「先做两轮通信,然后达成共识,最后上链」的模式,而Hotstuff采用的是「先上链,在区块中加入聚合签名,于是,在n个区块之后就可以视为通过了n轮的通信达成共识」。
于是,其实根本就不需要再去区分所谓prepare,commit这两轮通信的区别了,只需要简单地把每一轮节点的行为定义成「leader负责出块和收集签名」,然后「其他节点负责对leader出的块进行签名」,然后,只要收集到了2f1个签名,leader就可以出一个块,然后后面有n个块就相当于达成了共识。
BTC合约多空持仓人数比0.78 季度合约基差在800美元附近波动:截至12月16日10:30,根据OKEx交易大数据,BTC合约多空持仓人数比为0.78,市场做多人数下降;季度合约基差在800美元附近,永续合约资金费率转负,交割及永续合约持仓总量维持14亿美元附近波动,总体上多军实力相对占优;BTC交割及永续合约精英持仓方面,做空账户比为50%占据优势,多头持仓比为20.96%占据优势,精英账户多空双方出现分歧,继续关注大户持仓变化。从期权合约数据来看,看涨/看跌主动买入量比为0.83,主动看涨买入量下降。[2020/12/16 15:21:20]
这点的好处在于,O(n)的通信复杂度可以让诚实节点知道「我知道消息m将成为共识」,但是必须要O(n^2)的通信才能让每个诚实节点都确信「我还知道所有诚实节点也知道消息m是共识」,而通过leader收集签名并出块这种方法,当所有人看到区块b的时候,诚实节点会知道「我知道b是共识」,而在看到b后一块b'的时候,诚实节点等于知道了「所有签名的人也都知道了b是共识」。于是,每次出块的时候都只需要O(n)的消息复杂度,但是,在一个诚实leader和聚合签名的帮助下,通过两轮的O(n)消息复杂度,我们达到了之前O(n^2)的效果。
并且,这个事情和b'的共识的第一轮是同步进行的。换句话说,就是把每一轮BFT的过程也链起来之后,还把通信复杂度减少了一半。这一点,虽然之前也有类似的想法,但是我个人觉得Hotstuff是第一个把这个思路确切地落在算法里的,这点我觉得非常有趣,同时,也是未来的一个方向。
分析 | BTC多头交易热情高涨 多空比呈近3月高位:据TokenInsight数据显示,反映区块链行业整体表现的TI指数北京时间02月07日8时报752.39点,较昨日同期上涨10.4点,涨幅为1.4%。此外,在TokenInsight密切关注的10大行业中,24小时内涨幅最高的为治理协议行业,涨幅为164.79%;24小时内跌幅最高的为金融服务行业,跌幅为0.63%。
据监测显示,BTC 24h成交额为$374亿,活跃地址数较前日下降10.96%,转账数较前日上升0.33%。Coinwalle分析师Jeffrey认为,BTC多头交易热情高涨,多空比呈近3月高位,短期或将盘整。
另据Bituniverse智能AI量化分析,今日行情可开启LTC/BTC币币网格交易,区间0.006667-0.008199 BTC,同时赚取两币超额收益。[2020/2/7]
其实这个方法是从两个方向逐渐靠拢的——第一是从BFT的方向,大家逐渐意识到其实链式结构可以省掉BFT中的很多事情,例如其实我们不需要定序,而且对于后面一个区块达成共识实际上就相当于对于前面的区块进行了共识,而很多BFT算法,例如:avalanche都开始注意到了这个事;而从区块链共识算法,尤其是追求finality的方向来看,人们发现其实一个区块后面跟上2f1个节点的出块,就相当于达成了BFT,而如果通过多个人对于这些区块签名可以加速这个过程,像这一点,也在例如Polkadots这类的算法中有所体现。而Hotstuff可以说是这两种思路到了这个阶段最简洁的融合。
BFT的快速响应
大网络BFT算法在实际应用中最复杂的问题实际上是viewchange,这点我听不止一个采用PBFT算法的人说过了。这是因为实际上在PBFT以及所有传统BFT其实都是基于传统的拜占庭将军问题的,也就是说,我们会先假设leader是诚实的,然后以他为主导达成共识。
于是,viewchange是个不得已的事情,需要所有的诚实节点先timeout,然后对于viewchange这件事达成共识,然后,他们把这个共识告诉新的leader,新的leader还要把这个消息广播出去宣布viewchange,于是,这个viewchange的cost是O(n^3)。
这其中有两个问题:一个是viewchange的消息复杂度,一个是viewchange必须要等到诚实节点对于viewchange达成共识之后才会发生。
Hotstuff的一个非常有趣的新意在于把传统BFT的两轮共识变成了三轮,然后借此把viewchange的cost变成了O(n)。这个可以这么理解:传统的viewchange是O(n^2)消息复杂度,也就是说,所有的诚实节点在viewchange之前会确认所有的诚实节点确实都进行到下一个view,而在Hotstuff中,viewchange不需要等「我知道其他人也知道viewchange了」这件事就可以进行,于是,消息复杂度就降到了O(n),也就是说,只要诚实节点的内置timeout到了,那么就可以发viewchange给新的leader开始viewchange。
为什么需要把两轮变成三轮呢?因为之前BFT链式结构的简化中,严格来说这两个通信复杂度为O(n)的区块和PBFTO(n^2)消息复杂度的prepare和commit还是有区别的——当有两个区块连起来的时候,两边是相当的,但是其实每一个区块的消息复杂度都只有O(n),并不说明所有诚实节点都知道「所有诚实节点都会达成共识」。
而同样,viewchange的消息复杂度也只有O(n),于是如果一条消息刚有第一个区块的时候viewchange了,那么诚实节点会对于第一个区块是否达成了共识产生不一致,因为prepare和viewchange看起来都很有道理。
而把两轮变成三轮之后我们就解决了这个问题。因为我们可以规定任何两轮之后的东西才是共识,而如果没有到两轮就不算——对于prepare和viewchange都是如此。
于是,如果viewchange发生在第一轮之后,那么我们不认为之前prepare的是正确的,而viewchange也同理。相反,如果在第二轮之后发生viewchange,那么由于已经经过了两轮,所以这条消息已经经过了定序,即便在viewchange之后也会最终达成共识。
所以总体来说,Hotstuff的核心思路如下:
采用聚合签名的结构把每一轮的消息复杂度变成O(n);
用链式结构把O(n^2)的共识变成了两轮O(n)消息复杂度的区块提交;
在这种结构下,把viewchange的消息复杂度降到O(n),然后为了防止viewchange造成的不一致,把两轮区块提交变成了三轮;
整体下来,虽然前两条也很有趣,但是最核心的优点是viewchange变得更容易了,无论是时长,消息复杂度,还是对于下一任leader的工作压力。虽然代价是需要多一轮通信,但是这样的延迟,无论是对于世纪中viewchange的可能延迟,还是对于习惯了区块链共识算法延迟的我们而言,其实都不值一提。
LibraBFT
LibraBFT基本上就是Hotstuff,只不过在这之上做了两点改动。
其中一点是将Hotstuff用于区块链时候加上了现实考量的机制,例如引入了epoch的概念,允许共识节点替换,同时加上激励机制和惩罚机制…
另外一点是同步性上的改进:
Hotstuff是在partialsynchrony网络中生效的,这已经算是一个非常强的异步假设了,它和PBFT一样,但是现在很多的区块链算法都已经在用同步假设了。
而Hotstuff里的轮其实概念更像是PBFT的几个步骤,也就是说实际上这个轮不是一个时间概念,而是和PBFT一样,是上一个步骤结束之后自动进入的。换句话说,一个区块出现有可能很快,但也有可能在ViewChange的时候要等很久。于是呢,LibraBFT使用了Pacemaker机制,让每一轮的时间尽量有一个上限。
以上就是关于LibraBFT的简介了。在我看来,Hotstuff是一个非常有趣,甚至有可能是最近对于未来区块链的共识算法最有启发性的一个算法。而Libra采用这个算法其实也很有道理,因为Hotstuff不仅有现在大部分BFT的高输出,而且解决了大部分通行BFT的viewchange的问题,而在实践中这却是是非常影响BFT算法在区块链环境中使用的问题。
当然,对于Libra本身,我的意见都在这个答案里了:《如何评价Facebook发布的数字货币Libra?》
反正,对于Facebook而言,这是个进可威胁金融业,统治区块链领域,甚至和主流货币扳手腕;退可造噱头,蹭热点,涨股价,最后搞个Facebook版支付宝或者微信支付的项目,甚至,即便它被相关机构叫停,它还是能洗白之前隐私盗窃犯的形象,摇身一变变成强权和守旧的挑战者,对于Facebook而言,它几乎一定会成功,只不过是程度问题。
但是,无论如何,它都会对于区块链领域造成深远的影响,不是因为它做的事,不是因为它的技术,不是因为它可能的成就,而是因为它是Facebook。
因此,在以上这个意见里我没有提到的是,我觉得无论成功与否,它对于区块链整个行业造成的影响,都未必是正面的——如果它取得了巨大的成功了,以现在的路线,我们可以看到的是区块链对于互联网巨头挑战的失败,以及区块链领域再次被大鳄占领;如果它没有取得巨大的成功而只是一个成功的噱头,我们会看到其他的大鳄们站台的无数跟风的噱头出现,再割完一圈韭菜后翩翩离场,留下一个不再有任何生机的区块链行业。
来源链接:zhuanlan.zhihu.com
郑重声明: 本文版权归原作者所有, 转载文章仅为传播更多信息之目的, 如作者信息标记有误, 请第一时间联系我们修改或删除, 多谢。