自從以太坊將可驗證延遲函數(Verifiable Random Function, VDF)列入研究計劃並打算在以太坊 2.0 使用之後,VDF 得到了廣泛的關注。VDF 這個概念最初由斯坦福大學密碼學教授 Dan Boneh 等人在其論文 Verifiable Delay Function 中給出。該篇文章於 2018 年發表在密碼學頂級會議之一的 CRYPTO 上。

目前網絡上有一些英文和中文的文章介紹了 VDF 的概念和原理,但是它們要麼無法給出全面直觀的解釋,要麼只是粗淺地談論應用。本文試圖通過淺顯的語言和具體的例子來讓對密碼學和羣論不夠了解的讀者能夠全面而直觀地理解它的定義和原理。同時,本文還給出了它的可能的應用場景以及目前的研究和應用狀況。

原文標題:《一文搞懂可驗證延遲函數 VDF》
作者:邱飛暘
鏈聞經公衆號「NPC 源計劃」授權轉載

簡介

VDF 是一類數學函數,能夠使得該函數的計算需要至少一段已知的時間,即使是在同時使用少量 CPU 進行並行計算的情況下(這與比特幣的 Proof-of-Work (PoW) 不同,後文會詳細解釋)。

對於未精心設計過的算法,並行計算有可能極大地縮減其計算時間。以比特幣的挖礦算法爲例,設 0⩽nonce⩽232−10⩽nonce⩽232−1,如果只有一個運算單元,那麼可能需要耗費多達 232 次 SHA-256 計算的時間。如果有兩個運算單元,就可以將任務對半分攤,讓他們並行地計算哈希值。最多隻需要耗費 231 次 SHA-256 計算的時間。

同時滿足以下性質:

1、VDF 的結果的檢驗應當是非常有效率的;
2、唯一性(Uniqueness):對於任意一個 VDF 的輸入,應當有唯一的輸出結果能夠通過檢驗。也就是說,不存在兩個不同的輸出,他們有相同的輸入。如果輸出結果包含「結果」和關於結果的「證明」兩部分,那麼證明部分可以不具有唯一性,但需要保證「驗證者因爲證明而驗證通過,但是輸出結果卻不是正確的結果」這件事發生的概率小到可以忽略不計;
2、串行性(Sequentiality):攻擊者即使能夠提前計算很長時間(但不是任意長的時間),並且擁有很多並行處理器(但不是任意多的處理器),利用各種計算方法(確定地計算或是連蒙帶猜),能夠以少於 t 的時間計算出 VDF 結果的概率可以小到忽略不計(並不是 0,因爲也許攻擊者真的就運氣好到猜中了呢?)。

VDF 能夠抵抗並行計算加速,這意味着爲了計算 VDF,應當完成一系列串行才能完成的任務,後一個任務必須依賴於前一個任務。這時,對哈希函數有所瞭解的讀者可能會想到一種方案:連續將一個輸入哈希 tt 次。這樣的方案的確是無法通過並行算法顯著地加速的,但是這樣得到的結果,其驗證將會非常沒有效率:驗證者需要重複哈希 T 次的計算,即使保留一些中間結果,驗證的工作量和計算的工作量也是常數級別的差距。從這個例子我們可以看出,在這樣的定義下,可驗證延遲函數的構造並沒有想象中的那麼簡單。

事實上,對於上面並不嚴謹的定義,去掉任何一個性質都會導致我們能夠非常輕易地構造出可驗證延遲函數:

1、如果不要求驗證結果是高效的,也就是說沒有顯著地比計算結果更快,那麼我們可以通過剛纔提到的連續哈希的方案進行構造;
2、如果我們不需要它保證唯一性,那麼早在 2013 年 Mahmoody 等人的工作 Publicly Verifiable Proofs of Sequential Work 就已經實現了這一點;
3、如果它不保證串行性,那麼顯然構造方法就更多了。

與 PoW 的區別

或許有讀者會感覺 VDF 和 PoW 是一類東西,實際上,雖然他們計算起來都不是很容易,但是他們之間有很多關鍵的區別。

