可验证随机函数VRF
?
VRF 這個東東,在不少區(qū)塊鏈項目中都會聽到,比較火的 Algorand 和 Dfinity 的共識機制都用到了它。它的全稱叫 Verifiable Random Function(隨機可驗證函數(shù)),那它跟一般的隨機函數(shù)有什么不同?有什么用,為什么區(qū)塊鏈需要用到 VRF?這次被我騷擾的是資深全棧工程師黃祺,他曾在 BFTF 區(qū)塊鏈知享會中介紹區(qū)塊鏈中 VRF 的應用。
在區(qū)塊鏈中,大部分的共識算法,無論是 POW、POS,或是由他們衍生出來的 DPOS,都需要選出一堆或者一個節(jié)點來參與共識或者打包區(qū)塊,這個過程雖然會有持幣情況、設備配置、信譽等各種因素影響,但必須是隨機的、無法被預測的。這時候就可能會用到隨機算法。
在 BFTF 的分享沙龍上,黃祺解釋,可驗證隨機函數(shù)可以看作是一個隨機預言機(Random Oracle,RO),就是可以通過任意的一個輸入,獲得一個隨機數(shù)輸出。可驗證隨機函數(shù)比隨機預言機多了一個非交互的零知識證明,可以用來該隨機數(shù)輸出的正確性,表明這個隨機數(shù)的確是某個人生成的。
先說 RO,有兩個特征:
?1、對于不同的 Input,Output 的值是隨機的,并且均勻分布在值域范圍內。
?2、對于相同的 Input,它得到的 Output 一定是相同的。
舉例說明一下,假設某公鏈網(wǎng)絡用普通的 RO 選節(jié)點,有可能是這樣的情況:假設全網(wǎng)有 100 個節(jié)點,我想生成下一輪一個節(jié)點誰打包,我以某一輪的輪次作為輸入,然后隨機輸出的值必須要是在 1-100 之間的自然數(shù)(因為網(wǎng)絡中只有 100 個節(jié)點)。這就每一輪都選出了一個打包節(jié)點的人。
這里的問題是,由于輸入對應的輸出肯定是相同的,而輸入是公開的,就使得每一輪的抽簽結果變得可以被預知,攻擊者可以嘗試控制這個過程或者攻擊特定的節(jié)點。可是如果輸入不公開的話,我們要怎么保證這個輸入結果沒有問題呢?VRF 就用到了零知識證明,讓結果“可驗證”。
VRF 的方式是,讓各個節(jié)點自己抽簽,如果抽中了之后,大家可以很容易地驗證這個結果確實是你生成的。具體過程有可能是這樣的:假設現(xiàn)在是 round 10(第 10 輪),節(jié)點們可能會輪流抽簽,以節(jié)點自己的私鑰 + 一個全網(wǎng)都知道的隨機數(shù)(比如是這輪的輪次 10)作為輸入,生成了一個隨機數(shù)(0-100);設置一個條件:100 個節(jié)點輪流抽簽,誰先抽出來的隨機數(shù)大于 10,就是這一輪的打包者。假設 5 號節(jié)點抽到了 11,可是只有 5 號知道其他人不知道,因此他在廣播這個隨機的同時還需要廣播一個零知識證明。通過零知識證明,全網(wǎng)只需要通過 5 號的公鑰就可以驗證,接受 5 號為這輪打包者。
So,普通 RO 在私鑰 + 零知識證明的作用下,抽簽過程就可以在本地進行、不公開私鑰同時又可以全網(wǎng)驗證。
黃祺總結,可驗證隨機函數(shù)一共包含四個函數(shù):1、生成密鑰,生成一個公鑰私鑰對;2、生成隨機數(shù)輸出;3、計算零知識證明;4、驗證隨機數(shù)輸出。
看完上面的之后,我們大概可以明白,VRF 的目的就是要生成一個真正隨機而且無法被預測的值。在區(qū)塊鏈選出塊節(jié)點的過程中,為了保證安全,隨機是一個基本要求。不過,區(qū)塊鏈選節(jié)點不單純是隨機就 OK 的,還要考慮到攻擊成本等,所以共識機制往往加入算力和持幣權益等影響因素,以增加攻擊者的攻擊成本。如果單純使用隨機算法,就很容易受到女巫攻擊,攻擊者可以廉價找大量的傀儡機(肉雞)來增加自己抽中的概率。
這么一想,你會很容易明白為什么有那么多新型的共識算法都用到了 VRF,其實它們想達到的目的跟 POW 的答題過程有點像,都是為了找到隨機而又安全地抽取出塊節(jié)點。POW 被詬病的問題是功耗大和性能低,但是安全邊界明顯,而且比特幣運行已久都沒有大問題。POS 共識算法本身不需要大量算力,VRF 可又以在本地抽簽,所以 POS 共識算法用 VRF 的好處是功耗比較低,而且最新的算法,驗證零知識證明的速度已經(jīng)非常快。有不少知名的公鏈項目都用到了 VRF,包括本體、Cardano (共識算法為 Ouroboros,已經(jīng)迭代了 uroboros、Praos 和 Genesis 三個版本)、Dfinity 和 Algorand。
不同的項目用到 VRF 的不同點主要在于是怎么產(chǎn)生一開始的輸入,以及輸出要怎么用。以下是 VRF 在一些項目中的作用:?
根據(jù)本體官網(wǎng),VBFT 的每輪共識中:
-
根據(jù) VRF 從共識網(wǎng)絡中選擇備選提案節(jié)點,各個備選節(jié)點將獨立提出備選區(qū)塊;
-
根據(jù) VRF 從共識網(wǎng)絡中選擇多個驗證節(jié)點,每個驗證節(jié)點將從網(wǎng)絡中收集備選的區(qū)塊,進行驗證,然后對最高優(yōu)先級的備選區(qū)塊進行投票;
-
根據(jù) VRF 從共識網(wǎng)絡中選擇多個確認節(jié)點,對上述驗證節(jié)點的投票結果進行統(tǒng)計驗證,并確定出最終的共識結果。
-
所有節(jié)點都將接收確認節(jié)點的共識結果,并在一輪共識確認后開啟新的共識。
根據(jù)上交所技術公司的朱立解釋,Algorand 和 Dfinity 的共識算法中用 VRF 的套路大概是這樣的:輸入值由前一個隨機數(shù)(最初的隨機數(shù)卻是協(xié)議給定的)和某種代表高度、輪次的變量進行組合,然后用私鑰對之進行簽名(或者是先簽名再組合),最后哈希一下得出最新的隨機數(shù)。他認為:
“這樣產(chǎn)生的隨機數(shù)旁人很容易驗證其合乎算法,"V" 就這樣得到了;而哈希返回值又是隨機分布的,“R” 也因此得到保證。在此過程中,為降低操縱結果的可能性,有兩個注意事項:A) 簽名算法應當具有唯一性,也就是用同一把私鑰對同樣的信息進行簽名,只有一個合法簽名可以通過驗證——普通的非對稱加解密算法一般不具備這個屬性,如 SM2。如果用的簽名算法沒有這種 uniqueness 屬性,那在生成新隨機數(shù)的時候就存在通過反復多次嘗試簽名以挑出最有利者的余地,會降低安全性。B) 避免在生成新隨機數(shù)時將當前塊的數(shù)據(jù)作為隨機性來源之一,比如引用本塊交易列表的 merkle root 值等等,因為這樣做會給出塊人嘗試變更打包交易順序、嘗試打包不同交易以產(chǎn)生最有利的新隨機數(shù)的余地。在設計和檢視新的共識算法時,以上兩個注意事項是要特別留意的。
VRF 的返回結果可以用來公開完成節(jié)點或節(jié)點群體的選擇,也可以私密地完成選擇。以 Dfinity 為例,它是利用 mod 操作來唯一、公開地確定一個 Group。Algorand、Ouroboros Praos 是私密選擇的范例,大致套路是對 VRF 的最新返回值,配上輪次等變量后用私鑰進行簽名并哈希,如果哈希值小于某個閾值,節(jié)點就可以私密地知道自己被選中。這種方法很可能在網(wǎng)絡節(jié)點數(shù)較多時的表現(xiàn)會更穩(wěn)定,否則幸運兒個數(shù)上下波動會較大,進而影響協(xié)議表現(xiàn),包括空塊和分叉。”
根據(jù) CSDN 博主 Omni-Space 解釋,Cardano 的共識機制運作如下:
“首先是一些術語及作用的解釋:
-
在 Cardano 的運行中,時間被分為 slot。
-
每個 slot 只能產(chǎn)生一個塊,若這個塊有問題,或者應該產(chǎn)出這個塊的“礦工”(也就是 stakeholder 的候選人)不在線,或者產(chǎn)出的塊沒有廣播給大多數(shù)人,那么這個 slot 是當作廢棄的,也就是會跳過這個 slot 的塊。
圖片來自黃祺《區(qū)塊鏈中 VRF 的應用及原理解析》
-
多個 slot 為一個 epoch,權益的計算是以每個 epoch 開始前的歷史來計算,也就是說在這個 epoch 中所產(chǎn)生的權益變化不影響當前的這個 epoch 中的 slot 的出塊者的選擇和其他和歷史相關的東西。當前 epoch 中所產(chǎn)生的這些歷史只能在以后的 epoch 中生效。
-
每個 epoch 的開頭有個 genesis block(注意是每一個 epoch,不是整個鏈),這個 genesis block 不會上鏈 (整個鏈初始的那個 genesis 會,當然這一點可以根據(jù)實現(xiàn)自己決定),而是當前這個節(jié)點(礦工) 自己在內存中生成,這個 genesis block 會記錄好當前這個 epoch 中的可能參與出塊的 stakeholder 的候選人,及一個隨機種子ρ。
-
stakeholder 是權益持有者,也就是潛在礦工,在 Cardano 的實現(xiàn)中權益 stake 并不是直接指代有多少 Ada,而是和有多少 Ada 相關聯(lián)(更詳細的我不是很清楚),同時要成為一個 stakeholder 需要有 2% 的 Ada 才行。當然論文中不關注這些,直接定義了 stakeholder。而 stakeholder 并不一定要參與出塊,只有記錄在每個 epoch 的 genesis block 中的 stakeholder 才能參與當前 epoch 中 slot 的出塊,所以記錄在每個 epoch 中的 genesis block 中的 stakeholder 叫做 “stakeholder 候選人”
-
由這些 epoch 銜接而成的鏈就是由 Ouroboros 共識產(chǎn)生的鏈,這個鏈的基本屬性和 Bitcoin 相同(如每個塊包含上一個塊的 hash 等等)。
-
Slot Leader Selection 是指根據(jù)權益占比選擇按概率選擇出當前 slot 的出塊者。指代的是在當前的 epoch 中,按 genesis block 中記錄的 stakeholder 候選人的權益分別占用的比例為這個 epoch 中的每一個 slot 選擇出塊者的概率(注意這個概率是獨立事件,也就是有可能在同一個 epoch 中重復選出相同的人)。在論文中用函數(shù)
-
來表示按照權益占比為概率從stakeholder候選人選出該slot的出塊者U。注意在論文中只是定義了這個函數(shù)具有這樣的作用,在Cardano中使用了 “follow-the-satoshi(fts)” 算法(fts具有論文中定義的這個函數(shù)的性質)來選出這個slot leader也就是出塊者。
-
secure multiparty computation (MPC) MPC協(xié)議,參與者使用一種能達成MPC的密碼學協(xié)議來參與生成下一輪epoch的隨機種子ρ,這個MPC協(xié)議必須是保證guarantee output delivery(G.O.D,下文會解釋)。這個隨機種子ρ是用于Slot Leader Selection中的。
在已有這些基礎術語及作用的基礎上,現(xiàn)在來簡單介紹一下的工作流程:
如圖所示,執(zhí)行流程如下:(注:我并不保證這個流程是完全符合Cardano源碼的實現(xiàn)(畢竟我沒看過),但是是符合論文的描述的):
-
從鏈的真正創(chuàng)世塊開始,硬編碼進入了一些公鑰和這些公鑰vk對應的權益s及初始的種子ρ,之后,這個epoch會采用這些基礎信息繼續(xù)運行。
-
每個節(jié)點自己獨立運行代碼,根據(jù)當前epoch的種子ρ,執(zhí)行F(比如 follow-the-satoshi),把genesisblock中的權益,ρ和slot的index作為輸入,根據(jù)概率獲得當前這個slot應該由誰出塊。
-
若發(fā)現(xiàn)是自己出塊,則執(zhí)行打包交易等等操作,和bitcoin沒有太大區(qū)別,但是除了基礎工作之外,還會生成一個隨機數(shù),但是這個隨機數(shù)不放到鏈(塊)中,而是放一個承諾(后文解釋)。
-
若不是自己出塊,則等待出塊者出塊并廣播。收到這個塊的時候就進行和bitcoin類似的檢查,要是長時間未收到(超出這個slot的時間)則會認為這個slot的塊廢棄。
-
在當前epoch中不斷重復2的流程直到這個epoch中的所有slot結束。
-
在整個epoch的過程中會產(chǎn)出一個在這個epoch參與出塊者們(slot leaders)都共同認同的隨機種子ρ。
-
在自己的內存里記錄好這個ρ及下一個epoch參與的stakeholders,開啟下一個epoch周期,進入2的流程。
以上就是 Ouroboros 大致執(zhí)行的流程。”
VRF在區(qū)塊鏈領域的運用大致如上,不過在如上場景有沒有更好的解決方式,或者這個技術還能用在什么場景,還是值得討論的問題。
參考文章:
隨機選擇算法
區(qū)塊鏈中VRF的應用及原理解析
對可驗證隨機函數(shù)VRF的簡明解釋
簡評三個基于VRF的共識算法
可驗證隨機函數(shù)VRF之Algorand算法
圖靈獎得主Sivio Micali的Algorand區(qū)塊鏈協(xié)議簡介
Algorand 白皮書 1607.01341 版本
Cardano白皮書
Verifiable Random Functions
總結
以上是生活随笔為你收集整理的可验证随机函数VRF的全部內容,希望文章能夠幫你解決所遇到的問題。