a16z：如何用去中心化方式構建可公开驗證的隨機性信標？

公共隨機性是許多協議的重要組成部分，但我們仍然缺乏提供高安全性的去中心化隨機性信標。

原文：Public Randomness and Randomness Beacons（a16z crypto）

作者：Joseph Bonneau、Valeria Nikolaenko

編譯：aididiaojp.eth，Foresight News

封面：Photo by Austin Chan on Unsplash

公共隨機性是現實世界安全協議的重要組成部分。在賭博和多人遊戲中，隨機性會增加樂趣。在綠卡辦理、法官案件分配和體育比賽等其他事件中，隨機性提供了一種分配不可分割資源的公平方式。稅務審計或機場的安全抽查等事件同樣具有隨機性。

傳統上，我們依靠受信任的權威來確保隨機的真實性，但在 Web3 世界中，我們有更好的方式來實現這一點。本文將探索通過分布式隨機信標來構建可公开驗證的隨機性的方法，包括一些鏈上應用的實際部署分析。

屬性要求

生成隨機數是一項非常奇妙的事件。許多加密密鑰依賴於錯誤的隨機數生成器，最終導致密鑰被泄露。准確來說這是私人隨機性，只有一方需要生成和使用它。

相比之下，公共隨機性是一個多方參與的過程，大大提高了安全性。而產生安全公共隨機性的協議將具有以下屬性：

• 無偏差性 ：任何攻擊者或攻擊者聯盟都不能使輸出產生偏差。
• 可靠性：沒有攻擊者能夠阻止協議輸出。
• 可驗證性：任何人都可以輕松驗證協議輸出，並且應該看到與其他人相同的輸出。
• 不可預測：如果協議在時間 T 1 產生輸出，那么在某個時間 T 0 <T 1，沒有人能夠預測關於輸出結果的任何事情。

無偏差性是比不可預測性更弱的屬性，因為任何不可預測的協議都必須是無偏差的。如果你能夠對產出結果造成偏差影響，就可以借此做出預測，所以無偏差性的要求弱於不可預測性。例如大多數人預測結果時會依賴於不同的假設，並根據不同的預測來操作，所以實際上不會對其產出造成實質影響。

除了這些屬性之外，該協議還應該能夠高效地運行，並產生大量隨機位數。實際應用中，應用程序產生 128 個隨機位通常就足夠了。為了能作為彩票或資源分配等用途，對於輸出的每個單獨位都應保持不可預測性。理想情況下該協議在通信和計算成本方面也應該是實用的。

不同的協議可能會在不同的條件下實現這些屬性。例如某些協議可能對任何 f 1 個惡意節點的聯盟都是無偏的，並且對任何 f 2 <f 1 個惡意節點的聯盟都是不可預測的。在某些協議中參與者可能能夠將輸出偏置「一位」，這意味着他們可以在兩個可能的輸出之間進行選擇。其他攻擊可能允許他們完全固定輸出。然而通常情況下我們根本無法容忍任何偏見或可預測性。

密碼學解決方案：隨機信標

密碼學家通常從完美的解決方案开始思考。例如在公共隨機性構建中，隨機信標是一種理想化的解決方案，它定期產生滿足所有必要安全要求的隨機輸出。

這種理想化的隨機信標類似於在現實世界中並不存在的隨機預言或通用模型。但存在一個模型可以用來推理公共隨機性協議。

我們可以考慮一些理想隨機信標的近似方案。

• 中心化信標：產生良好隨機性的最簡單方法是通過具有 NIST 隨機性信標或 random.org 等服務的中心化第三方，它根據大氣噪音中的無线電波產生隨機性。這種對第三方的依賴完全破壞了去中心化的理念。在上面的示例中，在無需任何加密證明的情況下，我們必須相信相關組織正在正確地生成隨機性。
• 物理隨機性驗證：許多傳統彩票依賴於公共驗證，例如在一個裝有不同數字的乒乓球容器抽取乒乓球來獲得隨機數。不幸的是這些通常很容易被操縱。例如可以將某些球放在冰箱中，然後根據溫度不同來選擇乒乓球。
• 自然信標：一個常見的想法是使用隨機的自然現象，如天氣或宇宙輻射作為信標。但所有提議的來源都沒有強烈的共識。不同的觀察者會看到略有不同的值，這需要重新引入可信方進行官方測量，這樣就會具有中心化信標的所有缺點。
• 半中心化信標：直接從比特幣區塊頭或股票收盤價中獲取隨機性，這更容易公开驗證，任何一方都更難以完全控制。然而，對工作量證明區塊鏈隨機性和股價隨機性的微妙幹預仍然存在。例如，使用區塊鏈標頭，礦工可以選擇保留標頭產生他們不喜歡的信標值的區塊。或者他們可以選擇在根據首選信標輸出找到兩個碰撞區塊時進行幹預。

