區塊鏈中的數學(四十一)

2021-02-15 blocksight
寫在前面

上一節是目錄整理，可以方便地找到你感興趣的內容。

本文開始講隨機可驗證函數（VRF）的內容。

VRF基本概念

可驗證隨機函數（VRF）是公鑰密碼學與哈希函數結合的另外一種應用方式。
只有私鑰的持有者才能計算哈希。
但是任何擁有公鑰的人都可以驗證哈希的正確性。VRF有助於防止枚舉基於哈希的數據結構攻擊。

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

可驗證隨機函數可以看作是一個隨機預言機（Random Oracle，RO），通過任意的一個輸入，獲得一個隨機數輸出。可驗證隨機函數比隨機預言機多了一個非交互的零知識證明，可以用來驗證該隨機數輸出的正確性，表明這個隨機數的確是某個人或者節點生成的。

使用 VRF，達到的目的跟 POW 的過程有些類似，就是為了隨機而又安全地抽取出塊節點。

目前有兩個體制，一個VRF使用RSA，另一個VRF使用橢圓曲線（EC）。

VRF算法框架

VRF包含了一個密鑰生成算法，它可以生成一個公共VRF密鑰PK和私有的VRF密鑰SK。

圖中，M代表原始輸入消息，總體分為生成證明（generation）和驗證（verify）兩部分。

生成過程

P = VRF_proof(SK, M)  生成證明P，
R = VRF_proof_to_hash(P) 將證明轉化成hash值，有時簡寫成 R = VRF_P2H(P)

VRF_hash(SK, M) = VRF_proof_to_hash(VRF_proof(SK, M))

驗證過程

VRF_verify(PK, M, P) 利用公鑰對檢驗證明P是否是基於原始消息M產生的證明，如果是返回合法，否則非法。

VRF滿足的安全屬性 唯一性要求

唯一性是指，對於任何確定的VRF公鑰和任何輸入M，有一個唯一的的VRF輸出P，可以證明有效的。即使是一個惡意的證明者知道VRF私鑰SK，也產生不了更多的有效證明。

抗碰撞性

像其他任何密碼學散列函數一樣，VRF需要抗碰撞性， 即使對於知道VRF私鑰SK的惡意證明者，Collison抵抗也必須成立。

更確切地說，「完全抗碰撞」表現在計算上，對手無法找到兩個不同的VRF輸入M1和M2具有相同的VRF散列P，即使對方知道VRF密鑰SK。

稍微弱一點的抗碰撞性，稱為「可信抗碰撞」，即在 PK和SK在一種安全可信的方式下生成。

隨機性要求

偽隨機性確保了當一個對手驗證者看到一個VRF散列輸出R，而沒有相應的VRF證明P時，R與隨機值無法區分,即看到的R就像隨機值一樣（也就是hash函數的隨機性）。
更準確地說，假設公共和私有VRF密鑰（PK，SK）是以值得信賴的方式產生。偽隨機性保證了對於任何計算力有限的惡意對手，VRF散列在任何惡意對手選擇的「目標」VRF輸入M看起來都無法區分。

即不能從不同的輸入中提取到任何有效信息。

「選擇性偽隨機性」是一種相對較弱的安全屬性，在許多應用中已經足夠了。在這裡，對手必須選擇目標VRF輸入M獨立於公共VRF密鑰PK，以及在它觀察VRF輸出R和證明輸入M上的P之間的聯繫。

需要指出的是，VRF輸出R對於證明人來說不是隨機的，並且對於知道與VRF輸入M與對應的有效VRF證明P的一方來說也不是隨機的。 這很容易理解，因為對證明人而言，相同的輸入只會得到相同的輸出，這一點無「隨機性」。

小結

本文主要介紹了VRF的概念和算法結構，隨機性體現在外部看來，找不到輸出證明結果與輸入之間的關係，給人一種「隨機性」輸出的感覺。

