Algorand 系列二: Algorand 共识算法(2017)的设计原理-1

YOUChain Research

YOUChain 研究团队,成员毕业于国内外顶级名校,有长期的工业界经验。我们持续跟踪的区块链学界和业界的前沿发展,致力于深入区块链本质,推动学术和技术发展。团队诚邀加密、算法、区块链、工程人才加入!

本文来自 yipast@YOUChainResearch

一、背景知识

一提到Algorand就想到了VRF抽签。关于VRF,已有专门的文章进行了详细的分析 传送门,本文专注于Algorand早期版本的共识算法设计原理。

Algorand在2017年发布的协议是基于拜占庭共识(BA),命名为 BA`BA^*` 协议,主要包含两阶段:

  1. 第一阶段:分级共识协议 GC`GC`

  2. 第二阶段:二元拜占庭协议 BBA* 。

首先,我们来了解下这两个阶段详细的背景知识。

1.1 分级共识协议 GC

结合 graded broadcast 与 crusader agreement,分级共识协议概念的定义如下。

协议 P`{P}` 中每个节点 i`i` 有一个私密的、任意初始化的值 vi`v_i^{'}` 。若 n`n` 个节点中最多有 t`t` 个恶意节点,每个诚实节点 i`i` 输出一值级对 (vi,gi),gi{0,1,2}`(v_i,g_i), g_i \in \{0,1,2\}`,且满足以下三个条件:

  1. 对所有的诚实节点i`i`j`j`gigj1`|g_i-g_j| \leqslant 1`

  2. 对所有的诚实节点i`i`j`j`gi,gj>0vi=vj`g_i, g_j > 0 \Rightarrow v_i = v_j`

  3. v1=...=vn=v`v_1^\prime = ... = v_n^\prime = v`,则对所有的诚实节点 i`i` 都有 vi=v,gi=2`v_i = v, g_i = 2`

则称协议 P`{P}` 是一个 (n,t)`(n,t)` 分级的共识协议。

gradecast 就是一个 (n,t)`(n,t)` 分级的共识协议,包含了3-Step。而Algorand共识算法中第一阶段的GC包含了 gradecast 的最后两步。具体的内容如下。

#is(v)`\#_i^s(v)`: 在步骤 s`s` 中给节点 i`i` 发送 v`v` 的节点数量

Step 1:每个节点 i`i` 给所有节点发送 vi`v_i^{'}`

Step 2:当且仅当 #i2(x)2t+1`\#_i^2(x) \geqslant 2t+1` 时,每个节点 i`i` 给所有节点发送字符串 x`x`

输出决定条件:

