密碼抽簽
密碼抽簽算法用來決定誰來驗證下一個block溉卓。
密碼抽簽按兩條線索執(zhí)行：
- 選出“驗證者”和“領(lǐng)導(dǎo)者”皮迟；
- 是創(chuàng)建并不斷完善“種子”參數(shù)。
1. 選出“驗證者”和“領(lǐng)導(dǎo)者”
- 系統(tǒng)創(chuàng)建并不斷更新一個獨立參數(shù)桑寨，稱為“種子”,記為Q ^{r-1} 伏尼。第r輪的種子的參數(shù)是256位長度的字符串，入?yún)⑹堑趓-k輪結(jié)束后活躍用戶的公鑰集合尉尾，記為PK^{r-k}爆阶。k被稱為回溯參數(shù)或安全參數(shù)，比如=1沙咏，表示上一輪結(jié)束后的用戶集合辨图。上面2個參數(shù)屬于公共知識。
- 基于當(dāng)前 “種子”構(gòu)建并公布一個隨機算法肢藐，稱為“可驗證的隨機函數(shù)(verifiable random functions)"故河。該隨機算法中的一個關(guān)鍵參數(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. 由憑證構(gòu)建的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)生程序與上文類似湿刽。其中的烁，在第一個子步驟中憑證值最小（按字典方面排序）的那個“驗證者”的地位比較特殊，稱為“領(lǐng)導(dǎo)者”诈闺。
- 所有“驗證者”基于“領(lǐng)導(dǎo)者”組裝的新區(qū)塊運行拜占庭協(xié)議BA渴庆。
- 在BA的每次循環(huán)中的每一個子步驟中，被選中的“驗證者”都是不同的雅镊。這樣能有效防止驗證權(quán)力集中在某些用戶手中襟雷，避免“敵對者”通過腐化這些用戶來攻擊區(qū)塊鏈。
上述過程的特點是：
- “驗證者”在秘密情況下獲知自己被選中仁烹，但他們只有公布憑證才能證明自己的“驗證者”資格耸弄。盡管“敵對者”可以瞬間腐化身份公開的“驗證者”，但已不能篡改或撤回誠實驗證著已經(jīng)對外發(fā)出的消息卓缰。
- 所有“驗證者”公布自己的憑證并進行比較后叙赚，才能確定誰是“領(lǐng)導(dǎo)者”，也就是“領(lǐng)導(dǎo)者”可以視為由公共選舉產(chǎn)生僚饭。
- 隨機算法的性質(zhì)決定了事先很難判斷誰將被選為“驗證者”。因此胧砰，“驗證者”的選擇過程很難被操縱或預(yù)測鳍鸵。
- 盡管“敵對者”有可能事先安插一些交易來影響當(dāng)前公共賬本，但因為“種子”參數(shù)的存在尉间，他仍然不可能通過影響“驗證者”（特別是其中的“領(lǐng)導(dǎo)者”）的選擇來攻擊Algorand偿乖。
2. 種子的更新
用Br表示第輪結(jié)束后，拜占庭協(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★相當(dāng)于一個兩階段的投票機制画切。
- 第一階段，“驗證者”對其收到的候選區(qū)塊（為控制通訊成本囱怕，實際上用的是候選區(qū)塊的哈希摘要）運行分級共識協(xié)議（graded consensus）, 選出“驗證者”共識最多的候選區(qū)塊。
- 第二階段，“驗證者”對第一階段選出的候選區(qū)塊熄捍，運行二元拜占庭協(xié)議（binary Byzantine Agreement）列敲，即要么接受它，要么接受空區(qū)塊台丛。需要強調(diào)的耍缴，在每一階段中的每一個子步驟，Algorand可能使用完全不同的“驗證者”。
以下為敘述方便防嗡，假設(shè)：
- 系統(tǒng)處在第r輪变汪；
- 每一個子步驟都選出n名“驗證者”，其中惡意“驗證者”不超過t本鸣，并且n≥3t+1（也就是誠實“驗證者”占比在2/3以上）疫衩。另外，引入計數(shù)函數(shù)
#si(v)表示在第s步“驗證者”i 收到的消息v的次數(shù)（來自同一發(fā)送人的只能算1次）荣德。
3.1 第一階段：分級共識協(xié)議
- 運行密碼抽簽程序闷煤，選出“領(lǐng)導(dǎo)者”lr和這一步的“驗證者”。用vi表示“驗證者”i收到的并且他認(rèn)識是來自“領(lǐng)導(dǎo)者”lr的候選區(qū)塊涮瞻。
vir不一定等于“領(lǐng)導(dǎo)者”lr構(gòu)建的候選區(qū)塊：
- “驗證者”i辨認(rèn)“領(lǐng)導(dǎo)者”的方法是從他收到的所有“驗證者”憑證中找出按字典排序最小者鲤拿。但因為網(wǎng)絡(luò)通訊原因，“領(lǐng)導(dǎo)者”lr發(fā)出的信息可能沒有到達“驗證者”i處署咽。
- “領(lǐng)導(dǎo)者”lr正好被“敵對者”腐化近顷，對不同“驗證者”發(fā)出不同的候選區(qū)塊。
- “驗證者”i本身可能是惡意的宁否。
- “驗證者”i將收到的vi廣播給其他用戶窒升。廣播正確的vi代表他告訴其他驗證者他同意該vi。
- 當(dāng)且僅當(dāng)“驗證者”i在步驟2中收到消息x的次數(shù)超過了2t+1次（即
#2i(x)≥2t+1）慕匠，他將消息x發(fā)給其他用戶饱须。“驗證者”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贼邓，必有g(shù)j≥1,vj=vi姨蟋。此時所有誠實“驗證者”輸出的候選區(qū)塊是一樣的。當(dāng)然立帖，如果一開始的“驗證者”收到的候選區(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設(shè)定bi=0骏庸，輸出outi=0毛甲，并停止執(zhí)行協(xié)議（也可以認(rèn)為他以后將一直發(fā)出bi=0）；如果#1i(1)≥2t+1具被，那么“驗證者”i設(shè)定bi=1玻募；否則，“驗證者”i設(shè)定bi=0一姿。
- 第二步“驗證者”i發(fā)出bi七咧。如果#2i(1)≥2t+1，那么“驗證者”i設(shè)定bi=1叮叹，輸出outi=1艾栋，并停止執(zhí)行協(xié)議（也可以認(rèn)為他以后將一直發(fā)出bi=1）；如果#2i(0)≥2t+1蛉顽，那么“驗證者”i設(shè)定bi=0蝗砾；否則，“驗證者”i設(shè)定bi=1蜂林。
- 第三步“驗證者”i發(fā)出bi和SIGi(Qr-1,rj)。如果#3i(0)≥2t+1拇泣，那么“驗證者”i設(shè)定bi=0噪叙；如果#3i(1)≥2t+1，那么“驗證者”i設(shè)定bi=1霉翔；否則睁蕾，用Si表示所有給“驗證者”i發(fā)送消息的其他“驗證者”集合。
結(jié)論
- 每次隨機選出n名驗證者债朵，由于是根據(jù)概率來決定誰是驗證者子眶，n的值只有在所有驗證者廣播他的憑證后，節(jié)點才能知道n的值是多少序芦，并且≤真正的驗證者數(shù)量臭杰，因為存在網(wǎng)絡(luò)等問題。這樣的話谚中，這些交互的過程是一個同步交互的過程渴杆，肯定影響出塊時間寥枝。
- 每一輪共識的交互次數(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