1、PoW 不抵抗並行計算加速而 VDF 抵抗。實際上,PoW 不抵抗並行計算加速是符合中本聰的「一 CPU 一票」的設想的,而抗並行加速的性質只會與這個目的背道而馳。VDF 會使得多 CPU 的計算者和單 CPU 的計算者相比幾乎沒有什麼優勢;
2、對於固定的難度設定 d,PoW 可以有很多合法的解,這也是保證 PoW 共識網絡擁有穩定的吞吐量以及刺激礦工進行競爭的前提。而對於給定輸入 x,VDF 擁有唯一的輸出(這也是爲什麼它被稱作函數)。

上述兩條性質決定了 PoW 直接作爲隨機數的來源是有缺陷的,同時,VDF 也無法直接替代 PoW。但是這並不能說明 VDF 不可以被用到共識協議裏,這一點會在下一個章節詳談。

用途

上一章節我們介紹了 VDF 是什麼,以及它具有怎樣的性質,這一章節我們關注它的用途。

增強公共可驗證隨機數的安全性

區塊鏈上的隨機數一直是一個熱門話題。無論是在一些權益證明(Proof-of-Stake,PoS)共識協議的設計裏,還是在智能合約平臺,譬如 Ethereum 和 EOS,上一些非常火爆的遊戲類應用,隨機數都佔據了核心的地位。同時,很多這些應用中,實際設計的隨機數獲取方案還非常不成熟,以至經常會有應用因爲不安全的隨機數而被黑客攻擊 [6] 的新聞出現。

VDF 對於一些從公共來源獲取隨機數的方法非常有用。比如從股票市場或者是從 PoW 區塊鏈上獲取。這些隨機源擁有足夠的隨機性(更嚴格地講,是最小熵)。但是高頻交易者可以影響股價,同時,PoW 區塊鏈的礦工也可以通過不廣播自己挖出的區塊來降低自己不想要的隨機數結果的出現概率。但是這樣的攻擊方式成立的前提條件是攻擊者有時間在其他誠實參與者之前預測出隨機數結果。VDF 恰好能阻止這一點。如果將 VDF 的時間參數 tt 設置到足夠長(比如 10 個塊的間隔),將最新的區塊頭作爲輸入扔進 VDF 中,輸出作爲隨機數結果。那麼攻擊者只能在 10 個塊之後才能知道隨機數的結果是什麼,那個時候想要再改變結果已經很難了(需要 fork 10 個區塊)。

此外,VDF 也可以增強一些多方參與的隨機數方案。比如 Commit-and-Reveal 方案中,攻擊者可以拖到 Reveal 階段的最後再決定是否揭示自己的承諾。如果我們去掉 Commit 階段,並且協議的最後整合所有人的輸入之後不直接作爲隨機數結果,而是放入 VDF 中,並且將 VDF 的時間參數 tt 設置到足夠長(晚於最後提交期限),那麼即使是最後一刻提交的人也無法知道隨機數的結果,操縱結果也就無從談起。與之相比較,其他的多方參與方案通常最多容忍小於一半的惡意節點,並且交互的開銷要比上述方案更大。

解決 Nothing-at-stake Attack

正如上一節所述,VDF 可以用於增強隨機數生成方案的安全性,因此,在一些使用了隨機數來選取 Leader 的共識協議中也可以使用 VDF 在增強其安全性。一些節約能源的共識協議,例如 PoS,空間證明(Proof-of-Space)以及存儲證明(Proof-of-Storage),爲了防止 Nothing-at-stake attack,需要使用隨機選舉每隔一段時間選舉出一個 Leader。這些協議使用的隨機數方案大多隻在誠實參與者佔據大多數時保持安全。利用 VDF 可以降低這樣的限制到至少存在一個誠實參與者。

什麼是 Nothing-at-stake Attack?PoS 區塊鏈發生分叉時,共識參與者爲了自己的利益會選擇在不同的分叉鏈上同時進行抵押資產參與出塊,這樣分叉鏈有可能會一直存在並且分叉越來越多,嚴重危害系統的一致性,這樣的攻擊被叫做 Nothing-at-stakeattack。在 PoW 鏈上進行這樣的攻擊需要分散算力,因此這樣的攻擊只適用於「節約能源」的共識協議。

