星球日报
搜索
手机客户端
iPhone · Android
公众号
微信公众号

星云研究院:Avalanche论文解读(一)

2019-02-25

permissionless blockchain到底有什么最新的研究。

本文作者:星云研究院资深研究院汤载阳博士。华中科技大学计算机博士,日本会津大学和法国南巴黎国立电信学院访问学者,研究方向包括分布式系统、无线网络和区块链共识,在TPDS、ICDCS等顶级期刊会议上发表过论文。

上一篇介绍了Hyperledger相关工作,这一周我们来看看permissionless blockchain有什么最新的研究。

这篇论文“Avalanche: The Power of Metastable Consensus”实际上还没有被正式接收,来自于Cornell的Robert Kleinberg和Emin Gun Sirer研究组(顺带插一句,Cornell另一个大名鼎鼎的blockchain team就是石润婷老师研究组)。虽然还没被接收,但仍然是一篇质量非常高的论文。

个人觉得整个论文架构有一些说不上的奇怪,前半部分风格比较偏系统,后面的证明部分又略显晦涩。同事告诉我这篇论文其实是由两个同学共同完成,一个早期提出了理论模型,一个负责系统实现。这也是为什么我打算分两篇来解读的原因,不过很有可能后面的理论证明部分我看不懂就放弃写第二篇了。

Basics

首先还是介绍下文中的一些基本概念。

在任何基于复制状态机(replicated state machine,RSM)的分布式系统,都需要满足两个特性,即安全性和活性,文中定义如下:

P1. Safety. No two correct nodes will accept conflicting transactions. 
P2. Liveness. Any transaction issued by a correct client (aka virtuous transaction) will eventually be accepted by every correct node.

在很多其他论文中,这两个特性又称之为consistency和liveness,这里就不纠结了。

Slush

论文首先提出了名为Slush的共识算法,也是整个协议簇中最简单最基础的部分。Slush是非拜占庭协议,意味着其不能容忍作恶节点的存在。作者抽象出一个“染色”问题:任何时刻所有节点可能处于{red,blue,⊥ }三种状态之一,共识就是如何通过节点间的通信使得所有节点最终的颜色一致。

Slush算法描述如下:

星云研究院:Avalanche论文解读(一)

算法解释:

  • 在起始时刻,所有节点都是uncolored状态;

  • 节点u循环发起Query,总共m轮,每轮随机选择k个样本发送包含自身color的Query;

  • 当其他节点v收到一个Query时,则返回一个包括自己color的Respond,如果此时节点v还是uncolored状态,则先将Query中的color更新为自己的color再Respond;

  • 一旦收集到k个Responds,节点u判断是否存在某个color数大于等于αk,α > 0.5表示一个协议参数。如果存在某个color(red or blue)满足该阈值则将自身color更新为该color;

  • 如果没有在限定时间收集到k个Responds,则u重新抽样发送Query,直至收集到k个Responds

slush有如下优点:

  • memoryless,每轮之间节点除了自身color不记录额外信息;

  • 小样本抽样,不同于其他算法需要对所有节点发送请求,slush只需要发送k个请求;

  • 抗亚稳态,即便是50/50的初始状态(文中称之为metastable state),也可以通过抽样的随机扰动(random perturbation)打破平衡,然后反复抽样放大优势;

  • 如果m足够大,算法可以保证所有节点都有同等机会被染色;

但是slush并不能提供足够强的拜占庭安全保证,如果存在拜占庭节点故意将自身color变成和主流color不一样,则可能打乱平衡。因此slush并不是BFT,但为后续机制提供了基础。

Snowflake

相比slush,第二个算法snowflake做了进一步改进,其中轮询部分如下:

星云研究院:Avalanche论文解读(一)

详细分析:

  • 每个节点引入了一个计数器cnt变量,初始cnt=0,每当一轮Query返回的k个Responds某个color满足 ≥ αk,则将其cnt+1;

  • 如果满足条件的color和自身color不同,则将自身color设定为该color,并且重置cnt;

  • 引入另一个安全系数β ,当cnt大于β时,则最终确定该节点color,而不需要执行m次询问。

