星云研究院关于DAG最新研究:Avalanche论文解读(一)

自治元网络 · 协作的未来

 

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

个人觉得整个论文架构前半部分风格比较偏系统,后面的证明部分又略显晦涩。

同事告诉我这篇论文其实是由两个同学共同完成,一个早期提出了理论模型,一个负责系统实现。这也是为什么我打算分两篇来解读的原因。另外一篇,会择机进行推出。

Basics

首先介绍下文中的一些基本概念:

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

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.

在很多其他论文中,这两个特性又称之为consistencyliveness

 

Slush

论文首先提出了名为Slush的共识算法,也是整个协议簇中最简单最基础的部分。

Slush是非拜占庭协议,意味着其不能容忍作恶节点的存在。作者抽象出一个“染色”问题:任何时刻所有节点可能处于{red,blue,⊥ }三种状态之一,共识就是如何通过节点间的通信使得所有节点最终的颜色一致。

Slush算法描述如下:

算法解释:

  • 在起始时刻,所有节点都是uncolored状态;
  • 节点u循环发起Query,总共m轮,每轮随机选择k个样本发送包含自身colorQuery
  • 当其他节点v收到一个Query时,则返回一个包括自己colorRespond,如果此时节点v还是uncolored状态,则先将Query中的color更新为自己的colorRespond
  • 一旦收集到kResponds,节点u判断是否存在某个color数大于等于αkα > 0.5表示一个协议参数。如果存在某个colorred or blue)满足该阈值则将自身color更新为该color
  • 如果没有在限定时间收集到kResponds,则u重新抽样发送Query,直至收集到kResponds

slush有如下优点:

  • memoryless,每轮之间节点除了自身color不记录额外信息;
  • 小样本抽样,不同于其他算法需要对所有节点发送请求,slush只需要发送k个请求;
  • 抗亚稳态,即便是50/50的初始状态(文中称之为metastable state),也可以通过抽样的随机扰动(random perturbation)打破平衡,然后反复抽样放大优势;
  • 如果m足够大,算法可以保证所有节点都有同等机会被染色;

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

 

Snowflake

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

详细分析:

  • 每个节点引入了一个计数器cnt变量,初始cnt=0,每当一轮Query返回的kResponds某个color满足 ≥ αk,则将其cnt+1
  • 如果满足条件的color和自身color不同,则将自身color设定为该color,并且重置cnt
  • 引入另一个安全系数β ,当cnt大于β时,则最终确定该节点color,而不需要执行m次询问。

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

 

Snowball

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

算法具体如下:

详细分析:

  • 对每个color都增加一个confidence counter,例如d[R]、d[B];
  • 每当一轮Query返回的kResponds某个color’满足 ≥ αk,将该color’d[col’]+1,如果d[col’]最大,则将自身col更变为该col’;
  • 进一步地,如果col’和上次Respond通过阈值的lastcol不一样,则更新lastcolcol’,并且重置cnt;
  • 如果col’和上次Respond通过阈值的lastcol一样,则cnt+1,当cnt大于β时,则最终确定该节点color

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

 

Avalanche DAG

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

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

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

论文中提到“DAGs built by different nodes are guaranteed to be compatible”,这里并没有做过多的解释,个人理解是理论上DAG可以维持偏序(partial order),即DAG可以保证交易之间的相对顺序。举例来说,如果某个节点中存在

那么系统中所有节点都应该有

的关系,反之亦然。

有如下图所示的某个DAG:

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

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

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

详细分析:

  • 节点u找到新交易T(还未确定的交易
  •  ),启动一轮Query,即随机抽样k个节点发送包括该TQuery,注意此处Query中实际上包含了T和以及在DAG中所有T可达的其他交易(ancestry);
  • 对收到Query的节点而言,如果Query中的T以及其祖先交易在其conflict sets中处于preferred option,则返回yes-vote,反之则返回no-vote
  • 节点u收集返回的kResponds,如果该T满足阈值(即有超过αk个节点返回认可该交易的positive Responds),则该交易的cT赋值为1(收到一个chit),并且更新T交易所有祖先交易T’对应PT’的prefcnt
  • 类似Snowball,节点uT有一个confidence value,其计算方法如下:

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

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

具体描述如下:

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

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

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

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

 

Experiments

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

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

  • Avalanche本质上来说就是DAG,在只需要保证偏序的情况下,可以允许更多的并发,而传统的BFT策略则是需要保证Linearizability,开销更大。PS:很难简单地评价两者那种更好,因为在有智能合约运行的场景下,只保证偏序是显然不够的。
  • Avalanche不存在Leader,后者则可能成为性能瓶颈;
  • 每个节点通过采样只和k个其他节点通信,因此在网络规模增加时通信开销也不会增加太多。

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

  • TPSBitcoin3~7Algorand874Conflux3355Avalanche3400
  • LatencyBitcoin10~60minsAlgorand50sConflux7.6~13.8minsAvalanche1.35s

Thinking

  • 可以发现,同样都为DAG(虽然Avalanche不承认自己是),AvalancheConfluxTPS上几乎一样,实际上最原始的GHOST也能达到这个级别的性能。所以个人认为单从TPS上而言,Avalanche并没有太大提升。
  • 论文中作者承认cryptographic verification是当前一个主要性能瓶颈,但个人认为另一个瓶颈在于节点处理Query的环节,当中需要判断交易T isSTRONGLYPREFERRED,而这一步实际上需要遍历T所有的祖先交易的冲突交易集合,随着交易的增加这个开销将会变得非常大。
  • 尽管作者不愿意在论文中引用IOTA的工作,但两者确实有很多相似之处,核心思想都是优先保证诚实节点的liveness(交易只有接在正确的分支上才能被快速接受)。但两者都缺少economic incentive,并不能消除拜占庭节点的作恶动机。

(如对这篇论文和文章有其他见解,欢迎留言与汤载阳博士进行互动交流)

自治元网络 · 协作的未来

自治元网络,

是星云链最终的演化形态。

它聚焦链上复杂数据和交互,

面向复杂协作关系。

自治元网络的实现将带来

全新的共识激励机制和升级能力,

让每个人从去中心化协作中公平获益。

获取更多信息请访问

官网:nebulas.io

中文博客:blog.nebulas.io

英文博客:medium.com/nebulasio

Github : github.com/nebulasio/go-nebulas

Slack : nebulasio.herokuapp.com

Reddit : reddit.com/r/nebulas/

Twitter : @nebulasio

返回顶部