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

編者按：區塊鏈涉及到的技術很多，從互聯網底層到不明覺厲的密碼學，可是往往關注幣價者多而研究技術的人少。牛市的時候，大家為了炒幣也會努力學習，熊市的時候，反正也沒啥事，我覺得可以更加努力學習。作為一個文科生，我當然會有很多理科生看起來覺得很白癡的問題。作為一個記者，我不難找到業內懂的人用人話給我解釋，而且他們往往不會當面嫌棄我。這是小明學習筆記第四期，學習的是VRF。之前第一期學習的是虛擬機，第二期是跨鏈，第三期《小明學習筆記|一文看懂互聯網TCP/IP協議》，之后想學習有開源歷史和文化等。如果有其他有趣問題，歡迎投稿和提問。話說這篇小明學習筆記真的拖了太久，本來在設想中就是特別短的一篇，但是由于云棲大會、公鏈101等各種欄目和編輯部瑣事，實在是已經變成了“小明更新筆記日，例會無忘告主編”了。VRF這個東東，在不少區塊鏈項目中都會聽到，比較火的Algorand和Dfinity的共識機制都用到了它。它的全稱叫VerifiableRandomFunction，那它跟一般的隨機函數有什么不同？有什么用，為什么區塊鏈需要用到VRF？這次被我騷擾的是資深全棧工程師黃祺，他曾在BFTF區塊鏈知享會中介紹區塊鏈中VRF的應用。在區塊鏈中，大部分的共識算法，無論是POW、POS，或是由他們衍生出來的DPOS，都需要選出一堆或者一個節點來參與共識或者打包區塊，這個過程雖然會有持幣情況、設備配置、信譽等各種因素影響，但必須是隨機的、無法被預測的。這時候就可能會用到隨機算法。在BFTF的分享沙龍上，黃祺解釋，可驗證隨機函數可以看作是一個隨機預言機，就是可以通過任意的一個輸入，獲得一個隨機數輸出。可驗證隨機函數比隨機預言機多了一個非交互的零知識證明，可以用來該隨機數輸出的正確性，表明這個隨機數的確是某個人生成的。先說RO，有兩個特征：1、對于不同的Input，Output的值是隨機的，并且均勻分布在值域范圍內。2、對于相同的Input，它得到的Output一定是相同的。舉例說明一下，假設某公鏈網絡用普通的RO選節點，有可能是這樣的情況：假設全網有100個節點，我想生成下一輪一個節點誰打包，我以某一輪的輪次作為輸入，然后隨機輸出的值必須要是在1-100之間的自然數。這就每一輪都選出了一個打包節點的人。這里的問題是，由于輸入對應的輸出肯定是相同的，而輸入是公開的，就使得每一輪的抽簽結果變得可以被預知，攻擊者可以嘗試控制這個過程或者攻擊特定的節點。可是如果輸入不公開的話，我們要怎么保證這個輸入結果沒有問題呢？VRF就用到了零知識證明，讓結果“可驗證”。VRF的方式是，讓各個節點自己抽簽，如果抽中了之后，大家可以很容易地驗證這個結果確實是你生成的。具體過程有可能是這樣的：假設現在是round10，節點們可能會輪流抽簽，以節點自己的私鑰+一個全網都知道的隨機數作為輸入，生成了一個隨機數；設置一個條件：100個節點輪流抽簽，誰先抽出來的隨機數大于10，就是這一輪的打包者。假設5號節點抽到了11，可是只有5號知道其他人不知道，因此他在廣播這個隨機的同時還需要廣播一個零知識證明。通過零知識證明，全網只需要通過5號的公鑰就可以驗證，接受5號為這輪打包者。So，普通RO在私鑰+零知識證明的作用下，抽簽過程就可以在本地進行、不公開私鑰同時又可以全網驗證。黃祺總結，可驗證隨機函數一共包含四個函數：1、生成密鑰，生成一個公鑰私鑰對；2、生成隨機數輸出；3、計算零知識證明；4、驗證隨機數輸出。看完上面的之后，我們大概可以明白，VRF的目的就是要生成一個真正隨機而且無法被預測的值。在區塊鏈選出塊節點的過程中，為了保證安全，隨機是一個基本要求。不過，區塊鏈選節點不單純是隨機就OK的，還要考慮到攻擊成本等，所以共識機制往往加入算力和持幣權益等影響因素，以增加攻擊者的攻擊成本。如果單純使用隨機算法，就很容易受到女巫攻擊，攻擊者可以廉價找大量的傀儡機來增加自己抽中的概率。這么一想，你會很容易明白為什么有那么多新型的共識算法都用到了VRF，其實它們想達到的目的跟POW的答題過程有點像，都是為了找到隨機而又安全地抽取出塊節點。POW被詬病的問題是功耗大和性能低，但是安全邊界明顯，而且比特幣運行已久都沒有大問題。POS共識算法本身不需要大量算力，VRF可又以在本地抽簽，所以POS共識算法用VRF的好處是功耗比較低，而且最新的算法，驗證零知識證明的速度已經非常快。有不少知名的公鏈項目都用到了VRF，包括本體、Cardano、Dfinity和Algorand。不同的項目用到VRF的不同點主要在于是怎么產生一開始的輸入，以及輸出要怎么用。以下是VRF在一些項目中的作用：根據本體官網，VBFT的每輪共識中：根據VRF從共識網絡中選擇備選提案節點，各個備選節點將獨立提出備選區塊；根據VRF從共識網絡中選擇多個驗證節點，每個驗證節點將從網絡中收集備選的區塊，進行驗證，然后對最高優先級的備選區塊進行投票；根據VRF從共識網絡中選擇多個確認節點，對上述驗證節點的投票結果進行統計驗證，并確定出最終的共識結果。所有節點都將接收確認節點的共識結果，并在一輪共識確認后開啟新的共識。根據上交所技術公司的朱立解釋，Algorand和Dfinity的共識算法中用VRF的套路大概是這樣的：輸入值由前一個隨機數和某種代表高度、輪次的變量進行組合，然后用私鑰對之進行簽名，最后哈希一下得出最新的隨機數。他認為：“這樣產生的隨機數旁人很容易驗證其合乎算法，"V"就這樣得到了；而哈希返回值又是隨機分布的，“R”也因此得到保證。在此過程中，為降低操縱結果的可能性，有兩個注意事項：A)簽名算法應當具有唯一性，也就是用同一把私鑰對同樣的信息進行簽名，只有一個合法簽名可以通過驗證——普通的非對稱加解密算法一般不具備這個屬性，如SM2。如果用的簽名算法沒有這種uniqueness屬性，那在生成新隨機數的時候就存在通過反復多次嘗試簽名以挑出最有利者的余地，會降低安全性。B)避免在生成新隨機數時將當前塊的數據作為隨機性來源之一，比如引用本塊交易列表的merkleroot值等等，因為這樣做會給出塊人嘗試變更打包交易順序、嘗試打包不同交易以產生最有利的新隨機數的余地。在設計和檢視新的共識算法時，以上兩個注意事項是要特別留意的。VRF的返回結果可以用來公開完成節點或節點群體的選擇，也可以私密地完成選擇。以Dfinity為例，它是利用mod操作來唯一、公開地確定一個Group。Algorand、OuroborosPraos是私密選擇的范例，大致套路是對VRF的最新返回值，配上輪次等變量后用私鑰進行簽名并哈希，如果哈希值小于某個閾值，節點就可以私密地知道自己被選中。這種方法很可能在網絡節點數較多時的表現會更穩定，否則幸運兒個數上下波動會較大，進而影響協議表現，包括空塊和分叉。”根據CSDN博主Omni-Space解釋，Cardano的共識機制運作如下：首先是一些術語及作用的解釋：在Cardano的運行中，時間被分為slot。每個slot只能產生一個塊，若這個塊有問題，或者應該產出這個塊的“礦工”(也就是stakeholder的候選人)不在線，或者產出的塊沒有廣播給大多數人，那么這個slot是當作廢棄的，也就是會跳過這個slot的塊。圖片來自黃祺《區塊鏈中VRF的應用及原理解析》多個slot為一個epoch，權益的計算是以每個epoch開始前的歷史來計算，也就是說在這個epoch中所產生的權益變化不影響當前的這個epoch中的slot的出塊者的選擇和其他和歷史相關的東西。當前epoch中所產生的這些歷史只能在以后的epoch中生效。每個epoch的開頭有個genesisblock(注意是每一個epoch，不是整個鏈)，這個genesisblock不會上鏈(整個鏈初始的那個genesis會，當然這一點可以根據實現自己決定)，而是當前這個節點(礦工)自己在內存中生成，這個genesisblock會記錄好當前這個epoch中的可能參與出塊的stakeholder的候選人，及一個隨機種子ρ。stakeholder是權益持有者，也就是潛在礦工，在Cardano的實現中權益stake并不是直接指代有多少Ada，而是和有多少Ada相關聯(更詳細的我不是很清楚)，同時要成為一個stakeholder需要有2%的Ada才行。當然論文中不關注這些，直接定義了stakeholder。而stakeholder并不一定要參與出塊，只有記錄在每個epoch的genesisblock中的stakeholder才能參與當前epoch中slot的出塊，所以記錄在每個epoch中的genesisblock中的stakeholder叫做“stakeholder候選人”由這些epoch銜接而成的鏈就是由Ouroboros共識產生的鏈，這個鏈的基本屬性和Bitcoin相同(如每個塊包含上一個塊的hash等等)。SlotLeaderSelection是指根據權益占比選擇按概率選擇出當前slot的出塊者。指代的是在當前的epoch中，按genesisblock中記錄的stakeholder候選人的權益分別占用的比例為這個epoch中的每一個slot選擇出塊者的概率(注意這個概率是獨立事件，也就是有可能在同一個epoch中重復選出相同的人)。在論文中用函數來表示按照權益占比為概率從stakeholder候選人選出該slot的出塊者U。注意在論文中只是定義了這個函數具有這樣的作用，在Cardano中使用了“follow-the-satoshi(fts)”算法(fts具有論文中定義的這個函數的性質)來選出這個slotleader也就是出塊者。securemultipartycomputation(MPC)MPC協議，參與者使用一種能達成MPC的密碼學協議來參與生成下一輪epoch的隨機種子ρ，這個MPC協議必須是保證guaranteeoutputdelivery(G.O.D，下文會解釋)。這個隨機種子ρ是用于SlotLeaderSelection中的。在已有這些基礎術語及作用的基礎上，現在來簡單介紹一下的工作流程:如圖所示，執行流程如下：(注：我并不保證這個流程是完全符合Cardano源碼的實現(畢竟我沒看過)，但是是符合論文的描述的)：從鏈的真正創世塊開始，硬編碼進入了一些公鑰和這些公鑰vk對應的權益s及初始的種子ρ，之后，這個epoch會采用這些基礎信息繼續運行。每個節點自己獨立運行代碼，根據當前epoch的種子ρ，執行F(比如follow-the-satoshi)，把genesisblock中的權益，ρ和slot的index作為輸入，根據概率獲得當前這個slot應該由誰出塊。若發現是自己出塊，則執行打包交易等等操作，和bitcoin沒有太大區別，但是除了基礎工作之外，還會生成一個隨機數，但是這個隨機數不放到鏈(塊)中，而是放一個承諾(后文解釋)。若不是自己出塊，則等待出塊者出塊并廣播。收到這個塊的時候就進行和bitcoin類似的檢查，要是長時間未收到(超出這個slot的時間)則會認為這個slot的塊廢棄。在當前epoch中不斷重復2的流程直到這個epoch中的所有slot結束。在整個epoch的過程中會產出一個在這個epoch參與出塊者們(slotleaders)都共同認同的隨機種子ρ。在自己的內存里記錄好這個ρ及下一個epoch參與的stakeholders，開啟下一個epoch周期，進入2的流程。以上就是Ouroboros大致執行的流程。VRF在區塊鏈領域的運用大致如上，不過在如上場景有沒有更好的解決方式，或者這個技術還能用在什么場景，還是值得討論的問題。參考文章：隨機選擇算法區塊鏈中VRF的應用及原理解析對可驗證隨機函數VRF的簡明解釋簡評三個基于VRF的共識算法可驗證隨機函數VRF之Algorand算法圖靈獎得主SivioMicali的Algorand區塊鏈協議簡介Algorand白皮書1607.01341版本Cardano白皮書VerifiableRandomFunctions我是Odaily星球日報編輯盧曉明，探索真實區塊鏈，爆料、交流請加lohiuming，煩請備注姓名、單位、職務和事由。