除了隨機選舉之外,還有一種叫做 Proofs of Space and Time[7] 的方案可以防止這種攻擊。實際上該方案模擬了 PoW 的挖礦過程:挖出區塊的時間是不確定的,並且每個礦工都在互相競爭成爲最早挖出區塊的人。不一樣的地方在於,模擬挖礦過程實際上並不需要消耗大量的並行計算資源(Proof-of-Time),只有在進入挖礦時有一定的門檻(Proof-of-Space)。具體來講,整個挖礦過程按照時間順序被分成不同的區間,每一個區間都有一個公共隨機的挑戰 c (舉個例子,可以是前一個區間挖出的塊的哈希值)。假設某個礦工擁有的空間單位爲 N,他需要生成一個證明 π 來證明他擁有這 N 單位的空間,並且專門用於該區塊鏈的挖礦,這一點由 Proof-of-Space 保證。礦工的目標爲找到最小的 τ=H(c,π,i),1⩽i⩽N,然後將 c 作爲輸入計算一個 VDF (事實上是增量 VDF),該 VDF 的時間參數與 τ 正相關。這樣的設計中,擁有空間越多的礦工找到更小的 τ 的可能性更大,同時,VDF 保證了一段時間的流逝,使礦工大量分叉需要消耗大量的時間。

減輕 Long-range Attack

幾乎所有的 PoS 方案都面臨 Long-range attack 的問題。目前 PoS 協議依賴於外部的時間戳服務來幫助他們解決這個問題 —— 只要能判斷哪一條鏈更老,就能阻止這樣的攻擊發生。VDF 能夠幫助 PoS 解決這樣的問題。VDF 相當於一種時間流逝的證明,對於給定的 VDF,該 VDF 至少需要多久才能得出結果是一個公共知識。因此,只需要在 PoS 鏈上包含 VDF 的輸入與輸出即可證明給定區塊的歷史。

什麼是 Long-range Attack?在 PoS 協議中,任意時刻都有一組權益相關者擁有按照權益多少分配的投票權。PoS 假設大多數權益相關者並沒有理由對系統造成破壞,因爲這樣反而會損害自己的權益。但是如果這些權益相關者在某一個時間點出售了自己的權益,這樣的激勵對他們來講是無效的。這些已經出售了自己權益的曾經的權益相關者仍然可以在曾經某一個時間點輕易對(那時他們佔據大多數權益) PoS 鏈分叉達到原有鏈的的長度,從中攫取額外的利益,這樣的攻擊被稱作 Long-range attack。它在 PoW 上不太可能發生,因爲對於 PoW 來講,無論從哪一個時間點進行分叉,都必須要付出相應的算力才能追上原有的鏈,想要分叉的區塊越多,付出的算力也就越多。

但是必須要指出的是,這樣的方法並不是完美的,因爲 VDF 仍然是可以被特殊硬件加速的(儘管是常數級的)。如果攻擊者獲得了誠實節點 10 倍的計算速度,那麼這樣的加速對於使用 VDF 作證明的 PoS 鏈是不可接受的(攻擊者可以在 10 年之後僞造出 1 年以前的區塊)。

10 倍的加速對於隨機數生成的場景無所謂,因爲該場景下,不需要保證「攻擊者算得沒有誠實節點快」,只需要保證攻擊者無法在某個時間點(隨機數來源再也無法更改的時間點,例如股市閉市)之前無法計算出結果即可。從而在隨機數生成的場景,我們可以選取一個足夠長的時間參數,使得攻擊者即使加速也無法操縱隨機數。

副本證明(Proof of Replication)