去中心化隨機信標 (DRB)

解決中心化信標問題的一種方法是設計一個去中心化密碼協議來確保公共隨機性，這有點像設計去中心化的共識協議，但難度會更高。所有參與者都需要就輸出（隨機性）達成一致，而且協議中的惡意參與者也無法對輸出產生偏見或預測。

旨在模擬隨機信標的協議稱為分布式隨機信標 DRB（又名「distributed coin-flipping」）。DRB 在 1980 年代被驗證是無法解決的，現在由於區塊鏈技術的誕生，有了新的實現可能。如果 DRB 可用於提供鏈上隨機性，這將是構建公平、安全和透明的鏈上應用程序的關鍵要素。

經典方法：承諾 - 披露協議

在樂觀情況下，一個非常簡單的兩輪協議足以滿足 DRB 的需求。在第 1 輪中，每個參與者 i 生成一個隨機值 r i 並發布一個加密承諾 c i = Commit( r i )。在這個過程中，承諾可以簡單地是一個像 SHA-256 這樣的哈希函數。在每個參與者的承諾發布後，他們被鎖定在他們對 r i 的選擇中，但承諾不會透露任何有關其他參與者貢獻的信息。在第 2 輪中，每個參與者通過發布 r i「开啓他們的承諾」。然後組合所有隨機值，散列它們之間的連接。

這個協議很簡單，只要有一個參與者隨機選擇他們的 ri ，就會產生一個隨機信標輸出。不幸的是，它存在一個經典缺陷：當只有一個參與者透露了他們的隨機值時，最後一個參與者能夠計算假定的信標輸出。當他們計算出輸出結果時，就可以根據自己的喜好來選擇是否發布他們的結果或終止協議。而忽略錯誤參與者的貢獻並不能解決問題，因為這仍然讓攻擊者可以在兩個信標輸出之間進行選擇。

區塊鏈為這個問題提供了一種補救措施：每個參與者都可能被要求將一些資金放入托管中，如果他們不透露他們的隨機貢獻，這些資金就會被沒收。這正是以太坊上經典的 RANDAO 信標所採用的方法。這種方法的缺點是輸出仍然可能有偏差，如果托管中的資金少於信標結果上的資金量，這對攻擊者來說可能是值得的。想要更好地抵御偏向攻擊的安全性需要將更多的代幣放入托管中。

承諾 - 披露 - 恢復協議

一些協議不是試圖強迫所有各方透露他們的隨機貢獻，而是包含一個恢復機制，這樣即使少數參與者退出，其余參與者也可以完成協議。協議在任何一種情況下都產生相同的結果，這樣各方就不能通過選擇是否退出來影響輸出結果。

實現此目的的一種方法是讓每個參與者向其他參與者提供祕密的共享，以便他們中的大多數人可以使用例如 Shamir 的祕密共享來重新使用。然而，一個重要的屬性是其他人可以驗證提交的祕密是否已被正確共享，這需要使用更強大的可公开驗證的祕密共享保障（PVSS）。

其他幾種恢復機制也是可以使用的，但它們都有相同的限制。如果有 N 個參與者，並且如果任何最多 f 個節點的組退出，那么任何 Nf 個參與者組都必須能夠計算最終結果。但這也意味着 Nf 參與者的惡意聯盟可以通過私下模擬恢復機制來提前預測結果，這個過程可能發生在協議的第一輪期間，在此期間惡意聯盟可以修改他們自己的隨機性選擇並使結果產生偏差。

換句話說，任何 Nf 個節點的聯盟必須至少包含一個誠實節點。通過簡單的代數，Nf > f，所以 f < N/2，這些協議需要多數的誠實節點。這與原始的 commit-reveal 安全模型有很大不同，後者只需要 f<N（至少一個誠實的參與者）。

這些協議通常還需要大量的通信成本來在協議的每次運行中在所有節點之間共享額外的 PVSS 信息。在過去的幾年裏研究界在這個問題上做了相當多的工作，研究提案包括 RandShare、Scrape、SecRand、HERB 或 Albatross，但似乎都沒有看到實際應用。

基於隨機函數的可驗證協議

