第三类共识算法AVALANCE雪崩共识:Part1

最近AVAlanche受到了各大媒体关注,IOSG投了几千万美刀,然后也是在7月15号以公募价格0.05$结束,一共发行7.2亿代币,其中流通的为3.6个亿,其余的留给团队,简直赚大发了,上线市值就3600...

最近AVAlanche受到了各大媒体关注,IOSG投了几千万美刀,然后也是在7月15号以公募价格0.05$结束,一共发行7.2亿代币,其中流通的为3.6个亿,其余的留给团队,简直赚大发了,上线市值就3600多万!

那么其实,我们不禁要问,它的价值到底在哪里,现在公链的故事已经不多了,而Avalanche还能异军突起,这必然有其极为独特的地方,带着这个问题,我去研究了其相关的共识协议《Scalable and Probabilistic Leaderless BFT Consensus through Metastability》。

共识历史

实现共识是区块链的核心,最早的基于拜占庭的共识依赖节点间的互相通信来达成共识,但是问题是通信开销与节点个数的平方成正比,没法拓展。后来中本聪在2008年创造性的提出了中本聪共识,这种共识采用概率性安全保证,有一定的概率推翻已有共识。但是基于中本聪共识的协议,成本很高,性能很差,并且即使没有新的决定需要达成一致,系统也必须一直运转才能保证系统的安全。

Team Rocket团队推出的Snow共识簇,则是两者的结合,首先他也是概率性共识,但是不需要PoW;同时,他去除了BFT共识中leader的角色,这样就使得整个通信的开销降到了,每轮O(n)级别,同时由于不需要leader角色,也就不需要知道网络节点的成员,而这点传统的BFT协议也是做不到了,他们需要了解全网的节点。当然,天下没有免费的午餐,这样的处理带来的问题就是冲突交易的处理会比较的耗时。

那么Snow共识簇的思路是怎样的呢?又是如何做到的?

基本假设及思想

首先需要说下模型基本的假设:

  • 网络:采用普遍接受的异步网络模型,并且网络延迟服从指数分布
  • 恶意节点:采用普遍接受的恶意节点模型,恶意节点的算力有限,并且不能伪造数字签名;恶意节点内部消息传递速度不受限,并且可以自适应

那么他的思路其实比较的好理解,类似于流行病传播那样,1个节点初始的时候会有一个状态,(比如状态是颜色,而且蓝色),然后交易到达后,就把自己的颜色改为交易的颜色,然后再先询问其他有限的k个节点的颜色是什么样的;其他的节点收到这个询问之后,就对他进行相应,同时再询问其他的k个节点。一旦一个节点收到了k个响应,并且有α(α大于[k/2],是该共识的参数)个节点是同一个颜色,那么就把自己的颜色改为这个颜色。然后他继续询问m轮,并最终确定他的颜色。

可以看下这个他们开发团队做的demo

avademo.gif

这个基础的协议成为Slush,Slush的有些比较好的性质:

  • 无需记忆:节点不需要保存不同询问轮的其他节点状态
  • 相对于传统的共识协议需要询问(后面称为采样)每个节点,它的采样很少
  • 在任何网络环境下都能持续进行,这是由于重复采样会放大样本的不平衡
  • 如果询问的轮次m足够大,Slush能够保证所有节点的有很大的概率达成状态一致

但是Slush的问题是,他没有考虑拜占庭容错,比如说某个接待你倾向于一种颜色,那么恶意节点可以不断的把这个节点变成另一种颜色,使得整个网络达成不了共识。

那么这个问题该如何解决呢?其实思路也比较的简单,就是想办法让节点要改变的状态置信度很高,这样就不会来回变状态了,研究团队通过引入状态存储来进行解决。

Snowflake:BFT

通过在Slush引入一个计数器,来保存他之前的状态,除非计数器达到一定的门限β,节点才会改变状态。

计数器的规则如下:

  1. 每一个节点有一个计数器cnt
  2. 每次颜色改变,节点把计数器cnt重置为0
  3. 每次采样有≥α个响应(成功的采样),那么就把cnt+1

然而Snowflake的记忆的状态是比较短暂的,为了提高置信度,就需要让颜色改变的时候,cnt不会立即重置。

Snowball

因此,团队提出了Snowball共识。在Snowflake基础上修正cnt计数器为chit计数器,具体而言是这样的

  • 节点每收到一次成功采样,就把chit+1
  • 节点只有在当前颜色的chit小于新的颜色的chit的时候,才翻转颜色

Snow共识机制可以算是一种伟大的创新,他在中本聪共识簇和BFT共识簇上,提出了这种简单可理解的亚稳态共识。之前的性能提升很多是把DAG这种数据结构与中本聪共识进行结合,本身不能提供共识,只是通过让交易并发提高了吞吐量,而由于中本聪共识的局限性,不能改善延迟;而BFT共识受限于网络规模,局限也很大。而Snow共识实现了拓展性,吞吐量和延迟之间的均衡!

那么他是如何确定交易的序,并且性能到底如何呢,且听下回分解!

本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

  • 发表于 2020-07-22 00:31
  • 阅读 ( 318 )
  • 学分 ( 41 )
  • 分类:共识

0 条评论

请先 登录 后评论
Johnathan
Johnathan

PHD

7 篇文章, 803 学分