Algorand 链简析
-
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
,如果是就进行过程,如果不是则直接退出该StepStep 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左右。