Algorand 论文解读

Algorand是图灵奖获得者Silvio Micali主导研发的一种加密货币方案。该方案通过密码学抽签算法实现了拜占庭共识算法的大规模扩展，从而适用于公链数字货币体系。同传统加密货币共识算法PoW、PoS等相比拥有更安全、几乎不分叉、更高效（每轮共识达成时间在1分钟以内）等特性。

关键概念

Weighted users: 在Algorand中会对每个用户（用户特指Alogrand运行实例或者说节点）分配一个权重，该权重大小由相应用户所占有的资金数量决定（这点和PoS类似）。因此Alogrand算法需要系统中占有2/3（该比例由BFT算法特性决定）资金以上的为诚信节点方可避免分叉和双花。
Consensus by committee: 和传统BFT算法不同的是Algorand会随机选举一个小的节点子集运行BA算法从而实现BA扩展性。选举会依据节点占有的资金量分配相应的选中概率。
Cryptographic sortion: 为了防止针对committee的恶意攻击，Algorand在选举committee的时候采用了一种私密且非交互的方式。每个节点通过运行VRFs 以及自身私钥和来自区块链的公共信息（主要是随机种子）计算自己本轮是否是committee的成员。当节点发现自己是committee的成员之后会将VRFs返回的证明信息广播给其他用户，其他用户可依据该证明验证其身份。这样攻击者是无法提前知晓被选举的committee成员的。
Participant replacement: 同传统BFT算法不同的是BA* 在共识的每个阶段都会选举新的committee, 每个阶段之间节点之间没有私有状态会参与到共识中去。也就是每个阶段被选举的BA* committee成员将本次的决策信息发送到网络中去之后就与接下来的共识过程无直接关系。

算法假设

诚实节点运行的是bug-free的软件；
诚实节点所占有的金钱数量超过总数量的2/3；
大多数诚实节点（e.g,95%）发出的消息能够被大多数诚实节点(e.g,95%)在一定时间限制内接受到 -- 强同步，如果该条件不能满足则系统依然安全但是性能会受很大影响；
假设所有诚实节点的时钟是接近同步的（例如采用NTP）

执行流程概述

Algorand目前仅支持数字货币交易，每个交易包含了转出方的签名、转入方信息以及转账金额。一系列的交易组成一个区块，Algorand维护出块的顺序以及整个区块链状态。

Algorand按照轮次（rounds）的概念产生区块，每个round产生一个区块，Algorand通过BA* 算法保障整个网络在每个round产生的区块一致。

如下图所示交易以及其他信息在Algorand网络中通过gossip协议进行传播。

fig1

如下图所示，Alogrand算法通过加密抽签算法选举节点子集运行BA* 算法决定哪些pending transactions组成新的区块append到区块链上。BA*算法的每个step都会按照下图的方式进行，收钱进行抽签然后进行决策投票，最后通过gossip方式将本轮的决策广播出去。

fig2

Block提议

Block提议是BA*算法运行的前置阶段，Block提议是指每个被选中为区块提议成员的用户将一段时间内的pending transactions打包并发布出去的过程。具体流程如下：

所有用户运行cryptographic sortition算法判断自身是否为本次的出块成员。cryptographic sortition算法能够生成一个证明自己为共识节点的proof以及本节点的priority。其中优先级用于在众多共识节点中定本次该提议的block(即优先级高者优先)
被选中的出块节点向Algorand网络中广播 < proof,priority, block>;
其他节点在一定时间内等待接收来自出块节点的block，并丢弃低优先级的节点发送过来的区块;

BA* 共识

BA* 共识的目标是选择提议阶段产生的区块中最具优先级且被一直认可的区块确定下来添加到区块链上。

每个用户在round中初始化BA* 算法，并将其收到的具有最高优先级的区块作为参数输入到BA*；
BA* 包含多次重复步骤，每次步骤如图2所示；
- 2.1 每个节点运行密码学抽签算法检查自己是否为本step中的共识成员；
- 2.2 共识成员向网络中广播证明 $\pi$ 以及决议信息;
- 2.1 ~ 2.2 的步骤一直重复至足够数量的共识成员达成了共识；

以上便是整个区块的产生到添加到区块链的过程。

核心算法

Algorand的核心算法包括两个：1.密码学抽签算法，该算法用于保障每次参与共识的共识委员会成员接近完全随机；2. BA* 算法，该算法由共识委员会成员运行用于产出本次应该打包的区块。

密码学抽签算法

密码学抽签算法保障每个用户（ $pk_{i}, sk_{i}$ ）被选中为共识委员会成员的概率同其拥有的货币的金额成比例。即:假设每个用户的权重记为 $w_{i}$ (货币数量), 那么总的权重为 $W = \sum w_{i}$ （总货币量）, 那么用户i被选为共识委员会成员的概率就同其权重占比相匹配 $w_{i}/W$ ,

算法流程

如下图Algorithm 1所示为抽签算法的流程伪代码，抽签函数的输入为：sk: 用户私钥，seed: 伪随机种子，t: 期望被选为该role的用户的数量，role: 角色，w: 用户权重，W: 总权重

algo1

