本文作者：星云研究院资深研究院汤载阳博士。华中科技大学计算机博士，日本会津大学和法国南巴黎国立电信学院访问学者，研究方向包括分布式系统、无线网络和区块链共识，在TPDS、ICDCS等顶级期刊会议上发表过论文。上一篇介绍了Hyperledger相关工作，这一周我们来看看permissionlessblockchain有什么最新的研究。这篇论文“Avalanche:ThePowerofMetastableConsensus”实际上还没有被正式接收，来自于Cornell的RobertKleinberg和EminGunSirer研究组。虽然还没被接收，但仍然是一篇质量非常高的论文。个人觉得整个论文架构有一些说不上的奇怪，前半部分风格比较偏系统，后面的证明部分又略显晦涩。同事告诉我这篇论文其实是由两个同学共同完成，一个早期提出了理论模型，一个负责系统实现。这也是为什么我打算分两篇来解读的原因，不过很有可能后面的理论证明部分我看不懂就放弃写第二篇了。Basics首先还是介绍下文中的一些基本概念。在任何基于复制状态机的分布式系统，都需要满足两个特性，即安全性和活性，文中定义如下：P1.Safety.Notwocorrectnodeswillacceptconflictingtransactions.P2.Liveness.Anytransactionissuedbyacorrectclient(akavirtuoustransaction)willeventuallybeacceptedbyeverycorrectnode.在很多其他论文中，这两个特性又称之为consistency和liveness，这里就不纠结了。Slush论文首先提出了名为Slush的共识算法，也是整个协议簇中最简单最基础的部分。Slush是非拜占庭协议，意味着其不能容忍作恶节点的存在。作者抽象出一个“染色”问题：任何时刻所有节点可能处于{red,blue,⊥}三种状态之一，共识就是如何通过节点间的通信使得所有节点最终的颜色一致。Slush算法描述如下：
算法解释：在起始时刻，所有节点都是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满足该阈值则将自身color更新为该color；如果没有在限定时间收集到k个Responds，则u重新抽样发送Query，直至收集到k个Respondsslush有如下优点：memoryless，每轮之间节点除了自身color不记录额外信息；小样本抽样，不同于其他算法需要对所有节点发送请求，slush只需要发送k个请求；抗亚稳态，即便是50/50的初始状态，也可以通过抽样的随机扰动打破平衡，然后反复抽样放大优势；如果m足够大，算法可以保证所有节点都有同等机会被染色；但是slush并不能提供足够强的拜占庭安全保证，如果存在拜占庭节点故意将自身color变成和主流color不一样，则可能打乱平衡。因此slush并不是BFT，但为后续机制提供了基础。Snowflake相比slush，第二个算法snowflake做了进一步改进，其中轮询部分如下：
详细分析：每个节点引入了一个计数器cnt变量，初始cnt=0，每当一轮Query返回的k个Responds某个color满足≥αk，则将其cnt+1；如果满足条件的color和自身color不同，则将自身color设定为该color，并且重置cnt；引入另一个安全系数β，当cnt大于β时，则最终确定该节点color，而不需要执行m次询问。当给定一个ε-guarantee的拜占庭环境，Snowflake可以保证Safety和Liveness。Snowballsnowflake中每次color翻转时cnt都会重置，理论上来说已经足够安全。Snowball进一步作出改进，通过引入confidencecounter保证更加持久的可信度，使协议更难被攻击。算法具体如下：
详细分析：对每个color都增加一个confidencecounter，例如d、d；每当一轮Query返回的k个Responds某个color'满足≥αk，将该color'的d+1，如果d最大，则将自身col更变为该col’；进一步地，如果col’和上次Respond通过阈值的lastcol不一样，则更新lastcol为col’，并且重置cnt;如果col’和上次Respond通过阈值的lastcol一样，则cnt+1，当cnt大于β时，则最终确定该节点color。总的来说，Snowball中仍然是连续β满足阈值条件的color才可能成为最终color，但confidencecounter的引入保证了最终确定的color同样具有高信任度。AvalancheDAG作为论文中协议簇的最终版本，Avalanche将Snowball拓展为multi-decreeprotocol。为了适用于资产交易这样的真实场景，Avalanche相比前三个算法引入了很多新概念，具体如下：
图中，每个方块表示一笔交易，具有一对<chit,confidence>，可以看到颜色更深的方块confidence更高。而每个交易都有一个冲突交易集，例如T9、T6和T7属于同一个冲突交易集，即PT9=PT6=PT7，但由于T9具有更高的confidence，因此该交易集的preferredtx=T9。上面提到每个PT包括了pref和cnt两个属性，初始化的PT只有T本身，因此PT.pref=T，PT.cnt=0。当后续收到更多冲突交易后，PT集合增加，pref和cnt的更新则发生在收到Respond后。
Avalanche发送Query和收集Responds流程如下：
详细分析：节点u找到新交易T（还未确定的交易，即
最后，跟比特币一样，Avalanche也把对最终交易的确认时间点和决定权交给了应用层。应用层通过自己定义的谓词，把接受交易的风险加入考虑。确认一笔交易可以通过一个叫做“safeearycommitment”的动作来完成。对于诚实交易T（virtuoustransaction)，如果它是在包含它的冲突交易集PT中的唯一交易，并且受到的Chit超过阈值β1，那么就认为T是可以接受的。如果一个诚实交易T由于liveness问题没被接受，那么它依然可以通过重新选择不同的parents交易来被接受。由于不同的交易只会消费和生成自己的UTXO，彼此互不相干，因此，任何交易都可以重新选择parents。至此，Avalanche整个流程介绍完毕，抽象而言，节点间的通信如下所示：
Experiments实验部分主要包括了对Throughput和Scalability测试，这里简单放下结果。
总结下来就是，Avalanche可以保证在节点规模在2000左右时，仍然有将近7000TPS。如此之高的性能得益于三点：Avalanche本质上来说就是DAG，在只需要保证偏序的情况下，可以允许更多的并发，而传统的BFT策略则是需要保证Linearizability，开销更大。PS：很难简单地评价两者那种更好，因为在有智能合约运行的场景下，只保证偏序是显然不够的。Avalanche不存在Leader，后者则可能成为性能瓶颈；每个节点通过采样只和k个其他节点通信，因此在网络规模增加时通信开销也不会增加太多。难得的是，论文复现了Algorand和Conflux的实现，并且做了横向比较，为了统一，这里全部采用Bitcoin的transaction平均数据规模。结果如下：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和Conflux在TPS上几乎一样，实际上最原始的GHOST也能达到这个级别的性能。所以个人认为单从TPS上而言，Avalanche并没有太大提升。论文中作者承认cryptographicverification是当前一个主要性能瓶颈，但个人认为另一个瓶颈在于节点处理Query的环节，当中需要判断交易TisSTRONGLYPREFERRED，而这一步实际上需要遍历T所有的祖先交易的冲突交易集合，随着交易的增加这个开销将会变得非常大。尽管作者不愿意在论文中引用IOTA的工作，但两者确实有很多相似之处，核心思想都是优先保证诚实节点的liveness。但两者都缺少economicincentive，并不能消除拜占庭节点的作恶动机。
郑重声明： 本文版权归原作者所有， 转载文章仅为传播更多信息之目的， 如作者信息标记有误， 请第一时间联系我们修改或删除， 多谢。