Algorand 共识算法 BA* 入门
Algorand 由圖靈獎獲得者 Micali 提出的，其共識機制被稱為 BA*，是 PBFT 算法的改進。BA* 算法分為三階段：區(qū)塊生成、GC 和 BBA*。算法的停止時間是不確定的，但大概率保證在有限步內(nèi)結(jié)束。
協(xié)議里有兩種角色：Leader 和 Verifier
- Leader：在區(qū)塊生成階段創(chuàng)建區(qū)塊；
- Verifier：在之后的每一個階段里，對區(qū)塊進行共識。
下面對 BA* 協(xié)議的細節(jié)做一個具體介紹。
符號
- ：第 r 輪第 s步
- ：第 r 輪的 leader
- ：的 verifier 集合。如果 s=1，則為 potential leader 集合
- 和：的誠實 Verifier 和惡意 Verifier 集合
- ：第 r 輪里節(jié)點 i 生成的區(qū)塊
- ：空區(qū)塊。生成空區(qū)塊的那一輪是不存在leader的。
- ：節(jié)點 i 在簽名消息所用的臨時密鑰。每個都有對應(yīng)的臨時密鑰。
- ： i 的簽名，用于證明
- ：節(jié)點 i 在廣播的消息。根據(jù)不同，消息格式也不一樣
- ：
- ：
- ：
- ：在第 r 輪時已加入系統(tǒng)的所有節(jié)點的公鑰集合
基本概念
種子
是第 r 輪的種子，用于選舉 Leader 和 Verifier。的計算方式如下：
- 如果是合法區(qū)塊，則
- 如果，即空區(qū)塊，則
Leader 選舉
對于，計算如果滿足，則 i 為 potential leader。
其中最小的節(jié)點為真正的 leader。
Verifier 選舉
Verifier 選舉的方式和 Leader 選舉的方式一樣：對于，計算如果滿足，則 i 為 Verifier
區(qū)塊結(jié)構(gòu)
區(qū)塊結(jié)構(gòu)不是協(xié)議重點，但還是提一下。
- 如果是合法區(qū)塊，則
- 如果，即空區(qū)塊，則
BA*共識
BA*由三個部分組成
BA*將 leader 所生成的區(qū)塊映射成二進制值，分別表示區(qū)塊合法與否。
- 合法：共識結(jié)束后生成一個正常區(qū)塊
- 不合法：共識結(jié)束后生成空區(qū)塊（）
約定
假設(shè)
執(zhí)行前提
：節(jié)點 i 根據(jù)「Leader選舉規(guī)則」檢查自己是不是 potential leader。如果不是，結(jié)束該 step，否則執(zhí)行相應(yīng)規(guī)則。
：節(jié)點 i 根據(jù)「Verifier選舉規(guī)則」檢查自己是不是 vefier。如果不是，結(jié)束該 step，否則執(zhí)行相應(yīng)規(guī)則。
下文協(xié)議細節(jié)描述里，默認有這些檢查。
簽名
和都表示用當(dāng)前的臨時密鑰來簽名消息。
Step 的開始和結(jié)束
開始時間：一個節(jié)點在達成共識后，會同時進入每個Step（論文 P44.Lemma 5.5(a)）。但并不是所有節(jié)點同時開始。
- 設(shè)第一個誠實節(jié)點達成共識的時間是，則在時間內(nèi)，所有的誠實節(jié)點都會達成共識。
- 為什么是，見分析的 2.1.a 和 2.1.b（論文 p50-52）
結(jié)束時間：Step 結(jié)束的條件有兩種
- 達成 Ending Condition 條件
- 耗盡等待時間：第s步的等待時間為，表示的廣播時間上限，表示的廣播時間上限?！镜珵槭裁词?】
- 時沒有等待時間，因為不需要接收消息。
- 論文中默認等待后，能收到所有誠實節(jié)點在小于的step里發(fā)送的消息。
Step 1 生成區(qū)塊
這一步生成區(qū)塊并廣播
備注
- 其他節(jié)點通過驗證是否有，以檢查 i 是否有資格進行該步。
- 敵手收到所有的后，就能知道誰是leader，并立即控制它廣播新的，阻止它原來的廣播出去。這樣敵手就可以控制每一輪的 leader。廣播后銷毀就是為了避免這種情況發(fā)生，因為即使敵手控制了leader，也無法讓他發(fā)送新的。
GC
Step 2：GC第一步
備注
- 是協(xié)議要共識的值，在協(xié)議中不會用到。
- 整個協(xié)議里只有這一步檢查 Leader 和區(qū)塊的合法性
Step 3：GC第二步
Step 4：GC輸出
備注：表示區(qū)塊合法，表示區(qū)塊不合法
【思考】：在誠實節(jié)點中，似乎不會出現(xiàn)部分，部分的場景，而是會全部共識到合法區(qū)塊或空區(qū)塊。惡意的和Verifier不能對下一步的誠實節(jié)點進行單播，因為他們不知道下一步的誠實節(jié)點是誰。
BBA*
在BBA*中，會不斷對收到的歷史進行檢查，查看是否觸發(fā)Ending Condition
以下兩個結(jié)束條件是互斥的
【Ending Condition 0】
- 條件：收到超過的，且有；同時在中對應(yīng)的區(qū)塊是合法的（注意是區(qū)塊的哈希）
- 滿足條件則達成共識，將相應(yīng)的集合作為，停止該輪。
【Ending Condition 1】
- 條件：收到超過的，且有
- 滿足條件則達成共識， 將相應(yīng)的集合作為，停止該輪。
Step 5：Coin-Fixed-To-0
當(dāng)時進行這一步時，如果觸發(fā)Ending Condition 0 或 1，則停止。否則等待后
- 在收到的中，有超過2/3比例的，則令，否則另
- 廣播
- 【為什么要令和0】
Step 6：Coin-Fixed-To-1
和 Coin-Fixed-To-0 類似，當(dāng)時進行這一步時，如果觸發(fā) Ending Condition 0 或 1，則停止。否則等待后
- 在收到的中，有超過2/3的，則令，否則令
- 廣播
Step 7：Coin-Genuinely-Flipped
當(dāng)時進行這一步，如果觸發(fā) Ending Condition 0 或 1，則停止。否則等待后
- 可能出現(xiàn)三種互斥的情況：
- 在收到的中，有超過2/3的，則令
- 在收到的中，有超過2/3的，則令
- 否則令
- 廣播
Step m+3：最后一步
這一步比較特殊，不用檢查自己是不是Verifier，所有節(jié)點都要參與。
如果觸發(fā)Ending Condition 0 或 1，則停止。否則等待后
- 令和
- 廣播
達成共識，收集集合作為。
總結(jié)
【達成共識的情況】：有三種，分別是 Ending Condition 0、Ending Condition 1 和 Step m+3。
【Ending Condition】
拜占庭共識要保證參與共識的誠實節(jié)點大于2/3，但隨機選出的集合不能保證該條件。于是
臨時密鑰
在每一個里，節(jié)點 i 所用的使用臨時密鑰簽名消息。一旦消息廣播出去，立即銷毀簽名所用的私鑰。
這么做的理由：節(jié)點 i 發(fā)送消息的瞬間，敵手可以立即知道，就可以collud它，用它的重新簽名消息并廣播。比如敵手可以這么攻擊
- 時：則每一輪敵手都可以控制 leader
- 時，敵手可以有策略地控制verifier，使得每一輪都共識成空區(qū)塊
節(jié)點 i 每次會生成100萬輪*180步的臨時密鑰（在加入系統(tǒng)或臨時密鑰用完時生成）。下面簡單介紹兩種生成方案（論文 p32）
第一種方案
第二種方案
- i 生成100萬輪*180步的公私鑰對
- 利用全部的私鑰生成 Merkle Tree，廣播 Root。
- i 廣播時，附帶公鑰和 Merkle Tree的驗證路徑
總結(jié)
以上是生活随笔為你收集整理的Algorand 共识算法 BA* 入门的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 公有链的本质挑战
- 下一篇： HISTORY OF ETHEREUM