每个节点 i`i` 的输出对 (vi,gi)`(v_i,g_i)` 的计算如下: {#i3(x)2t+1, then vi=x, gi=2#i3(x)t+1, then vi=x, gi=1else,vi=, gi=0 \begin{cases} \#_i^3(x) \geqslant 2t+1, & \text{ then } v_i=x, \ g_i=2 \\ \#_i^3(x) \geqslant t+1, & \text{ then } v_i=x, \ g_i=1 \\ else, & v_i = \perp, \ g_i=0 \end{cases} 定理:若 n3t+1`n \geqslant 3t+1`,则 GC`GC` 是一个 (n,t)`(n,t)` 分级的广播协议。

1.2 二元拜占庭协议 BBA`BBA^*`

二元拜占庭协议BBA`BBA^*`借鉴了Feldman、Micali提出的二元BA​协议

前提:诚实节点超过 2/3,即总节点数 n3t+1`n \geq 3t+1`,其中 t`t` 代表恶意节点的最大可能数量。

不管恶意节点如何操作,每次主循环的执行都有 1/3 的概率把节点带入协议中。

该协议有一个设置的要求:需要一个共同的随机字符串 r`r`,不依赖节点的key (Algorand中是 Qr`Q^r`)。

协议实际上是一个3步循环:节点间不停的交换布尔值。

节点可以在任意时间退出该循环。如果节点 i`i` 在退出前,在某步骤广播了一个值 b`b`,退出后,其它节点就假装从 i`i` 那收到了 b`b` 值。

另外,协议用了一个计数器 γ`\gamma`,标记3步循环执行的次数。

3步循环:

Step 1:Coin-Fixed-To-0 Step。节点 i`i` 按照如下情况发送对应的 bi`b_i` 值: bi={0,#i1(0)2t+1,输出 outi=0, 停止1,#i1(1)2t+10,other b_i = \begin{cases} 0,\quad \#_i^1(0) \geqslant 2t+1,\quad \text{输出 } out_i=0, \text{ 停止} \\ 1,\quad \#_i^1(1) \geqslant 2t+1 \\ 0,\quad \text{other}\\ \end{cases}

Step 2:Coin-Fixed-To-1 Step。节点 i`i` 按照如下情况发送对应的 bi`b_i` 值: bi={1,#i2(1)2t+1,输出 outi=1, 停止0,#i2(0)2t+11,other b_i = \begin{cases} 1,& \#_i^2(1) \geqslant 2t+1,\quad \text{输出 } out_i=1, \text{ 停止} \\ 0,& \#_i^2(0) \geqslant 2t+1 \\ 1,& \text{other}\\ \end{cases}

Step 3:Coin-Genuinely-Flipped Step。节点 i`i` 按照如下情况发送对应的 bi`b_i` 值和 SIGi(r,γ)`SIG_i(r, \gamma)``: bi={0,#i3(0)2t+11,#i3(1)2t+1clsb(minjSiH(SIGi(r,γ))),other b_i = \begin{cases} 0,& \#_i^3(0) \geqslant 2t+1 \\ 1,& \#_i^3(1) \geqslant 2t+1 \\ c \triangleq lsb(min_{j \in S_i} H(SIG_i(r, \gamma))),& \text{other}\\ \end{cases}

other情况下,令 Si={jN, j`S_i = \{j \in N,\ j` 为在第3步给节点 i`i` 发送了合适消息的节点 }`\}`γi`\gamma_i` 加1,返回步骤1。

lsb(x)`lsb(x)` 表示 x`x` 的最低有效位(Least Significant Bit)。是指一个二进制数字中的第0位(即最低位),权值为2^0,可以用它来检测数的奇偶性。

1.3 BA`BA^*` 协议

BA`BA^*` 协议可以通过分级共识协议GC`GC`、二元拜占庭协议BBA`BBA^*`来描述。

Step 1、2:每个节点 i`i` 执行 GC`GC`,输入为初始值 vi`v_i^\prime`,计算出一对 (vi,gi)`(v_i,g_i)`

Step 3:每个节点 i`i` 执行 BBA`BBA^*`,初始输入为0(若 gi=2`g_i=2`,则为1),计算bit位 outi`out_i`

输出决定条件:若 outi=0`out_i=0`,则每个节点 i`i` 的输出为 vi`v_i`,否则为 `\perp`注:输出即达成共识。

定理:若 n3t+1`n \geqslant 3t+1`,则 BA`BA^*`是一个 (n,t)`(n,t)` 分级的、稳健为1的 BA`BA` 协议。

为何能在Algorand中使用 BA`BA^*` 协议?

首先,Algorand中的通信都是通过广播,而 BA`BA^*` 协议不仅仅适用于传统的通信网络,同时适用于gossip网络。

其次,Algorand最大的特性之一是节点可替换,而 BA`BA^*` 协议完全满足这一属性。

综上,只要满足节点可替换、能在gossip网络工作的 BA`BA` 协议都适用于Algorand系统。Micali、Vaikunthannatan对 BA`BA^*` 进行了扩展,使得其能在大部分节点是诚实的系统中高效运行。这个协议同样可用于Algorand。

二、Algorand共识核心

在了解Algorand共识的具体内容之前,我们先来看看它的整个思考过程。

在Algorand的设想中,理想的每一轮共识 r`r` 都需要满足两个属性:

  1. 完全的正确。所有诚实的节点对同一个区块 Br`B^r` 达成一致。

  2. 完备性。最大化 Br`B^r` 中的交易集合 PAYr`PAY^r`

由于恶意节点的存在,同时满足这两个属性比较困难。所以Algorand采取了更实际的目标: 带着压倒性的概率,保证完全正确和完备性接近 h`h`h>2/3`h > 2/3`,是诚实节点的比例)。换而言之,优先满足正确性。毕竟,未在当前轮处理的交易可以在下一轮处理,而分叉是无法容受的。

于是,问题转化为协议如何设计来满足完全的正确,以及最大程度的保证完备性。

1、如何保证完全的正确?

最初的方法是在每一轮 r`r` 的开始,每个节点 i`i` 构建自己的候选区块 Bir`B_i^r` ,最终所有节点对一个候选区块达成共识。然而该方法的缺陷就是无法保证完备性,甚至可能最终总是对空块达成共识。

2、如何解决完备性的问题?

分三步走:选择一个领导者 lr`l^r`,领导者广播它自己的区块 Blrr`B_{l^r}^r`,节点对来自 lr`l^r` 的区块达成共识。

只要领导者 lr`l^r` 是诚实节点,则完全的正确和完备性都能得到保证。若领导者是恶意节点,我们也不介意最终对空块达成共识。

2.1 符号定义

r0`r \geqslant 0`:第几轮

s1`s \geqslant 1`:第几步

Br`B^r`:第 r`r` 轮生成的区块

PKr`PK^r`:第 r1`r-1` 轮结束后第 r`r` 轮开始时的公钥集合

Sr`S^r`:第 r1`r-1 ` 轮结束后第 r`r` 轮开始时的状态

PAYr`PAY^r`:第 r`r` 轮的支付集合

lr`l^r`:第 r`r` 轮的领导者,它选择第 r`r` 轮的支付集合 PAYr`PAY^r`,并决定种子 Qr`Q^r`

Qr`Q^r`:第 r`r` 轮结束时生成的种子,被用来选择第 r+1`r+1` 轮的验证者。独立于区块中的支付集合,且不能被 lr`l^r` 操纵。

SVr,s`SV^{r,s}`:第 r`r` 轮第 s`s` 步选中的验证者集合

2.2 领导者选择

参考了 Micali、Rivest 设计的微支付机制,Algorand规定节点 i`i` 只有满足以下条件,才能成为potential leader: ri .H(SIGi(r,1,Qr1))p,iPKrk`r_i \triangleq \ .H(SIG_i(r,1,Q^{r-1})) \leqslant p, \quad \forall i \in PK^{r-k}`

  1. 凭证 σirSIGi(r,1,Qr1)`\sigma_i^r \triangleq SIG_i(r,1,Q^{r-1})` :节点 i`i`r,Qr1`r, Q^{r-1}` 的数字签名,1代表这是第 r`r` 轮的第1步。

  2. H(SIGi(r,1,Qr1))`H(SIG_i(r,1,Q^{r-1}))`:对签名进行哈希,最后得到一个256-bit的字符串

  3. .H(SIGi(r,1,Qr1))`.H(SIG_i(r,1,Q^{r-1}))`:前面的"."是二进制小数点,因此,ri .H(SIGi(r,1,Qr1))`r_i \triangleq \ .H(SIG_i(r,1,Q^{r-1}))` 是一个256-bit、大于0小于1的小数.

  4. p`p` 的选择需要满足至少有一个potential leader是诚实节点。

通过揭示自己的凭证:σirSIGi(r,1,Qr1)`\sigma_i^r \triangleq SIG_i(r,1,Q^{r-1})`,节点 i`i` 可以向任何人证明自己是第 r`r` 轮的potential verifier。

以上的定义表明,领导者 lr`l^r` 是一个potential leader,他的凭证哈希值比其它所有的potential leader j`j` 都要小: H(σlrr,s)H(σjr,s)`H(\sigma_{l^r}^{r,s}) \leqslant H(\sigma_j^{r,s})`.

注:r`r` 轮的potential leader必须至少有 k`k` 轮是属于系统,即 iPKrk`i \in PK^{r-k}`. 此举也是Algorand为了防止女巫攻击而设计的look-back机制。

2.3 验证者选择

根据论文,从第 rk`r-k` 轮的系统节点中随机选择一部分来组成第 r`r` 轮的验证者集合。节点 i`i` 只有满足以下条件,才能成为 SVr,s`SV^{r,s}` 中的验证者:

.H(SIGi(r,s,Qr1))p,iPKrk`.H(SIG_i(r,s,Q^{r-1})) \leqslant p^\prime, \quad \forall i \in PK^{r-k}`

验证节点 iSVr,s`i \in SV^{r,s}` 在第 r`r`s`s` 步发送消息 mir,s`m_i^{r,s}`,该消息里必须包含它的凭证 σir,sSIGi(r,s,Qr1)`\sigma_i^{r,s} \triangleq SIG_i(r,s,Q^{r-1})`,以便下一步的验证者能够识别该消息是步骤s的合格消息。

p`p^\prime` 的选择需保证以极大的概率满足以下的条件。注:在 SVr,s`SV^{r,s}` 中,#good`\#_{good}` 是诚实节点的数量,#bad`\#_{bad}` 是恶意节点的数量。

  • Algorand1`Algorand_1^\prime`

    • #good>2#bad`\#_{good} > 2 \cdot \#_{bad}`

    • #good+4#bad<2n`\#_{good} + 4 \cdot \#_{bad} < 2n`n`n`SVr,s`SV^{r,s}` 的期望基数

  • Algorand2`Algorand_2^\prime`

    • #good>tH`\#_{good} > t_H`

    • #good+2#bad<2tH`\#_{good} + 2 \cdot \#_{bad} < 2t_H`tH`t_H` 是指定的阈值

这两个条件说明了:

  1. 在BA协议的最后一步,至少需要给定数量的诚实节点对新区块 Br`B^r` 进行数字签名;

  2. 每轮只有一个区块拥有必需数量的签名;

  3. BA协议每一步都需要2/3的诚实节点。

2.4 区块的生成

领导者 lr`l^r ` 若是诚实的,则新区块的形式如下:

Br=(r,PAYr,SIGlr(Qr1),H(Br1)) B^r = (r, PAY^r, SIG_{l^r}(Q^{r-1}), H(B^{r-1}))

假若领导者 lr`l^r` 是恶意的,则新区块会是以下两种形式之一:

Br=(r,PAYr,SIGi(Qr1),H(Br1))=Bϵr(r,,Qr1,H(Br1)) B^r= (r, PAY^r, SIG_i(Q^{r-1}), H(B^{r-1})) \\ = B_\epsilon^r \triangleq (r, \varnothing, Q^{r-1}, H(B^{r-1}))

  • 形式(1):有可能交易集合PAYr=`PAY^r = \varnothing`i`i` 是第 r`r` 轮的potential leader,然而 i`i` 不一定是领导者 lr`l^r`(当 lr`l^r` 不展示它的凭证,导致其它节点无法验证时)。

  • 形式(2):在 BA`BA` 协议的第 r`r` 轮中,所有诚实节点输出默认值,即空区块 Bϵr`B_\epsilon^r` 时,出现这种形式。

尽管形式(1)、(2)中都会出现交易集合为空的情况,但是两者是不同的区块,且在不同的情况下出现:

  1. Br=(r,,SIGi(Qr1),H(Br1))`B^r = (r, \varnothing, SIG_i(Q^{r-1}), H(B^{r-1}))` :BA协议所有步骤都执行得很顺利;

  2. Bϵr`B_\epsilon^r`:BA协议某部分出错了,所以输出默认值。

Algoran`Algoran^{\prime}` 中第 r`r` 轮生成区块 Br`B^r` 的过程

  1. 所有的节点 iPKrk`i \in PK^{r-k}`,检测自己是否是potential leader,若是:

    • i`i` 使用它知道的所有交易,及当前的区块链 B0,...,Br1`B^0,...,B^{r-1}`,准备最大化的交易集合 PAYir`PAY_i^r`,来组成它自己的候选区块 Bir=(r,PAYir,SIGi(Qr1),H(Br1))`B_i^r = (r, PAY_i^r, SIG_i(Q^{r-1}), H(B^{r-1}))`

    • 然后 i`i` 广播它的第 r`r` 轮第1步的消息 mir,1`m_i^{r,1}`,消息里包含了

      • 候选区块 Bir`B_i^r`

      • 候选区块哈希的签名

      • 它的凭证 σir,1`\sigma_i^{r,1}`,以证明它确实是第 r`r` 轮的potential verifier

  2. 所有被选中的 verifier jSVr,2`j \in SV^{r,2}` 选出这一轮的leader:

    • 从收到的消息 mir,1`m_i^{r,1}` 中获取第1步的凭证:σi1r,1,...,σinr,1`\sigma_{i_1}^{r,1}, ..., \sigma_{i_n}^{r,1}`

    • 计算凭证的哈希值:H(σi1r,1),...,H(σinr,1)`H(\sigma_{i_1}^{r,1}), ..., H(\sigma_{i_n}^{r,1})`,找到其中哈希值最小的凭证 σljr,1`\sigma_{l_j}^{r,1}`,认为 lj`l_j` 是第 r`r` 轮的leader

  3. 步骤2的验证者开始执行BA协议:

    • 为了最小化必需的通信量,验证者的输入 vj`v_j^\prime` 并不使用从leader那收到的区块 Bj`B_j`,而是使用区块的哈希 vj=H(Bj)`v_j^\prime = H(B_j)`

    • 所以BA协议的最后一个步骤中验证者是计算并广播 H(Br)`H(B^r)`,而 H(Br)`H(B^r)` 经过了足够多验证者的签名,所以新区块的哈希就是 H(Br)`H(B^r)`

2.5 问题

上面介绍了领导者选择、验证者选择以及区块的生成,但是也有不少的疑问。比如,如何保证领导者、验证者的选择是随机且独立的?

用户通过出示自己的凭证 σir,s`\sigma_i^{r,s}`,以证明它确实是第 r`r` 轮第 s`s` 步的potential verifier。根据凭证的形式 σir,sSIGi(r,s,Qr1)`\sigma_i^{r,s} \triangleq SIG_i(r,s,Q^{r-1})` 可知,只要 Qr1`Q^{r-1}` 的选择是随机且独立,则领导者和验证者 lr,s`l^{r,s}` 的选择随机且独立的概率接近 h`h`。论文中有详细的证明过程。自此,问题转化为如何保证 Qr1`Q^{r-1}` 的选择随机且独立。

Algorand将 Qr`Q^r` 命名为种子,种子 Qr`Q^r` 的获取方法如下:

Qr{H(SIGlr(Qr1),r),Br是空区块H(Qr1,r),其它 Q^r \triangleq \begin{cases} H(SIG_{l^r}(Q^{r-1}),r), & B^r \text{是空区块} \\ H(Q^{r-1},r), & \text{其它} \end{cases}

可以证明若 Qr1`Q^{r-1}` 的选择是随机且独立的,则 Qr`Q^r` 的选择也是随机且独立的。具体的证明过程,感兴趣的读者可以去看论文,本文不再赘述。

而实际情况是,我们无法保证 Qr1`Q^{r-1}` 的选择是完全随机且独立的,只能尽量保证 Qr1`Q^{r-1}` 不会被操控。这样一来,领导者诚实可靠的概率 h`h'` 接近于 h`h`,即 h>h2(1+hh2)`h' > h^2(1+h-h^2)`。若 h=80h=80%,则 h>.7424`h'>.7424`

问题二:在领导者选择、验证者选择上,我们都要求第 r`r` 轮被选中的节点在第 rk`r-k` 轮就已经存在。为何要如此设计?

根据 Markov-chain-like 的分析,不管Adversary在第 r1`r-1` 轮如何选择,只要它不能往系统中注入新的节点,它就无法让一个诚实节点被选中为第 r+40`r+40` 轮的领导者的概率降低到远远低于 h`h`

因此,从第 rk`r-k` 轮就已经存在的节点中选出第 r`r` 轮的领导者和验证者,可以保证Adversary无法极大的改变一个诚实节点被选中为第 r`r` 轮领导者的概率。可以说,look-back参数 k`k` 是一个安全参数。

除了以上两个问题外,其实还有很多其它重要的问题,比如look-back参数 k`k` 如何选择等。这些问题我们后面会有文章做详细的介绍。

交流群

受限于笔者的学识和能力,文章内容难免有纰漏之处。技术探讨,请添加加微信 kvdoth 备注「YOUChain 技术交流」,进群交流。

公众号

欢迎添加「有令」公众号,了解项目最新进展和技术分享。

wxmp
wxmp
相关文章推荐