Algorand 由圖靈獎(jiǎng)獲得者 Micali 提出的，其共識(shí)機(jī)制被稱為 BA*，是 PBFT 算法的改進(jìn)。BA* 算法分為三階段：區(qū)塊生成、GC 和 BBA*。算法的停止時(shí)間是不確定的，但大概率保證在有限步內(nèi)結(jié)束。

協(xié)議里有兩種角色：Leader 和 Verifier

• Leader：在區(qū)塊生成階段創(chuàng)建區(qū)塊；
• Verifier：在之后的每一個(gè)階段里，對區(qū)塊進(jìn)行共識(shí)。

下面對 BA* 協(xié)議的細(xì)節(jié)做一個(gè)具體介紹。

符號(hào)

• ：第 r 輪第 s步
• ：第 r 輪的 leader
• ：的 verifier 集合。如果 s=1，則為 potential leader 集合
• 和：的誠實(shí) Verifier 和惡意 Verifier 集合
• ：第 r 輪里節(jié)點(diǎn) i 生成的區(qū)塊
• ：空區(qū)塊。生成空區(qū)塊的那一輪是不存在leader的。
• ：節(jié)點(diǎn) i 在簽名消息所用的臨時(shí)密鑰。每個(gè)都有對應(yīng)的臨時(shí)密鑰。
• ： i 的簽名，用于證明
• ：節(jié)點(diǎn) i 在廣播的消息。根據(jù)不同，消息格式也不一樣
  • ：
  • ：
  • ：
• ：在第 r 輪時(shí)已加入系統(tǒng)的所有節(jié)點(diǎn)的公鑰集合

基本概念

種子

是第 r 輪的種子，用于選舉 Leader 和 Verifier。的計(jì)算方式如下：

• 如果是合法區(qū)塊，則
• 如果，即空區(qū)塊，則

Leader 選舉

對于，計(jì)算如果滿足，則 i 為 potential leader。

其中最小的節(jié)點(diǎn)為真正的 leader。

Verifier 選舉

Verifier 選舉的方式和 Leader 選舉的方式一樣：對于，計(jì)算如果滿足，則 i 為 Verifier

區(qū)塊結(jié)構(gòu)

區(qū)塊結(jié)構(gòu)不是協(xié)議重點(diǎn)，但還是提一下。

• 如果是合法區(qū)塊，則
• 如果，即空區(qū)塊，則

BA*共識(shí)

BA*由三個(gè)部分組成

生成區(qū)塊（s=1，即第一步）：所有節(jié)點(diǎn)檢查自己是不是potential leader，如果是，則生成區(qū)塊并廣播

GC協(xié)議（2≤s≤3）：有點(diǎn)像PBFT的后兩個(gè)階段，verifier 會(huì)生成1個(gè)二進(jìn)制值

BBA（s≥4）：BBA共識(shí)的修改版。每次 BBA都由3步組成，會(huì)不斷地循環(huán)。什么時(shí)候結(jié)束是不確定的，依概率結(jié)束。

BA*將 leader 所生成的區(qū)塊映射成二進(jìn)制值，分別表示區(qū)塊合法與否。

• 合法：共識(shí)結(jié)束后生成一個(gè)正常區(qū)塊
• 不合法：共識(shí)結(jié)束后生成空區(qū)塊（）

約定

假設(shè)

每一步中，都有，即誠實(shí)Verifier比例大于Verifier集合的2/3。（P31.Parameters第1點(diǎn)）

對于發(fā)的消息，最多經(jīng)過時(shí)間能被誠實(shí)節(jié)點(diǎn)收到。（P45第6行）

執(zhí)行前提

：節(jié)點(diǎn) i 根據(jù)「Leader選舉規(guī)則」檢查自己是不是 potential leader。如果不是，結(jié)束該 step，否則執(zhí)行相應(yīng)規(guī)則。

：節(jié)點(diǎn) i 根據(jù)「Verifier選舉規(guī)則」檢查自己是不是 vefier。如果不是，結(jié)束該 step，否則執(zhí)行相應(yīng)規(guī)則。