ETH 2.0總質押數突破2600萬:金色財經報道，數據顯示，ETH 2.0總質押數已超2600.23萬，為26002251個，按當前市場價格，價值約505.13億美元。此外，目前ETH 2.0質押總地址數已超85.93萬，為859266個。[2023/7/16 10:58:18]

Alchemy Pay已支持土耳其用戶通過銀行轉賬購買加密貨幣:6月30日消息，加密貨幣支付提供商Alchemy Pay發文稱，已為土耳其所有主要銀行（包括Ziraat Bank、Turkiye Bankasi、Isbank等）提供支持，允許用戶通過銀行與當地法幣土耳其里拉（TRY）購買加密貨幣。[2023/6/30 22:10:40]

Harmony Bridge攻擊者今天轉移約150萬美元資金:金色財經報道，據區塊鏈安全審計公司Beosin旗下Beosin EagleEye安全風險監控、預警與阻斷平臺監測顯示，2023年2月14日，Harmony Bridge攻擊者正在持續轉移被盜資產，今日共轉移了997余個ETH，價值約150萬美元。

此前消息，2022年6月24日，Harmony開發的以太坊與Harmony間的資產跨鏈橋Horizon遭到攻擊，損失金額約為1億美元。[2023/2/14 12:06:15]

Mano 首席技術官：Web3 的額外部分是對等發現層、密碼學和共識協議:金色財經現場報道，在Coinlive舉辦的峰會上，題為“塑造新加坡數字資產類別的未來”的圓桌討論邀請了 Cobo 首席運營官 Lily Z. King、新加坡管理大學 (SMU) 經濟學助理教授（實踐） Goh Jing Rong、Immin Mano Thanabalan 首席技術官、德國創業亞洲 Yitch，區塊鏈協會 (BAS) 合作伙伴總監 Yoon KC (Steven)。關于 Web3 是什么以及數字資產在 Web3 生態系統中扮演什么角色的問題，Mano 首先說 Web3 的額外部分是對等發現層、密碼學和共識協議，這可能是最有趣的。 YC 澄清應該是 Web3 而不是 Web 3.0。

Lily 補充說，EWeb3 有望成為一個更加開放的互聯網，讓所有用戶都能從中受益。 Jing Rong 列出了下一代互聯網的三個定義，使用新聞技術來改進當前的網絡，并專注于去中心化，即控制權被分配給生態系統中的多方。最后一個給出答案的 Yitch 解釋說，歸根結底，數字資產只是數字，除非你可以創造現實世界的效用。其他問題，如數字資產的機構采用、法規等，引起了小組成員的不同回應。[2022/12/22 22:00:54]

馬斯克：SBF代表的是無效的利他主義:金色財經報道，馬斯克發推稱，SBF（代表的）是無效的利他主義，但他們（傳統媒體）認為他宣揚的是有效的利他主義。容易引起誤會。

此前消息，馬斯克稱，與老式媒體相比，在推特上有關FTX事件的報道超級快，而且質量更好。更不用說還流傳著很多meme。[2022/11/18 13:18:53]

Tags：POCSLOTLOT區塊鏈PocolandSLOT幣PlotX為什么現在不提區塊鏈了

DOT