本文作者：星云研究院资深研究院汤载阳博士。华中科技大学计算机博士，日本会津大学和法国南巴黎国立电信学院访问学者，研究方向包括分布式系统、无线网络和区块链共识，在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算法描述如下：
Agri10x公司与印度政府合作 利用区块链帮助农民销售农产品:5月13日消息，Agri10x公司与印度政府合作，计划利用区块链技术去掉中间商，帮助偏远地区的农民出售农产品。（CoinDesk）[2020/5/13]
算法解释：在起始时刻，所有节点都是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做了进一步改进，其中轮询部分如下：
动态 | 以太坊开发者Virgil Griffith现在已被正式起诉:据Theblock消息，以太坊开发者Virgil Griffith现在因涉嫌协助朝鲜深入了解区块链和加密货币而受到正式指控，据称Griffith是因“阴谋违反《国际紧急经济权力法》”而被起诉。此前消息，Griffith于去年11月被捕，罪名是联邦政府指控他于4月非法前往朝鲜，并在“平壤区块链和加密货币会议”上作了陈述。[2020/1/9]
详细分析：每个节点引入了一个计数器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保证更加持久的可信度，使协议更难被攻击。算法具体如下：
声音 | 余弦：基于MimbleWimble的BEAM和Grin面临交易中间人劫持等安全问题:区块链安全公司慢雾创始人余弦发微博称，根据最近一段时间的研究，相比其他数字货币，基于MimbleWimble的BEAM和Grin至少有这几种独特安全问题：1. 交易中间人劫持问题；2. 交易针对性拒绝服务问题；3. 交易的交互复杂导致的其他传统网络安全问题。颠覆性的交易设计，大众适应期恐怕会不短。[2019/3/22]
详细分析：对每个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相比前三个算法引入了很多新概念，具体如下：
东京燃气宣布出资DIGITALGRID，或意在后者区块链技术: 3月29日，东京燃气宣布出资日本综合能源服务公司DIGITALGRID，目前出资金额及占股比例均未公示。有媒体表示，东京燃气此举的目的可能是为了获取对方已大力研发许久的区块链技术。[2018/3/30]
图中，每个方块表示一笔交易，具有一对<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（还未确定的交易，即
2018共识大会-黑客马拉松获奖揭晓 PayPal首席工程师赢得星云挑战:由Coindesk举办的，区块链领域最高级别会议-共识大会的黑客马拉松活动于纽约当地时间5月12日至5月13日进行，197名来自世界各地的顶尖开发者参与了此次活动。
星云联合创始人兼CTO钟馥百担任本次大赛评委，他给出的挑战题目是：用星云主网实现预测市场。经过30多个小时的紧张开发后，PayPal的首席数据工程师Amir Youssefi的Predict Mart and Social Network（预测市场）项目，通过搭建预言机将结果上链的方式，赢得了星云的挑战，获得了等值5120美元的NAS奖励。星云链（NAS）是致力于构建可持续升级的良性生态3.0公链。（已于3月29号主网上线)[2018/5/15]
最后，跟比特币一样，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，并不能消除拜占庭节点的作恶动机。
郑重声明： 本文版权归原作者所有， 转载文章仅为传播更多信息之目的， 如作者信息标记有误， 请第一时间联系我们修改或删除， 多谢。