区块广播:

Algorand 共识算法(2017)的设计原理-2

EOS柚子CNM水手发布在 技术文档
 7424  4

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

本文来自 yipast@YOUChainResearch

上一篇文章中我们讨论了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^\primeAlgorand1′ 花费的时间短。

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

一、Algorand'_1Algorand1′ 协议
为了保证安全,节点 ii 使用它的长期公私钥对来生成它的凭证 \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) 来表示节点 ii 在第 rr 轮的 ss 步用私钥对 xx 签名,即 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,就开始了它第 rr 轮的Step 1。

节点 ii 使用 Q^{r-1}Qr?1 来检测是否 i \in SV^{r,1}i∈SVr,1

i \notin SV^{r,1}i∈/SVr,1,ii 在Step 1不做任何处理

i \in SV^{r,1}i∈SVr,1,即 ii 是potential leader,则它做如下处理:

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

然后 ii 计算出它的候选区块 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) 消息是有选择的广播。即对每个节点 jj,

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

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

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

为了减少通信量、缩短共识所需的时间,每个potential leader ii 将它的凭证 \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,就开始了它第 rr 轮的Step 2。

节点 ii 从 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,ii 在Step 2不做任何处理

i \in SV^{r,2}i∈SVr,2,节点等待时间 t_2 \triangleq \lambda + \Lambdat2?λ+Λ ,在等待期间,ii 执行以下动作。

节点从收到的所有 (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)

若节点已经从 ll 收到了有效的消息 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), ii 设置 v_i^\prime \triangleq H(B_l^r)vi′?H(Blr),否则设置 v_i^\prime \triangleq \perpvi′?⊥

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,就开始了它第 rr 轮的Step 3。

节点 ii 从 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,ii 在Step 3不做任何处理

i \in SV^{r,3}i∈SVr,3,节点等待时间 t_3 \triangleq t_2 + 2\lambda = 3\lambda + \Lambdat3?t2+2λ=3λ+Λ ,在等待期间,ii 执行以下动作。

若存在一个 v^\prime \neq \perpv′?=⊥,节点收到了至少 \frac{2}{3}32 个有效而不同的消息 m_j^{r,2} \triangleq (ESIG_j(v^\prime), \sigma_j^{r,2})mjr,2?(ESIGj(v′),σjr,2),ii 计算出消息 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,就开始了它第 rr 轮的Step 4。

节点 ii 从 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,ii 在Step 4不做任何处理

i \in SV^{r,4}i∈SVr,4,节点等待时间 t_4 \triangleq t_3 + 2\lambda = 5\lambda + \Lambdat4?t3+2λ=5λ+Λ ,在等待期间,ii 执行以下动作。

按照如下规则来计算GC的输出 v_i, g_ivi,gi。

假设存在一个 v' \neq \perpv′?=⊥,节点 ii 收到了至少 \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 2gi?2。

否则,假设存在一个 v' \neq \perpv′?=⊥,节点 ii 收到了至少 \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 1gi?1。

否则,节点设置 v_i \triangleq H(B_{\epsilon}^r)vi?H(B?r) 和 g_i \triangleq 0gi?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\ 35≤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,就开始了它第 rr 轮的Step ss。

节点 ii 从 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,ii 在Step ss 不做任何处理

i \in SV^{r,s}i∈SVr,s,节点 ii 执行以下动作。

节点等待时间 t_s \triangleq t_s + 2\lambda = (2s-3)\lambda + \Lambdats?ts+2λ=(2s?3)λ+Λ

以0结束:在等待时,若存在一个值 v \neq \perpv?=⊥ 和步骤 s^\primes′,使得:

(a)5 \leqslant s^\prime \leqslant s, s^\prime-2 \equiv 0 \ mod \ 35?s′?s,s′?2≡0 mod 3,即 s^\primes′ 是Coin-Fixed-To-0步骤,

(b)ii 收到至少 t_H = \frac{2n}{3} + 1tH=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)ii 收到了一个有效消息 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)

