一文看懂可驗證隨機函數VRF | 小明學習筆記

編者按：本文來自36氪戰略合作區塊鏈媒體「Odaily星球日報」（公眾號ID：o-daily，APP下載）

編者按：區塊鏈涉及到的技術很多，從網際網路底層到不明覺厲的密碼學，可是往往關注幣價者多而研究技術的人少。牛市的時候，大家為了炒幣也會努力學習，熊市的時候，反正也沒啥事，我覺得可以更加努力學習。作為一個文科生，我當然會有很多理科生看起來覺得很白痴的問題。作為一個記者，我不難找到業內懂的人用人話給我解釋，而且他們往往不會當面嫌棄我。

這是小明學習筆記第四期，學習的是VRF。之前第一期學習的是虛擬機（《小明學習筆記 | 一文看懂區塊鏈跨鏈機制》），第二期是跨鏈（《小明學習筆記 | 一文看懂區塊鏈虛擬機》），第三期《小明學習筆記 | 一文看懂網際網路TCP/IP協議》，之後想學習有開源歷史和文化等。如果有其他有趣問題，歡迎投稿和提問。

話說這篇小明學習筆記真的拖了太久，本來在設想中就是特別短的一篇，但是由於雲棲大會、公鏈 101 等各種欄目和編輯部瑣事，實在是已經變成了 「小明更新筆記日，例會無忘告主編」 了。

VRF 這個東東，在不少區塊鏈項目中都會聽到，比較火的 Algorand 和 Dfinity 的共識機制都用到了它。它的全稱叫 Verifiable Random Function（隨機可驗證函數），那它跟一般的隨機函數有什麼不同？有什麼用，為什麼區塊鏈需要用到 VRF？這次被我騷擾的是資深全棧工程師黃祺，他曾在 BFTF 區塊鏈知享會中介紹區塊鏈中 VRF 的應用。

在區塊鏈中，大部分的共識算法，無論是 POW、POS，或是由他們衍生出來的 DPOS，都需要選出一堆或者一個節點來參與共識或者打包區塊，這個過程雖然會有持幣情況、設備配置、信譽等各種因素影響，但必須是隨機的、無法被預測的。這時候就可能會用到隨機算法。

在 BFTF 的分享沙龍上，黃祺解釋，可驗證隨機函數可以看作是一個隨機預言機（Random Oracle，RO），就是可以通過任意的一個輸入，獲得一個隨機數輸出。可驗證隨機函數比隨機預言機多了一個非交互的零知識證明，可以用來該隨機數輸出的正確性，表明這個隨機數的確是某個人生成的。

先說 RO，有兩個特徵：

 1、對於不同的 Input，Output 的值是隨機的，並且均勻分布在值域範圍內。

 2、對於相同的 Input，它得到的 Output 一定是相同的。

舉例說明一下，假設某公鏈網絡用普通的 RO 選節點，有可能是這樣的情況：假設全網有 100 個節點，我想生成下一輪一個節點誰打包，我以某一輪的輪次作為輸入，然後隨機輸出的值必須要是在 1-100 之間的自然數（因為網絡中只有 100 個節點）。這就每一輪都選出了一個打包節點的人。

這裡的問題是，由於輸入對應的輸出肯定是相同的，而輸入是公開的，就使得每一輪的抽籤結果變得可以被預知，攻擊者可以嘗試控制這個過程或者攻擊特定的節點。可是如果輸入不公開的話，我們要怎麼保證這個輸入結果沒有問題呢？VRF 就用到了零知識證明，讓結果「可驗證」。

VRF 的方式是，讓各個節點自己抽籤，如果抽中了之後，大家可以很容易地驗證這個結果確實是你生成的。具體過程有可能是這樣的：假設現在是 round 10（第 10 輪），節點們可能會輪流抽籤，以節點自己的私鑰 + 一個全網都知道的隨機數（比如是這輪的輪次 10）作為輸入，生成了一個隨機數（0-100）；設置一個條件：100 個節點輪流抽籤，誰先抽出來的隨機數大於 10，就是這一輪的打包者。假設 5 號節點抽到了 11，可是只有 5 號知道其他人不知道，因此他在廣播這個隨機的同時還需要廣播一個零知識證明。通過零知識證明，全網只需要通過 5 號的公鑰就可以驗證，接受 5 號為這輪打包者。

So，普通 RO 在私鑰 + 零知識證明的作用下，抽籤過程就可以在本地進行、不公開私鑰同時又可以全網驗證。

黃祺總結，可驗證隨機函數一共包含四個函數：1、生成密鑰，生成一個公鑰私鑰對；2、生成隨機數輸出；3、計算零知識證明；4、驗證隨機數輸出。

