Algorand 链简析

NIJUNPEI

Algorand 简析

本文不涉及数学描述，只描述流程概念

一、什么是 Algorand ？

Algorand是由MIT机械工程与计算机科学系教授、图灵奖得主Silvio Micali与合作者于2016年提出一个区块链协议，目前已有成熟产品——ALGO区块链平台。Algorand的共识算法是BA*，是一种PBFT算法的改进。

二、什么是 BA* ？

1. 总述

BA*算法分为三个阶段：

Step 1: 区块的生成
Step 2~3: GC（分级共识协议）
Step 4~~: BBA*（二元拜占庭协议）

算法中涉及两个关键角色：

Leader: 区块生成阶段创建区块
Verifier: 区块生成阶段之后的阶段里对区块进行共识

算法的停止时间不确定，是大概率保证有限步内可以结束。

2. 一些前提

需要知道一些前提，来理解算法流程。

BA* 中有( r, s )的概念，r即round，表示某一轮共识；s即step，表示这一轮的某一步

2.1 执行前提

s = 1: 节点 i 根据「Leader选举规则」检查自己是不是 potential leader。如果不是，结束该 step，否则执行相应规则
s >= 2: 节点 i 根据「Verifier选举规则」检查自己是不是 vefier。如果不是，结束该 step，否则执行相应规则

2.2 Step

开始时间：一个节点在达成共识[公式]后，会同时进入每个Step，但并不是所有节点同时开始。

设第一个诚实节点达成共识的时间是Tr，则在[Tr, Tr + ℷ]时间内，所有诚实节点都会达成本轮共识

结束时间：Step 结束的时间有两种

达成Ending Condition条件
耗尽等待时间

2.3 临时秘钥

每个节点在 ( r, s ) 签名时所用的秘钥，每个 ( r, s ) 的秘钥是不同的，即当前的秘钥为临时秘钥，在后面的过程会销毁失效

三、算法流程

1. 生成区块

Step 1

检查自己是否属于本轮的 Verifier，如果是进行下面的步骤，如果不是不作处理
生成一个区块 B
用临时秘钥签名区块 esig(H(B))，签名完以后销毁临时秘钥
签署一个用来验证自己身份属于 Verifier 集合的签名σ
生成消息 m = (B, esig(H(B)), σ)，广播

备注：

其他节点通过 σ 验证发送这个消息的人是否属于验证者集合，以检查消息发送者是否有资格。
恶意节点收到消息后，就知道谁是leader，并可以立即控制它广播新的消息，阻止他原来的消息继续广播，这样恶意节点可以控制发送新的消息，所以销毁临时秘钥就是为了让恶意节点即便控制了leader也无法继续发送新的消息。

2. GC（分级共识协议）

每一步开始之前都会检查自己是不是Verifier，如果是就进行过程，如果不是则直接退出该Step

Step 2: GC 第一步

从收到的多个本轮区块消息中，找到 Leader，这里有一个基于签名的算法，简单说就是通过一个计算得到一个值，Leader 的值是最小的
检查 Leader 发来的区块B的合法性，若合法，令v = H(B)；若不合法，令v = ⟘
广播消息

备注：

上面的v是GC里面用到的，在BBA中不会用到
整个协议只有这一步会检查leader和验证区块的合法性

Step 3: GC 第二步

在收到的消息中，如果有超过 2/3 的是合法的，则打包消息 m 标识为合法消息，否则标识为不合法
广播消息

Step 4: GC 输出

收到消息存在下面三种情况：
- 合法消息数 n > 2/3，令 v = v'，b = 0
- 合法消息数 1/3 < n < 2/3，令 v = v'，b = 1
- 合法消息数 n < 1/3，令 v = ⟘，b = 1
广播消息 m = (ESIG(b), ESIG(v), σ)

备注：

b = 0表示合法区块，b = 1表示非法区块

3. BBA*（二元拜占庭协议）

在 BBA* 过程中会不断收到历史消息m(s')，然后进行检查，查看是否触发Ending Condition

【Ending Condition 0】

条件：收到超过 2n/3 的合法消息，且 s' - 2 = 0 mod 3
满足条件则达成共识，本轮结束

【Ending Condition 0】

条件：收到 2n/ 3 的费发消息，且 s' - 2 = 1 mod 2
满足条件则达成共识，出一个空块，结束该轮

Step 5: Coin-Fixed-To-0

当 6 <= s <= m+2, s - 2 == 1 mod 3时进行这一步，如果触发Ending Condition，退出，否则：

如果收到的消息中有超过 2/3 比例的消息是非法消息，令 b = 1，否则 b = 0
广播消息

Step 6: Coin-Fixed-To-1

当 5 <= s <= m+2, s - 2 == 0 mod 3时进行这一步，如果触发Ending Condition，退出，否则：

如果收到的消息中有超过 2/3 比例的消息是合法消息，令 b = 0，否则 b = 1
广播消息

Step 7: Coin-Genuinely-Flipped

当 7 <= s <= m+2, s - 2 == 2 mod 3时进行这一步，如果触发Ending Condition，退出，否则：

可能出现三种互斥情况：
- 收到的有超过 2/3 比例的非法消息，令 b = 1
- 收到的有超过 2/3 比例的合法消息，令 b = 0
- 否则令 b = lsb(...) (有一个数学公式)
广播消息

Step m+3: 最后一步

这一步不需要检查自己是不是Verifier，所有的节点都会参与。

如果触发Ending Condition，则停止，否则等待 ts 时间后

令 out = 1 和 B = 空块
广播消息(消息包含out签名，区块签名，身份签名)

达成共识

四、总结

BA*算法是主要对PBFT在安全性方面有较大的改善，使用BA*共识算法的处理tps为pow的125倍左右，也就是在875左右。