區塊鏈中VRF的應用及原理解析
黃祺
Tarax Network 聯合創始人& CTO
圖片描述
圖片描述
圖片描述
曾先後在中科院計算所智能科學組、索尼中國研究院、百度、今日頭條從事分佈式數據共享方面的技術研究。
今天給大家帶來的這個分享叫做《區塊鏈中VRF的應用及原理解析》，起因是來自我們團隊在做的一條叫Tarax Network 的公鏈。因為場景定位的緣故，我們想找到一種低功耗的方式來進行共識。那麼POW 肯定是沒辦法考慮的，很容就會想到POS。繼而考慮到，無論是POW 或是POS，都是想不被預測的隨機找到一個節點進行區塊打包，並讓這個區塊能被全網承認。
那麼在隨機選點這件事上，VRF基於可驗證隨機選點的抽籤，是做的最直接的。
當然，POW 並不只是有隨機選點打包的功能，還有一些博弈和人性上的考量，目前的POS 方案中，也並不是隨機選點完就OK了，替代了隨機選點的方案，自然也會去從其他方面重新對博弈和人性上的問題進行設計。
不過我們先一個一個問題解決，拋開博弈的這塊內容不談，先研究研究VRF。
我們帶著兩個問題來看待這件事：
1、什麼是可驗證隨機函數？
2、現在的一些鏈的方案是如何使用可驗證隨機函數的？什麼是可驗證隨機函數可驗證隨機函數可以看作是一個
1、對於不同的Input，Output 的值是隨機的，並且均勻分佈在值域範圍內。
1、對於不同的Input，Output 的值是隨機的，並且均勻分佈在值域範圍內。
2、對於相同的Input，它得到的Output 一定是相同的。
2、對於相同的Input，它得到的Output 一定是相同的。
但是可驗證隨機函數比隨機預言機多了一個非交互的零知識證明，可以用來該隨機數輸出的正確性，表明這個隨機數的確是某個人生成的。
可驗證隨機函數它包含四個函數。
1、生成密鑰，生成一個公鑰私鑰對，這個後面就不詳細講了
2、生成隨機數輸出
3、計算零知識證明
4、驗證隨機數輸出
正文
正文
正文
可驗證隨機函數抽籤
最簡單的方法，上面我們通過VRF生成了這個隨機數value之後，可以通過設置一個全網公認閾值來判斷是否被抽中，比如我們都認同了一個值100為閾值，假設某輪我隨機到101那麼，我就被允許進行下一步。
然而這種最簡單的方案沒有辦法防止女巫攻擊。所以現在大部分的VRF抽籤方案都將基於權益來進行票數分配，然後進行抽籤算法的設計。我們來看下現在最普遍的一種方案，通過二項分佈來進行抽籤結果的計算。
首先我們已經通過私鑰生成了value了，這個value實際上可以看作是大的正整數，假設是256bit的，那麼它的取值範圍應該處於0到2的256次方之間。相應的它
與2的256次方相除，可以得到一個0到1之間的值。
將這個值放到二項分佈的累積分佈中進行比對，可以得到相應的值（詳見PPT）。
如果這個值大於零，就相當於抽到了可以進行下一步的簽。
將這個值和之前VRF生成的和一起，廣播給其他人，其他任何收到的用戶結合廣播者的公鑰以及全網都知道的值，則可以驗證以下兩個條件是否成立：
分享完VRF以及它現在的一些應用之後，有幾個問題需要我們共同思考一下：
1、抽籤有沒有必要用VRF？
圖片描述
謝謝大家。
Verifiable Random Functions [1999]
Ouroboros: A provably secure proof-of-stake blockchain protocol [2017] Algorand:
Scaling Byzantine Agreements for Cryptocurrencies [2017]
Ouroboros Praos: An adaptively-secure, semi-synchronous proof-of- stake blockchain [2018]
https://github.com/iost-official/Documents/blob/master/ Technical_White_Paper/EN/Tech_white_paper_EN.md
https://tools.ietf.org/html/draft-irtf-cfrg-vrf-02
https://github.com/Realiserad/fts-tree
https://www.cs.bu.edu/~goldbe/projects/vrf
1、利用驗證是否正確
2、利用通過二項分佈函數得到j'是否與j相等
假設兩個條件均成立，那麼就證明這個抽籤結果是正確的，是可信的。
到此為止，從抽籤生成到驗證的過程就完成了。
通過上面這個過程的描述，不難看出基於VRF的抽籤機制有幾個優點：
1、首先它的抽籤過程不需要與其他通信，直接在本機就能夠的到這個抽籤結果，而且這個x輸入是大家公認的，針對同一個x的輸出value是固定的，因此無法通過多次嘗試來改變抽籤結果
2、某個節點收到其他節點的抽籤信息之後，可以用附帶的證明，來證明這個隨機數的正確性，保證它的確是由私鑰的擁有者計算出來的。因此這個抽籤結果是無法被偽造的。
3、VRF主要用來的得出一個偽隨機數，抽籤的部分主要是由一個二項分佈函數負責，而通過構建二項分佈的參數，我們可以很方便的控制需要被得出的中籤權益的個數，適配不同的需要抽籤的場景。
說完基於VRF的抽籤算法，我們再來看看這個抽籤算法給區塊鏈共識帶來了些什麼。
VRF抽籤給共識帶來的變化
這個我們從一個具體的例子展開講。
Ouroboros 是Cardano 的共識算法，它很有意思，一開始它提出的是一種共識的流程方案，不過這種方案是可證實安全的，而並沒有涉及到每一部分的實現。而之後它會在論文版本的更新中，以及具體的實現方案中，逐漸加上實現的細節。
到目前為止，他的理論版本已經迭代了三個版本了，分別是Ouroboros、Praos和Genesis。而在第二個版本Praos中，引入了VRF的部分作為區塊提出節點的抽取。
首先大概講一下Ouroboros 的共識流程：
而在每個epoch 開始之前，上一輪epoch 中，會確定一個random seed，以及若干Stake Holders，作為這一輪epoch 的參與節點，根據random seed，會得出這一輪的所有slot 的slot leader ，由它們進行依次打包。
上一輪中，Random Seed 的交由一個交互式的PVSS 方案產生。舉一個簡單的例子來說明一下就類似於，兩個不能通過實時溝通進行猜拳的人，如果一個人收到另一個人的出拳結果，完全可以發出一個必勝的出拳來獲勝，這樣就不公平了，那麼現在這樣，我們先每個人用一張牌代替自己的出拳，然後將它蓋上，大家都不知道出的是什麼，但是都能保證大家都已經選好了這個出拳了。之後在依次公佈結果。產生了這個Random Seed 之後，然後用Follow the Satoshi 算法，得到每個slot 的slot leader，可以將Follow the Satoshi 看作是一個隨機預言機，可以利用Random Seed 以及每個StakeHolder 的權益值，給每個slot 隨機分配一個stake holder 作為slot leader，而這個結果是在這一次epoch 開始之前，每個節點都知道的，它們可以自己算出來。
這樣就會有一個問題：
我可以提前知道某個區塊的打包節點，那麼攻擊者就可以提前攻擊這個打包節點，來達到它攻擊的目的。
之後在Praos中，也就是Ouroboros的第二個版本中，它引入VRF來代替了這種Follow the Satoshi的方案，剛剛我們了解過VRF抽籤的過程以及特性之後，可以知道，引入了VRF之後，每一輪的slot的slot leader只有這個節點自己知道，他發布之後，其他節點可以驗證他是不是真有這個角色，這樣就可以避免上面所說的攻擊。
但是這也帶來了新問題，上面說到Follow the Satoshi能夠隨機的給每個slot都分配上slot leader，但是VRF這種基於概率的抽籤方式，在這點上就沒有辦法做到一定。又可能出現某一輪slot沒有抽出slot leader或者抽出了多個slot leader的情況。因此Praos中，新增了額外的方案來處理這種情況。
對比這兩種方案，VRF在引入了slot leader不可預知的安全性升級之外，也引入了兩種異常情況。但是這兩種異常情況是否是VRF引入的新問題呢？我們來思考一下。
實際上，這個問題不論是Follow the Satoshi還是VRF的方案，都必須去解決，因為就算我能保證每個slot都有slot leader，我也沒辦法保證slot leader是否能在這個slot裡打出包來。而驗證分叉的方案，又是只要是鏈就一定會考慮的問題，假設某個slot leader被攻擊，而在自己的slot里大量重複打包，也會造成分叉問題。
所以在沒有新問題引人的情況下，增加了打包節點的匿名性，實際上是對系統有了一個安全性上的升級。
然後我們再來看看其他的有使用或者極大的依賴於VRF的一些共識算法。
思路大體上是用可驗證隨機函數抽籤，來降低參與共識節點或者某種角色的數量的數量。
正文
正文
正文
正文
幾個問題
與隨機預言機相比怎樣？
謝謝大家。
圖片描述
https://github.com/pinqy520/vrf.js
圖片描述
參考文獻—————————————————————————————————————————————————————
圖片描述
https://v.qq.com/x/page/e0735yg5l7t.html
Blockchain Funds-Technology Federation
圖片描述
圖片描述
