基于Algorand結(jié)合VRF的共識機(jī)制介紹

相信大家對于PoS權(quán)益證明的概念都不陌生，但是究竟一個PoS的Protocol是如運(yùn)作的？如何公平的選出下個區(qū)塊的生產(chǎn)者？如何保證區(qū)塊生產(chǎn)者不能bias下次自己再次當(dāng)選的機(jī)率？這些實行的細(xì)節(jié)都是需要經(jīng)過更多特別設(shè)計的。今天就來簡單介紹一下Algorand這個相對新的共識算法。

提出Algorand算法的是一位圖靈獎的得主Silvio Micali，若是以一個投資者的角度來看，這個項目背后的學(xué)術(shù)實力是絕對不容質(zhì)疑的。Silvio稱Algorand為Pure Proof of Stake。因為在他的設(shè)計中，貨幣的持有者不需要把某數(shù)量的貨幣抵押出去（會有一段時間不能使用），或是代理（delegate）給其他人來參與PoS共識機(jī)制，而是只要自己錢包里面擁有balance就可以一同參與這個共識機(jī)制。這確實比較符合去中心化的理念，畢竟降低了參與共識的門坎。

個人認(rèn)為Algorand真正創(chuàng)新的突破在于結(jié)合VRF（Verifiable Random Function）的Leader以及Committee抽簽（cryptographic sorTITIon）、防止重要節(jié)點(diǎn)遭到惡意使用者攻擊的ParTIcipant Replacement機(jī)制，以下就針對VRF做一些基本介紹，至于Algorand改良的拜占庭算法BA*。

Verifiable Random FuncTIon（VRF）

Verifiable Random Function，中文是可驗證隨機(jī)函數(shù)。簡單的說，VRF能夠由私鑰（SK）以及信息（X）產(chǎn)生一組可驗證的偽隨機(jī)（pseudorandom）隨機(jī)數(shù)Y以及證明Ρ。任何人都可以通過Verify（）函數(shù)來檢驗這個隨機(jī)字串是否真的是該公鑰對應(yīng)私鑰持有者，依照規(guī)定使用Evaluate（）函數(shù)所產(chǎn)生，而不是自己亂掰的：

· Evaluate（SK，X）→（Y，?）。產(chǎn)生隨機(jī)數(shù)：輸入私鑰SK，信息X，輸出pseudorandom output string Y以及proof?。

· Verify（VK，X，Y，?）→0/1.驗證隨機(jī)數(shù)：輸入公鑰VK，信息X，隨機(jī)數(shù)Y，以及the proof?。若該隨機(jī)數(shù)確實是由該公鑰對應(yīng)之私鑰使用Evaluate函示所產(chǎn)生，則回傳1（true）

為什么我們需要這個VRF呢？一起看下去吧

Cryptographic Sortition

無論是在何種BFT的共識機(jī)制中，都是由Leader以及Committee來完成區(qū)塊的發(fā)布以及共識決議。例如EOS的dPoS BFT是固定21個BP輪流擔(dān)任Leader以及投票者、Zilliqa通過PoW加入Committee進(jìn)行PBFT共識算法。這些比較直觀的拜占庭共識算法都有一個共同特征，就是大家都可以看到下一個區(qū)塊的Leader是誰，以及負(fù)責(zé)協(xié)議共識的Committee是誰。這造成了一個可能的風(fēng)險，就是這些區(qū)塊生產(chǎn)者以及Committee成員容易成為有心人是攻擊的目標(biāo)，無論是DDOS也好，賄賂也好，都讓攻擊者有清楚的目標(biāo)。這也使的要成為一個Leader或是Committee member的安全門坎更高。

Algorand為了解決這種潛在的風(fēng)險，利用VRF來掩蓋Leader Selection的步驟。可以想像成：一般的BFT在每一輪開始時公平公開選出Leader以及Committee，Algorand則是像在每一輪開始時公布中獎號碼，每個使用者都可以自己拿自己的票根對獎，中獎的人即可成為下一輪的Leader（或是Committee Verifier），但在中獎?wù)咦约罕砻魃矸萸?，沒有人知道誰中獎，也就是沒有人能預(yù)測下一輪的Leader以及Committee。當(dāng)然中獎與否并不是口說無憑，中獎?wù)咝枰鍪局歇勛C明，而這個證明是大家都可以驗證的，這正是我們剛剛說到的VRF。

在每一輪每一個步驟（step）開始前，每一個使用者都可以通過Sortition（）函示，由自己的私鑰配合VRF來檢驗自己有沒有資格成為Leader或是委員會的成員（看VRF的evaluate（）函示output是否符合某些規(guī)定，機(jī)率與持有貨幣成正比）。若發(fā)現(xiàn)自己是Leader，該使用者就會準(zhǔn)備好要發(fā)布的區(qū)塊，附上自己確實中獎的Proof一起廣播出去。同理，在接下來每一個需要Committee決議投票的步驟中，每一個使用者都先檢驗自己是否成功被抽中進(jìn)入委員會，是的話就把自己的投票（或是其他要協(xié)議的值）隨著Proof一起廣播出去。

Participant Replacement

上述的設(shè)計對安全性有很大的幫助，由于沒有人能預(yù)測參與下一輪共識的成員，所以惡意節(jié)點(diǎn)無法事前鎖定要攻擊的對象。當(dāng)一個惡意節(jié)點(diǎn)知道某人是這一輪的Leader時，代表這個信息已經(jīng)散布到網(wǎng)絡(luò)之中，該Leader想要廣播的區(qū)塊已經(jīng)讓網(wǎng)絡(luò)上的其他節(jié)點(diǎn)知道，因此已經(jīng)算是「功臣身退」了，現(xiàn)在才要攻擊它一切都太晚了。同理，在后面所有的共識過程中，在每一個成員廣播出自己決議的同時，投出那一票的瞬間，他們就已經(jīng)達(dá)成了自己此步驟身為委員會成員的義務(wù)，再下一個步驟中的又會有新的委員會出現(xiàn)，生生不息的繼續(xù)完成每一輪的共識。

這就是所謂的Participant Replacement，每一個共識步驟的決議成員都不同且彼此獨(dú)立，使得惡意使用者無法有效率的攻擊這個網(wǎng)絡(luò)。

細(xì)心的你可能會注意到，這種自己在家對獎的模式讓很多人同時成為Leader呢？答案是會的，可能會有多個節(jié)點(diǎn)都符合條件成為Leader，但最后大家可以規(guī)定簡單的經(jīng)過hash來排序，決定出Prioroty最高的那個leader，并只幫忙廣播它的區(qū)塊。

總結(jié)一下，Algorand在每一個區(qū)塊leader的產(chǎn)生到共識的每一個決議步驟，都不是事先選擇好，而是當(dāng)下發(fā)現(xiàn)自己有權(quán)利參與的節(jié)點(diǎn)，在參與共識的同時附上Proof來廣播。這不同于一些BFT模型是節(jié)點(diǎn)廣播區(qū)塊之后等待某些已知使用者回復(fù)簽章，而是Locally收集網(wǎng)絡(luò)上的各種簽章投票，在幫助gossiping的同時自己運(yùn)行自己的共識算法。

小結(jié)

Algorand算法的出現(xiàn)造成了一陣不小的轟動（單然還有BA*也是重點(diǎn)），透過VRF來進(jìn)行去中心化世界中隨機(jī)數(shù)生產(chǎn)的概念也被越來越區(qū)塊鏈應(yīng)用。這里僅僅簡單介紹了一下VRF以及他在共識協(xié)議中可以帶來的改變。