上一篇文章中我们讨论了Algorand共识算法的设计原理，它每一轮的共识流程可简短的描述如下：
随机选择一个leader来提议一个新区块；
随机选择节点组成委员会，对leader提议的新区块达成Byzantine共识；委员会成员对达成共识的区块进行数字签名。
Algorand的论文中详细描写了两个协议实例，`Algorand_1'`Algorand1′、`Algorand_2'`Algorand2′ 。这两个实例在两方面拥有极大的区别：
对委员会中诚实用户数量的要求不同。
`Algorand_1'`Algorand1′ ：委员会中至少 2/3 成员是诚实的。
`Algorand_2'`Algorand2′ ：委员会中诚实成员数总是 `\geqslant t_H`⩾tH(一个固定的阈值)，而至少 2/3 成员诚实的概率极大。
达成Byzantine共识所需要的步骤数不同。
`Algorand_1'`Algorand1′ ：达成共识所需要的步骤很大概率下是固定的。
`Algorand_2'`Algorand2′ ：达成共识所需要的步骤数可以是任意的，一般比 `Algorand_1^\prime`Algorand1′ 花费的时间短。
通过这两个基本的实例，可以演化出其他的变体。下面我们先说明这两个算法的详细内容，再进行分析。
一、`Algorand'_1`Algorand1′ 协议
为了保证安全，节点 `i`i 使用它的长期公私钥对来生成它的凭证 `\sigma_i^{r,s}`σir,s，但使用临时公私钥对 `(pk_i^{r,s},sk_i^{r,s})`(pkir,s,skir,s) 来签名消息。
为了简单起见，使用 `esig_i(x) \triangleq sig_{pk_i^{r,s}}(x)`esigi(x)≜sigpkir,s(x) 来表示节点 `i`i 在第 `r`r 轮的 `s`s 步用私钥对 `x`x 签名，即 `ESIG_i(x) \triangleq SIG_{pk_i^{r,s}}(x) \triangleq (i,m,esig_i(m))`ESIGi(x)≜SIGpkir,s(x)≜(i,m,esigi(m)) 。
Step 1: Block Proposal
节点 `i \in PK^{r-k}`i∈PKr−k 只要拥有 `B^{r-1}`Br−1，可以用来计算出 `Q^{r-1}`Qr−1，就开始了它第 `r`r 轮的Step 1。
节点 `i`i 使用 `Q^{r-1}`Qr−1 来检测是否 `i \in SV^{r,1}`i∈SVr,1
若 `i \notin SV^{r,1}`i∈/SVr,1，`i`i 在Step 1不做任何处理
若 `i \in SV^{r,1}`i∈SVr,1，即 `i`i 是potential leader，则它做如下处理：
收集广播给它的第 `r`r 轮的支付，并且从中得出最大化的交易集合 `PAY_i^r`PAYir
然后 `i`i 计算出它的候选区块 `B_i^r = (r,PAY_i^r,SIG_i(Q^{r-1}),H(B^{r-1}))`Bir=(r,PAYir,SIGi(Qr−1),H(Br−1))
最后计算出消息 `m_i^{r,1} = (B_i^r,esig_i(H(B_i^r)), \sigma_i^{r,1})`mir,1=(Bir,esigi(H(Bir)),σir,1)
销毁临时私钥 `sk_i^{r,1}`skir,1，广播消息 `m_i^{r,1}`mir,1
有选择的广播：为了缩短 Step 1的全局执行时间， `(r,1)`(r,1) 消息是有选择的广播。即对每个节点 `j`j，
节点收到第一条`(r,1)`(r,1) 消息并验证成功后，正常广播；
随后收到的、并验证成功的 `(r,1)`(r,1) 消息，当且仅当它包含的凭证哈希比之前收到的 `(r,1)`(r,1) 消息的凭证哈希都要小时才会被广播出去。
若节点收到了两条来自同一个节点 `i`i、但不同形式的 `m_i^{r,1}`mir,1 消息时，节点丢弃掉第二条消息。
为了减少通信量、缩短共识所需的时间，每个potential leader `i`i 将它的凭证 `\sigma_i^{r,1}`σir,1 和 `m_i^{r,1}`mir,1 分开广播，因为凭证消息包比较小，能快速的在整个网络上传播，有助于让拥有较大凭证哈希值的 `m_i^{r,1}`mir,1 停止被广播。
Step 2: 分级共识协议GC的第一步
节点 `i \in PK^{r-k}`i∈PKr−k 只要拥有 `B^{r-1}`Br−1，就开始了它第 `r`r 轮的Step 2。
节点 `i`i 从 `B^{r-1}`Br−1 中计算出 `Q^{r-1}`Qr−1，并且检测是否 `i \in SV^{r,2}`i∈SVr,2
若 `i \notin SV^{r,2}`i∈/SVr,2，`i`i 在Step 2不做任何处理
若 `i \in SV^{r,2}`i∈SVr,2，节点等待时间 `t_2 \triangleq \lambda + \Lambda`t2≜λ+Λ ，在等待期间，`i`i 执行以下动作。
节点从收到的所有 `(r,1)`(r,1) 消息中为所有的凭证 `\sigma_j^{r,1}`σjr,1 计算哈希值，找到领导者 `l: \ H(\sigma_l^{r,1}) \leqslant H(\sigma_j^{r,1})`l: H(σlr,1)⩽H(σjr,1)
若节点已经从 `l`l 收到了有效的消息 `m_l^{r,1} = (B_l^r, esig_l(H(B_l^r)), \sigma_l^{r,1})`mlr,1=(Blr,esigl(H(Blr)),σlr,1)， `i`i 设置 `v_i^\prime \triangleq H(B_l^r)`vi′≜H(Blr)，否则设置 `v_i^\prime \triangleq \perp`vi′≜⊥
i计算出消息 `m_i^{r,2} \triangleq (ESIG_i(v_i^\prime), \sigma_i^{r,2})`mir,2≜(ESIGi(vi′),σir,2)；销毁临时私钥 `sk_i^{r,2}`skir,2，广播 `m_i^{r,2}`mir,2
Step 3: GC的第二步
节点 `i \in PK^{r-k}`i∈PKr−k 只要拥有 `B^{r-1}`Br−1，就开始了它第 `r`r 轮的Step 3。
节点 `i`i 从 `B^{r-1}`Br−1 中计算出 `Q^{r-1}`Qr−1，并且检测是否 `i \in SV^{r,3}`i∈SVr,3
若 `i \notin SV^{r,3}`i∈/SVr,3，`i`i 在Step 3不做任何处理
若 `i \in SV^{r,3}`i∈SVr,3，节点等待时间 `t_3 \triangleq t_2 + 2\lambda = 3\lambda + \Lambda`t3≜t2+2λ=3λ+Λ ，在等待期间，`i`i 执行以下动作。
若存在一个 `v^\prime \neq \perp`v′=⊥，节点收到了至少 `\frac{2}{3}`32 个有效而不同的消息 `m_j^{r,2} \triangleq (ESIG_j(v^\prime), \sigma_j^{r,2})`mjr,2≜(ESIGj(v′),σjr,2)，`i`i 计算出消息 `m_i^{r,3} \triangleq (ESIG_i(v^\prime), \sigma_i^{r,3})`mir,3≜(ESIGi(v′),σir,3)；否则 `m_i^{r,3} \triangleq (ESIG_i(\perp), \sigma_i^{r,3})`mir,3≜(ESIGi(⊥),σir,3)
销毁临时私钥 `sk_i^{r,3}`skir,3，广播 `m_i^{r,3}`mir,3
Step 4：GC的输出及 `BBA^*`BBA∗ 的第一步
节点 `i \in PK^{r-k}`i∈PKr−k 只要拥有 `B^{r-1}`Br−1，就开始了它第 `r`r 轮的Step 4。
节点 `i`i 从 `B^{r-1}`Br−1 中计算出 `Q^{r-1}`Qr−1，并且检测是否 `i \in SV^{r,4}`i∈SVr,4
若 `i \notin SV^{r,4}`i∈/SVr,4，`i`i 在Step 4不做任何处理
若 `i \in SV^{r,4}`i∈SVr,4，节点等待时间 `t_4 \triangleq t_3 + 2\lambda = 5\lambda + \Lambda`t4≜t3+2λ=5λ+Λ ，在等待期间，`i`i 执行以下动作。
按照如下规则来计算GC的输出 `v_i, g_i`vi,gi。
假设存在一个 `v' \neq \perp`v′=⊥，节点 `i`i 收到了至少 `\frac{2}{3}`32 个有效而不同的消息 `m_j^{r,3} \triangleq (ESIG_j(v'), \sigma_j^{r,3})`mjr,3≜(ESIGj(v′),σjr,3)，则节点设置 `v_i \triangleq v'`vi≜v′ 和 `g_i \triangleq 2`gi≜2。
否则，假设存在一个 `v' \neq \perp`v′=⊥，节点 `i`i 收到了至少 `\frac{1}{3}`31 个有效的消息 `m_j^{r,3} \triangleq (ESIG_j(\perp), \sigma_j^{r,3})`mjr,3≜(ESIGj(⊥),σjr,3)，则节点设置 `v_i \triangleq v'`vi≜v′ 和 `g_i \triangleq 1`gi≜1。
否则，节点设置 `v_i \triangleq H(B_{\epsilon}^r)`vi≜H(Bϵr) 和 `g_i \triangleq 0`gi≜0。
节点计算`BBA^*`BBA∗的输入：`b_i \triangleq \begin{cases} 0, &g_i=2 \\ 1, &\text{其它}\end{cases}`bi≜{0,1,gi=2其它
计算消息 `m_i^{r,4} \triangleq (ESIG_i(b_i),ESIG_i(v_i), \sigma_i^{r,4})`mir,4≜(ESIGi(bi),ESIGi(vi),σir,4)，销毁临时私钥 `sk_i^{r,4}`skir,4，广播 `m_i^{r,4}`mir,4。
Step s, `5 \leq s \leq m+2, s-2 \equiv\ 0\ mod\ 3`5≤s≤m+2,s−2≡ 0 mod 3：`BBA^*`BBA∗ 的 Coin-Fixed-To-0
节点 `i \in PK^{r-k}`i∈PKr−k 只要拥有 `B^{r-1}`Br−1，就开始了它第 `r`r 轮的Step `s`s。
节点 `i`i 从 `B^{r-1}`Br−1 中计算出 `Q^{r-1}`Qr−1，并且检测是否 `i \in SV^{r,s}`i∈SVr,s
若 `i \notin SV^{r,s}`i∈/SVr,s，`i`i 在Step `s`s 不做任何处理
若 `i \in SV^{r,s}`i∈SVr,s，节点 `i`i 执行以下动作。
节点等待时间 `t_s \triangleq t_s + 2\lambda = (2s-3)\lambda + \Lambda`ts≜ts+2λ=(2s−3)λ+Λ
以0结束：在等待时，若存在一个值 `v \neq \perp`v=⊥ 和步骤 `s^\prime`s′，使得：
（a）`5 \leqslant s^\prime \leqslant s, s^\prime-2 \equiv 0 \ mod \ 3`5⩽s′⩽s,s′−2≡0 mod 3，即 `s^\prime`s′ 是Coin-Fixed-To-0步骤，
（b）`i`i 收到至少 `t_H = \frac{2n}{3} + 1`tH=32n+1 个有效消息 `m_j^{r,s^\prime-1} = (ESIG_j(0), ESIG_j(v), \sigma_j^{r,s^\prime-1})`mjr,s′−1=(ESIGj(0),ESIGj(v),σjr,s′−1)，同时，
（c）`i`i 收到了一个有效消息 `m_j^{r,1} = (B_j^r, esig_j(H(B_j^r)), \sigma_j^{r,1})`mjr,1=(Bjr,esigj(H(Bjr)),σjr,1)，`v = H(B_j^r)`v=H(Bjr)
则 `i`i 停止等待，并结束步骤s（实际上是结束了第 `r`r 轮），设置 B^r = B_j^rBr=Bjr，将子步骤（b）中消息 `m_j^{r,s^\prime-1}`mjr,s′−1 的集合设置为它自己的 `CERT^r`CERTr
以1结束：在等待时，若存在一个步骤 `s^\prime`s′，使得：
（a'）`6 \leqslant s^\prime \leqslant s, s^\prime-2 \equiv 1 \ mod \ 3`6⩽s′⩽s,s′−2≡1 mod 3，即 `s^\prime`s′ 是Coin-Fixed-To-1步骤
（b'）`i`i 收到至少 `t_H`tH 个有效消息 `m_j^{r,s^\prime-1} = (ESIG_j(1), ESIG_j(v_j), \sigma_j^{r,s^\prime-1})`mjr,s′−1=(ESIGj(1),ESIGj(vj),σjr,s′−1)，
则 `i`i 停止等待，并结束步骤s（实际上是结束了第 `r`r 轮），设置 `B^r = B_\epsilon^r`Br=Bϵr，将子步骤（b'）中消息 `m_j^{r,s^\prime-1}`mjr,s′−1 的集合设置为它自己的 `CERT^r`CERTr。
否则，在等待的最后，节点 `i`i 进行如下处理。
收到的所有有效 `m_j^{r,s-1}`mjr,s−1 中，`v_j`vj 拥有大部分投票，则节点设置 `v_i=v_j`vi=vj。按如下规则设置 `b_i`bi。
在收到的`m_j^{r,s-1}`mjr,s−1中，有超过2/3的`m_j^{r,s-1}=(ESIG_j(0),ESIG_j(v_j),\sigma_j^{r,s-1})`mjr,s−1=(ESIGj(0),ESIGj(vj),σjr,s−1)，则令`b_i=0`bi=0
否则，在收到的`m_j^{r,s-1}`mjr,s−1中，有超过2/3的`m_j^{r,s-1}=(ESIG_j(1),ESIG_j(v_j),\sigma_j^{r,s-1})`mjr,s−1=(ESIGj(1),ESIGj(vj),σjr,s−1)，则令`b_i=1`bi=1
否则，`b_i=0`bi=0
节点计算消息 `m_i^{r,s} \triangleq (ESIG_i(b_i),ESIG_i(v_i), \sigma_i^{r,s})`mir,s≜(ESIGi(bi),ESIGi(vi),σir,s)，销毁临时私钥 `sk_i^{r,s}`skir,s，广播 `m_i^{r,s}`mir,s。
Step s, `6 \leq s \leq m+2, s-2 \equiv\ 1\ mod\ 3`6≤s≤m+2,s−2≡ 1 mod 3：`BBA^*`BBA∗ 的 Coin-Fixed-To-1
节点 `i \in PK^{r-k}`i∈PKr−k 只要拥有 `B^{r-1}`Br−1，就开始了它第 `r`r 轮的Step `s`s。
节点 `i`i 从 `B^{r-1}`Br−1 中计算出 `Q^{r-1}`Qr−1，并且检测是否 `i \in SV^{r,s}`i∈SVr,s
若 `i \notin SV^{r,s}`i∈/SVr,s，`i`i 在Step `s`s 不做任何处理
若 `i \in SV^{r,s}`i∈SVr,s，节点 `i`i 执行以下动作。
节点等待时间 `t_s \triangleq (2s-3)\lambda + \Lambda`ts≜(2s−3)λ+Λ
以0结束：同 Coin-Fixed-To_0。
以1结束：同 Coin-Fixed-To_0。
否则，在等待的最后，节点 `i`i 进行如下处理。
收到的所有有效 `m_j^{r,s-1}`mjr,s−1 中，`v_j`vj 拥有大部分投票，则节点设置 `v_i=v_j`vi=vj。按如下规则设置 `b_i`bi。
在收到的`m_j^{r,s-1}`mjr,s−1中，有超过2/3的`m_j^{r,s-1}=(ESIG_j(0),ESIG_j(v_j),\sigma_j^{r,s-1})`mjr,s−1=(ESIGj(0),ESIGj(vj),σjr,s−1)，则令`b_i=0`bi=0
否则，在收到的`m_j^{r,s-1}`mjr,s−1中，有超过2/3的`m_j^{r,s-1}=(ESIG_j(1),ESIG_j(v_j),\sigma_j^{r,s-1})`mjr,s−1=(ESIGj(1),ESIGj(vj),σjr,s−1)，则令`b_i=1`bi=1
否则，`b_i=1`bi=1
节点计算消息 `m_i^{r,s} \triangleq (ESIG_i(b_i),ESIG_i(v_i), \sigma_i^{r,s})`mir,s≜(ESIGi(bi),ESIGi(vi),σir,s)，销毁临时私钥 `sk_i^{r,s}`skir,s，广播 `m_i^{r,s}`mir,s。
Step s, `7 \leq s \leq m+2, s-2 \equiv\ 2\ mod\ 3`7≤s≤m+2,s−2≡ 2 mod 3：`BBA^*`BBA∗ 的 Coin-Genuinely-Flipped
节点 `i \in PK^{r-k}`i∈PKr−k 只要拥有 `B^{r-1}`Br−1，就开始了它第 `r`r 轮的Step `s`s。
节点 `i`i 从 `B^{r-1}`Br−1 中计算出 `Q^{r-1}`Qr−1，并且检测是否 `i \in SV^{r,s}`i∈SVr,s
若 `i \notin SV^{r,s}`i∈/SVr,s，`i`i 在Step `s`s 不做任何处理
若 `i \in SV^{r,s}`i∈SVr,s，节点 `i`i 执行以下动作。
节点等待时间 `t_s \triangleq (2s-3)\lambda + \Lambda`ts≜(2s−3)λ+Λ
以0结束：同 Coin-Fixed-To_0。
以1结束：同 Coin-Fixed-To_0。
否则，在等待的最后，节点 `i`i 进行如下处理。
收到的所有有效 `m_j^{r,s-1}`mjr,s−1 中，`v_j`vj 拥有大部分投票，则节点设置 `v_i=v_j`vi=vj。按如下规则设置 `b_i`bi。
在收到的`m_j^{r,s-1}`mjr,s−1中，有超过2/3的`m_j^{r,s-1}=(ESIG_j(0),ESIG_j(v_j),\sigma_j^{r,s-1})`mjr,s−1=(ESIGj(0),ESIGj(vj),σjr,s−1)，则令`b_i=0`bi=0
否则，在收到的`m_j^{r,s-1}`mjr,s−1中，有超过2/3的`m_j^{r,s-1}=(ESIG_j(1),ESIG_j(v_j),\sigma_j^{r,s-1})`mjr,s−1=(ESIGj(1),ESIGj(vj),σjr,s−1)，则令`b_i=1`bi=1
否则，设置 `b_i \triangleq lsb(min_{j \in SV_i^{r,s-1}} H(\sigma_J^{r,s-1}))`bi≜lsb(minj∈SVir,s−1H(σJr,s−1))，`SV_i^{r,s-1}`SVir,s−1 为从收到的有效消息 `m_j^{r,s-1}`mjr,s−1 中获得的 `(r,s-1)`(r,s−1)-验证者。
节点计算消息 `m_i^{r,s} \triangleq (ESIG_i(b_i),ESIG_i(v_i), \sigma_i^{r,s})`mir,s≜(ESIGi(bi),ESIGi(vi),σir,s)，销毁临时私钥 `sk_i^{r,s}`skir,s，广播 `m_i^{r,s}`mir,s。
步骤 `m + 3`m+3：`BBA^*`BBA∗的最后一步
节点 `i \in PK^{r-k}`i∈PKr−k 只要知道了 `B^{r-1}`Br−1，就开启了它的第r轮第 `m + 3`m+3 步
节点从 `B^{r-1}`Br−1 中计算出 `Q^{r-1}`Qr−1，并且检测是否 `i \in SV^{r,m+3}`i∈SVr,m+3
若 `i \notin SV^{r,m+3}`i∈/SVr,m+3，`i`i 在Step `m+3`m+3 不做任何处理
若 `i \in SV^{r,m+3}`i∈SVr,m+3，节点 `i`i 执行以下动作。
等待时间 `t_{m+3} \triangleq t_{m+2} + 2\lambda = (2m+3)\lambda + \Lambda`tm+3≜tm+2+2λ=(2m+3)λ+Λ。
以0结束：同 Coin-Fixed-To_0 步骤
以1结束：同 Coin-Fixed-To_0 步骤
否则，在等待结束时，节点 `i`i 执行以下动作。
设置 `out_i \triangleq 1, B^r \triangleq B_\epsilon^r`outi≜1,Br≜Bϵr
节点计算消息 `m_i^{r,m+3}=(ESIG_i(out_i),ESIG_i(H(B^r)),\sigma_i^{r,m+3})`mir,m+3=(ESIGi(outi),ESIGi(H(Br)),σir,m+3)
销毁临时私钥 `sk_i^{r,m+3}`skir,m+3，广播 `m_i^{r,m+3}`mir,m+3 来验证 `B^r`Br
非验证者在第 `r`r 轮的区块重构
节点 `i`i 只要知道了 `B^{r-1}`Br−1，就开启了它的第 `r`r 轮，并且按以下方法等待区块信息。
在等待期间，若存在 `v, s^\prime`v,s′ 使得：
（a）`5 \leqslant s^\prime \leqslant m+3,\ s^\prime-2 \equiv 0 \ mod \ 3`5⩽s′⩽m+3, s′−2≡0 mod 3
（b）`i`i 收到至少 `t_H`tH 个有效消息 `m_j^{r,s^\prime-1} = (ESIG_j(0), ESIG_j(v), \sigma_j^{r,s^\prime-1})`mjr,s′−1=(ESIGj(0),ESIGj(v),σjr,s′−1)
（c）`i`i 收到一个有效消息 `m_j^{r,1} = (B_j^r, esig_j(H(B_j^r)), \sigma_j^{r,1}),\ v = H(B_j^r)`mjr,1=(Bjr,esigj(H(Bjr)),σjr,1), v=H(Bjr)
`i`i 停止它的 `r`r 轮执行，令 `B^r=B_j^r`Br=Bjr，将子步骤（b）中消息 `m_j^{r,s^\prime-1}`mjr,s′−1 的集合设置为它自己的 `CERT^r`CERTr
在等待期间，若存在 `s^\prime`s′ 使得：
（a'）`6 \leqslant s^\prime \leqslant m+3, s^\prime-2 \equiv 1 \ mod \ 3`6⩽s′⩽m+3,s′−2≡1 mod 3
（b'）`i`i 收到至少 `t_H`tH 个有效消息 `m_j^{r,s^\prime-1} = (ESIG_j(1), ESIG_j(v_j), \sigma_j^{r,s^\prime-1})`mjr,s′−1=(ESIGj(1),ESIGj(vj),σjr,s′−1)
`i`i 停止它的 `r`r 轮执行，令 `B^r=B_\epsilon^r`Br=Bϵr，将子步骤（b'）中消息 `m_j^{r,s^\prime-1}`mjr,s′−1 的集合设置为它自己的 `CERT^r`CERTr
在等待期间，若 `i`i 收到至少 `t_H`tH 个有效消息 `m_j^{r,m+3} = (ESIG_j(1), ESIG_j(H(B_\epsilon^r)), \sigma_j^{r,m+3})`mjr,m+3=(ESIGj(1),ESIGj(H(Bϵr)),σjr,m+3)，则 `i`i 停止它的 `r`r 轮执行，令 `B^r=B_\epsilon^r`Br=Bϵr，将1和 `H(B_\epsilon^r)`H(Bϵr) 的消息 `m_j^{r,m+3}`mjr,m+3的集合设置为它自己的 `CERT^r`CERTr。
以上就是整个共识算法的内容，但是文字描述并不直观，下面的这张图可以帮助大家更好的理解这个算法。
Algorand1
二、`Algorand'_2`Algorand2′ 协议
`Algorand'_2`Algorand2′ 的流程与 `Algorand'_1`Algorand1′ 的流程大体上是一致的，细节上有差异。
以下是 `Algorand'_2`Algorand2′ 的具体流程。
Step 1: Block Proposal
节点 `i \in PK^{r-k}`i∈PKr−k 只要拥有 `CERT^{r-1}`CERTr−1，可以用来计算出 `H(B^{r-1})、Q^{r-1}`H(Br−1)、Qr−1，就开始了它第 `r`r 轮的Step 1。
`CERT^r`CERTr：由数字签名`H(B^r)`H(Br)的集合组成，包含了`SV^r`SVr中的大部分成员，且含有能证明每个成员属于`SV^r`SVr的证据。其作用是将区块`B^r`Br转化成证明区块`\overline{B^r}`Br，同时完成区块的验证。
节点 `i`i 使用 `Q^{r-1}`Qr−1 来检测是否 `i \in SV^{r,1}`i∈SVr,1
若 `i \notin SV^{r,1}`i∈/SVr,1，`i`i 在Step 1不做任何处理
若 `i \in SV^{r,1}`i∈SVr,1，即 `i`i 是potential leader，则它做如下处理：
假若 `i`i 拥有 `B^0,…,B^{r-1}`B0,…,Br−1，收集广播给它的第 `r`r 轮的支付，并且从中得出最大化的交易集合 `PAY_i^r`PAYir
假若 `i`i 不拥有 `B^0,…,B^{r-1}`B0,…,Br−1，则设置 `PAY_i^r = \phi`PAYir=ϕ
然后 `i`i 计算出它的候选区块 `B_i^r = (r,PAY_i^r,SIG_i(Q^{r-1}),H(B^{r-1}))`Bir=(r,PAYir,SIGi(Qr−1),H(Br−1))
最后计算出消息 `m_i^{r,1} = (B_i^r,esig_i(H(B_i^r)), \sigma_i^{r,1})`mir,1=(Bir,esigi(H(Bir)),σir,1)
销毁临时私钥 `sk_i^{r,1}`skir,1，分别广播消息 `m_i^{r,1}`mir,1 和 `(SIG_i(Q^{r-1}), \sigma_i^{r,1})`(SIGi(Qr−1),σir,1)
有选择的广播：为了缩短 Step 1的全局执行时间， `(r,1)`(r,1) 消息是有选择的广播。即对每个节点 `j`j，
节点收到第一条`(r,1)`(r,1) 消息并验证成功后，正常广播；
随后收到的、并验证成功的 `(r,1)`(r,1) 消息，当且仅当它包含的凭证哈希比之前收到的 `(r,1)`(r,1) 消息的凭证哈希都要小时才会被广播出去。
若节点收到了两条来自同一个节点 `i`i、但不同形式的 `m_i^{r,1}`mir,1 消息时，节点丢弃掉第二条消息。
为了减少通信量、缩短共识所需的时间，每个potential leader `i`i 将它的凭证 `\sigma_i^{r,1}`σir,1 和 `m_i^{r,1}`mir,1 分开广播，因为凭证消息包比较小，能快速的在整个网络上传播，有助于让拥有较大凭证哈希值的 `m_i^{r,1}`mir,1 停止被广播。
Step 2: 分级共识协议GC的第一步
节点 `i \in PK^{r-k}`i∈PKr−k 只要拥有 `CERT^{r-1}`CERTr−1，就开始了它第 `r`r 轮的Step 2。
节点 `i`i 等待时间 `t_2 \triangleq \lambda + \Lambda`t2≜λ+Λ ，在等待期间，`i`i 执行以下动作。
等待 `2\lambda`2λ 时间后，节点从收到的所有 `(r,1)`(r,1) 消息中为所有的凭证 `\sigma_j^{r,1}`σjr,1 计算哈希值，找到领导者 `l: \ H(\sigma_l^{r,1}) \leqslant H(\sigma_j^{r,1})`l: H(σlr,1)⩽H(σjr,1)
若节点有一个与 `CERT^{r-1}`CERTr−1 中包含的哈希值 `H(B^{r-1})`H(Br−1) 相匹配的区块 `B^{r-1} `Br−1，并从 `l`l 收到了有效的消息 `m_l^{r,1} = (B_l^r, esig_l(H(B_l^r)), \sigma_l^{r,1})`mlr,1=(Blr,esigl(H(Blr)),σlr,1)，则 `i`i 停止等待，并设置 `v_i^\prime \triangleq (H(B_l^r), l)`vi′≜(H(Blr),l)
否则等待时间 `t_2`t2 结束，`i`i 设置 `v_i^\prime \triangleq \perp`vi′≜⊥`
`v_i^\prime`vi′ 被设置后，`i`i 从 `CERT^{r-1}`CERTr−1 中计算 `Q^{r-1}`Qr−1，检测是否 `i \in SV^{r,2}`i∈SVr,2
若 `i \in SV^{r,2}`i∈SVr,2，`i`i 计算消息 `m_i^{r,2} \triangleq (ESIG_i(v_i^\prime), \sigma_i^{r,2})`mir,2≜(ESIGi(vi′),σir,2)，销毁临时私钥 `sk_i^{r,2}`skir,2，广播 `m_i^{r,2}`mir,2。否则，`i`i 停止，不广播任何消息。
Step 3: GC的第二步
节点 `i \in PK^{r-k}`i∈PKr−k 只要拥有 `CERT^{r-1}`CERTr−1，就开始了它第 `r`r 轮的Step 3。
节点 `i`i 等待时间 `t_3 \triangleq t_2 + 2\lambda = 3\lambda + \Lambda`t3≜t2+2λ=3λ+Λ ，在等待期间，`i`i 执行以下动作。
假设存在一个 `v`v，节点 `i`i 收到了至少 `t_H`tH 个有效而不同的消息 `m_j^{r,2} \triangleq (ESIG_j(v), \sigma_j^{r,2})`mjr,2≜(ESIGj(v),σjr,2)，则节点停止等待，并设置 `v'=v`v′=v
否则等待时间 `t_3`t3 结束，`i`i 设置 `v_i^\prime \triangleq \perp`vi′≜⊥`
`v_i^\prime `vi′ 被设置后，`i`i 从 `CERT^{r-1}`CERTr−1 中计算 `Q^{r-1}`Qr−1，检测是否 `i \in SV^{r,3}`i∈SVr,3 若 `i \in SV^{r,3}`i∈SVr,3，`i`i 计算消息 `m_i^{r,2} \triangleq (ESIG_i(v_i^\prime), \sigma_i^{r,2})`mir,2≜(ESIGi(vi′),σir,2)，销毁临时私钥 `sk_i^{r,2}`skir,2，广播 `m_i^{r,2}`mir,2。否则，`i`i停止，不广播任何消息。
Step 4：GC的输出及 `BBA^*`BBA∗ 的第一步
节点 `i \in PK^{r-k}`i∈PKr−k 只要结束了Step 3，就开始了它的Step 4。
节点 `i`i 等待时间 `2\lambda `2λ ，在等待期间，`i`i 执行以下动作。
按照如下规则来计算 `v_i, g_i`vi,gi 和GC的输出。
假设存在一个 `v' \neq \perp`v′=⊥，节点 `i`i 收到了至少 `t_H`tH 个有效而不同的消息 `m_j^{r,3} \triangleq (ESIG_j(v'), \sigma_j^{r,3})`mjr,3≜(ESIGj(v′),σjr,3)，则节点停止等待，并设置 `v_i \triangleq v'`vi≜v′ 和 `g_i \triangleq 2`gi≜2。
假若节点 `i`i 收到了至少 `t_H`tH 个有效的消息 `m_j^{r,3} \triangleq (ESIG_j(\perp), \sigma_j^{r,3})`mjr,3≜(ESIGj(⊥),σjr,3)，则节点停止等待，并设置 `v_i \triangleq \perp`vi≜⊥ 和 `g_i \triangleq 0`gi≜0。
否则，当时间 `2\lambda`2λ 已过，若节点 `i`i 收到了至少 `\lceil \frac{t_H}{2} \rceil`⌈2tH⌉ 个有效的消息 `m_j^{r,3} \triangleq (ESIG_j(v'), \sigma_j^{r,3})`mjr,3≜(ESIGj(v′),σjr,3)，则节点设置 `v_i \triangleq v'`vi≜v′ 和 `g_i \triangleq 1`gi≜1。
否则，当时间 `2\lambda`2λ 已过，设置 `v_i \triangleq \bot`vi≜⊥ 和 `g_i \triangleq 0`gi≜0。
当 `v_i, g_i`vi,gi 都被设置了，节点计算`BBA^*`BBA∗的输入：`b_i \triangleq \begin{cases} 0, &g_i=2 \\ 1, &\text{otherwise}\end{cases}`bi≜{0,1,gi=2otherwise
若 `i \in SV^{r,4}`i∈SVr,4，计算消息 `m_i^{r,4} \triangleq (ESIG_i(b_i),ESIG_i(v_i), \sigma_i^{r,4})`mir,4≜(ESIGi(bi),ESIGi(vi),σir,4)，销毁临时私钥 `sk_i^{r,4}`skir,4，广播 `m_i^{r,4}`mir,4。否则，`i`i 停止，不广播任何消息。
Step s, `5 \leq s \leq m+2, s-2 \equiv\ 0\ mod\ 3`5≤s≤m+2,s−2≡ 0 mod 3：`BBA^*`BBA∗ 的 Coin-Fixed-To-0
节点 `i \in PK^{r-k}`i∈PKr−k 只要结束了Step `s-1`s−1，就开始了它的Step `s`s。
节点 `i`i 等待时间 `2\lambda `2λ ，在等待期间，`i`i 执行以下动作。
以0结束：在等待时，若存在一个值 `v \neq \perp`v=⊥ 和步骤 `s^\prime`s′，使得：
（a）`5 \leqslant s^\prime \leqslant s, s^\prime-2 \equiv 0 \ mod \ 3`5⩽s′⩽s,s′−2≡0 mod 3，即 `s^\prime`s′ 是Coin-Fixed-To-0步骤，
（b）`i`i 收到至少 `t_H`tH 个有效消息 `m_j^{r,s^\prime-1} = (ESIG_j(0), ESIG_j(v), \sigma_j^{r,s^\prime-1})`mjr,s′−1=(ESIGj(0),ESIGj(v),σjr,s′−1)，同时，
（c）`i`i 收到了一个有效消息 `(SIG_j(Q^{r-1}), \sigma_j^{r,1})`(SIGj(Qr−1),σjr,1)，
则 `i`i 停止等待，并结束步骤s（实际上是结束了第 `r`r 轮），将 `H(B^r)`H(Br) 设为 `v`v 的第一部分，将子步骤（b）中消息 `m_j^{r,s^\prime-1}`mjr,s′−1 的集合以及 `(SIG_j(Q^{r-1}), \sigma_j^{r,1})`(SIGj(Qr−1),σjr,1) 设置为它自己的 `CERT^r`CERTr。
以1结束：在等待时，若存在一个步骤 `s^\prime`s′，使得：
（a'）`6 \leqslant s^\prime \leqslant s, s^\prime-2 \equiv 1 \ mod \ 3`6⩽s′⩽s,s′−2≡1 mod 3，即 `s^\prime`s′ 是Coin-Fixed-To-1步骤
（b'）`i`i 收到至少 `t_H`tH 个有效消息 `m_j^{r,s^\prime-1} = (ESIG_j(1), ESIG_j(v_j), \sigma_j^{r,s^\prime-1})`mjr,s′−1=(ESIGj(1),ESIGj(vj),σjr,s′−1)，
则 `i`i 停止等待，并结束步骤s（实际上是结束了第 `r`r 轮），设置 `B^r = B_\epsilon^r`Br=Bϵr，将子步骤（b'）中消息 `m_j^{r,s^\prime-1}`mjr,s′−1 的集合设置为它自己的 `CERT^r`CERTr。
若节点收到至少 `t_H`tH 个有效的 `m_j^{r,s-1} = (ESIG_j(1), ESIG_j(v_j), \sigma_j^{r,s-1})`mjr,s−1=(ESIGj(1),ESIGj(vj),σjr,s−1)，则停止等待，并设置 `b_i \triangleq 1`bi≜1。
若节点收到至少 `t_H`tH 个有效的 `m_j^{r,s-1} = (ESIG_j(0), ESIG_j(v_j), \sigma_j^{r,s-1})`mjr,s−1=(ESIGj(0),ESIGj(vj),σjr,s−1)，（节点并没有对同一个 `v`v 达成共识），则停止等待，并设置 `b_i \triangleq 0`bi≜0。
否则，当时间 `2\lambda`2λ 已过，设置 `b_i \triangleq 0`bi≜0。
当 `b_i`bi 被设置，节点从 `CERT^{r-1}`CERTr−1 中算出 `Q^{r-1}`Qr−1，并验证是否 `i \in SV^{r,s}`i∈SVr,s。
若 `i \in SV^{r,s}`i∈SVr,s，计算消息 `m_i^{r,s} \triangleq (ESIG_i(b_i),ESIG_i(v_i), \sigma_i^{r,s})`mir,s≜(ESIGi(bi),ESIGi(vi),σir,s)，销毁临时私钥 `sk_i^{r,s}`skir,s，广播 `m_i^{r,s}`mir,s。否则，`i`i 停止，不广播任何消息。
Step s, `6 \leq s \leq m+2, s-2 \equiv\ 1\ mod\ 3`6≤s≤m+2,s−2≡ 1 mod 3：`BBA^*`BBA∗ 的 Coin-Fixed-To-1
节点 `i \in PK^{r-k}`i∈PKr−k 只要结束了Step `s-1`s−1，就开始了它的Step `s`s。
节点 `i`i 等待时间 `2\lambda `2λ ，在等待期间，`i`i 执行以下动作。
以0结束：同 Coin-Fixed-To_0。
以1结束：同 Coin-Fixed-To_0。
若节点收到至少 `t_H`tH 个有效的 `m_j^{r,s-1} = (ESIG_j(0), ESIG_j(v_j), \sigma_j^{r,s-1})`mjr,s−1=(ESIGj(0),ESIGj(vj),σjr,s−1)，（节点并没有对同一个 `v`v 达成共识），则停止等待，并设置 `b_i \triangleq 0`bi≜0。
否则，当时间 `2\lambda`2λ 已过，设置 `b_i \triangleq 1`bi≜1。
当 `b_i`bi 被设置，节点从 `CERT^{r-1}`CERTr−1 中算出 `Q^{r-1}`Qr−1，并验证是否 `i \in SV^{r,s}`i∈SVr,s。
若 `i \in SV^{r,s}`i∈SVr,s，计算消息 `m_i^{r,s} \triangleq (ESIG_i(b_i),ESIG_i(v_i), \sigma_i^{r,s})`mir,s≜(ESIGi(bi),ESIGi(vi),σir,s)，销毁临时私钥 `sk_i^{r,s}`skir,s，广播 `m_i^{r,s}`mir,s。否则，`i`i 停止，不广播任何消息。
Step s, `7 \leq s \leq m+2, s-2 \equiv\ 2\ mod\ 3`7≤s≤m+2,s−2≡ 2 mod 3：`BBA^*`BBA∗ 的 Coin-Genuinely-Flipped
节点 `i \in PK^{r-k}`i∈PKr−k 只要结束了Step `s-1`s−1，就开始了它的Step `s`s。
节点 `i`i 等待时间 `2\lambda `2λ ，在等待期间，`i`i 执行以下动作。
以0结束：同 Coin-Fixed-To_0。
以1结束：同 Coin-Fixed-To_0。
若节点收到至少 `t_H`tH 个有效的 `m_j^{r,s-1} = (ESIG_j(0), ESIG_j(v_j), \sigma_j^{r,s-1})`mjr,s−1=(ESIGj(0),ESIGj(vj),σjr,s−1)，（节点并没有对同一个 `v`v 达成共识），则停止等待，并设置 `b_i \triangleq 0`bi≜0。
若节点收到至少 `t_H`tH 个有效的 `m_j^{r,s-1} = (ESIG_j(1), ESIG_j(v_j), \sigma_j^{r,s-1})`mjr,s−1=(ESIGj(1),ESIGj(vj),σjr,s−1)，则停止等待，并设置 `b_i \triangleq 1`bi≜1。
否则，当时间 `2\lambda`2λ 已过，设置 `b_i \triangleq lsb(min_{j \in SV_i^{r,s-1}} H(\sigma_J^{r,s-1}))`bi≜lsb(minj∈SVir,s−1H(σJr,s−1))，`SV_i^{r,s-1}`SVir,s−1 为从收到的有效消息 `m_j^{r,s-1}`mjr,s−1 中获得的 `(r,s-1)`(r,s−1)-验证者。
当 `b_i`bi 被设置，节点从 `CERT^{r-1}`CERTr−1 中算出 `Q^{r-1}`Qr−1，并验证是否 `i \in SV^{r,s}`i∈SVr,s。
若 `i \in SV^{r,s}`i∈SVr,s，计算消息 `m_i^{r,s} \triangleq (ESIG_i(b_i),ESIG_i(v_i), \sigma_i^{r,s})`mir,s≜(ESIGi(bi),ESIGi(vi),σir,s)，销毁临时私钥 `sk_i^{r,s}`skir,s，广播 `m_i^{r,s}`mir,s。否则，`i`i 停止，不广播任何消息。
非验证者在第 `r`r 轮的区块重构
节点 `i`i 只要知道了 `CERT^{r-1}`CERTr−1，就开启了它的第 `r`r 轮。
节点 `i`i 遵从协议每一步骤的指示，参与所有消息的广播，但是若某一步骤中，节点不是验证者，则不初始化任何广播。
节点在某些Step，一旦进入了 以0结束 或 以1结束，就用对应的 `CERT^r`CERTr 结束当前的 `r`r 轮。
自此之后，节点在等待接收子区块 `B^r`Br 之时开始它的第 `r+1`r+1 轮。
三、总结
以上是笔者根据论文内容进行的梳理，尽管 `Algorand'_1`Algorand1′ 和 `Algorand'_2`Algorand2′ 两者在内容表述上有所差异，但原理和总体流程相差无几。本文不对两者的优劣对比作任何评价，毕竟二者所适用的情况有所不同。
看完整篇论文之后，笔者很佩服Algorand共识算法逻辑的严谨以及证明的详尽。然而，笔者觉得，算法过于复杂，不适用于工业应用，尤其是对时间、通信复杂度要求颇高的区块链。
从上文可以看出，该共识算法达成共识最少需要五轮通信，而PBFT是两轮（prepare、commit）。在通信复杂度上，该算法至少是PBFT的两倍以上。YOUChain的测试结果表明，不管共识算法如何优化，通信环境越差，达成共识所需要的时间越长，最终的tps越低。
Algorand于18年4月份更新的共识算法大大简化了共识流程，可以说是基本上看不到之前协议的影子（后面我们会有文章对它进行详细的分析）。但这也充分说明了Algorand团队也意识到该算法在实际应用上的缺陷。不过不能否认，Algorand 2017年的论文是不可多得的佳作，里面的诸多概念和思考方式能给人极大地启发，值得深度研究。
交流群
受限于笔者的学识和能力，文章内容难免有纰漏之处。技术探讨，请添加加微信 kvdoth 备注「YOUChain 技术交流」，进群交流。
公众号
欢迎添加「有令」公众号，了解项目最新进展和技术分享。
网友评论