当给定一个ε-guarantee的拜占庭环境,Snowflake可以保证Safety和Liveness。

Snowball

snowflake中每次color翻转时cnt都会重置,理论上来说已经足够安全。Snowball进一步作出改进,通过引入confidence counter保证更加持久的可信度,使协议更难被攻击。算法具体如下:

星云研究院:Avalanche论文解读(一)

详细分析:

  • 对每个color都增加一个confidence counter,例如d[R]、d[B];

  • 每当一轮Query返回的k个Responds某个color'满足 ≥ αk,将该color'的d[col']+1,如果d[col’]最大,则将自身col更变为该col’;

  • 进一步地,如果col’和上次Respond通过阈值的lastcol不一样,则更新lastcol为col’,并且重置cnt;

  • 如果col’和上次Respond通过阈值的lastcol一样,则cnt+1,当cnt大于β时,则最终确定该节点color。

总的来说,Snowball中仍然是连续β满足阈值条件的color才可能成为最终color,但confidence counter的引入保证了最终确定的color同样具有高信任度。

Avalanche DAG

作为论文中协议簇的最终版本,Avalanche将Snowball拓展为multi-decree protocol。

为了适用于资产交易这样的真实场景,Avalanche相比前三个算法引入了很多新概念,具体如下:

星云研究院:Avalanche论文解读(一)  表示节点u内所记录的所有交易集合; 
星云研究院:Avalanche论文解读(一) 表示所有和交易T冲突的交易集合(这里论文描述不够清楚,PT应该包括T本身),比如两个冲突的交易Ti和Tj,由于冲突具有传递性,有 星云研究院:Avalanche论文解读(一) ,每个冲突交易集都有pref和cnt两个属性,简单地说这些都跟交易T的confidence value相关,具体后文会详细介绍。

所有交易以有向无环图(DAG)的形式联系在一起,类似IOTA和Conflux。

星云研究院:Avalanche论文解读(一) 表示交易T的parent是T’; 
星云研究院:Avalanche论文解读(一) 表示从在至少一条路径从交易T到交易T’。

论文中提到“DAGs built by different nodes are guaranteed to be compatible”,这里并没有做过多的解释,个人理解是理论上DAG可以维持偏序(partial order),即DAG可以保证交易之间的相对顺序。举例来说,如果某个节点中存在 星云研究院:Avalanche论文解读(一) ,那么系统中所有节点都应该有 星云研究院:Avalanche论文解读(一)的关系,反之亦然。

有如下图所示的某个DAG

星云研究院:Avalanche论文解读(一)

图中,每个方块表示一笔交易,具有一对 <chit, confidence> ,可以看到颜色更深的方块confidence 更高。而每个交易都有一个冲突交易集,例如T9、T6和T7属于同一个冲突交易集,即PT9=PT6=PT7,但由于T9具有更高的confidence,因此该交易集的preferred tx=T9。

上面提到每个PT包括了pref和cnt两个属性,初始化的PT只有T本身,因此PT.pref=T,PT.cnt=0。当后续收到更多冲突交易后,PT集合增加,pref和cnt的更新则发生在收到Respond后(见下一部分)。

星云研究院:Avalanche论文解读(一)

Avalanche发送Query和收集Responds流程如下:

星云研究院:Avalanche论文解读(一)

详细分析:

  • 节点u找到新交易T(还未确定的交易,即 星云研究院:Avalanche论文解读(一) ),启动一轮Query,即随机抽样k个节点发送包括该T的Query,注意此处Query中实际上包含了T和以及在DAG中所有T可达的其他交易(ancestry);

  • 对收到Query的节点而言,如果Query中的T以及其祖先交易在其conflict sets中处于preferred option,则返回yes-vote,反之则返回no-vote;

  • 节点u收集返回的k个Responds,如果该T满足阈值(即有超过αk个节点返回认可该交易的positive Responds),则该交易的cT赋值为1(收到一个chit),并且更新T交易所有祖先交易T’对应PT’的pref和cnt;

  • 类似Snowball,节点u对T有一个confidence value,其计算方法如下:

星云研究院:Avalanche论文解读(一)

简单地说就是交易T的d(T)等于其所有后代交易的cT’(即T’的chit)之和,chit的获取方式见第三步。需要指出的是,任何交易的chit只可能为0或1,但随着DAG规模的不断增长,dT也会随着其后代的增加而表现出单调增特性。

这里再详细介绍下第二步中,Query返回positive和negative的机制。当其他节点收到u发送的Query后,在DAG中找到T的所有祖先交易T',如果每个T’在其冲突交易集合PT’中都处于preferred状态,则返回一个yes-vote,反之返回no-vote。具体描述如下:

星云研究院:Avalanche论文解读(一)

最后,跟比特币一样,Avalanche 也把对最终交易的确认时间点(acceptance point)和决定权交给了应用层。应用层通过自己定义的谓词(Predicate),把接受交易的风险加入考虑。

确认一笔交易可以通过一个叫做 “safe eary commitment” 的动作来完成。对于诚实交易 T(virtuous transaction),如果它是在包含它的冲突交易集 PT 中的唯一交易,并且受到的 Chit 超过阈值 β1,那么就认为 T 是可以接受的。如果一个诚实交易 T 由于 liveness 问题没被接受,那么它依然可以通过重新选择不同的 parents 交易来被接受。

由于不同的交易只会消费和生成自己的 UTXO,彼此互不相干,因此,任何交易都可以重新选择 parents。

至此,Avalanche整个流程介绍完毕,抽象而言,节点间的通信如下所示:

星云研究院:Avalanche论文解读(一)

Experiments

实验部分主要包括了对Throughput和Scalability测试,这里简单放下结果。

星云研究院:Avalanche论文解读(一)

星云研究院:Avalanche论文解读(一)

总结下来就是,Avalanche可以保证在节点规模在2000左右时,仍然有将近7000TPS。如此之高的性能得益于三点:

  • Avalanche本质上来说就是DAG,在只需要保证偏序的情况下,可以允许更多的并发,而传统的BFT策略则是需要保证Linearizability,开销更大。PS:很难简单地评价两者那种更好,因为在有智能合约运行的场景下,只保证偏序是显然不够的。

  • Avalanche不存在Leader,后者则可能成为性能瓶颈;

  • 每个节点通过采样只和k个其他节点通信,因此在网络规模增加时通信开销也不会增加太多。

难得的是,论文复现了Algorand和Conflux的实现,并且做了横向比较,为了统一,这里全部采用Bitcoin的transaction平均数据规模(250bytes)。结果如下:

  • TPS:Bitcoin为3~7,Algorand为874,Conflux为3355,Avalanche为3400;

  • Latency:Bitcoin为10~60mins,Algorand为50s,Conflux为7.6~13.8mins,Avalanche为1.35s;

Thinking:

  • 可以发现,同样都为DAG(虽然Avalanche不承认自己是),Avalanche和Conflux在TPS上几乎一样,实际上最原始的GHOST也能达到这个级别的性能。所以个人认为单从TPS上而言,Avalanche并没有太大提升。

  • 论文中作者承认cryptographic verification是当前一个主要性能瓶颈,但个人认为另一个瓶颈在于节点处理Query的环节,当中需要判断交易T isSTRONGLYPREFERRED,而这一步实际上需要遍历T所有的祖先交易的冲突交易集合,随着交易的增加这个开销将会变得非常大。

  • 尽管作者不愿意在论文中引用IOTA的工作,但两者确实有很多相似之处,核心思想都是优先保证诚实节点的liveness(交易只有接在正确的分支上才能被快速接受)。但两者都缺少economic incentive,并不能消除拜占庭节点的作恶动机。

原创文章,作者:星云链。转载/内容合作/寻求报道请联系 report@odaily.com ;违规转载法律必究。

参与讨论

登录后参与讨论

星云链

特邀作者

星云链

星云链是自治元网络,协作的未来已来。

总文章数: 2


分享至

微信扫一扫分享

0