'CryptoYC'
研究|第三代共识协议:Avalanche雪崩
🌿

研究|第三代共识协议:Avalanche雪崩

在以太坊持续拥堵,gas fee不断提高的时候,市场开始关注公链,其中avalanche就是表现较好的公链之一,并且生态增长也非常迅速。由三种架构组成,可以将执行环境和链本身分开,同时DAG结构和独特的共识机制确保了安全性。

什么是雪崩

雪崩(avax)是一个为defi设计的开源区块链平台,特点是企业级协作性,高度可扩展性。核心是一组统一并且可互操作的基础设施,让任何人都能在avax生态系统中根据自己的需求建立区块链网络或者在链上发行资产。同时实现历史记录删减和链上治理,代码于 2020 年 3 月开源。2020年9月22日正式上线主网。平台上构建的项目超过225个,包括circle,the graph,sushiswap,chainlink等defi项目。

创始团队

Founder:康奈尔大学教授Emin Gün Sirer,土耳其裔美国计算机科学家,极客,IC3联合创始人,曾在贝尔实验室负责搭建大型操作系统。2001开发的karma虚拟货币系统第一个运用了PoW。

Founder&CPO(Chief Portocol Architect):Ted Yin,康奈尔大学博士三年级,CEO的学生。Facebook Libra协议HotStuff共识第一作者。

Co-founder:Kevin Sekniqi,康奈尔大学博士四年级

Chief economist:Amani Moin 是康奈尔大学的经济学五年级博士生。

融资&投资机构

image

图片来源:CYC整理

2021.9三箭资本领投

图片来源:https://www.feixiaohao.co/currencies/avalanche/

架构

雪崩和以太坊的架构不相同,它是由3种架构组成:X链,C链,P链,目的是将执行环境和链本身分开。

图片来源:https://www.jinse.com/news/blockchain/1113629.html

X链:交易链,处理个人之间点对点的创建资产和交易资产的功能。

C链:智能合约链,可以快速执行以太坊虚拟机,兼容solidity和以太坊的开发工具。

P链:DAG结构的平台链,元数据区块链,主要负责质押代币,协调网络验证者,跟踪活动子网和创建自定义子网。P链API允许客户端创建子网,并且向子网添加验证器和创建区块链。

共识机制

Gun教授把avax协议称为第三代共识协议,相比拜占庭容错协议和中本聪共识协议来说,不仅更去中心化,性能也非常好。而且结合了拜占庭共识算法和中本聪共识算法的特征,优势明显

图片来源:https://www.chainnews.com/articles/759620336608.htm

avalanche协议有四种机制组成了一组BFT协议,也被称为snow family protocol。首先是从非拜占庭协议slush开始,一种亚稳定投票机制。在这个基础上构建了其他三个拜占庭协议:snowflake,snowball和avalanche。并且采用了UTXO模型。值得注意的是,在协议中有个条件作为诚实节点和拜占庭节点的约定:诚实节点不会发出冲突交易;拜占庭节点也不可能伪造一笔和诚实节点产生冲的的交易。即拜占庭节点发出的错误交易只能和曾经发出的交易产生冲突,不能和诚实节点的交易冲突。

Slush

BFT的原始状态,不能提供完整的BFT保证。用红蓝色举例。在slush里,节点一开始是无颜色状态,在收到交易之后,将自己的颜色更新为交易中所携带的颜色,并且在网络中均匀随机的挑选一组小的常数样本k,发起询问。非彩色节点在接受到询问时,将会用询问颜色作为响应颜色,已经有颜色的节点,只能用当前颜色作为回应色。每次询问节点收集了k个节点的回应,发现有大于或等于α个节点都是相同的颜色,α>k/2,并且自己的颜色和他们的颜色不相同,那么就会翻转自己的颜色。重新回到询问节点,在进行询问一次。一共有m轮,最后节点在时间m结束时决定最终颜色。

特点:

  1. 无记忆:节点除了保持当前颜色以外,不保留任何状态,比如与其他节点交互历史。
  2. 只询问一组固定大小的节点k,并且k的值很小。
  3. 在任何网络配置下都可以进行。

Snowflake

在slush基础上增加了一个counter,为每一个节点增加了一个counter是用来记录该节点当前节点颜色的可信程度。它可以对最小状态做出很强的保证。每个节点计算器存储了网络连续样本和该节点显示相同颜色的次数。当counter达到β(一个安全参数)值,则节点接受当前颜色。

  • 每个节点包含一个计数器 cnt;
  • 每次改变颜色时,cnt重置为0;
  • 每次的成功询问之后(产生相同颜色的响应>α),节点cnt增加。