副本證明所需要解決的問題是,服務器如何向客戶端證明自己在某一專門的存儲介質上存儲了指定的數據,即使這樣的數據是可以從別的存儲來源輕易獲得的。注意副本證明是爲了證明服務器擁有一份數據的副本,而不是證明它有這樣的數據。舉個例子,雲存儲服務提供商聲稱自己爲客戶的數據做了額外的兩份冗餘備份來保證用戶數據的 availability,因此客戶需要爲這樣的冗餘備份交更多的錢。但是怎麼證明雲服務提供商有一共三份副本而不是兩份或者只有一份呢?這就需要用到副本證明。一種思路是利用在時間上不對稱的編碼方案(也就是編碼很慢,但是解碼很快),VDF 可以做到這一點(事實上是可解碼 VDF)。身份爲 id 的服務器首先將文件分成 b-bit 大小的文件塊 Bi\,1⩽i⩽n,然後計算 Bi⊕H(id||i) 並將結果作爲輸入放進 VDF 計算得到 yi\,1⩽i⩽n,其中 H 是輸出長度爲 b-bit 的防碰撞哈希函數。服務器存儲所有的 yi,客戶端不斷隨機挑選 ii 進行輪詢要求服務器返回 yi,服務器在規定時間內需要響應給客戶端相應的結果,而客戶端可以在很短的時間內通過解碼 yi 得到 Bi 完成驗證。如果服務器沒有存儲 yi ,那麼想要正確響應客戶端必須計算 yi,然而這樣的計算無法在規定的時間內完成。服務器也可以只存儲一部分 yi (比例爲 ρ),由於客戶端是隨機輪詢,每一次服務器成功欺騙客戶端的概率爲 ρ。只要客戶端重複 k 次這樣的輪詢,就可以將服務器欺騙成功的概率降到 ρk。需要補充的一點是,服務器可以不存儲 Bi,由於 yi 解碼很快,即使只存儲 yi 也不會太影響性能。

基本原理

既然 VDF 是一個函數,那麼它就必然具有這樣的形式:f:X→Y。爲了實現前文所述的功能,即「抵抗並行計算的延遲」以及「可驗證的結果」,VDF 中必然包含一個用於計算結果的算法以及一個用於驗證結果的算法。同時,這樣的密碼學工具通常還包含一個配置階段,用來確定後續需要使用的參數。因此,VDF 被描述爲三個算法的一個三元組 (Setup(Setup, EvalEval, Verify)Verify)。

每個算法的定義如下:

  • Setup(λ,t)→pp=(ek,vk) 接受安全參數 λ 以及時間參數 t,生成一個公共參數 pp,這個參數是所有人都可以看到的。公共參數 pp 包含了一個用於計算的參數 ek 和一個用於驗證的參數 vk;
  • Eval(ek,x)→(y,π) 接受計算參數 ek 和輸入 x∈X,計算出輸出 y∈Y 和證明 π;
  • Verify(vk,x,y,π)→{accept,reject}接受 vk,x,y 以及 π,輸出 accept (驗證通過)或者 reject (驗證失敗)。

如圖 1 所示我們可以看到 VDF 通常的運行流程。

VDF 究竟是什麼?爲什麼它能受到以太坊的青睞?圖 1:可驗證延遲函數

以上幾個算法有一些需要補充說明的地方:

  • 關於 SetupSetup

1、SetupSetup 的運行時間不能太久,它被安全參數 λ 所限制;
2、Setup 這個階段通常會需要隨機數作爲參數以保證安全性,如果隨機數是私下選擇的,也就是不可公開的,那麼這個階段就會需要一個可被信任的一方來進行隨機數的選擇,稱之爲trusted setup。相反,如果隨機數可以是公共隨機數,那麼這個階段就不需要這樣的 trusted setup。顯然,我們希望儘量避免 trusted setup。

  • 關於 Eval

1、證明 π 不是必須的,如果僅僅通過 y 就能驗證的話;
2、在 y 的計算中,不允許有隨機數的引入(爲了保證唯一性),但是在 π 的生成過程中可以引入;
3、爲了保證串行性,Eval 在擁有不超過關於 t 的多項式對數 ****(Poly-log)個並行處理器時,運行時間必須爲 t;
4、爲什麼 Eval 要允許一定程度的並行計算達到時間 t 呢?因爲可能並沒有構造能夠完美地讓並行和串行計算時間完全相同,所以我們需要容忍一定量的不太顯著的並行加速。

  • 關於 Verify

