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

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

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

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

Verifiable Random Function（VRF）

Verifiable Random Function，中文是可驗(yàn)證隨機(jī)函數(shù)。簡(jiǎn)單的說，VRF能夠由私鑰（SK）以及信息（X）產(chǎn)生一組可驗(yàn)證的偽隨機(jī)（pseudorandom）隨機(jī)數(shù)Y以及證明Ρ。任何人都可以通過Verify（）函數(shù)來檢驗(yàn)這個(gè)隨機(jī)字串是否真的是該公鑰對(duì)應(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.驗(yàn)證隨機(jī)數(shù)：輸入公鑰VK，信息X，隨機(jī)數(shù)Y，以及the proof?。若該隨機(jī)數(shù)確實(shí)是由該公鑰對(duì)應(yīng)之私鑰使用Evaluate函示所產(chǎn)生，則回傳1（true）

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

Cryptographic Sortition

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

Algorand為了解決這種潛在的風(fēng)險(xiǎn)，利用VRF來掩蓋Leader Selection的步驟?？梢韵胂癯桑阂话愕腂FT在每一輪開始時(shí)公平公開選出Leader以及Committee，Algorand則是像在每一輪開始時(shí)公布中獎(jiǎng)號(hào)碼，每個(gè)使用者都可以自己拿自己的票根對(duì)獎(jiǎng)，中獎(jiǎng)的人即可成為下一輪的Leader（或是Committee Verifier），但在中獎(jiǎng)?wù)咦约罕砻魃矸萸?，沒有人知道誰(shuí)中獎(jiǎng)，也就是沒有人能預(yù)測(cè)下一輪的Leader以及Committee。當(dāng)然中獎(jiǎng)與否并不是口說無(wú)憑，中獎(jiǎng)?wù)咝枰鍪局歇?jiǎng)證明，而這個(gè)證明是大家都可以驗(yàn)證的，這正是我們剛剛說到的VRF。

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

Participant Replacement

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

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

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

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

小結(jié)

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