ii 停止等待,并结束步骤s(实际上是结束了第 rr 轮),设置 B^r = B_j^rBr=Bjr,将子步骤(b)中消息 m_j^{r,s^\prime-1}mjr,s′?1 的集合设置为它自己的 CERT^rCERTr

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

(a’)6 \leqslant s^\prime \leqslant s, s^\prime-2 \equiv 1 \ mod \ 36?s′?s,s′?2≡1 mod 3,即 s^\primes′ 是Coin-Fixed-To-1步骤

(b’)ii 收到至少 t_HtH 个有效消息 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),

ii 停止等待,并结束步骤s(实际上是结束了第 rr 轮),设置 B^r = B_\epsilon^rBr=B?r,将子步骤(b’)中消息 m_j^{r,s^\prime-1}mjr,s′?1 的集合设置为它自己的 CERT^rCERTr。

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

收到的所有有效 m_j^{r,s-1}mjr,s?1 中,v_jvj 拥有大部分投票,则节点设置 v_i=v_jvi=vj。按如下规则设置 b_ibi。

在收到的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=0bi=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=1bi=1

否则,b_i=0bi=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\ 36≤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,就开始了它第 rr 轮的Step ss。

节点 ii 从 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,ii 在Step ss 不做任何处理

i \in SV^{r,s}i∈SVr,s,节点 ii 执行以下动作。

节点等待时间 t_s \triangleq (2s-3)\lambda + \Lambdats?(2s?3)λ+Λ

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

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

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

收到的所有有效 m_j^{r,s-1}mjr,s?1 中,v_jvj 拥有大部分投票,则节点设置 v_i=v_jvi=vj。按如下规则设置 b_ibi。

在收到的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=0bi=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=1bi=1

否则,b_i=1bi=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\ 37≤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,就开始了它第 rr 轮的Step ss。

节点 ii 从 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,ii 在Step ss 不做任何处理

i \in SV^{r,s}i∈SVr,s,节点 ii 执行以下动作。

节点等待时间 t_s \triangleq (2s-3)\lambda + \Lambdats?(2s?3)λ+Λ

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

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

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

收到的所有有效 m_j^{r,s-1}mjr,s?1 中,v_jvj 拥有大部分投票,则节点设置 v_i=v_jvi=vj。按如下规则设置 b_ibi。

在收到的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=0bi=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=1bi=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 + 3m+3:BBA^*BBA?的最后一步

节点 i \in PK^{r-k}i∈PKr?k 只要知道了 B^{r-1}Br?1,就开启了它的第r轮第 m + 3m+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,ii 在Step m+3m+3 不做任何处理

i \in SV^{r,m+3}i∈SVr,m+3,节点 ii 执行以下动作。

等待时间 t_{m+3} \triangleq t_{m+2} + 2\lambda = (2m+3)\lambda + \Lambdatm+3?tm+2+2λ=(2m+3)λ+Λ。

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

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

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

设置 out_i \triangleq 1, B^r \triangleq B_\epsilon^routi?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^rBr

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

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

在等待期间,若存在 v, s^\primev,s′ 使得:

(a)5 \leqslant s^\prime \leqslant m+3,\ s^\prime-2 \equiv 0 \ mod \ 35?s′?m+3, s′?2≡0 mod 3

(b)ii 收到至少 t_HtH 个有效消息 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)ii 收到一个有效消息 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)

ii 停止它的 rr 轮执行,令 B^r=B_j^rBr=Bjr,将子步骤(b)中消息 m_j^{r,s^\prime-1}mjr,s′?1 的集合设置为它自己的 CERT^rCERTr

在等待期间,若存在 s^\primes′ 使得:

(a’)6 \leqslant s^\prime \leqslant m+3, s^\prime-2 \equiv 1 \ mod \ 36?s′?m+3,s′?2≡1 mod 3

(b’)ii 收到至少 t_HtH 个有效消息 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)