算法首先使用VRFs函数进行计算 $<hash, \pi> := VRF_{sk}(seed||role)$ 该函数返回一个哈希值和一个证明，其中哈希值由私钥和输入参数功能决定，他人不可伪造；证明 $\pi$ 可以让任何知晓该用户公钥的用户验证hash值确实由该输入推导出来，该hash值的随机范围在[0, $2^{hashlen} - 1$ ]。
为了能够使用户被选中的概率和其所拥有的货币相对应，Algorand将用户User按照其拥有多少单位的货币分割成sub-users，也即：假设用户i拥有 $w_i$ 的货币, 那么该用户就拥有 $w_i$ 个sub-users.（i, j）其中 $j \in \{1, ...., w_j \}$ 代表了i拥有的 ${j^{th}}$ 个货币，每一个单位货币被选中的概率p = $\frac tW$
用户的w个sub-users中被选中k个的概率遵循二项分布： $B(k;w, p) = \binom{k}{w}p^k(1-p)^{w-k}$ 其中 $\sum_{k=0}^wB(k;w,p) = 1$ ;
为了确定用户w个sub-users中多少个sub-user被选中，抽签算法将[0,1) 区间分割成连续的区间： $I^j = [\sum_{k=0}^jB(k;w,p), \sum_{k=0}^{j+1}B(k;w,p))$ 其中 $j \in \{1, ..., w\}$
如果 $hash/2^{hashlen}$ 落在区间 $I^j$ 上，那么该用户共有j个sub-users被选中，该数字j能够通过 $\pi$ 被其他用户验证, j >0 就证明本节点在本轮次中被选中为共识委员会成员。

如Algorithm 2算法所示为其他用户验证的逻辑，该逻辑类似抽签算法，通过用户公钥以及hash, $\pi$ ，seed等可进行正确性验证。

algo2

伪随机种子选取

从上述的随机算法来看其中伪随机种子seed至关重要，每个轮次中各用户应该拥有同样的seed才能够保证整个算法执行的正确性以及验证的正确性。其伪随机种子的选择算法如下：

初始种子seed0 在创世区块产生时由当时的参与者使用distributed random number generation 产生；
在后续的某轮次r中，seed会随着区块的产生更新。负责区块提议的用户u同时提出对应区块下一阶段使用的seed值： $<seed, \pi> \leftarrow VRF_{sk_{u}}(seed_{r-1}||r)$ ;
为了降低攻击者的攻击，抽签算法使用的seed会每R轮更新一次;

BA* 算法

算法前置条件

Algorithm 1中提到，抽签算法的输入中有一个期望角色数量t的设置，对于Algorand区块提议角色而言t的值应该大于1，为了安全性和效率而言 1 <= $t_{PROPOSAR}$ <= 70, 取值在26左右比较合理。

每个节点等待提议的区块有一个超时时间， $\lambda_{STEPVAR} + \lambda_{PROORITY}$ 前者是网络需要多长时间使得上一轮中的用户完成BA*的最后一步，后面一个时间是gosspi最高优先级区块hash及其证明所耗费的时间, 实验保守估计每个时间在5秒左右。

BA*

如Algorithm 3所示是BA* 算法的概要描述，用户在观察区块提议时间结束之后会将其观察的区块传入BA* 算法并开始执行BA*过程：

algo3

Reduction: 全网将对所有共识成员观察到的区块进行共识的问题转换成对某个区块或者空块进行共识问题, 这里分为两个步骤（如Algorithm 7）：
- 1.1 CommiteeVote 如算法4描述该算法授权检查自己是否为共识成员，如果是则将自己观察到的区块hash广播到网络中去
- 1.2 等待 $\lambda_{BLOCK} + \lambda_{STEP}$ 的时间，收集大部分用户投票的区块 T*t
- 1.3 如果步骤1.2超时则提议投票给空块，否则将1.2中获得的区块提交出去（为啥还需要后续过程，因为本过程只能够保证当前节点已经知晓网络中大多数同意的区块，类似PBFT算法中的Prepare阶段之后还需Commit）
  
  algo7
BinaryBA*:
BinaryBA* 算法将会在一个最大步数限制的情况下进行多次投票，在网络状况良好的情况下函数会在step=1的时候停止。
- 2.1 step = 1 时，用户判断自己是否投票委员会成员，如果是则将Reduction中得到的区块hash进行投票，并收集结果，如果此时已经达到共识，另外发送三次投票（为了其他用户共识时能够收集到足够数量的投票）并尝试将该区块状态标记为final；
- 2.2 当2.1 返回为空或者超时的情况下将再次发起投票，并收集结果。如果确实为空则证明本轮共识为空块，此时将发起三次投票（同上）；如果是超时说明2.1中的失败并非为空而是收集投票为到达规定阈值，继续进行投票；
- 2.3 本次如果超时将, 那么会运行CommonCoin函数该函数将给足网络时间去同步投票信息。同时该函数会随机让系统用户选择下一轮投空还是投blockhash从而让攻击者只有1/2的命中率。
CountVotes: 对标记为FINAL的区块进行计数，取得足够数量的FINAL标记将被持久化到区块链中。

algo8