在意識到一組 Nf 個參與者可以計算上述協議中的隨機信標值之後，有了一種更簡單的方法：在 N 個參與方之間共享一個長期密鑰，並要求使用它來評估可驗證的隨機函數 (VRF)。密鑰通過 t -out-of- N 閾值方案共享，任何 t 個參與者都可以計算 VRF（但較小的聯盟不能）。對於 t = Nf ，這為 f 個惡意節點提供了與上面討論的承諾 - 披露協議相同的安全彈性。

Dfinity 使用閾值 BLS 籤名（用作 VRF），並率先使用這種方法作為其共識協議的一部分。獨立的 drand 隨機信標使用基本相同的方法，一組參與者閾值 BLS 在每一輪中籤署一個計數器。League of Entropy 是 drand 的开源實例，它是由公司和大學裏的研究小組共同運行，截至 2022 年 9 月共使用 16 個參與節點，每 30 秒產生一次隨機性。

這些方法的缺點是初始化閾值密鑰相對復雜，當節點加入或離开時重新配置密鑰也是如此。但是在常見情況下協議是非常有效。

如上所述，簡單地籤署一個計數器值不會在每輪增加任何新的隨機性，但如果足夠數量的參與者的密鑰被泄露，那么該協議將在未來的每一輪中都是可預測的。

Chainlink VRF 將這種方法（使用 NSEC5 VRF）與請求隨機性的各方指定的外部隨機源相結合，通常是實踐中最常見的區塊鏈標頭。然後數據通過 VRF 饋送，該 VRF 由一方運行或閾值化到一組。

以太坊的信標鏈目前使用基於 BLS 的 VRF：每輪的提議者將其 VRF 值添加到組合中。與 commit-reveal 範例相比，節省了一輪通信（假設長期 BLS 公鑰注冊一次），盡管這種設計繼承了 commit-reveal 方法的一些缺陷，包括通過保留輸出來偏置信標輸出的可能性。

基於延遲函數的可驗證協議

最後一個有前景的新方向是使用基於時間的密碼學驗證，特別是可驗證的延遲函數 ( VDF )。這種方法有望提供良好的通信效率，並具有對 N-1 個惡意節點的防御穩健性。

回到最初的 commit-reveal 安全協議，傳統的承諾可以用定時承諾代替，以消除參與者拒絕透露他們隨機貢獻的問題。定時提交可以由原始提交者或任何愿意計算慢函數（本質上是 VDF）的人有效地完成。因此如果任何參與者退出 commit-reveal 協議，他們的承諾仍然可以被其他人執行。至關重要的是執行承諾的最短時間足夠長，不能在協議的第一輪（提交階段）完成，否則惡意參與者可以足夠快地打开其他人的承諾，從而修改自己的貢獻並影響輸出結果。

現代 VDF 可以實現更實用的一輪協議：完全放棄承諾。每個參與者可以簡單地發布他們的隨機貢獻 r i，最終結果是每個參與者的貢獻的組合通過 VDF 運行。計算 VDF 的時間延遲確保沒有人可以選擇他們的承諾以使最終輸出有偏差。這種方法由 Arjen Lenstra 和 Benjamin Wesolowski 在 2015 年提出，是 VDF 开發中的關鍵激勵應用。

這種方法已經看到了一些實際的部署。Chia 在其共識協議制定中使用了重復平方的 VDF。Starkware 使用基於 SNARK 的 VDF 實現了基於概念驗證的 VDF 信標。以太坊為了在共識層產生隨機性，也計劃使用這種方法，構建一個專用的 ASIC 來計算 VDF。

小結

公共隨機性是許多協議的重要組成部分，但我們仍然缺乏提供高安全性的標准 DRB。上述方法的許多混合和組合都是可能的。例如可以將基於 VRF 的協議與基於 VDF 的協議結合起來，例如 RandRunner。以太坊的信標鏈目前使用 VRF，盡管未來可能會添加 VDF 以消除區塊扣留攻擊的偏見可能性。

什么時候可以接受誠實多數協議也是一個开放的問題。對於一個相對較小的、經過審查的參與者群體，比如 League of Entropy，誠實的多數假設是合理的。另一方面，只需要一個誠實參與者的協議有一個固有的優勢，及更多的參與者只能提高安全性，這意味着這些協議可能會在开放的、無需許可的參與下進行部署。

鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播信息之目的，不構成任何投資建議，如有侵權行為，請第一時間聯絡我們修改或刪除，多謝。