看完上面的之後，我們大概可以明白，VRF 的目的就是要生成一個真正隨機而且無法被預測的值。在區塊鏈選出塊節點的過程中，為了保證安全，隨機是一個基本要求。不過，區塊鏈選節點不單純是隨機就 OK 的，還要考慮到攻擊成本等，所以共識機制往往加入算力和持幣權益等影響因素，以增加攻擊者的攻擊成本。如果單純使用隨機算法，就很容易受到女巫攻擊，攻擊者可以廉價找大量的傀儡機（肉雞）來增加自己抽中的概率。

這麼一想，你會很容易明白為什麼有那麼多新型的共識算法都用到了 VRF，其實它們想達到的目的跟 POW 的答題過程有點像，都是為了找到隨機而又安全地抽取出塊節點。POW 被詬病的問題是功耗大和性能低，但是安全邊界明顯，而且比特幣運行已久都沒有大問題。POS 共識算法本身不需要大量算力，VRF 可又以在本地抽籤，所以 POS 共識算法用 VRF 的好處是功耗比較低，而且最新的算法，驗證零知識證明的速度已經非常快。有不少知名的公鏈項目都用到了 VRF，包括本體、Cardano （共識算法為 Ouroboros，已經迭代了 uroboros、Praos 和 Genesis 三個版本）、Dfinity 和 Algorand。

不同的項目用到 VRF 的不同點主要在於是怎麼產生一開始的輸入，以及輸出要怎麼用。以下是 VRF 在一些項目中的作用： 

根據本體官網，VBFT 的每輪共識中：

根據 VRF 從共識網絡中選擇備選提案節點，各個備選節點將獨立提出備選區塊；

根據 VRF 從共識網絡中選擇多個驗證節點，每個驗證節點將從網絡中收集備選的區塊，進行驗證，然後對最高優先級的備選區塊進行投票；

根據 VRF 從共識網絡中選擇多個確認節點，對上述驗證節點的投票結果進行統計驗證，並確定出最終的共識結果。

所有節點都將接收確認節點的共識結果，並在一輪共識確認後開啟新的共識。

根據上交所技術公司的朱立解釋，Algorand 和 Dfinity 的共識算法中用 VRF 的套路大概是這樣的：輸入值由前一個隨機數（最初的隨機數卻是協議給定的）和某種代表高度、輪次的變量進行組合，然後用私鑰對之進行籤名（或者是先籤名再組合），最後哈希一下得出最新的隨機數。他認為：

「這樣產生的隨機數旁人很容易驗證其合乎算法，"V" 就這樣得到了；而哈希返回值又是隨機分布的，「R」 也因此得到保證。在此過程中，為降低操縱結果的可能性，有兩個注意事項：A) 籤名算法應當具有唯一性，也就是用同一把私鑰對同樣的信息進行籤名，只有一個合法籤名可以通過驗證——普通的非對稱加解密算法一般不具備這個屬性，如 SM2。如果用的籤名算法沒有這種 uniqueness 屬性，那在生成新隨機數的時候就存在通過反覆多次嘗試籤名以挑出最有利者的餘地，會降低安全性。B) 避免在生成新隨機數時將當前塊的數據作為隨機性來源之一，比如引用本塊交易列表的 merkle root 值等等，因為這樣做會給出塊人嘗試變更打包交易順序、嘗試打包不同交易以產生最有利的新隨機數的餘地。在設計和檢視新的共識算法時，以上兩個注意事項是要特別留意的。

VRF 的返回結果可以用來公開完成節點或節點群體的選擇，也可以私密地完成選擇。以 Dfinity 為例，它是利用 mod 操作來唯一、公開地確定一個 Group。Algorand、Ouroboros Praos 是私密選擇的範例，大致套路是對 VRF 的最新返回值，配上輪次等變量後用私鑰進行籤名並哈希，如果哈希值小於某個閾值，節點就可以私密地知道自己被選中。這種方法很可能在網絡節點數較多時的表現會更穩定，否則幸運兒個數上下波動會較大，進而影響協議表現，包括空塊和分叉。」

根據 CSDN 博主 Omni-Space 解釋，Cardano 的共識機制運作如下：

「首先是一些術語及作用的解釋：

在 Cardano 的運行中，時間被分為 slot。

每個 slot 只能產生一個塊，若這個塊有問題，或者應該產出這個塊的「礦工」(也就是 stakeholder 的候選人)不在線，或者產出的塊沒有廣播給大多數人，那麼這個 slot 是當作廢棄的，也就是會跳過這個 slot 的塊。

圖片來自黃祺《區塊鏈中 VRF 的應用及原理解析》

多個 slot 為一個 epoch，權益的計算是以每個 epoch 開始前的歷史來計算，也就是說在這個 epoch 中所產生的權益變化不影響當前的這個 epoch 中的 slot 的出塊者的選擇和其他和歷史相關的東西。當前 epoch 中所產生的這些歷史只能在以後的 epoch 中生效。