1、Verify 中不引入隨機數,也就是說,它是確定性算法;
2、Verify 的運行時間要比 t 小得多,具體來講,他們在運行時間上擁有指數級別的差距(Exponential gap)

基於上述定義,VDF 還有一些擁有特殊性質的變種:

1、可解碼 VDF (Decodable VDF):如果對於一個 VDF 方案,存在一個算法對於任意 x∈X 能夠從 y∈Y 反向計算出 x,那麼這個 VDF 就是可解碼 VDF。在這樣的情況下,證明 π 是不需要的。當然,一個平凡的構造是,將 π 放進 y 裏面;
2、增量 VDF (Incremental VDF):如果在 Setup 算法中,參數 t 沒有被唯一確定,而是允許在 Eval 的輸出之一 π 中指定,這樣的 VDF 被稱作增量 VDF。一種效果類似的構造是,在 Setup 中設定 t 爲一個單位的時間,如果想要在計算階段達到不同的延遲時間,例如 T=nt,只需要串行 n 次 Eval 即可。但是這樣的構造會導致 n 倍的證明長度,增量 VDF 不會產生額外的證明;
3、陷門 VDF (Trapdoor VDF):如果某個 VDF 方案存在一個算法,使得知道某一祕密值 sk 的人能夠通過這個算法迅速由 Eval 的輸入得到 Eval 的輸出,那麼這個 VDF 是陷門 VDF。更直觀的理解是,陷門 VDF 有一個後門可以讓人繞過延遲限制迅速算出結果。
4、弱 VDF (Weak VDF):如果我們放寬限制,允許「即使在 Eval 中使用多項式(Polynomial)個並行處理器才能在 t 時間算出結果」這樣的情況出現,這樣的 VDF 被稱作弱 VDF。弱 VDF 在實際應用中會更加消耗誠實參與者的算力(因爲相比 VDF 而言需要更多的並行處理器才能達到 t 時間)。但如果將 VDF 用於生成公共可驗證的隨機數,可以將計算任務交給一個誠實參與者,其他參與者等着驗證。這時,這樣的唯一計算者是可能擁有足夠多的處理器的。

一種簡單的構造方式

上文提到了使用連續的哈希操作是一種防止並行的計算加速的手段,但是這樣的手段非常低效,不符合 VDF
的定義。我們希望能夠找到一種驗證更加迅速的防並行的構造方式。考慮這樣的一個例子:

首先選擇一個數 λ=161 ,然後然後對於任意的輸入 x,我們執行下面的操作 t 次:

1、計算 k=X2
2、取 k 除以 λ 的餘數得到 l
3、令 k 取 l,返回第一步,如果是最後一次操作,輸出結果 y

假設我們的輸入 x=11,t=8 那麼結果爲 95,事實上,如果我們讓 t 取不同的值,把結果都記錄下來,可以得到下述表格:

VDF 究竟是什麼?爲什麼它能受到以太坊的青睞?

更一般地講,如果 a≡b mod m 代表 a 和 b 分別除以 m 的餘數相同的話,那麼上述操作實際上就是計算:

VDF 究竟是什麼?爲什麼它能受到以太坊的青睞?

如果我們知道 λ 的因式分解,例如 161=7×23,那麼我們可以通過兩次指數運算來快速計算出 y 的值。首先計算函數ϕ(161)=(7−1)×(23−1)=132,然後計算 2 t 除以 ϕ(161) 的餘數:

VDF 究竟是什麼?爲什麼它能受到以太坊的青睞?

然後計算 x124 除以 λ的餘數:

VDF 究竟是什麼?爲什麼它能受到以太坊的青睞?

上述過程比起連續平方 8 次看似沒有減輕多少工作量,但實際上當 t 和 λ 非常大(t≈230)時,遠比連續平方快得多。一般地,函數

