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


Log in to reply
 

Copyright © 2018 bbs.dian.org.cn All rights reserved.

Looks like your connection to Dian was lost, please wait while we try to reconnect.