以太坊研究

在區塊鏈上實現隨機性是很困難的。當開發者試圖在鏈上獲取一個隨機值時，時常犯的一個錯誤是使用諸如未來區塊的哈希、區塊難度或時間戳等量（quantities）來獲取隨機值。這種方式的問題在於，這些量很容易受到礦工的操控。比如，假設我們運行一個鏈上博彩遊戲，用戶需要猜測下一個區塊的哈希是偶數還是奇數。某個礦工可以打賭是偶數，而如果他挖礦的下個區塊哈希是奇數，則他將丟棄這個區塊。通過丟棄哈希是奇數的區塊會在一定程度上增加該礦工中彩的幾率。在現實世界中，有許多通過區塊變量（block variables）生成“隨機性”的例子，但這些例子都面臨著一個無法避免的問題，

01

VDF 定義

1. 連續性：任何人都可以在t個連續步驟內計算f(x)，但任何擁有大量處理器的攻擊者無法通過更少的步驟將f(x)的輸出和隨機數區分開來；
2. 可高效驗證性：給定輸出y，任何觀察者都可以在很短時間（即log(t)）內驗證y = f(x)。

換句話說，VDF函數在計算方面（即便是在高度並行的處理器上）花費的時間要比在單個處理器上進行驗證所花費的時間要多得多。此外，驗證者接受錯誤的VDF輸出的可能性必須非常小（驗證者在初始化時由安全參數λ進行選擇）。在達到最終結果之前，任何人都無法將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進行求值需要進行大量的並行處理（parallel processing），這也導致Boneh等人稱之為“弱VDF”。之後，Pietrzak和Wesolowski不約而同地通過重複平方運算（repeated squaring）得出了高度相似的VDF結構。以下是Pietrzak方案的運行方式：

1. 為了設立VDF函數，需選擇一個時間參數T，一個階數未知的有限阿貝爾群G，以及一個哈希函數H；
2. 假設輸入是X，通過計算y = g2T 讓g = H(x)對VDF進行求值。

重複平方計算是不可並行的，並且在完成最後的平方運算之前是無法揭示出計算結果的。這是因為我們不知道阿貝爾群G的階數。但這將導致攻擊者通過使用群論（group theory）來加速計算過程。

現在，假設某人斷言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）：

1. 證明者計算v = g^(2^(T/2)) 並將v發送給驗證者；
2. 驗證者將 {1, … , 2^1}中的隨機數r發送給證明者；
3. 證明者和驗證者對 g₁= g^(r) v 和z₁= v^(r z)進行計算;
4. 證明者和驗證者遞歸地證明z₁ = g₁^(2^(T/2))

上述方案可以通過Fiat-Shamir啟發式算法來實現非交互。藉此，證明者通過對(G,g,z,T,v)進行哈希，在遞歸的每個等級生成一個挑戰r，並在證明中附加v。在這種情況下，證明中就包含了 log₂ T 個元素，並要求接近於(1 + 2/√T) T。

03

Pietrzak方案的安全性分析

1. 當計算遞歸中的第二步時，我們將得到g₁ = g^(r) v，其中 v = g^(2^(T/2)) m，並需要展示g₁^(T/2 )= v^(r) zm；
2. 左邊的m項是m^(T/2)；
3. 右邊的m項是m^(r+1)；
4. 由於m的階數為d，當r+1 = T/2 mod d時這兩個數會相等，這種情況發生的概率是1/d。

如果你想進一步瞭解為什麼低階假設是Pietrzak方案完備性的充要條件，可以查看Boneh最近關於VDF結構的調查報告: http://crypto.stanford.edu/~dabo/papers/VDFsurvey.pdf

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立 場。編譯文章僅為傳播更有價值的信息】(備註：本文翻譯自作者文章，正文內容涉及一些數字上標和下標的情況，為方便理解，請參考原文。英文原文鏈接見“版權信息”。)

閱讀更多 比特幣資訊 的文章

關鍵字: 隨機 獲取 科技