VDF 究竟是什麼?爲什麼它能受到以太坊的青睞?

如果

VDF 究竟是什麼?爲什麼它能受到以太坊的青睞?

這個函數被稱之爲歐拉函數(Euler’s Totient Function)。上述例子可以一般化爲:

VDF 究竟是什麼?爲什麼它能受到以太坊的青睞?

因此,如果沒有任何人知道 λλ 的因式分解,也就無法快速計算出 ϕ(λ),從而只能重複 t 次平方操作使用

VDF 究竟是什麼?爲什麼它能受到以太坊的青睞?

計算出 y。

事實上,這個構造可以使用羣論得到更加本質的解釋。我們發現,由於模運算 y 的值是小於 λ 的,而所有小於 λ 且與 λ 互素的數一起組成了一個羣(Group) [8],這個羣被稱作整數模 λ 乘法羣 [9],記作 (Z/λZ)。這個羣的階(Order),也就是元素個數就等於歐拉函數 ϕ(λ) 的值。因此,關鍵問題落在瞭如何生成這樣的知道階的羣。

目前主要有兩種方法:

1、使用 RSA 羣
2、使用虛二次域的類羣(The class group of an imaginary quagratic number field)

RSA 羣的生成與 RSA 加密算法類似,選取大素數 p 和 q,其中 p=2 m+1,q=2n+1 且 m,n 均爲素數。令 N=pq,則 (Z/NZ) 即爲所需羣。然而一個很顯然的問題是,這其中涉及到了 trusted setup,我們必須相信生成 N 的參與者不會泄露 p 和 q。我們也可以使得羣生成算法使用公共隨機數來直接選取足夠大的 N 使得因式分解 N 非常困難,但是這樣的 N 需要非常大以至於這樣的方法非常不現實。第二種方法解決了第一種方法的問題,但是由於第二種方法解釋起來涉及概念較多,本篇文章不會涉及。同時,對於結果 yy 的快速驗證需要用到證明系統,有興趣的讀者可以參考 Boneh 的一篇綜述 [10]。

研究與應用現狀

學術界第一次正式提出 VDF 的概念是在 Boneh 的論文中,他在論文中給出了 VDF 的應用場景以及形式化的模型,安全分析和一般構造方法。之後出現了分別出現了兩篇 VDF 的構造論文,分別是 Wesolowski 的 Efficient VDF[11] 以及 Pietrzak 的 Simple VDF[12]。兩者都利用在不知道階的羣中連續做平方運算的方法來構造 VDF,不同的是,他們生成證明的構造有所區別。簡單來講,Wesolowski 的證明更短,驗證更快;但是 Pietrzak 的構造中,生成證明的速度更快,同時證明系統依賴的安全假設更弱。2019 年 Feo 等人 [13] 使用超奇異同源 (Supersingular Isogenies) 以及雙線性對(Bilinear Pairings)構造 VDF。相比於 Wesolowski 和 Pietrzak 的工作,他們的構造本身就是非交互的,不需要經過轉換,同時不需要證明 π 即可完成驗證,但是他們的構造中 Setup 耗費的時間更長,更爲主要的是,目前還只能進行 trusted setup。

在應用領域,Chia Network [14] 計劃使用 VDF 來支持他們的 Proof-of-Space;以太坊研究團隊也打算在以太坊 2.0 中引入 VDF,以期在以太坊 2.0 信標鏈中使用 RANDAO + VDF 隨機選取出塊人。最初 [15] 以太坊計劃使用 RANDAO + VDF 的方案。但由於以太坊 2.0 的計劃瞬息萬變,截至文章最後修改前,以太坊信標鏈計劃將區塊間隔限制到 6 秒,64 個區塊爲一個 epoch,因此一個 epoch 爲 6.4 分鐘,每一個 epoch 需要進行一次出塊人切換,因此 VDF 的時間參數最少應設置爲 6.4 分鐘,但是目前以太坊計劃將其設置爲
102.4 分鐘,目的是防止潛在的攻擊者利用特殊硬件加速 VDF。

來源鏈接:mp.weixin.qq.com