Snowball

对第二个协议做了改进,添加了更持久的可信度标识,提高了协议安全性和共识结果的可靠性,更难被攻击,更通用化,主要功能是增加置信度

  • 每次询问成功,自信数(confidentce)会增加颜色可信度;
  • 当节点的颜色可信度低于询问的颜色可信度,节点颜色将会翻转。

Avalanche

核心协议,在snowball的基础上添加了动态,仅限添加(append-only)的DAG(有向无环图)结构来进行交易。两大优势:高效,安全

DAG(有向无环图)

上文提到雪崩协议是DAG结构,并不是传统链状区块链,是因为雪崩中是由多个snowball单向指令组成一个多指令协议,协议维护所有一致交易的动态,对所有交易只添加DAG,存在一个汇聚点就是DAG的起点。添加DAG结构有两个优点

  • 提高有效性。对每一次DAG顶点投票相当于隐性的给这条路径上从创世顶点开始的所有顶点的交易都投了票
  • 提高安全性。DAG把所有交易都交织在一起,和btc链一样。
图片来源:avax白皮书
图片来源:avax白皮书

(术语:在DAG中,用祖先表达可以通过父代到达的所有节点,子孙表达子代交易及其后代。)

如果一笔交易所获积极的响应投票超过一个阈值,那么这个交易就收集了一个chit,节点最后会计算他们的confidene作为总数量和chit一起记录在后代交易中。但是值得注意的是,chit和DAG结构是分离的,所以攻击者不可以通过更改chit和confidence来攻击。

DAG的最大挑战就是双花,当snowball中出现了一笔冲突交易T被询问,那么DAG中所有可以从T到达的edge都隐式的被询问。如果T的整个祖先的表现在在冲突集里表现是最好的(即confidence分数高),那么被询问节点就会积极响应。下图显示了过程,紫色区域内表示有冲突交易的节点被分到同一个集合,如T2,T3。

来源:https://assets.website-files.com

安全性

建模框架:CTMC(连续时间马可夫链)。因为状态转换并不是在epoch中同时进行,而是随时在发生而且相互独立。

安全性:同样利用超几何分布模型,根据霍夫丁推导,得到不等式(1),根据函数本身来看,安全性是非常高的,节点数量越大,出错概率越趋向于零。

图片来源:avax白皮书
图片来源:avax白皮书

协议总结:雪崩是亚稳定协议。通过对网络的重复采样进行运作,当一笔交易被广播到网络,协议会通过“重复随机抽样”来系统中所有的验证者里随机抽选一批验证节点参与区块验证。每个节点会随机选择一批小数量节点询问,如果多数节点对事件叙述相同,那么判断为真,相反则切换事件内容,重复采样将会多次进行直到达到收敛。通过反复抽样,直到有足够的节点可以确认大概率正确,完成确认。这个在正常运行中是非常迅速的。注意在一轮交互完成前,节点选择结果不能更改,除非重新开始新一轮。这个过程类似用DAG结构实现模糊的非拜占庭共识。DAG中的节点不需要和所有节点交互,只需要接受其他节点反馈并和一定数量的节点交互,达成概率性共识。

代币经济

总供应量为7.2亿,创世区块将产生3.6亿。

来源:https://www.feixiaohao.co/currencies/avalanche/

代币铸造&分发:

铸造公式:

图片来源:avax白皮书
图片来源:avax白皮书

释放函数图:

图片来源:avax白皮书
图片来源:avax白皮书

100%质押时间是12个月,50%质押时间是2周。通过长时间质押可以产生11%的代币,用来激励长期投资者。

来源:https://www.feixiaohao.co/currencies/avalanche/

小结

过去四十多年,被科学家广泛认同的两个协议就是经典协议和中本聪协议。雪崩成为第三个协议,相比拜占庭,有更高的容错率,安全性高和中本聪协议相比,更高效。可以通过抽样,质押来实现公平治理,因为每个节点都是平等的,所以验证者中并不存在所谓的leader,没有“富者更富”一说。

参考文献:

  1. https://assets.website-files.com/5d80307810123f5ffbb34d6e/6008d7bbf8b10d1eb01e7e16_Avalanche%20Platform%20Whitepaper.pdf
  2. https://assets.website-files.com/5d80307810123f5ffbb34d6e/6009805681b416f34dcae012_Avalanche%20Consensus%20Whitepaper.pdf
  3. https://assets.website-files.com/5d80307810123f5ffbb34d6e/6008d7bc56430d6b8792b8d1_Avalanche%20Native%20Token%20Dynamics.pdf