可验证随机函数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的全部內容，希望文章能夠幫你解決所遇到的問題。