下文協(xié)議細(xì)節(jié)描述里，默認(rèn)有這些檢查。

簽名

和都表示用當(dāng)前的臨時(shí)密鑰來簽名消息。

Step 的開始和結(jié)束

開始時(shí)間：一個(gè)節(jié)點(diǎn)在達(dá)成共識(shí)后，會(huì)同時(shí)進(jìn)入每個(gè)Step（論文 P44.Lemma 5.5(a)）。但并不是所有節(jié)點(diǎn)同時(shí)開始。

• 設(shè)第一個(gè)誠實(shí)節(jié)點(diǎn)達(dá)成共識(shí)的時(shí)間是，則在時(shí)間內(nèi)，所有的誠實(shí)節(jié)點(diǎn)都會(huì)達(dá)成共識(shí)。
• 為什么是，見分析的 2.1.a 和 2.1.b（論文 p50-52）

結(jié)束時(shí)間：Step 結(jié)束的條件有兩種

• 達(dá)成 Ending Condition 條件
• 耗盡等待時(shí)間：第s步的等待時(shí)間為，表示的廣播時(shí)間上限，表示的廣播時(shí)間上限。【但為什么是?】
  • 時(shí)沒有等待時(shí)間，因?yàn)椴恍枰邮障ⅰ?/li>
  • 論文中默認(rèn)等待后，能收到所有誠實(shí)節(jié)點(diǎn)在小于的step里發(fā)送的消息。

Step 1 生成區(qū)塊

這一步生成區(qū)塊并廣播

生成區(qū)塊

生成。其中表示用進(jìn)行簽名的，簽名完后銷毀。

廣播和

備注

• 其他節(jié)點(diǎn)通過驗(yàn)證是否有，以檢查 i 是否有資格進(jìn)行該步。
• 敵手收到所有的后，就能知道誰是leader，并立即控制它廣播新的，阻止它原來的廣播出去。這樣敵手就可以控制每一輪的 leader。廣播后銷毀就是為了避免這種情況發(fā)生，因?yàn)榧词箶呈挚刂屏薼eader，也無法讓他發(fā)送新的。

GC

Step 2：GC第一步

從收到的多個(gè)里找到，即最小的節(jié)點(diǎn)。

檢查發(fā)來的區(qū)塊的合法性：若合法，令；若不合法，令。

廣播

備注

• 是協(xié)議要共識(shí)的值，在協(xié)議中不會(huì)用到。
• 整個(gè)協(xié)議里只有這一步檢查 Leader 和區(qū)塊的合法性

Step 3：GC第二步

在收到的中，如果有超過 2/3 的（他們的全部相同），則令；否則，則令

廣播

Step 4：GC輸出

收到的中，有 3 種可能出現(xiàn)的情況

如果有超過的，則令

如果有超過的，且，則令。這里可以保證只有唯一的超過1/3的值。

否則令

廣播

備注：表示區(qū)塊合法，表示區(qū)塊不合法

【思考】：在誠實(shí)節(jié)點(diǎn)中，似乎不會(huì)出現(xiàn)部分，部分的場景，而是會(huì)全部共識(shí)到合法區(qū)塊或空區(qū)塊。惡意的和Verifier不能對下一步的誠實(shí)節(jié)點(diǎn)進(jìn)行單播，因?yàn)樗麄儾恢老乱徊降恼\實(shí)節(jié)點(diǎn)是誰。

BBA*

在BBA*中，會(huì)不斷對收到的歷史進(jìn)行檢查，查看是否觸發(fā)Ending Condition

以下兩個(gè)結(jié)束條件是互斥的

【Ending Condition 0】

• 條件：收到超過的，且有；同時(shí)在中對應(yīng)的區(qū)塊是合法的（注意是區(qū)塊的哈希）
• 滿足條件則達(dá)成共識(shí)，將相應(yīng)的集合作為，停止該輪。

【Ending Condition 1】

• 條件：收到超過的，且有
• 滿足條件則達(dá)成共識(shí)， 將相應(yīng)的集合作為，停止該輪。

Step 5：Coin-Fixed-To-0