下一節繼續說基於RSA公鑰體制的VRF算法具體內容。

歡迎關注&在看， 疑問請留言！

相關閱讀：

區塊鏈中的數學（四十）   目錄整理，一目了然！

區塊鏈中的數學（三十九）   Uniwap核心算法解析-完結篇

區塊鏈中的數學（三十八）   Uniwap核心算法解析（下）

區塊鏈中的數學（三十七） Uniwap核心算法解析（中）

區塊鏈中的數學（三十六） Uniwap自動化做市商核心算法解析（上）

區塊鏈中的數學（三十五）  何為交易可鍛性？

區塊鏈中的數學（三十四）  Miller Rabin算法」憑證「解讀與實現

區塊鏈中的數學（六）   secp256k1籤名和驗證過程

區塊鏈中的數學（五）   橢圓曲線加密原理和實例演練

相關焦點

  • 區塊鏈中的「鏈」與「圈」
    區塊鏈主要分為三種鏈：公鏈、私鏈、聯盟鏈。 公鏈：就是公共區塊鏈，它是指世界任何一個人都可以參與、完全去中心化的共識區塊鏈。公鏈的特點是開發者無權幹涉用戶，可以保護用戶免受開發者影響；訪問門檻低，只要有一臺聯網的電腦，任何人都可以訪問，數據完全公開透明，不可篡改。
  • 區塊鏈中的哈希值是做什麼的
    打開APP 區塊鏈中的哈希值是做什麼的 Shiva Sai Kumar B 發表於 2020-03-05 11:55:53 我們使用一個數學算法稱為SHA-256（安全哈希算法-256位）。SHA 256是SHA-1的繼承者，SHA-1有160位。 2. 如何在區塊鏈中使用哈希值？ 在區塊鏈中，每個塊都有前一個塊的哈希值，前一個塊被稱為當前塊的父塊，如果考慮父塊有一個當前區塊。它將會有上一個塊的哈希值即父塊。 在區塊鏈中，每個塊都有前一個塊的哈希值。
  • 讀透區塊鏈系列篇4-區塊鏈中的「馬斯洛需求層次」模型|火星號精選
    數學層這一層為區塊鏈的最底層，對區塊鏈的影響是最為根本的，這一層發生的任何突破都會對上面四層產生影響。因為說到底，區塊鏈技術是構建在數字網絡上的。屬於虛擬的非物質世界，最為底層的表達是數字，從這個角度說，任何技術的背後都是數學，一個技術的邊界也可以理解為數學的邊界。
  • 區塊鏈中的那些密碼學
    區塊鏈中的密碼在比特幣區塊鏈的整個體系中，大量使用了公開的加密算法，如Merkle Tree哈希數算法，橢圓曲線算法、哈希算法、對稱加密算法及一些編碼算法。各種算法在比特幣區塊鏈中的作用如下：哈希算法 比特幣系統中使用的兩個哈希函數分別是：1.SHA-256，主要用於完成PoW（工作量證明）計算；2.RIPEMD160，主要用於生成比特幣地址。
  • 區塊鏈中的PoC共識算法是什麼意思?
    共識算法是區塊鏈技術的核心要素, 由於區塊鏈的快速發展，共識已得到各界關注，它將人類帶入數學領域的信任時代，因為有共識的存在，人類可以展開無信用抵押的大規模協作
  • 區塊鏈日報丨杜拜將區塊鏈用於旅遊業,沃爾瑪實施區塊鏈配送體系
    編者按：由於區塊鏈技術火爆，各個行業的企業紛紛加入，區塊鏈行業也因大量的企業加入而變得更加繁榮。Bianews將以日報形式為區塊鏈從業者、用戶傳遞行業信息，讓大家能夠從多層面、多維度去了解區塊鏈這個行業，從而做出自己正確的判斷。
  • 萬向區塊鏈實驗室董事長肖風:區塊鏈經濟才是真正的共享經濟
    而區塊鏈技術在2009年出現後，它可以更好地發揮自組織在經濟活動中的治理效率。肖風進一步指出，區塊鏈可以分三個層次，最底層的一個層次是分布式網絡；在分布式網絡基礎上加一層密碼學的帳本體系，就變成了分布式帳本；而在分布式帳本上加上基於博弈論的共識算法和基於數字貨幣的激勵機制就是共有區塊鏈，比如比特幣公有鏈。
  • 英國區塊鏈協會在最新報告中尋找「區塊鏈證據」
    宣傳區塊鏈產品的功效或許是件好事，但它真的經得起仔細審查嗎?來自英國區塊鏈協會雜誌的新論文基於循證實踐對區塊鏈技術進行了探索，結果令人懷疑。區塊鏈證據中心(CEBB)是英國區塊鏈協會的一部分，分析了2016年至2020年啟動的417個區塊鏈項目和初創公司。除此之外，Angel.co的研究人員仔細檢查了4800多家公司的資料庫。在被分析的公司中，只有7%在看到「明確定義的問題」時顯示了過濾過的證據。62%的人有未經過濾的證據，31%的人沒有提供證據。
  • 加快推進區塊鏈產業發展壯大 湖南省區塊鏈協會成立
    (湖南省區塊鏈協會成立大會現場)(授牌儀式)華聲在線12月23日訊(記者 龍騰 通訊員 劉寧波)今天，湖南省區塊鏈協會第一屆會員代表大會在長沙市召開，湖南省區塊鏈協會正式成立。會議表決通過《湖南省區塊鏈協會章程》等文件，選舉產生了第一屆理事會班子，湖南天河國雲科技有限公司當選會長單位。湖南省區塊鏈協會的成立，是湖南省區塊鏈產業適應市場經濟運行，向規模化、組織化邁進的一個良好開端。今年10月，省政府辦公廳印發《湖南省區塊鏈發展總體規劃(2020-2025年)》，全面啟動區塊鏈產業五年行動計劃，加快推進全省區塊鏈產業發展壯大。
  • 一文讀懂區塊鏈中的哈希值
    我們使用一個數學算法稱為SHA-256（安全哈希算法-256位）。SHA 256是SHA-1的繼承者，SHA-1有160位。2. 如何在區塊鏈中使用哈希值？在區塊鏈中，每個塊都有前一個塊的哈希值，前一個塊被稱為當前塊的父塊，如果考慮父塊有一個當前區塊。它將會有上一個塊的哈希值即父塊。在區塊鏈中，每個塊都有前一個塊的哈希值。
  • ...區塊鏈教育報告:加密貨幣和區塊鏈教育正在全球頂級高校中興起
    他說道：「區塊鏈行業發展的很順利，也導致很多資金注入到區塊鏈企業中。通過研究這個領域，學生將受益匪淺。」類似的情況也出現在世界各地的其他頂尖大學院校中，大學生們紛紛湧入加密貨幣和區塊鏈課程，部分原因也是因為受過「分布式帳本」技術專業培訓的畢業生在就業市場相對搶手。
  • 區塊鏈的三個「天然缺陷」|區塊鏈技術|算法|程式語言|哈希_網易科技
    我們總是會把區塊鏈技術「完美化」，殊不知，在經濟學家、密碼學家、計算機科學家眼中，區塊鏈技術還有很多需要改進的地方。例如《區塊鏈核心技術開發與應用》就認為目前區塊鏈技術在數學工具、博弈論、密碼學、代碼存在局限性的情況下，還有很大的改進空間。換言之區塊鏈技術要想被大規模商用，還有很長的路要走。那麼，目前的區塊鏈還存在什麼不完美的地方呢？
  • 什麼是區塊鏈中的節點
    再說區塊鏈的世界，大家都已經知道區塊鏈是去中心化的分布式資料庫，它不依託於哪一個中心化的伺服器，是由千千萬萬個「小伺服器」組成。只要我們下載一個區塊鏈客戶端，我們就變成了那千千萬萬個「小伺服器」中的一員。這樣來說，如果我們要玩區塊鏈的話，我們自己就相當於是一個節點。節點也分輕節點和全節點。
  • 王小雲院士:密碼學是區塊鏈技術的起源
    科技日報記者 劉傳書12月7日，由中國科學院學部主辦、中國信息通信研究院等單位聯合支持的「區塊鏈技術與應用」科學與技術前沿論壇在深圳舉辦。中國科學院信息技術科學部鄭志明院士、數學物理學部王小雲院士等四位院士發表主題演講，同時還有300餘名來自政府和企業界的代表出席會議，圍繞區塊鏈與數字身份、監管科技、金融應用等話題展開討論。中國科學院院士、清華大學高等研究院「楊振寧講座」教授、國際密碼協會會士(IACR Fellow)王小雲院士，在大會上進行了主題為「Hash函數與區塊鏈技術」的開幕報告。
  • 區塊鏈中的數據結構
    區塊鏈結構本身為一條鍊表，節點為區塊。而傳統鍊表實現，便是通過指針將各個節點串聯起來稱為最終的鏈。如下便是我們最常見的一個鍊表：區塊鏈中，並未採用指針，而是使用了哈希指針！（2）哈希指針如下圖對於該節點，我們可以看到有兩個指針指向這個節點（實際上為一個），其中P為該節點的地址，H()為該節點的哈希值，該值與節點中內容有關。
  • 「區塊鏈學習乾貨」PoW、PoS……區塊鏈常見共識機制一文全解
    通過前面幾篇乾貨系列文章的學習，相信關注我們的小夥伴都已經明白了區塊鏈是一個去中心化、分布式的系統，能夠保證鏈上數據公開透明，同時保護數據的隱私安全。區塊鏈中沒有權威性中心機構來驗證數據交易，但鏈上的每筆交易卻是安全、可驗證的。這都得歸功於區塊鏈的共識機制。
  • 關於區塊鏈的普遍誤解:狹義區塊鏈和廣義區塊鏈的區別
    狹義區塊鏈和廣義區塊鏈的區別 我們從技術角度分析一下區塊鏈到底是什麼?其實從本質上來說，區塊鏈是一種底層基礎架構，它的應用範圍不僅局限於金融行業，也可以在其他行業。在眾多討論中，我們發現人們對於區塊鏈的理解確實存在許多誤區，往往將區塊鏈具象成分布式帳本、智能合約、密碼學這
  • 獨家| ChinaLedger白碩:區塊鏈中的隱私保護
    雷鋒網AI金融評論報導，在5月11日由北京國家會計學院主辦，區塊鏈初創公司靈鈦科技，能源區塊鏈實驗室，眾安科技、新加坡第三方支付公司Omise協辦的 「區塊鏈在中國的應用與產業發展主題論壇」 上，Chinaledger技術委員會主任白碩老師圍繞「區塊鏈中的隱私保護」的主題進行了講述。
  • 湖南省區塊鏈協會成立
    23日下午，湖南省區塊鏈協會第一屆會員代表大會在長沙市馬欄山（長沙）視頻文創園召開，會議表決通過《湖南省區塊鏈協會章程》等文件，選舉產生了第一屆理事會班子，湖南天河國雲科技有限公司當選會長單位，湖南省區塊鏈協會宣告正式成立。「湖南省區塊鏈協會的成立，是湖南區塊鏈產業適應市場經濟運行，向規模化、組織化邁進的一個良好開端。
  • 全面認知區塊鏈的科學特徵
    小編：記得關注哦 來源：數字資產研究院CIDA 他指出，區塊鏈不僅是技術，而且是科學。並且，區塊鏈是一門綜合科學，涉及數學、密碼學、計算機科學、量子計算等。相關學科並沒有窮盡，很可能存在尚未被發現的學科。