密碼抽簽
密碼抽簽算法用來決定誰來驗證下一個block。
密碼抽簽按兩條線索執(zhí)行：
- 選出“驗證者”和“領導者”；
- 是創(chuàng)建并不斷完善“種子”參數(shù)。
1. 選出“驗證者”和“領導者”
- 系統(tǒng)創(chuàng)建并不斷更新一個獨立參數(shù)，稱為“種子”,記為Q ^{r-1} 。第r輪的種子的參數(shù)是256位長度的字符串，入?yún)⑹堑趓-k輪結束后活躍用戶的公鑰集合，記為PK^{r-k}。k被稱為回溯參數(shù)或安全參數(shù)，比如=1，表示上一輪結束后的用戶集合。上面2個參數(shù)屬于公共知識。
- 基于當前 “種子”構建并公布一個隨機算法，稱為“可驗證的隨機函數(shù)(verifiable random functions)"。該隨機算法中的一個關鍵參數(shù)是用戶的私鑰，這個私鑰只有用戶本人才知道。
- 每個用戶使用自己的私鑰對“種子”進行簽名，用函數(shù)SIGi來表示，用它作為參數(shù)，運行系統(tǒng)公布的隨機算法，用函數(shù)H()來表示，得到自己的憑證（credential）= H(SIGi(r,1,Q^{r-1}))(函數(shù)SIGi有多個輸入?yún)?shù)時，表示將這些參數(shù)簡單串聯(lián)后再進行電子簽名)。
3.1. 憑證是一個近乎隨機的、由0和1組成的長度為256的字符串，并且不同用戶的憑證幾乎不可能相同；
3.2. 由憑證構建的2進制小數(shù)0.H(SIGi(r,1,Q^{r-1}))（也就是將憑證字符串寫到小數(shù)點后）在0和1之間均勻分布。 - 憑證值滿足一定條件的用戶就是這一輪的“驗證者”（verifiers）。
4.1. 條件是：對0和1之間的一個數(shù)，0.H(SIGi(r,1,Q^{r-1}))≤p發(fā)生的概率為p，稱所有滿足此條件的用戶為“驗證者”。
4.2. 有1-10^{-18}的概率保證在所有“驗證者”中，至少有一個是誠實的。 - “驗證者”組裝一個新區(qū)塊并連同自己的憑證一起對外發(fā)出。第r輪第s步（s>1）的“驗證者”的產(chǎn)生程序與上文類似。其中，在第一個子步驟中憑證值最小（按字典方面排序）的那個“驗證者”的地位比較特殊，稱為“領導者”。
- 所有“驗證者”基于“領導者”組裝的新區(qū)塊運行拜占庭協(xié)議BA。
- 在BA的每次循環(huán)中的每一個子步驟中，被選中的“驗證者”都是不同的。這樣能有效防止驗證權力集中在某些用戶手中，避免“敵對者”通過腐化這些用戶來攻擊區(qū)塊鏈。
上述過程的特點是：
- “驗證者”在秘密情況下獲知自己被選中，但他們只有公布憑證才能證明自己的“驗證者”資格。盡管“敵對者”可以瞬間腐化身份公開的“驗證者”，但已不能篡改或撤回誠實驗證著已經(jīng)對外發(fā)出的消息。
- 所有“驗證者”公布自己的憑證并進行比較后，才能確定誰是“領導者”，也就是“領導者”可以視為由公共選舉產(chǎn)生。
- 隨機算法的性質(zhì)決定了事先很難判斷誰將被選為“驗證者”。因此，“驗證者”的選擇過程很難被操縱或預測。
- 盡管“敵對者”有可能事先安插一些交易來影響當前公共賬本，但因為“種子”參數(shù)的存在，他仍然不可能通過影響“驗證者”（特別是其中的“領導者”）的選擇來攻擊Algorand。
2. 種子的更新
用Br表示第輪結束后，拜占庭協(xié)議BA★輸出的區(qū)塊。
“種子”的更新過程是：
Q^r =H(SIGlr(Q^{r-1}，r)), 如果B^r不是空區(qū)塊
Q^r =H(Q^{r-1}，r）, 如果B^r是空區(qū)塊
如果Algorand在第r輪受到了“敵對者”攻擊，B^r可能是空的.
3. Algorand的拜占庭協(xié)議BA★
拜占庭協(xié)議BA★相當于一個兩階段的投票機制。
- 第一階段，“驗證者”對其收到的候選區(qū)塊（為控制通訊成本，實際上用的是候選區(qū)塊的哈希摘要）運行分級共識協(xié)議（graded consensus）, 選出“驗證者”共識最多的候選區(qū)塊。
- 第二階段，“驗證者”對第一階段選出的候選區(qū)塊，運行二元拜占庭協(xié)議（binary Byzantine Agreement），即要么接受它，要么接受空區(qū)塊。需要強調(diào)的，在每一階段中的每一個子步驟，Algorand可能使用完全不同的“驗證者”。
以下為敘述方便，假設：
- 系統(tǒng)處在第r輪；
- 每一個子步驟都選出n名“驗證者”，其中惡意“驗證者”不超過t，并且n≥3t+1（也就是誠實“驗證者”占比在2/3以上）。另外，引入計數(shù)函數(shù)
#si(v)表示在第s步“驗證者”i 收到的消息v的次數(shù)（來自同一發(fā)送人的只能算1次）。
3.1 第一階段：分級共識協(xié)議
- 運行密碼抽簽程序，選出“領導者”lr和這一步的“驗證者”。用vi表示“驗證者”i收到的并且他認識是來自“領導者”lr的候選區(qū)塊。
vir不一定等于“領導者”lr構建的候選區(qū)塊：
- “驗證者”i辨認“領導者”的方法是從他收到的所有“驗證者”憑證中找出按字典排序最小者。但因為網(wǎng)絡通訊原因，“領導者”lr發(fā)出的信息可能沒有到達“驗證者”i處。
- “領導者”lr正好被“敵對者”腐化，對不同“驗證者”發(fā)出不同的候選區(qū)塊。
- “驗證者”i本身可能是惡意的。
- “驗證者”i將收到的vi廣播給其他用戶。廣播正確的vi代表他告訴其他驗證者他同意該vi。
- 當且僅當“驗證者”i在步驟2中收到消息x的次數(shù)超過了2t+1次（即
#2i(x)≥2t+1），他將消息x發(fā)給其他用戶?！膀炞C者”i按以下規(guī)則輸出(vi,gi)：
如果存在x使得#3i(x)≥2t+1，則vi=x,gi=2；//2輪都投票成功 如果x存在使得#3i(x)≥t+1，則vi=x,gi=1；//只有1輪投票成功 否則vi=?，gi=1，其中?代表空區(qū)塊。
含義是：
- 如果存在誠實“驗證者”i，使得,gi=2，那么對任意其他“驗證者”j，必有gj≥1,vj=vi。此時所有誠實“驗證者”輸出的候選區(qū)塊是一樣的。當然，如果一開始的“驗證者”收到的候選區(qū)塊都是v，那么最后一批“驗證者”輸出的也將都是v。
- 對所有的誠實“驗證者”i，gi≤1，并且他們輸出的候選區(qū)塊不一定相同。
第二階段：二元拜占庭協(xié)議
基于分級共識協(xié)議的輸出{(vi,gi):i=1,2,K……n}對每個誠實“驗證者”賦值：
- 如果gi=2，那么bi=0；
- 其他情況，bi=1。
這些bi就是二元拜占庭協(xié)議的輸入。
- 第一步“驗證者”i發(fā)出bi。如果#1i(0)≥2t+1，那么“驗證者”i設定bi=0，輸出outi=0，并停止執(zhí)行協(xié)議（也可以認為他以后將一直發(fā)出bi=0）；如果#1i(1)≥2t+1，那么“驗證者”i設定bi=1；否則，“驗證者”i設定bi=0。
- 第二步“驗證者”i發(fā)出bi。如果#2i(1)≥2t+1，那么“驗證者”i設定bi=1，輸出outi=1，并停止執(zhí)行協(xié)議（也可以認為他以后將一直發(fā)出bi=1）；如果#2i(0)≥2t+1，那么“驗證者”i設定bi=0；否則，“驗證者”i設定bi=1。
- 第三步“驗證者”i發(fā)出bi和SIGi(Qr-1,rj)。如果#3i(0)≥2t+1，那么“驗證者”i設定bi=0；如果#3i(1)≥2t+1，那么“驗證者”i設定bi=1；否則，用Si表示所有給“驗證者”i發(fā)送消息的其他“驗證者”集合。
結論
- 每次隨機選出n名驗證者，由于是根據(jù)概率來決定誰是驗證者，n的值只有在所有驗證者廣播他的憑證后，節(jié)點才能知道n的值是多少，并且≤真正的驗證者數(shù)量，因為存在網(wǎng)絡等問題。這樣的話，這些交互的過程是一個同步交互的過程，肯定影響出塊時間。
- 每一輪共識的交互次數(shù)太多了，每次交互意味著被動同步延時，對性能是個不小的影響。
- algorand的性能是比特幣的125倍，按照論文中給出的數(shù)據(jù)，每小時可以共識的交易還是750M字節(jié)每小時，計算一下(按照每筆交易長度100字節(jié)計算)：75010241024/60/60/100=2184.5 TPS，考慮到實際環(huán)境的運行，估計可以達到1000TPS左右。
參考文獻：
https://people.csail.mit.edu/nickolai/papers/gilad-algorand-eprint.pdf
https://www.leiphone.com/news/201802/D835Yu95sY7ihrAp.html
