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

YOUChain Research

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

本文来自 yipast@YOUChainResearch

上一篇文章中我们讨论了Algorand共识算法的设计原理,它每一轮的共识流程可简短的描述如下:

  1. 随机选择一个leader来提议一个新区块;

  2. 随机选择节点组成委员会,对leader提议的新区块达成Byzantine共识;委员会成员对达成共识的区块进行数字签名。

Algorand的论文中详细描写了两个协议实例,Algorand1`Algorand_1'`Algorand2`Algorand_2'` 。这两个实例在两方面拥有极大的区别:

  • 对委员会中诚实用户数量的要求不同。

    • Algorand1`Algorand_1'` :委员会中至少 2/3 成员是诚实的。

    • Algorand2`Algorand_2'` :委员会中诚实成员数总是 tH`\geqslant t_H`(一个固定的阈值),而至少 2/3 成员诚实的概率极大。

  • 达成Byzantine共识所需要的步骤数不同。

    • Algorand1`Algorand_1'` :达成共识所需要的步骤很大概率下是固定的。

    • Algorand2`Algorand_2'` :达成共识所需要的步骤数可以是任意的,一般比 Algorand1`Algorand_1^\prime` 花费的时间短。

通过这两个基本的实例,可以演化出其他的变体。下面我们先说明这两个算法的详细内容,再进行分析。

一、Algorand1`Algorand'_1` 协议

为了保证安全,节点 i`i` 使用它的长期公私钥对来生成它的凭证 σir,s`\sigma_i^{r,s}`,但使用临时公私钥对 (pkir,s,skir,s)`(pk_i^{r,s},sk_i^{r,s})` 来签名消息。

为了简单起见,使用 esigi(x)sigpkir,s(x)`esig_i(x) \triangleq sig_{pk_i^{r,s}}(x)` 来表示节点 i`i` 在第 r`r` 轮的 s`s` 步用私钥对 x`x` 签名,即 ESIGi(x)SIGpkir,s(x)(i,m,esigi(m))`ESIG_i(x) \triangleq SIG_{pk_i^{r,s}}(x) \triangleq (i,m,esig_i(m))`

Step 1: Block Proposal

节点 iPKrk`i \in PK^{r-k}` 只要拥有 Br1`B^{r-1}`,可以用来计算出 Qr1`Q^{r-1}`,就开始了它第 r`r` 轮的Step 1。

  • 节点 i`i` 使用 Qr1`Q^{r-1}` 来检测是否 iSVr,1`i \in SV^{r,1}`

  • iSVr,1`i \notin SV^{r,1}`i`i` 在Step 1不做任何处理

  • iSVr,1`i \in SV^{r,1}`,即 i`i` 是potential leader,则它做如下处理:

    • 收集广播给它的第 r`r` 轮的支付,并且从中得出最大化的交易集合 PAYir`PAY_i^r`

    • 然后 i`i` 计算出它的候选区块 Bir=(r,PAYir,SIGi(Qr1),H(Br1))`B_i^r = (r,PAY_i^r,SIG_i(Q^{r-1}),H(B^{r-1}))`

    • 最后计算出消息 mir,1=(Bir,esigi(H(Bir)),σir,1)`m_i^{r,1} = (B_i^r,esig_i(H(B_i^r)), \sigma_i^{r,1})`

    • 销毁临时私钥 skir,1`sk_i^{r,1}`,广播消息 mir,1`m_i^{r,1}`

有选择的广播:为了缩短 Step 1的全局执行时间, (r,1)`(r,1)` 消息是有选择的广播。即对每个节点 j`j`

  • 节点收到第一条(r,1)`(r,1)` 消息并验证成功后,正常广播;

  • 随后收到的、并验证成功的 (r,1)`(r,1)` 消息,当且仅当它包含的凭证哈希比之前收到的 (r,1)`(r,1)` 消息的凭证哈希都要小时才会被广播出去。

  • 若节点收到了两条来自同一个节点 i`i`、但不同形式的 mir,1`m_i^{r,1}` 消息时,节点丢弃掉第二条消息。

为了减少通信量、缩短共识所需的时间,每个potential leader i`i` 将它的凭证 σir,1`\sigma_i^{r,1}`mir,1`m_i^{r,1}` 分开广播,因为凭证消息包比较小,能快速的在整个网络上传播,有助于让拥有较大凭证哈希值的 mir,1`m_i^{r,1}` 停止被广播。

Step 2: 分级共识协议GC的第一步

节点 iPKrk`i \in PK^{r-k}` 只要拥有 Br1`B^{r-1}`,就开始了它第 r`r` 轮的Step 2。

  • 节点 i`i`Br1`B^{r-1}` 中计算出 Qr1`Q^{r-1}`,并且检测是否 iSVr,2`i \in SV^{r,2}`

  • iSVr,2`i \notin SV^{r,2}`i`i` 在Step 2不做任何处理

  • iSVr,2`i \in SV^{r,2}`,节点等待时间 t2λ+Λ`t_2 \triangleq \lambda + \Lambda` ,在等待期间,i`i` 执行以下动作。

    1. 节点从收到的所有 (r,1)`(r,1)` 消息中为所有的凭证 σjr,1`\sigma_j^{r,1}` 计算哈希值,找到领导者 l: H(σlr,1)H(σjr,1)`l: \ H(\sigma_l^{r,1}) \leqslant H(\sigma_j^{r,1})`

    2. 若节点已经从 l`l` 收到了有效的消息 mlr,1=(Blr,esigl(H(Blr)),σlr,1)`m_l^{r,1} = (B_l^r, esig_l(H(B_l^r)), \sigma_l^{r,1})`i`i` 设置 viH(Blr)`v_i^\prime \triangleq H(B_l^r)`,否则设置 vi`v_i^\prime \triangleq \perp`

    3. i计算出消息 mir,2(ESIGi(vi),σir,2)`m_i^{r,2} \triangleq (ESIG_i(v_i^\prime), \sigma_i^{r,2})`;销毁临时私钥 skir,2`sk_i^{r,2}`,广播 mir,2`m_i^{r,2}`

