0 Algorand
Algorand是图灵奖得主、MIT教授Sivio Micali提出的一种新型区块链共识方法。现在已经进入测试网上线阶段，官方网站访问地址： https://www.algorand.com/ 。在网站的“白皮书”页面下，放出了三篇文章，分别是：
- Algorand Agreement - Super Fast and Partition Resilient Byzantine Agreement
- Algorand: Scaling Byzantine Agreements for Cryptocurrencies
- Algorand Theoretical Paper
本文的主要内容以《Algorand: Scaling Byzantine Agreements for Cryptocurrencies》为主线。展开叙述 Algorand 区块链及其共识算法的相关内容。
1 区块链技术研究现状
1.1 Proof-of-Work
数字货币鼻祖比特币采用的共识技术就是 Proof-of-Work ，由于比特币是中本聪发明的，因此这项技术又被称为 Nakamoto consensus。在产生新块时，比特币必须控制计算时间同时避免过多计算资源的浪费。目前，比特币的出块频率控制在10分钟。
- 缺陷1 - 由于可能出现分叉，因此用户看到自己的交易后，还需要至少等待6个区块（约1小时），才能确信交易成功。
- 缺陷2 - 新加入的用户初始化时可能会被攻击者限制网络后只接收攻击者提供的非法账本（某个无效分叉），造成安全问题。
- 缺陷3 - 尽管引入了工作量证明，仍可能遭受女巫攻击（51%）。
1.2 Byzantine 共识
拜占庭一致协议起初用于在一个小型服务器组之间传递服务信息。后续的一些改进能够支持更多节点。但是为了防止女巫攻击，拜占庭共识必须指定一簇固定可信节点。进一步，如果固定节点遭受攻击控制，则整个网络都不可靠。
BA* 算法是拜占庭的一种衍生。它继承了2/3节点可信的要求，支持大量用户任意加入，不需要选择固定可信节点。
1.3 Proof-of-Stake
Algorand 根据用户资金确定权重的思想就源于权益证明。在普通的数字货币权益证明中，一个用户可能恶意地在网络创建分叉，如果这个恶意行为被发现，则用户损失它的数字货币。不同于上述实现，Algorand 能够把一切控制在分叉发生前，只要攻击者控制的节点不超过 1/3 权重，则它无法实施攻击。 相比于 PoW，PoS 无需计算，提升了出块效率。
1.4 树形和DAG
相比于链式结构，树形结构和DAG（有向无环图）能够提升吞吐量。目前的一些研究实现中，树和DAG仍然依赖于 PoS。
2 Algorand 关键技术
Algorand 是一种全新设计的区块链数字货币系统。它使用的 BA* 算法能够支持海量用户（实验数据 500,000）安全加入，并在一分钟内确信交易。从名字可以看出，rand 作为核心概念，采用 VRF(Verifiable random function) 技术来伪随机地生成可被任意三方验证结果值。
总体来讲，Algorand 需要解决三个问题：
- 阻止女巫攻击
- 支持百万级用户量
- 抵御DoS攻击
为了解决以上问题，Algorand 采用了如下关键技术。
2.1 用户权重 (Weighted Users)
Algorand 网络基于用户的资金量，为每个用户指定权重，这个权重在共识投票中具有关键作用。BA* 算法保证，只要 2/3 权重的用户（注意不是2/3的用户）处于正常状态，则能够迅速达成最终共识，没有分叉和双花问题。
2.2 委员会模式 (Consensus by Committee)
BA* 算法采用委员会模式来解决用户量扩展问题。采用这种模式，每一轮进行区块共识时，只随机从所有用户中抽取一个很小的部分来完成（典型的，每1500个用户抽取1个）。在随机过程中，也引入了权重概念，能够最大化保证抽取到合法用户。
2.3 加密抽签 (Cryptographic Sortition)
为了防止攻击者去攻击/贿赂委员。BA* 算法在抽取时，采用秘密地、非交互式的算法。网络中每个用户，使用 (私钥pk, 公共信息info) 进行 VRF 计算可以自己算出是否是被选中。被选中节点可以算出一串身份证明，随相关信息一通广播。这样，攻击者在委员广播之前，无法得知抽签结果。
2.4 参与者轮换
接着2.3节，攻击者可能在侦测到委员发的消息后，进行攻击。BA* 算法要求委员一轮只能发送一次消息，也就是说，委员在发出第一条消息后，就不再具有委员身份。下一轮，BA* 算法会重新抽取委员，进行轮换，攻击者攻击上一轮委员无用。
3 系统流程概览
每个 Algorand 持有自己的公私钥。所有交易的历史记录组成区块链，交易记录中的每笔交易都是签名后的公钥对应资产的转账记录。
Algorand 采用 Gossip 协议 来传播信息（交易）。用户会把自己接受到的所有交易记录下来并写入到 Block 中，如果用户被选为委员，将广播这个 Block。BA* 算法将最终确定一个合法 Block，在所有节点达成共识。
3.1 交易流程
Algorand 的交易流程如下图所示：
3.2 区块结构
Algorand 区块链网络中，一个区块的结构如下图所示。整体上分为两个部分 Metadata 和 Transactions。Metadata 主要提供给 BA* 算法使用。当节点对区块进行校验时，任意非法字段都将导致节点向 BA* 传递空块。
| 字段 | 属性 | 特征 |
|---|---|---|
| round number | Metadata | 合法有效 |
| VRF seed | Metadata | 有效的种子值 |
| pre-hash | Metadata | 与前一区块Hash一致 |
| timestamp | Metadata | 时间戳，不早于前一区块 |
| tx1 | Transactions | 经过合法性校验的交易1 |
| tx2 | Transactions | 经过合法性校验的交易2 |
| ... | Transactions | ... |
3.3 Gossip 协议
Gossip 协议的传播方式示意图如下。圆圈代表节点（用户），箭头代表单向传播数据。在 Algorand 网络，流程如下：
- 交易源节点使用自己私钥对交易数据进行签名，防篡改；
- 源节点基于资金权重选择邻近节点集（图中一层选中节点），广播数据
- 一层选中节点对交易进行验证：
- 验证失败：丢弃，不再进一步转发该数据，流程结束；
- 验证成功：基于资金权重选择邻近节点集（图中二层选中节点），广播数据。
3.4 区块提交
经过加密抽签，每个用户都按资金量有一定概率被选为提交区块的节点。被选中节点有优先级的差异，以 priority 字段标识并以 proof 字段自证。其他未被选中的用户会等待一定的时间，以接收区块。
3.5 使用 BA* 达成共识
3.4 的区块提交并不能保证所有用户都接收到相同的内容。Algorand 采用 BA* 算法。一轮中，节点可能收到多个不同区块，节点使用优先权最高的区块对 BA* 算法进行初始化。 BA* 算法不断执行如下步骤：1）加密抽取委员；2）委员广播消息亮明身份。直到有足够的委员达成共识。
4 加密抽签
加密抽签算法目标是从所有节点中，根据节点的权重，随机抽取出一小部分节点。为了使得选中节点能够自证，他们必须持有一组公私钥对。
- 节点被选中的概率 = w(自身权重) / W（系统权重总和）
4.1 抽签流程
抽签使用 VRF 方法进行，下图展示了算法流程。
| 参数 | 释义 | 说明 |
|---|---|---|
sk |
用户私钥 | 与下文提到的用户公钥 pk 相对应 |
seed |
随机种子 | |
role |
角色类型 | 例如用户可能被选为区块广播者，或者在 BA* 算法的某一部被选为 |
t |
角色数量 | 系统定义参数 |
w |
用户权重 | 根据用户资金量确定的权重值 |
W |
系统权重总和 | 根据系统所有用户总资金量确定的权重值 |
j |
选中次数 | 用户资金可能被多次选中，需要记录次数 |
π |
证据 | 用于验证该用户提供的密文 |
- ②：VRF函数以字符串作为输入，以密文
hash和证据π为返回。使用用户公钥pk结合证据π能够验证密文hash是否签发自对应私钥sk。 - 注意此处概率 p = t / W, 不是 w / W。这是 Algorand 的一个trick，算法中将每份资金视为一个 子用户(sub-user)。例如一个用户有 1000 资金，则该用户在算法中对应 1000 个子用户。上图中的j用来记录该用户被选中的次数。
- ③：计算根据资金，用户有多少 子用户(sub-user) 会被抽中。这个数量由
hash决定。
下图展示了其他用户验证信息的算法过程，关键参数是信息发送者的公钥 pk。
4.2 Seed 选取
根据5.1的论述，seed 必须作为系统的公知参数送到每个节点进行加密抽签。并且还需要保证 seed 不被攻击者控制或扰乱。
Algorand 给出的解决方案是，每一轮的 seed(r) 由上一轮 seed(r-1) 使用 VRF 算法确定。sku 代表每个用户 u 的私钥。至于最后使用谁的计算结果，u 是预先确定的。这样，哪怕 u 被攻击者控制，也能保证最终生成的 seed 是伪随机的。
这个算出的下一轮 seed 被放在本轮区块中广播。如果 seed 非法或者广播信息不含有 seed，则用户视整个信息为空。计算下一轮 seed 的方式为：
创世块的 seed 可以在系统初始化时随机指定。为了进一步避免操纵行为， seed 每R轮进行一次刷新。
- seed(r-1) -- > seed(r-1-(r mod R))
5 区块提议
根据测试经验值，Algorand 每轮大概选取26个区块提议者（τpropersor=26）比较合适。
5.1 最小化传输
每一轮，由 4.1 可知一个子用户可能被选中多次，所有选中的节点可能都会广播一个区块出来，造成网络资源浪费和时延。Algorand 借助 hash 来计算用户每个子用户的优先级，只取优先级最高子用户发出的区块。另外，在传播中，分为两条消息，一条先导消息包含 hash （约 200B），一条完整区块信息（约 1Mb）。先导信息数据包很小，传播快，能指示优先级，便于用户取舍区块。
5.2 等待周期
显而易见地，由于网络存在时延，各个节点在每一轮需要等待一定的时间以接受广播的区块。
- 周期过短：大多数节点收不到区块导致共识为空块
- 周期过长：影响交易确认的时间及整个网络的性能
在 Algorand 中，当一个节点完成 (r-1) 轮时，说明其他节点最多落后一个步骤，记这个步骤需要的时间估算为 T(setpavr)；又记节点从收到的区块选出优先级最高的区块时间为 T(priority)。则两者相加就是合理等待周期。
实验表明，一个较合适的选择是 5 秒。
6 BA*算法
BA*算法包含两个主要过程：
- 将在所有区块中选择的问题简化为选择空块或者确定的某一块。
- 对 1. 的结论达成选择共识
6.1 主流程
其主流程的算法伪代码如下图所示：
| 参数 | 释义 | 说明 |
|---|---|---|
ctx |
账本状态 | 包括 seed ，权重，上一共识区块 |
round |
轮数 | 处于第几轮中 |
block |
区块 | 选出的最高优先区块 |
经过 Reduction() 步骤，完成问题二元简化。经过 BinaryBA* 算出区块。将算出区块与投票区块进行对比。如果一致则达成最终共识；否则达成临时共识。
6.2 投票阶段
6.2.1 发起投票
发起投票的算法如下图所示。主要是2个步骤
- 使用加密抽签算法，计算出自己是否被抽中
- 被抽中则使用 Gossip 协议广播签名后的内容
6.2.2 投票计数
首先，节点会从消息缓存中读取属于对应 round 和 step 的消息。如果消息读完且定时器超时，则返回 TIMEOUT；读到消息，则对该消息调用 ProcessMsg() 函数处理（算法流程如下图2），主要是确认投票的有效性。一旦对某个值得投票数达到 T · τ ，则返回该值。这一步能够确保完成投票后输出的值，要不各个节点都相同，要不就是 TIMEOUT。
6.2.3 归约（Reduction）
Algorand 区块链中，归约步骤的主要作用是，把本来需要在许多任意值达成共识的问题简化为二元问题：要不选择确定的某个区块 hash作为共识，要不以空块 hash作为共识。其算法流程如下图所示。
6.2.4 二元共识
二元共识解决 6.2.3 节中归约完成后的二元问题：选中那个被选中的区块，还是选择空块。其算法流程如下图所示：
Algorand 定义了两种共识状态 最终态 final 和 临时态 tentative。final 共识代表该区块已经写入区块链且不会再发生任何更改；tentative 共识代表暂时无法保证数据一致性，这有可能是攻击者或者网络延时造成的。
7 性能
- 主机：Amazon’s EC2 m4.2xlarge （8核）
- 网络：20M 带宽
- 数量：1000
- 用户数：50000（每台机器模拟 50 个用户）
- 区块大小：1M
7.1 时延
实验模拟了不同用户数量时，出块时延。可以看到，从5000用户增长到50000用户，时延变化并不明显。控制在20s左右。
进一步，实验吧用户数调整为每个 EC2 虚机 500用户，时延情况如下。同样的，随着用户增长，时延并未显著变大，控制在80s左右。比上一实验情况多了4倍时间，这主要是带宽限制造成的。
下图是模拟区块大小变化对共识时延的影响情况。
7.2 安全测试
下图显示了在系统中不同恶意用户比例下完成一轮 Algorand 的时间。
（完）