當(dāng)時(shí)進(jìn)行這一步時(shí)，如果觸發(fā)Ending Condition 0 或 1，則停止。否則等待后

• 在收到的中，有超過2/3比例的，則令，否則另
• 廣播
• 【為什么要令和0】

Step 6：Coin-Fixed-To-1

和 Coin-Fixed-To-0 類似，當(dāng)時(shí)進(jìn)行這一步時(shí)，如果觸發(fā) Ending Condition 0 或 1，則停止。否則等待后

• 在收到的中，有超過2/3的，則令，否則令
• 廣播

Step 7：Coin-Genuinely-Flipped

當(dāng)時(shí)進(jìn)行這一步，如果觸發(fā) Ending Condition 0 或 1，則停止。否則等待后

• 可能出現(xiàn)三種互斥的情況：
  • 在收到的中，有超過2/3的，則令
  • 在收到的中，有超過2/3的，則令
  • 否則令
• 廣播

Step m+3：最后一步

這一步比較特殊，不用檢查自己是不是Verifier，所有節(jié)點(diǎn)都要參與。

如果觸發(fā)Ending Condition 0 或 1，則停止。否則等待后

• 令和
• 廣播

達(dá)成共識(shí)，收集集合作為。

總結(jié)

【達(dá)成共識(shí)的情況】：有三種，分別是 Ending Condition 0、Ending Condition 1 和 Step m+3。

【Ending Condition】

若因?yàn)槭盏匠^ 2n/3 的而觸發(fā) Ending Condition，則在的 step 里，肯定是因?yàn)楹谋M等待時(shí)間而結(jié)束step。

觸發(fā) Ending Condition 0，則一定是 Coin-Fixed-To-0；如果觸發(fā) Ending Condition 1，則一定是 Coin-Fixed-To-1。

Ending Condition 要求收到的個(gè)數(shù)要超過確定值，而其他的都只要求收到的中有2/3滿足條件即可。

拜占庭共識(shí)要保證參與共識(shí)的誠實(shí)節(jié)點(diǎn)大于2/3，但隨機(jī)選出的集合不能保證該條件。于是

進(jìn)行多次的隨機(jī)選取（循環(huán)），只要有一次參與共識(shí)的誠實(shí)節(jié)點(diǎn)大于 2/3，就能達(dá)成共識(shí)。

如果不進(jìn)行多次隨機(jī)選取（循環(huán)），則惡意節(jié)點(diǎn)每次把合法區(qū)塊變成空區(qū)塊的概率就會(huì)大大增加。

臨時(shí)密鑰

在每一個(gè)里，節(jié)點(diǎn) i 所用的使用臨時(shí)密鑰簽名消息。一旦消息廣播出去，立即銷毀簽名所用的私鑰。

這么做的理由：節(jié)點(diǎn) i 發(fā)送消息的瞬間，敵手可以立即知道，就可以collud它，用它的重新簽名消息并廣播。比如敵手可以這么攻擊

• 時(shí)：則每一輪敵手都可以控制 leader
• 時(shí)，敵手可以有策略地控制verifier，使得每一輪都共識(shí)成空區(qū)塊

節(jié)點(diǎn) i 每次會(huì)生成100萬輪*180步的臨時(shí)密鑰（在加入系統(tǒng)或臨時(shí)密鑰用完時(shí)生成）。下面簡單介紹兩種生成方案（論文 p32）

第一種方案

i 生成 PMK 和 SMK

廣播 PMK

通過 SMK 和計(jì)算出100萬輪*180步的。計(jì)算完后銷毀 SMK

任何人可以通過 PMK 和計(jì)算出（這一步論文里沒有寫，是我猜的）

第二種方案

• i 生成100萬輪*180步的公私鑰對
• 利用全部的私鑰生成 Merkle Tree，廣播 Root。
• i 廣播時(shí)，附帶公鑰和 Merkle Tree的驗(yàn)證路徑

https://zhuanlan.zhihu.com/p/32282367

總結(jié)

以上是生活随笔為你收集整理的Algorand 共识算法 BA* 入门的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。