ii 停止它的 rr 轮执行,令 B^r=B_\epsilon^rBr=B?r,将子步骤(b’)中消息 m_j^{r,s^\prime-1}mjr,s′?1 的集合设置为它自己的 CERT^rCERTr

在等待期间,若 ii 收到至少 t_HtH 个有效消息 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),则 ii 停止它的 rr 轮执行,令 B^r=B_\epsilon^rBr=B?r,将1和 H(B_\epsilon^r)H(B?r) 的消息 m_j^{r,m+3}mjr,m+3 的集合设置为它自己的CERT^rCERTr。

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

Algorand1

二、Algorand'_2Algorand2′ 协议
Algorand'_2Algorand2′ 的流程与 Algorand'_1Algorand1′ 的流程大体上是一致的,细节上有差异。

以下是 Algorand'_2Algorand2′ 的具体流程。

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,就开始了它第 rr 轮的Step 1。

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

节点 ii 使用 Q^{r-1}Qr?1 来检测是否 i \in SV^{r,1}i∈SVr,1

i \notin SV^{r,1}i∈/SVr,1,ii 在Step 1不做任何处理

i \in SV^{r,1}i∈SVr,1,即 ii 是potential leader,则它做如下处理:

假若 ii 拥有 B^0,…,B^{r-1}B0,…,Br?1,收集广播给它的第 rr 轮的支付,并且从中得出最大化的交易集合PAY_i^rPAYir

假若 ii 不拥有 B^0,…,B^{r-1}B0,…,Br?1,则设置 PAY_i^r = \phiPAYir=?

然后 ii 计算出它的候选区块 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) 消息是有选择的广播。即对每个节点 jj,

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

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

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

为了减少通信量、缩短共识所需的时间,每个potential leader ii 将它的凭证 \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,就开始了它第 rr 轮的Step 2。

节点 ii 等待时间 t_2 \triangleq \lambda + \Lambdat2?λ+Λ ,在等待期间,ii 执行以下动作。

等待 2\lambda2λ 时间后,节点从收到的所有 (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,并从 ll 收到了有效的消息 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),则 ii 停止等待,并设置 v_i^\prime \triangleq (H(B_l^r), l)vi′?(H(Blr),l)

否则等待时间 t_2t2 结束,ii 设置 v_i^\prime \triangleq \perpvi′?⊥`

v_i^\primevi′ 被设置后,ii 从 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,ii 计算消息 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。否则,ii 停止,不广播任何消息。

Step 3: GC的第二步

节点 i \in PK^{r-k}i∈PKr?k 只要拥有 CERT^{r-1}CERTr?1,就开始了它第 rr 轮的Step 3。

节点 ii 等待时间 t_3 \triangleq t_2 + 2\lambda = 3\lambda + \Lambdat3?t2+2λ=3λ+Λ ,在等待期间,ii 执行以下动作。

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

否则等待时间 t_3t3 结束,ii 设置 v_i^\prime \triangleq \perpvi′?⊥`

v_i^\prime vi′ 被设置后,ii 从 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,ii 计算消息 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。否则,ii 停止,不广播任何消息。

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

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

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

按照如下规则来计算 v_i, g_ivi,gi 和GC的输出。

假设存在一个 v' \neq \perpv′?=⊥,节点 ii 收到了至少 t_HtH 个有效而不同的消息 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 2gi?2。

假若节点 ii 收到了至少 t_HtH 个有效的消息 m_j^{r,3} \triangleq (ESIG_j(\perp), \sigma_j^{r,3})mjr,3?(ESIGj(⊥),σjr,3),则节点停止等待,并设置 v_i \triangleq \perpvi?⊥ 和 g_i \triangleq 0gi?0。

否则,当时间 2\lambda2λ 已过,若节点 ii 收到了至少 \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 1gi?1。

否则,当时间 2\lambda2λ 已过,设置 v_i \triangleq \botvi?⊥ 和 g_i \triangleq 0gi?0。

