以太坊研究 | 可驗證延遲函式（VDF）介紹
在區塊鏈上實現隨機性是很困難的。當開發者試圖在鏈上獲取一個隨機值時，時常犯的一個錯誤是使用諸如未來區塊的雜湊、區塊難度或時間戳等量（quantities）來獲取隨機值。這種方式的問題在於，這些量很容易受到礦工的操控。比如，假設我們執行一個鏈上博彩遊戲，使用者需要猜測下一個區塊的雜湊是偶數還是奇數。某個礦工可以打賭是偶數，而如果他挖礦的下個區塊雜湊是奇數，則他將丟棄這個區塊。通過丟棄雜湊是奇數的區塊會在一定程度上增加該礦工中彩的機率。
在現實世界中，有許多通過區塊變數（block variables）生成“隨機性”的例子，但這些例子都面臨著一個無法避免的問題，即從計算角度來說，觀察者很容易就能夠知道自己做出的選擇將對鏈上生成的隨機性帶來怎樣的影響 。另一個相關的問題是在權益證明協議中選出領導者（leaders）和驗證者（validators）。在這種情況下，有能力影響或預測隨機性的礦工可以對自身何時被選中去挖礦和生成區塊進行干預。有很多種技術用於克服這一問題，比如共識演算法Ouroboros的可驗證金鑰共享機制（VSS）。然而，這些技術都存在同樣的缺陷：大多數參與者必須誠實且不會串謀。 在上述兩種情況下，攻擊者很容易明白不同的輸入將如何影響偽隨機數生成器（PRNG）生成的結果。 因此，Boneh等人對可驗證延遲函式（VDF，即verifiable delay functions）進行了定義，詳見：https://eprint.iacr.org/2018/601.pdf。VDF是一些需要一定量的連續計算來進行求值的函式，但是一旦找到了解決方案，任何人都可以很容易地驗證該方案的正確性。我們可以將VDF看成對偽隨機數生成器的輸出進行時間延遲，這種延遲可以阻止惡意行為對偽隨機數生成器的輸出造成影響，因為在任何人完成對VDF的計算之前，所有的輸入都將確定下來。在選出領導者方面，VDF可以在很大程度上對可驗證隨機函式（verifiable random functions）加以改善。基於VDF只需通過任何一個誠實的參與者便可以選出領導者，而無需要求大多數參與者都是誠實的。這一方案還將提高系統的魯棒性，因為即使再多的平行計算（parallelism）也無法對VDF計算進行加速，並且任何非惡意參與者都可以輕易地驗證其他人的VDF輸出的正確性。
01
VDF 定義
給定延遲時間t，可驗證延遲函式f必須同時保證：- 連續性：任何人都可以在t個連續步驟內計算f(x)，但任何擁有大量處理器的攻擊者無法通過更少的步驟將f(x)的輸出和隨機數區分開來；
- 可高效驗證性：給定輸出y，任何觀察者都可以在很短時間（即log(t)）內驗證y = f(x)。
假設在一場博彩遊戲中，使用者需要提交一個16位（16 bits）的整數，而獲獎號碼則是通過向需要20分鐘進行計算的VDF提供種子（seed）來確定的。如果某個攻擊者在進行了1分鐘的VDF計算之後就能知道VDF輸出中的4位（4 bits），那該攻擊者就能夠更改自己所提交的整數，使自己中彩的機率提高了16倍！
在談及VDF的結構之前，讓我們先看看為何一個“明顯”但不正確的方法無法解決這一問題。這樣的方法就包括重複進行雜湊運算（repeated hashing）：如果某個雜湊函式h的計算需要 t 個步驟，那通過使用 f = h(h(...h(x))) 作為VDF函式將肯定能夠滿足上面所提到的連續性要求。
確實，參與者將無法通過平行計算來加速計算，因為任何一個雜湊的運用都完全取決於前一個雜湊的輸出。然而，這並不滿足第二個條件，即VDF函式的高效驗證需求。在這種方法中，任何想要驗證 f(x) = y 的參與者都將需要重新計算整條雜湊鏈。我們需要的是，在VDF求值時，在計算時耗費的時間比在驗證時耗費的時間更多，而非更少。
02
VDF 候選結構
目前總共有三種候選結構滿足VDF的要求，只是每種都有自身的缺點。第一種結構是由Boneh等人在最初的VDF論文（https://eprint.iacr.org/2018/601.pdf）中概述的，他們使用單射有理對映（injective rational maps）。- 為了設立VDF函式，需選擇一個時間引數T，一個階數未知的有限阿貝爾群G，以及一個雜湊函式H；
- 假設輸入是X，通過計算y = g2T 讓g = H(x)對VDF進行求值。
現在，假設某人斷言VDF的輸出是某個數字z（可能等於或不等於y）。這意味著z=g^(2^((T/2)) )和v=g^(2^((T/2)) )。由於這兩個等式有同樣的指數，通過核查一個隨機的線性組合（linear combination，如v^(r) z = (g^(r)v)^(2^(T/2))，其中r是{1, … , 2^(λ)}中的隨機數，λ是安全引數）來同時對它們進行驗證。更正式地說，證明者（prover）和驗證者（verifier）需執行以下的互動式證明方案（interactive proof scheme）：
- 證明者計算v = g^(2^(T/2)) 並將v傳送給驗證者；
- 驗證者將 {1, … , 2^1}中的隨機數r傳送給證明者；
- 證明者和驗證者對 g₁= g^(r) v 和z₁= v^(r z)進行計算;
- 證明者和驗證者遞迴地證明z₁ = g₁^(2^(T/2))
03
Pietrzak方案的安全性分析
- 當計算遞迴中的第二步時，我們將得到g₁ = g^(r) v，其中 v = g^(2^(T/2)) m，並需要展示g₁^(T/2 )= v^(r) zm；
- 左邊的m項是m^(T/2)；
- 右邊的m項是m^(r+1)；
- 由於m的階數為d，當r+1 = T/2 mod d時這兩個數會相等，這種情況發生的概率是1/d。
Pietrzak方案的安全性分析假定的是，參與者可以很容易地生成一個滿足低階假設的未知的階數群。下面我們將看到，目前已知的群都不能滿足這些限制條件，保證沒有任何一方能夠推翻該VDF協議。
比如，我們試著使用大家都慣用的群：整數模兩個大素數的乘積（RSA群）。這些群具有未知的階數，因為找到階數將需要對一個大整數進行因式分解。然而，這些群並不滿足低階假設的要求。確實，元素-1的階數總是2。但這種情況可以通過將RSA群G除以子群{1，-1}得出商數（quotient）來解決。事實上，如果G的模數是強素數（使得p-1/2也是素數）的乘積，那麼在取得上述商之後，除了1之外沒有其他低階的元素了。
這一安全分析意味著RSA群對於Pietrzak的VDF方案是安全的，但還有一個問題：為了生成一個RSA群，參與者必須知道如何對模數N進行因式分解。設計一個無需信任的RSA群選擇協議，但沒人知道模數N的因式分解，這在該領域中是一個有趣而重要且有待解決的問題。
實現Pietrzak方案的另一個工作途徑涉及使用虛二次數語的類群。該群系可以通過讓受信任的第三方進行選擇來避免上述問題。簡單地選擇一個大的負素數也能夠產生群，但即使對選擇這個素數的人來說，要確定這個群內的階數在計算上也是不可行的。然而，與RSA群不同，在二次數域的類群中找到低階元素的難度並沒有得到深入的研究。這類方案在落地之前還需要進行更多的研究。
04
VDF的現狀和未解決的問題
此外，Wesolowski方案假設存在某些群，它們能夠滿足一種稱為自適應基本假設（adaptive root assumption）的要求，這在數學文獻中還沒有得到深入的研究。這一領域還存在其他一些未解決的問題，包括構造抗量子VDF，以及ASIC在實踐中破壞VDF結構安全性的可能性。至於VDF在行業中的採用方面，一些區塊鏈領域的公司正嘗試在共識演算法中使用VDF。比如Chia使用了上文中提到的重複平方運算技術。以太坊基金會似乎也在開發一個偽隨機數生成器使RANDAO與VDF相結合。雖然這兩個專案將對區塊鏈社群非常有益，但這一領域的研究仍處於早期階段。【文章版權歸原作者所有，其內容與觀點不代表Unitimes立 場。編譯文章僅為傳播更有價值的資訊】(備註：本文翻譯自作者文章，正文內容涉及一些數字上標和下標的情況，為方便理解，請參考原文。英文原文連結見“版權資訊”。)