共识机制-Algorand共识算法介绍

Algorand共识算法是图灵奖获得者Silvio Micali在2017年底提出。Michali是MIT的教授，是一位密码学家和计算机理论学家，在伪随机数以及零知识证明领域很有名。

Algorand共识算法的论文的下载地址：https://people.csail.mit.edu/nickolai/papers/gilad-algorand.pdf。

本文先介绍一下VRF，再介绍Algorand共识算法的流程：

1）VRF（Verifiable Random Function）可验证随机函数

从VRF的名字可知，VRF是随机生成函数，而且这个函数是可验证的。VRF函数的输出由两部分组成：随机结果以及随机证明（proof）。有关VRF函数的具体计算可以参考：https://tools.ietf.org/html/draft-goldbe-vrf-01.html。

VRF函数的实现一般有两种：一种基于RSA算法，一种基于EC算法。下图详细解释RSA算法的生成和验证流程（EC算法逻辑上类似）：

OS2IP是字符串转整数字函数，I2OSP是整数转字符串函数，MGF是Mask Generation Function（掩码生成函数）。从上图可以看出，验证数据是RSA的加密结果，验证过程从RSA的公钥进行解密验证。随机数据的生成是对验证数据再进行Hash处理。

简单的说，VRF提供了一个随机数据生成方法，而且这个随机过程和私钥有关，并可以通过公钥被验证。

2）Algorand的共识过程

Algorand的共识分为两个步骤：1）随机选举区块生成者生成区块 2）形成共识（也就是论文中的BA*算法）。

3）Algorand的随机选举

Algorand算法中的节点都有权重（weight），该权重和账户的余额成正比。

上图中的t是选中的账户余额阀值，w=账户余额/账户余额阀值，也就是说w是账户中可以分割成多少个账户余额阀值。利用多项式分布B(k;w,p)，计算出hash对应的比例在哪个区间内，则最后选中的次数就是多少，也就是最后的j的数值。

特别说明的是，因为共识过程分为两个步骤，所以随机选择也有两种role：1）生成区块的选择 2）共识过程（BA*)选择。

4）随机选择中的Seed

VRF函数中的Seed算法如下：

当前轮（round）的Seed是之前轮的Seed和轮数的VRF的随机结果。SKu是选择的生成区块的节点的私钥。第一轮的Seed是随机生成的。

5）Algorand的区块生成

每个节点在新一轮的开始，都会以“区块生成者”的role，计算随机选举。选中的节点中，生成区块并且广播区块信息。

6）Algorand的BA*算法

BA*算法又分为两步阶段：1）同步确定最大优先级区块 2）是否该区块能稳定共识。有关第一阶段的过程如下图所示：

先从节点中，随机选举出投票人，第一步：投票人会广播自己认为的最大比例的区块，第二步，投票人再次广播它知道的最大比例的区块。经过两步就能确定最大比例的区块。

有关第二阶段，过程和第一阶段类似，只是步数可能更多。

总结：Algorand采用了VRF函数，并结合账户的余额比例，随机确定区块生成以及投票人角色。根据论文中的模拟数据，比特币的POW共识换成Algorand共识后，TPS增长125倍。和DPOS+BFT相比，Algorand的安全性更强，只要超过2/3的账户余额是诚实节点，Algorand即安全。