每個 epoch 的開頭有個 genesis block(注意是每一個 epoch，不是整個鏈)，這個 genesis block 不會上鏈 (整個鏈初始的那個 genesis 會，當然這一點可以根據實現自己決定)，而是當前這個節點(礦工) 自己在內存中生成，這個 genesis block 會記錄好當前這個 epoch 中的可能參與出塊的 stakeholder 的候選人，及一個隨機種子ρ。

stakeholder 是權益持有者，也就是潛在礦工，在 Cardano 的實現中權益 stake 並不是直接指代有多少 Ada，而是和有多少 Ada 相關聯(更詳細的我不是很清楚)，同時要成為一個 stakeholder 需要有 2% 的 Ada 才行。當然論文中不關注這些，直接定義了 stakeholder。而 stakeholder 並不一定要參與出塊，只有記錄在每個 epoch 的 genesis block 中的 stakeholder 才能參與當前 epoch 中 slot 的出塊，所以記錄在每個 epoch 中的 genesis block 中的 stakeholder 叫做 「stakeholder 候選人」

由這些 epoch 銜接而成的鏈就是由 Ouroboros 共識產生的鏈，這個鏈的基本屬性和 Bitcoin 相同(如每個塊包含上一個塊的 hash 等等)。

Slot Leader Selection 是指根據權益佔比選擇按概率選擇出當前 slot 的出塊者。指代的是在當前的 epoch 中，按 genesis block 中記錄的 stakeholder 候選人的權益分別佔用的比例為這個 epoch 中的每一個 slot 選擇出塊者的概率(注意這個概率是獨立事件，也就是有可能在同一個 epoch 中重複選出相同的人)。在論文中用函數

來表示按照權益佔比為概率從stakeholder候選人選出該slot的出塊者U。注意在論文中只是定義了這個函數具有這樣的作用，在Cardano中使用了 「follow-the-satoshi(fts)」 算法(fts具有論文中定義的這個函數的性質)來選出這個slot leader也就是出塊者。

secure multiparty computation (MPC) MPC協議，參與者使用一種能達成MPC的密碼學協議來參與生成下一輪epoch的隨機種子ρ，這個MPC協議必須是保證guarantee output delivery(G.O.D，下文會解釋)。這個隨機種子ρ是用於Slot Leader Selection中的。

在已有這些基礎術語及作用的基礎上，現在來簡單介紹一下的工作流程:

如圖所示，執行流程如下：(註：我並不保證這個流程是完全符合Cardano源碼的實現(畢竟我沒看過)，但是是符合論文的描述的)：

從鏈的真正創世塊開始，硬編碼進入了一些公鑰和這些公鑰vk對應的權益s及初始的種子ρ，之後，這個epoch會採用這些基礎信息繼續運行。

每個節點自己獨立運行代碼，根據當前epoch的種子ρ，執行F(比如 follow-the-satoshi)，把genesisblock中的權益，ρ和slot的index作為輸入，根據概率獲得當前這個slot應該由誰出塊。

若發現是自己出塊，則執行打包交易等等操作，和bitcoin沒有太大區別，但是除了基礎工作之外，還會生成一個隨機數，但是這個隨機數不放到鏈(塊)中，而是放一個承諾(後文解釋)。

若不是自己出塊，則等待出塊者出塊並廣播。收到這個塊的時候就進行和bitcoin類似的檢查，要是長時間未收到(超出這個slot的時間)則會認為這個slot的塊廢棄。

在當前epoch中不斷重複2的流程直到這個epoch中的所有slot結束。

在整個epoch的過程中會產出一個在這個epoch參與出塊者們(slot leaders)都共同認同的隨機種子ρ。

在自己的內存裡記錄好這個ρ及下一個epoch參與的stakeholders，開啟下一個epoch周期，進入2的流程。

以上就是 Ouroboros 大致執行的流程。」

VRF在區塊鏈領域的運用大致如上，不過在如上場景有沒有更好的解決方式，或者這個技術還能用在什麼場景，還是值得討論的問題。

參考文章：

隨機選擇算法

區塊鏈中VRF的應用及原理解析

對可驗證隨機函數VRF的簡明解釋

簡評三個基於VRF的共識算法

可驗證隨機函數VRF之Algorand算法

圖靈獎得主Sivio Micali的Algorand區塊鏈協議簡介

Algorand 白皮書 1607.01341 版本

Cardano白皮書

Verifiable Random Functions

我是Odaily星球日報編輯盧曉明，探索真實區塊鏈，爆料、交流請加lohiuming，煩請備註姓名、單位、職務和事由。