Step 3: GC的第二步

节点 iPKrk`i \in PK^{r-k}` 只要拥有 Br1`B^{r-1}`,就开始了它第 r`r` 轮的Step 3。

  • 节点 i`i`Br1`B^{r-1}` 中计算出 Qr1`Q^{r-1}`,并且检测是否 iSVr,3`i \in SV^{r,3}`

  • iSVr,3`i \notin SV^{r,3}`i`i` 在Step 3不做任何处理

  • iSVr,3`i \in SV^{r,3}`,节点等待时间 t3t2+2λ=3λ+Λ`t_3 \triangleq t_2 + 2\lambda = 3\lambda + \Lambda` ,在等待期间,i`i` 执行以下动作。

    1. 若存在一个 v`v^\prime \neq \perp`,节点收到了至少 23`\frac{2}{3}` 个有效而不同的消息 mjr,2(ESIGj(v),σjr,2)`m_j^{r,2} \triangleq (ESIG_j(v^\prime), \sigma_j^{r,2})`i`i` 计算出消息 mir,3(ESIGi(v),σir,3)`m_i^{r,3} \triangleq (ESIG_i(v^\prime), \sigma_i^{r,3})`;否则 mir,3(ESIGi(),σir,3)`m_i^{r,3} \triangleq (ESIG_i(\perp), \sigma_i^{r,3})`

    2. 销毁临时私钥 skir,3`sk_i^{r,3}`,广播 mir,3`m_i^{r,3}`

Step 4:GC的输出及 BBA`BBA^*` 的第一步