v_i, g_ivi,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。否则,ii 停止,不广播任何消息。

Step s, 5 \leq s \leq m+2, s-2 \equiv\ 0\ mod\ 35≤s≤m+2,s?2≡ 0 mod 3:BBA^*BBA? 的 Coin-Fixed-To-0

节点 i \in PK^{r-k}i∈PKr?k 只要结束了Step s-1s?1,就开始了它的Step ss。

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

以0结束:在等待时,若存在一个值 v \neq \perpv?=⊥ 和步骤 s^\primes′,使得:

(a)5 \leqslant s^\prime \leqslant s, s^\prime-2 \equiv 0 \ mod \ 35?s′?s,s′?2≡0 mod 3,即 s^\primes′ 是Coin-Fixed-To-0步骤,

(b)ii 收到至少 t_HtH 个有效消息 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)ii 收到了一个有效消息 (SIG_j(Q^{r-1}), \sigma_j^{r,1})(SIGj(Qr?1),σjr,1),

ii 停止等待,并结束步骤s(实际上是结束了第 rr 轮),将 H(B^r)H(Br) 设为 vv 的第一部分,将子步骤(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^rCERTr。

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

(a’)6 \leqslant s^\prime \leqslant s, s^\prime-2 \equiv 1 \ mod \ 36?s′?s,s′?2≡1 mod 3,即 s^\primes′ 是Coin-Fixed-To-1步骤

(b’)ii 收到至少 t_HtH 个有效消息 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),

ii 停止等待,并结束步骤s(实际上是结束了第 rr 轮),设置 B^r = B_\epsilon^rBr=B?r,将子步骤(b’)中消息 m_j^{r,s^\prime-1}mjr,s′?1 的集合设置为它自己的 CERT^rCERTr。

若节点收到至少 t_HtH 个有效的 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 1bi?1。

若节点收到至少 t_HtH 个有效的 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),(节点并没有对同一个 vv 达成共识),则停止等待,并设置 b_i \triangleq 0bi?0。

否则,当时间 2\lambda2λ 已过,设置 b_i \triangleq 0bi?0。

b_ibi 被设置,节点从 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。否则,ii 停止,不广播任何消息。

Step s, 6 \leq s \leq m+2, s-2 \equiv\ 1\ mod\ 36≤s≤m+2,s?2≡ 1 mod 3:BBA^*BBA? 的 Coin-Fixed-To-1

节点 i \in PK^{r-k}i∈PKr?k 只要结束了Step s-1s?1,就开始了它的Step ss。

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

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

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

若节点收到至少 t_HtH 个有效的 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),(节点并没有对同一个 vv 达成共识),则停止等待,并设置 b_i \triangleq 0bi?0。

否则,当时间 2\lambda2λ 已过,设置 b_i \triangleq 1bi?1。

b_ibi 被设置,节点从 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。否则,ii 停止,不广播任何消息。

Step s, 7 \leq s \leq m+2, s-2 \equiv\ 2\ mod\ 37≤s≤m+2,s?2≡ 2 mod 3:BBA^*BBA? 的 Coin-Genuinely-Flipped

节点 i \in PK^{r-k}i∈PKr?k 只要结束了Step s-1s?1,就开始了它的Step ss。

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

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

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

若节点收到至少 t_HtH 个有效的 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),(节点并没有对同一个 vv 达成共识),则停止等待,并设置 b_i \triangleq 0bi?0。

若节点收到至少 t_HtH 个有效的 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 1bi?1。

否则,当时间 2\lambda2λ 已过,设置 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_ibi 被设置,节点从 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。否则,ii 停止,不广播任何消息。

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

节点 ii 只要知道了 CERT^{r-1}CERTr?1,就开启了它的第 rr 轮。

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

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

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

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

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

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

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

  • 正序
  • 最新
只看帖主楼层直达
登录 账号发表你的看法,还没有账号?立即免费 注册