节点 iPKrk`i \in PK^{r-k}` 只要拥有 Br1`B^{r-1}`,就开始了它第 r`r` 轮的Step 4。

  • 节点 i`i`Br1`B^{r-1}` 中计算出 Qr1`Q^{r-1}`,并且检测是否 iSVr,4`i \in SV^{r,4}`

  • iSVr,4`i \notin SV^{r,4}`i`i` 在Step 4不做任何处理

  • iSVr,4`i \in SV^{r,4}`,节点等待时间 t4t3+2λ=5λ+Λ`t_4 \triangleq t_3 + 2\lambda = 5\lambda + \Lambda` ,在等待期间,i`i` 执行以下动作。

    1. 按照如下规则来计算GC的输出 vi,gi`v_i, g_i`

      1. 假设存在一个 v`v' \neq \perp`,节点 i`i` 收到了至少 23`\frac{2}{3}` 个有效而不同的消息 mjr,3(ESIGj(v),σjr,3)`m_j^{r,3} \triangleq (ESIG_j(v'), \sigma_j^{r,3})`,则节点设置 viv`v_i \triangleq v'`gi2`g_i \triangleq 2`

      2. 否则,假设存在一个 v`v' \neq \perp`,节点 i`i` 收到了至少 13`\frac{1}{3}` 个有效的消息 mjr,3(ESIGj(),σjr,3)`m_j^{r,3} \triangleq (ESIG_j(\perp), \sigma_j^{r,3})`,则节点设置 viv`v_i \triangleq v'`gi1`g_i \triangleq 1`

      3. 否则,节点设置 viH(Bϵr)`v_i \triangleq H(B_{\epsilon}^r)`gi0`g_i \triangleq 0`

    2. 节点计算BBA`BBA^*`的输入:bi{0,gi=21,其它`b_i \triangleq \begin{cases} 0, &g_i=2 \\ 1, &\text{其它}\end{cases}`

    3. 计算消息 mir,4(ESIGi(bi),ESIGi(vi),σir,4)`m_i^{r,4} \triangleq (ESIG_i(b_i),ESIG_i(v_i), \sigma_i^{r,4})`,销毁临时私钥 skir,4`sk_i^{r,4}`,广播 mir,4`m_i^{r,4}`

Step s, 5sm+2,s2 0 mod 3`5 \leq s \leq m+2, s-2 \equiv\ 0\ mod\ 3`BBA`BBA^*` 的 Coin-Fixed-To-0

节点 iPKrk`i \in PK^{r-k}` 只要拥有 Br1`B^{r-1}`,就开始了它第 r`r` 轮的Step s`s`

  • 节点 i`i`Br1`B^{r-1}` 中计算出 Qr1`Q^{r-1}`,并且检测是否 iSVr,s`i \in SV^{r,s}`

  • iSVr,s`i \notin SV^{r,s}`i`i` 在Step s`s` 不做任何处理

  • iSVr,s`i \in SV^{r,s}`,节点 i`i` 执行以下动作。

    • 节点等待时间 tsts+2λ=(2s3)λ+Λ`t_s \triangleq t_s + 2\lambda = (2s-3)\lambda + \Lambda`

    • 以0结束:在等待时,若存在一个值 v`v \neq \perp` 和步骤 s`s^\prime`,使得:

      (a)5ss,s20 mod 3`5 \leqslant s^\prime \leqslant s, s^\prime-2 \equiv 0 \ mod \ 3`,即 s`s^\prime` 是Coin-Fixed-To-0步骤,

      (b)i`i` 收到至少 tH=2n3+1`t_H = \frac{2n}{3} + 1` 个有效消息 mjr,s1=(ESIGj(0),ESIGj(v),σjr,s1)`m_j^{r,s^\prime-1} = (ESIG_j(0), ESIG_j(v), \sigma_j^{r,s^\prime-1})`,同时,

      (c)i`i` 收到了一个有效消息 mjr,1=(Bjr,esigj(H(Bjr)),σjr,1)`m_j^{r,1} = (B_j^r, esig_j(H(B_j^r)), \sigma_j^{r,1})`v=H(Bjr)`v = H(B_j^r)`

      i`i` 停止等待,并结束步骤s(实际上是结束了第 r`r` 轮),设置 Br=BjrB^r = B_j^r,将子步骤(b)中消息 mjr,s1`m_j^{r,s^\prime-1}` 的集合设置为它自己的 CERTr`CERT^r`

    • 以1结束:在等待时,若存在一个步骤 s`s^\prime`,使得:

      (a')6ss,s21 mod 3`6 \leqslant s^\prime \leqslant s, s^\prime-2 \equiv 1 \ mod \ 3`,即 s`s^\prime` 是Coin-Fixed-To-1步骤

      (b')i`i` 收到至少 tH`t_H` 个有效消息 mjr,s1=(ESIGj(1),ESIGj(vj),σjr,s1)`m_j^{r,s^\prime-1} = (ESIG_j(1), ESIG_j(v_j), \sigma_j^{r,s^\prime-1})`

      i`i` 停止等待,并结束步骤s(实际上是结束了第 r`r` 轮),设置 Br=Bϵr`B^r = B_\epsilon^r`,将子步骤(b')中消息 mjr,s1`m_j^{r,s^\prime-1}` 的集合设置为它自己的 CERTr`CERT^r`

    • 否则,在等待的最后,节点 i`i` 进行如下处理。

      收到的所有有效 mjr,s1`m_j^{r,s-1}` 中,vj`v_j` 拥有大部分投票,则节点设置 vi=vj`v_i=v_j`。按如下规则设置 bi`b_i`

      • 在收到的mjr,s1`m_j^{r,s-1}`中,有超过2/3的mjr,s1=(ESIGj(0),ESIGj(vj),σjr,s1)`m_j^{r,s-1}=(ESIG_j(0),ESIG_j(v_j),\sigma_j^{r,s-1})`,则令bi=0`b_i=0`

      • 否则,在收到的mjr,s1`m_j^{r,s-1}`中,有超过2/3的mjr,s1=(ESIGj(1),ESIGj(vj),σjr,s1)`m_j^{r,s-1}=(ESIG_j(1),ESIG_j(v_j),\sigma_j^{r,s-1})`,则令bi=1`b_i=1`

      • 否则,bi=0`b_i=0`

      节点计算消息 mir,s(ESIGi(bi),ESIGi(vi),σir,s)`m_i^{r,s} \triangleq (ESIG_i(b_i),ESIG_i(v_i), \sigma_i^{r,s})`,销毁临时私钥 skir,s`sk_i^{r,s}`,广播 mir,s`m_i^{r,s}`

Step s, 6sm+2,s2 1 mod 3`6 \leq s \leq m+2, s-2 \equiv\ 1\ mod\ 3`BBA`BBA^*` 的 Coin-Fixed-To-1

节点 iPKrk`i \in PK^{r-k}` 只要拥有 Br1`B^{r-1}`,就开始了它第 r`r` 轮的Step s`s`

  • 节点 i`i`Br1`B^{r-1}` 中计算出 Qr1`Q^{r-1}`,并且检测是否 iSVr,s`i \in SV^{r,s}`

  • iSVr,s`i \notin SV^{r,s}`i`i` 在Step s`s` 不做任何处理

  • iSVr,s`i \in SV^{r,s}`,节点 i`i` 执行以下动作。

    • 节点等待时间 ts(2s3)λ+Λ`t_s \triangleq (2s-3)\lambda + \Lambda`

    • 以0结束:同 Coin-Fixed-To_0。

    • 以1结束:同 Coin-Fixed-To_0。

    • 否则,在等待的最后,节点 i`i` 进行如下处理。

      收到的所有有效 mjr,s1`m_j^{r,s-1}` 中,vj`v_j` 拥有大部分投票,则节点设置 vi=vj`v_i=v_j`。按如下规则设置 bi`b_i`

      • 在收到的mjr,s1`m_j^{r,s-1}`中,有超过2/3的mjr,s1=(ESIGj(0),ESIGj(vj),σjr,s1)`m_j^{r,s-1}=(ESIG_j(0),ESIG_j(v_j),\sigma_j^{r,s-1})`,则令bi=0`b_i=0`

      • 否则,在收到的mjr,s1`m_j^{r,s-1}`中,有超过2/3的mjr,s1=(ESIGj(1),ESIGj(vj),σjr,s1)`m_j^{r,s-1}=(ESIG_j(1),ESIG_j(v_j),\sigma_j^{r,s-1})`,则令bi=1`b_i=1`

      • 否则,bi=1`b_i=1`

      节点计算消息 mir,s(ESIGi(bi),ESIGi(vi),σir,s)`m_i^{r,s} \triangleq (ESIG_i(b_i),ESIG_i(v_i), \sigma_i^{r,s})`,销毁临时私钥 skir,s`sk_i^{r,s}`,广播 mir,s`m_i^{r,s}`

Step s, 7sm+2,s2 2 mod 3`7 \leq s \leq m+2, s-2 \equiv\ 2\ mod\ 3`BBA`BBA^*` 的 Coin-Genuinely-Flipped

节点 iPKrk`i \in PK^{r-k}` 只要拥有 Br1`B^{r-1}`,就开始了它第 r`r` 轮的Step s`s`

  • 节点 i`i`Br1`B^{r-1}` 中计算出 Qr1`Q^{r-1}`,并且检测是否 iSVr,s`i \in SV^{r,s}`

  • iSVr,s`i \notin SV^{r,s}`i`i` 在Step s`s` 不做任何处理

  • iSVr,s`i \in SV^{r,s}`,节点 i`i` 执行以下动作。

    • 节点等待时间 ts(2s3)λ+Λ`t_s \triangleq (2s-3)\lambda + \Lambda`

    • 以0结束:同 Coin-Fixed-To_0。

    • 以1结束:同 Coin-Fixed-To_0。

    • 否则,在等待的最后,节点 i`i` 进行如下处理。

      收到的所有有效 mjr,s1`m_j^{r,s-1}` 中,vj`v_j` 拥有大部分投票,则节点设置 vi=vj`v_i=v_j`。按如下规则设置 bi`b_i`

      • 在收到的mjr,s1`m_j^{r,s-1}`中,有超过2/3的mjr,s1=(ESIGj(0),ESIGj(vj),σjr,s1)`m_j^{r,s-1}=(ESIG_j(0),ESIG_j(v_j),\sigma_j^{r,s-1})`,则令bi=0`b_i=0`

      • 否则,在收到的mjr,s1`m_j^{r,s-1}`中,有超过2/3的mjr,s1=(ESIGj(1),ESIGj(vj),σjr,s1)`m_j^{r,s-1}=(ESIG_j(1),ESIG_j(v_j),\sigma_j^{r,s-1})`,则令bi=1`b_i=1`

      • 否则,设置 bilsb(minjSVir,s1H(σJr,s1))`b_i \triangleq lsb(min_{j \in SV_i^{r,s-1}} H(\sigma_J^{r,s-1}))`SVir,s1`SV_i^{r,s-1}` 为从收到的有效消息 mjr,s1`m_j^{r,s-1}` 中获得的 (r,s1)`(r,s-1)`-验证者。

      节点计算消息 mir,s(ESIGi(bi),ESIGi(vi),σir,s)`m_i^{r,s} \triangleq (ESIG_i(b_i),ESIG_i(v_i), \sigma_i^{r,s})`,销毁临时私钥 skir,s`sk_i^{r,s}`,广播 mir,s`m_i^{r,s}`

步骤 m+3`m + 3`BBA`BBA^*`的最后一步

节点 iPKrk`i \in PK^{r-k}` 只要知道了 Br1`B^{r-1}`,就开启了它的第r轮第 m+3`m + 3`

  • 节点从 Br1`B^{r-1}` 中计算出 Qr1`Q^{r-1}`,并且检测是否 iSVr,m+3`i \in SV^{r,m+3}`

  • iSVr,m+3`i \notin SV^{r,m+3}`i`i` 在Step m+3`m+3` 不做任何处理

  • iSVr,m+3`i \in SV^{r,m+3}`,节点 i`i` 执行以下动作。

    • 等待时间 tm+3tm+2+2λ=(2m+3)λ+Λ`t_{m+3} \triangleq t_{m+2} + 2\lambda = (2m+3)\lambda + \Lambda`

    • 以0结束:同 Coin-Fixed-To_0 步骤

    • 以1结束:同 Coin-Fixed-To_0 步骤

    • 否则,在等待结束时,节点 i`i` 执行以下动作。

      设置 outi1,BrBϵr`out_i \triangleq 1, B^r \triangleq B_\epsilon^r`

      节点计算消息 mir,m+3=(ESIGi(outi),ESIGi(H(Br)),σir,m+3)`m_i^{r,m+3}=(ESIG_i(out_i),ESIG_i(H(B^r)),\sigma_i^{r,m+3})`
      销毁临时私钥 skir,m+3`sk_i^{r,m+3}`,广播 mir,m+3`m_i^{r,m+3}` 来验证 Br`B^r`

非验证者在第 r`r` 轮的区块重构

节点 i`i` 只要知道了 Br1`B^{r-1}`,就开启了它的第 r`r` 轮,并且按以下方法等待区块信息。

  • 在等待期间,若存在 v,s`v, s^\prime` 使得:

    (a)5sm+3, s20 mod 3`5 \leqslant s^\prime \leqslant m+3,\ s^\prime-2 \equiv 0 \ mod \ 3`

    (b)i`i` 收到至少 tH`t_H` 个有效消息 mjr,s1=(ESIGj(0),ESIGj(v),σjr,s1)`m_j^{r,s^\prime-1} = (ESIG_j(0), ESIG_j(v), \sigma_j^{r,s^\prime-1})`

    (c)i`i` 收到一个有效消息 mjr,1=(Bjr,esigj(H(Bjr)),σjr,1), v=H(Bjr)`m_j^{r,1} = (B_j^r, esig_j(H(B_j^r)), \sigma_j^{r,1}),\ v = H(B_j^r)`

    i`i` 停止它的 r`r` 轮执行,令 Br=Bjr`B^r=B_j^r`,将子步骤(b)中消息 mjr,s1`m_j^{r,s^\prime-1}` 的集合设置为它自己的 CERTr`CERT^r`

  • 在等待期间,若存在 s`s^\prime` 使得:

    (a')6sm+3,s21 mod 3`6 \leqslant s^\prime \leqslant m+3, s^\prime-2 \equiv 1 \ mod \ 3`

    (b')i`i` 收到至少 tH`t_H` 个有效消息 mjr,s1=(ESIGj(1),ESIGj(vj),σjr,s1)`m_j^{r,s^\prime-1} = (ESIG_j(1), ESIG_j(v_j), \sigma_j^{r,s^\prime-1})`

    i`i` 停止它的 r`r` 轮执行,令 Br=Bϵr`B^r=B_\epsilon^r`,将子步骤(b')中消息 mjr,s1`m_j^{r,s^\prime-1}` 的集合设置为它自己的 CERTr`CERT^r`

  • 在等待期间,若 i`i` 收到至少 tH`t_H` 个有效消息 mjr,m+3=(ESIGj(1),ESIGj(H(Bϵr)),σjr,m+3)`m_j^{r,m+3} = (ESIG_j(1), ESIG_j(H(B_\epsilon^r)), \sigma_j^{r,m+3})`,则 i`i` 停止它的 r`r` 轮执行,令 Br=Bϵr`B^r=B_\epsilon^r`,将1和 H(Bϵr)`H(B_\epsilon^r)` 的消息 mjr,m+3`m_j^{r,m+3}` 的集合设置为它自己的 CERTr`CERT^r`

以上就是整个共识算法的内容,但是文字描述并不直观,下面的这张图可以帮助大家更好的理解这个算法。

Algorand1
Algorand1

二、Algorand2`Algorand'_2` 协议

Algorand2`Algorand'_2` 的流程与 Algorand1`Algorand'_1` 的流程大体上是一致的,细节上有差异。

以下是 Algorand2`Algorand'_2` 的具体流程。

Step 1: Block Proposal

节点 iPKrk`i \in PK^{r-k}` 只要拥有 CERTr1`CERT^{r-1}`,可以用来计算出 H(Br1)Qr1`H(B^{r-1})、Q^{r-1}`,就开始了它第 r`r` 轮的Step 1。

CERTr`CERT^r`:由数字签名H(Br)`H(B^r)`的集合组成,包含了SVr`SV^r`中的大部分成员,且含有能证明每个成员属于SVr`SV^r`的证据。其作用是将区块Br`B^r`转化成证明区块Br`\overline{B^r}`,同时完成区块的验证。

  • 节点 i`i` 使用 Qr1`Q^{r-1}` 来检测是否 iSVr,1`i \in SV^{r,1}`

  • iSVr,1`i \notin SV^{r,1}`i`i` 在Step 1不做任何处理

  • iSVr,1`i \in SV^{r,1}`,即 i`i` 是potential leader,则它做如下处理:

    • 假若 i`i` 拥有 B0,,Br1`B^0,…,B^{r-1}`,收集广播给它的第 r`r` 轮的支付,并且从中得出最大化的交易集合 PAYir`PAY_i^r`

    • 假若 i`i` 不拥有 B0,,Br1`B^0,…,B^{r-1}`,则设置 PAYir=ϕ`PAY_i^r = \phi`

    • 然后 i`i` 计算出它的候选区块 Bir=(r,PAYir,SIGi(Qr1),H(Br1))`B_i^r = (r,PAY_i^r,SIG_i(Q^{r-1}),H(B^{r-1}))`

    • 最后计算出消息 mir,1=(Bir,esigi(H(Bir)),σir,1)`m_i^{r,1} = (B_i^r,esig_i(H(B_i^r)), \sigma_i^{r,1})`

    • 销毁临时私钥 skir,1`sk_i^{r,1}`,分别广播消息 mir,1`m_i^{r,1}`(SIGi(Qr1),σir,1)`(SIG_i(Q^{r-1}), \sigma_i^{r,1})`

有选择的广播:为了缩短 Step 1的全局执行时间, (r,1)`(r,1)` 消息是有选择的广播。即对每个节点 j`j`

  • 节点收到第一条(r,1)`(r,1)` 消息并验证成功后,正常广播;

  • 随后收到的、并验证成功的 (r,1)`(r,1)` 消息,当且仅当它包含的凭证哈希比之前收到的 (r,1)`(r,1)` 消息的凭证哈希都要小时才会被广播出去。

  • 若节点收到了两条来自同一个节点 i`i`、但不同形式的 mir,1`m_i^{r,1}` 消息时,节点丢弃掉第二条消息。

为了减少通信量、缩短共识所需的时间,每个potential leader i`i` 将它的凭证 σir,1`\sigma_i^{r,1}`mir,1`m_i^{r,1}` 分开广播,因为凭证消息包比较小,能快速的在整个网络上传播,有助于让拥有较大凭证哈希值的 mir,1`m_i^{r,1}` 停止被广播。

Step 2: 分级共识协议GC的第一步

节点 iPKrk`i \in PK^{r-k}` 只要拥有 CERTr1`CERT^{r-1}`,就开始了它第 r`r` 轮的Step 2。

  • 节点 i`i` 等待时间 t2λ+Λ`t_2 \triangleq \lambda + \Lambda` ,在等待期间,i`i` 执行以下动作。

    1. 等待 2λ`2\lambda` 时间后,节点从收到的所有 (r,1)`(r,1)` 消息中为所有的凭证 σjr,1`\sigma_j^{r,1}` 计算哈希值,找到领导者 l: H(σlr,1)H(σjr,1)`l: \ H(\sigma_l^{r,1}) \leqslant H(\sigma_j^{r,1})`

    2. 若节点有一个与 CERTr1`CERT^{r-1}` 中包含的哈希值 H(Br1)`H(B^{r-1})` 相匹配的区块 Br1`B^{r-1} `,并从 l`l` 收到了有效的消息 mlr,1=(Blr,esigl(H(Blr)),σlr,1)`m_l^{r,1} = (B_l^r, esig_l(H(B_l^r)), \sigma_l^{r,1})`,则 i`i` 停止等待,并设置 vi(H(Blr),l)`v_i^\prime \triangleq (H(B_l^r), l)`

    3. 否则等待时间 t2`t_2` 结束,i`i` 设置 vi`v_i^\prime \triangleq \perp``

    4. vi`v_i^\prime` 被设置后,i`i`CERTr1`CERT^{r-1}` 中计算 Qr1`Q^{r-1}`,检测是否 iSVr,2`i \in SV^{r,2}`

    5. iSVr,2`i \in SV^{r,2}`i`i` 计算消息 mir,2(ESIGi(vi),σir,2)`m_i^{r,2} \triangleq (ESIG_i(v_i^\prime), \sigma_i^{r,2})`,销毁临时私钥 skir,2`sk_i^{r,2}`,广播 mir,2`m_i^{r,2}`。否则,i`i` 停止,不广播任何消息。

Step 3: GC的第二步

节点 iPKrk`i \in PK^{r-k}` 只要拥有 CERTr1`CERT^{r-1}`,就开始了它第 r`r` 轮的Step 3。

  • 节点 i`i` 等待时间 t3t2+2λ=3λ+Λ`t_3 \triangleq t_2 + 2\lambda = 3\lambda + \Lambda` ,在等待期间,i`i` 执行以下动作。

    1. 假设存在一个 v`v`,节点 i`i` 收到了至少 tH`t_H` 个有效而不同的消息 mjr,2(ESIGj(v),σjr,2)`m_j^{r,2} \triangleq (ESIG_j(v), \sigma_j^{r,2})`,则节点停止等待,并设置 v=v`v'=v`

    2. 否则等待时间 t3`t_3` 结束,i`i` 设置 vi`v_i^\prime \triangleq \perp``

    3. vi`v_i^\prime ` 被设置后,i`i`CERTr1`CERT^{r-1}` 中计算 Qr1`Q^{r-1}`,检测是否 iSVr,3`i \in SV^{r,3}`iSVr,3`i \in SV^{r,3}`i`i` 计算消息 mir,2(ESIGi(vi),σir,2)`m_i^{r,2} \triangleq (ESIG_i(v_i^\prime), \sigma_i^{r,2})`,销毁临时私钥 skir,2`sk_i^{r,2}`,广播 mir,2`m_i^{r,2}`。否则,i`i` 停止,不广播任何消息。

Step 4:GC的输出及 BBA`BBA^*` 的第一步

节点 iPKrk`i \in PK^{r-k}` 只要结束了Step 3,就开始了它的Step 4。

  • 节点 i`i` 等待时间 2λ`2\lambda ` ,在等待期间,i`i` 执行以下动作。

    1. 按照如下规则来计算 vi,gi`v_i, g_i` 和GC的输出。

      1. 假设存在一个 v`v' \neq \perp`,节点 i`i` 收到了至少 tH`t_H` 个有效而不同的消息 mjr,3(ESIGj(v),σjr,3)`m_j^{r,3} \triangleq (ESIG_j(v'), \sigma_j^{r,3})`,则节点停止等待,并设置 viv`v_i \triangleq v'`gi2`g_i \triangleq 2`

      2. 假若节点 i`i` 收到了至少 tH`t_H` 个有效的消息 mjr,3(ESIGj(),σjr,3)`m_j^{r,3} \triangleq (ESIG_j(\perp), \sigma_j^{r,3})`,则节点停止等待,并设置 vi`v_i \triangleq \perp`gi0`g_i \triangleq 0`

      3. 否则,当时间 2λ`2\lambda` 已过,若节点 i`i` 收到了至少 tH2`\lceil \frac{t_H}{2} \rceil` 个有效的消息 mjr,3(ESIGj(v),σjr,3)`m_j^{r,3} \triangleq (ESIG_j(v'), \sigma_j^{r,3})`,则节点设置 viv`v_i \triangleq v'`gi1`g_i \triangleq 1`

      4. 否则,当时间 2λ`2\lambda` 已过,设置 vi`v_i \triangleq \bot`gi0`g_i \triangleq 0`

    2. vi,gi`v_i, g_i` 都被设置了,节点计算BBA`BBA^*`的输入:bi{0,gi=21,otherwise`b_i \triangleq \begin{cases} 0, &g_i=2 \\ 1, &\text{otherwise}\end{cases}`

    3. iSVr,4`i \in SV^{r,4}`,计算消息 mir,4(ESIGi(bi),ESIGi(vi),σir,4)`m_i^{r,4} \triangleq (ESIG_i(b_i),ESIG_i(v_i), \sigma_i^{r,4})`,销毁临时私钥 skir,4`sk_i^{r,4}`,广播 mir,4`m_i^{r,4}`。否则,i`i` 停止,不广播任何消息。

Step s, 5sm+2,s2 0 mod 3`5 \leq s \leq m+2, s-2 \equiv\ 0\ mod\ 3`BBA`BBA^*` 的 Coin-Fixed-To-0

节点 iPKrk`i \in PK^{r-k}` 只要结束了Step s1`s-1`,就开始了它的Step s`s`

  • 节点 i`i` 等待时间 2λ`2\lambda ` ,在等待期间,i`i` 执行以下动作。

    • 以0结束:在等待时,若存在一个值 v`v \neq \perp` 和步骤 s`s^\prime`,使得:

      (a)5ss,s20 mod 3`5 \leqslant s^\prime \leqslant s, s^\prime-2 \equiv 0 \ mod \ 3`,即 s`s^\prime` 是Coin-Fixed-To-0步骤,

      (b)i`i` 收到至少 tH`t_H` 个有效消息 mjr,s1=(ESIGj(0),ESIGj(v),σjr,s1)`m_j^{r,s^\prime-1} = (ESIG_j(0), ESIG_j(v), \sigma_j^{r,s^\prime-1})`,同时,

      (c)i`i` 收到了一个有效消息 (SIGj(Qr1),σjr,1)`(SIG_j(Q^{r-1}), \sigma_j^{r,1})`

      i`i` 停止等待,并结束步骤s(实际上是结束了第 r`r` 轮),将 H(Br)`H(B^r)` 设为 v`v` 的第一部分,将子步骤(b)中消息 mjr,s1`m_j^{r,s^\prime-1}` 的集合以及 (SIGj(Qr1),σjr,1)`(SIG_j(Q^{r-1}), \sigma_j^{r,1})` 设置为它自己的 CERTr`CERT^r`

    • 以1结束:在等待时,若存在一个步骤 s`s^\prime`,使得:

      (a')6ss,s21 mod 3`6 \leqslant s^\prime \leqslant s, s^\prime-2 \equiv 1 \ mod \ 3`,即 s`s^\prime` 是Coin-Fixed-To-1步骤

      (b')i`i` 收到至少 tH`t_H` 个有效消息 mjr,s1=(ESIGj(1),ESIGj(vj),σjr,s1)`m_j^{r,s^\prime-1} = (ESIG_j(1), ESIG_j(v_j), \sigma_j^{r,s^\prime-1})`

      i`i` 停止等待,并结束步骤s(实际上是结束了第 r`r` 轮),设置 Br=Bϵr`B^r = B_\epsilon^r`,将子步骤(b')中消息 mjr,s1`m_j^{r,s^\prime-1}` 的集合设置为它自己的 CERTr`CERT^r`

    • 若节点收到至少 tH`t_H` 个有效的 mjr,s1=(ESIGj(1),ESIGj(vj),σjr,s1)`m_j^{r,s-1} = (ESIG_j(1), ESIG_j(v_j), \sigma_j^{r,s-1})`,则停止等待,并设置 bi1`b_i \triangleq 1`

    • 若节点收到至少 tH`t_H` 个有效的 mjr,s1=(ESIGj(0),ESIGj(vj),σjr,s1)`m_j^{r,s-1} = (ESIG_j(0), ESIG_j(v_j), \sigma_j^{r,s-1})`,(节点并没有对同一个 v`v` 达成共识),则停止等待,并设置 bi0`b_i \triangleq 0`

    • 否则,当时间 2λ`2\lambda` 已过,设置 bi0`b_i \triangleq 0`

    • bi`b_i` 被设置,节点从 CERTr1`CERT^{r-1}` 中算出 Qr1`Q^{r-1}`,并验证是否 iSVr,s`i \in SV^{r,s}`

    • iSVr,s`i \in SV^{r,s}`,计算消息 mir,s(ESIGi(bi),ESIGi(vi),σir,s)`m_i^{r,s} \triangleq (ESIG_i(b_i),ESIG_i(v_i), \sigma_i^{r,s})`,销毁临时私钥 skir,s`sk_i^{r,s}`,广播 mir,s`m_i^{r,s}`。否则,i`i` 停止,不广播任何消息。

Step s, 6sm+2,s2 1 mod 3`6 \leq s \leq m+2, s-2 \equiv\ 1\ mod\ 3`BBA`BBA^*` 的 Coin-Fixed-To-1

节点 iPKrk`i \in PK^{r-k}` 只要结束了Step s1`s-1`,就开始了它的Step s`s`

  • 节点 i`i` 等待时间 2λ`2\lambda ` ,在等待期间,i`i` 执行以下动作。

    • 以0结束:同 Coin-Fixed-To_0。

    • 以1结束:同 Coin-Fixed-To_0。

    • 若节点收到至少 tH`t_H` 个有效的 mjr,s1=(ESIGj(0),ESIGj(vj),σjr,s1)`m_j^{r,s-1} = (ESIG_j(0), ESIG_j(v_j), \sigma_j^{r,s-1})`,(节点并没有对同一个 v`v` 达成共识),则停止等待,并设置 bi0`b_i \triangleq 0`

    • 否则,当时间 2λ`2\lambda` 已过,设置 bi1`b_i \triangleq 1`

    • bi`b_i` 被设置,节点从 CERTr1`CERT^{r-1}` 中算出 Qr1`Q^{r-1}`,并验证是否 iSVr,s`i \in SV^{r,s}`

    • iSVr,s`i \in SV^{r,s}`,计算消息 mir,s(ESIGi(bi),ESIGi(vi),σir,s)`m_i^{r,s} \triangleq (ESIG_i(b_i),ESIG_i(v_i), \sigma_i^{r,s})`,销毁临时私钥 skir,s`sk_i^{r,s}`,广播 mir,s`m_i^{r,s}`。否则,i`i` 停止,不广播任何消息。

Step s, 7sm+2,s2 2 mod 3`7 \leq s \leq m+2, s-2 \equiv\ 2\ mod\ 3`BBA`BBA^*` 的 Coin-Genuinely-Flipped

节点 iPKrk`i \in PK^{r-k}` 只要结束了Step s1`s-1`,就开始了它的Step s`s`

  • 节点 i`i` 等待时间 2λ`2\lambda ` ,在等待期间,i`i` 执行以下动作。

    • 以0结束:同 Coin-Fixed-To_0。

    • 以1结束:同 Coin-Fixed-To_0。

    • 若节点收到至少 tH`t_H` 个有效的 mjr,s1=(ESIGj(0),ESIGj(vj),σjr,s1)`m_j^{r,s-1} = (ESIG_j(0), ESIG_j(v_j), \sigma_j^{r,s-1})`,(节点并没有对同一个 v`v` 达成共识),则停止等待,并设置 bi0`b_i \triangleq 0`

    • 若节点收到至少 tH`t_H` 个有效的 mjr,s1=(ESIGj(1),ESIGj(vj),σjr,s1)`m_j^{r,s-1} = (ESIG_j(1), ESIG_j(v_j), \sigma_j^{r,s-1})`,则停止等待,并设置 bi1`b_i \triangleq 1`

    • 否则,当时间 2λ`2\lambda` 已过,设置 bilsb(minjSVir,s1H(σJr,s1))`b_i \triangleq lsb(min_{j \in SV_i^{r,s-1}} H(\sigma_J^{r,s-1}))`SVir,s1`SV_i^{r,s-1}` 为从收到的有效消息 mjr,s1`m_j^{r,s-1}` 中获得的 (r,s1)`(r,s-1)`-验证者。

    • bi`b_i` 被设置,节点从 CERTr1`CERT^{r-1}` 中算出 Qr1`Q^{r-1}`,并验证是否 iSVr,s`i \in SV^{r,s}`

    • iSVr,s`i \in SV^{r,s}`,计算消息 mir,s(ESIGi(bi),ESIGi(vi),σir,s)`m_i^{r,s} \triangleq (ESIG_i(b_i),ESIG_i(v_i), \sigma_i^{r,s})`,销毁临时私钥 skir,s`sk_i^{r,s}`,广播 mir,s`m_i^{r,s}`。否则,i`i` 停止,不广播任何消息。

非验证者在第 r`r` 轮的区块重构

节点 i`i` 只要知道了 CERTr1`CERT^{r-1}`,就开启了它的第 r`r` 轮。

  • 节点 i`i` 遵从协议每一步骤的指示,参与所有消息的广播,但是若某一步骤中,节点不是验证者,则不初始化任何广播。

  • 节点在某些Step,一旦进入了 以0结束 或 以1结束,就用对应的 CERTr`CERT^r` 结束当前的 r`r` 轮。

  • 自此之后,节点在等待接收子区块 Br`B^r` 之时开始它的第 r+1`r+1` 轮。

三、总结

以上是笔者根据论文内容进行的梳理,尽管 Algorand1`Algorand'_1`Algorand2`Algorand'_2` 两者在内容表述上有所差异,但原理和总体流程相差无几。本文不对两者的优劣对比作任何评价,毕竟二者所适用的情况有所不同。

看完整篇论文之后,笔者很佩服Algorand共识算法逻辑的严谨以及证明的详尽。然而,笔者觉得,算法过于复杂,不适用于工业应用,尤其是对时间、通信复杂度要求颇高的区块链。

从上文可以看出,该共识算法达成共识最少需要五轮通信,而PBFT是两轮(prepare、commit)。在通信复杂度上,该算法至少是PBFT的两倍以上。YOUChain的测试结果表明,不管共识算法如何优化,通信环境越差,达成共识所需要的时间越长,最终的tps越低。

Algorand于18年4月份更新的共识算法大大简化了共识流程,可以说是基本上看不到之前协议的影子(后面我们会有文章对它进行详细的分析)。但这也充分说明了Algorand团队也意识到该算法在实际应用上的缺陷。不过不能否认,Algorand 2017年的论文是不可多得的佳作,里面的诸多概念和思考方式能给人极大地启发,值得深度研究。

交流群

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

公众号

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

wxmp
wxmp
相关文章推荐