a16z：通過去中心化隨機信標構建 Web3 公共隨機性

創作者：Joseph Bonneau 和 Valeria Nikolaenko

翻譯者：[email protected]

審核者：[email protected]

原文：Public Randomness and Randomness Beacons

共隨機性是許多現實世界安全協議的重要組成部分。在某些應用程序中，例如賭博和多人遊戲，隨機性會增加樂趣。在其他應用中，隨機性提供了一種公平的方式來分配不可分割的資源，從綠卡到巡迴法院法官的案件分配，再到體育比賽的種子。它還用於分配負面資源，例如稅務審計或機場的二次安檢。

傳統上，我們依賴受信任的權威來為這些協議生成隨機性，但在 web3 世界中，我們需要做得更好。在這篇文章中，我們將探索通過分佈式隨機信標構建可公開驗證的隨機性的方法，然後討論一些鏈上應用程序。（即將發布的第二部分將特別關注領導人選舉，同時提供對替代領導人選舉方法的評估。）

預期屬性

生成隨機數是一項眾所周知的微妙任務。例如，許多加密密鑰已經泄露，因為它們依賴於一個有缺陷的隨機數生成器（Cloudflare 的熔岩燈牆可以作為一種創造性的緩解措施）。然而，這只是私人隨機性，只有一方需要生成和使用它。

相比之下，公共隨機性是一個多方參與過程，這大大增加了難度。產生公共隨機性的良好協議將具有以下安全屬性：

• 無偏倚：任何攻擊者或攻擊者聯盟都不應該能夠使輸出產生偏差。可靠：任何攻擊者都不能阻止協議產生輸出。
• 可驗證：任何人都可以輕鬆驗證協議輸出，並且應該看到與其他人相同的輸出。
• 不可預測：如果協議在 T1 時間產生輸出，那麼在某個時間 T0＜T1 之前，沒有人應該能夠預測關於輸出的任何事情，理想情況下，T0 非常接近 T1。

無偏倚是比不可預測性更弱的屬性，因為任何不可預測的協議都必須是無偏的。計算機科學家會說，無偏倚會降低為不可預測性，因為如果你有偏見，你就可以預測。但有時我們會想要分別推理它們，因為它們可能依賴於不同的假設——例如，不誠實的多數人可能會預測結果，但不會對其產生偏見。

除了這些屬性之外，該協議還應該能夠高效地運行併產生大量隨機位。（在實踐中，應用程序生成 128 個隨機位通常就足夠了，使用它們來播種偽隨機數生成器 [PNRG] 以根據需要輸出更多位。但是，對於輸出的每個單獨位都應保持不可預測性，以用於此類應用程序作為彩票或資源分配。）理想情況下，該協議在通信和計算成本方面也應該是有效的。

不同的協議可能會在不同的條件下實現這些屬性。例如，某些協議可能不受任何 f1 惡意節點聯盟的偏見，並且無法被任何 f2＜f1 惡意節點聯盟預測。也有不同程度的偏見。例如，在某些協議中，參與者可能能夠將輸出偏置“一位”——這意味着他們可以在兩個可能的輸出之一之間進行選擇。其他攻擊可能允許他們完全修復輸出。然而，通常情況下，我們根本不想容忍任何偏見（或可預測性）。

密碼學理想：隨機信標

密碼學家通常從考慮問題的理想解決方案開始。在公共隨機性的情況下，隨機信標是一種理想化的服務，它定期產生滿足所有必要安全要求的隨機輸出。

這種理想化的隨機信標，類似於其他加密抽象——例如隨機預言或通用組模型——在現實世界中並不存在。但這是一個有用的目標，也是一個有用的模型來推理依賴公共隨機性的協議。

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

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

去中心化隨機信標 (DRB)

解決集中式信標問題的一種自然方法是設計一個分散的密碼協議來產生公共隨機性。這個問題有點像設計去中心化的共識協議，只是更難。不僅所有參與者都需要就輸出（隨機性）達成一致，而且協議中的惡意參與者也不應該對輸出產生偏見或預測。

旨在模擬隨機信標的協議稱為分佈式隨機信標 (DRB)。（其他名稱包括“distributed coin-flipping”。）這個問題已經研究了幾十年，在 1980 年代證明了著名的不可能結果，但在區塊鏈時代重新點燃了興趣。DRB 可用於提供鏈上隨機性，這將是公平、安全和透明的鏈上應用程序的關鍵要素。

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

在樂觀情況下，一個非常簡單的兩輪協議足以滿足 DRB 的需求。在第 1 輪中，每個參與者 i 生成一個隨機值 ri 併發布一個密碼承諾 ci=Commit(ri)。在這個應用程序中，承諾可以簡單地是一個像 SHA-256 這樣的哈希函數。在每個參與者的承諾發布后，他們被鎖定在他們選擇的 ri 中，但承諾不會透露有關其他參與者貢獻的任何信息。在第 2 輪中，每個參與者通過發布 ri 來“開啟他們的承諾”。然後組合所有隨機值，例如通過對它們進行異或或（最好）散列它們的連接。

該協議很簡單，只要其中一個參與者隨機選擇他們的 ri，就會產生隨機信標輸出。不幸的是，它存在一個典型的缺陷：當所有參與者都透露了他們的隨機值時，最後一個參與者能夠計算假定的信標輸出。如果他們不喜歡它，他們可以拒絕發布他們的值，中止協議。忽略錯誤參與者的貢獻並不能解決問題，因為這仍然讓攻擊者在兩個信標輸出之間進行選擇（一個用他們的貢獻計算，一個不計算）。

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

承諾-披露-恢復協議

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

實現這一目標的一種方法是讓每個參與者向其他參與者提供其秘密的共享，以便他們中的大多數人可以使用例如 Shamir 的秘密共享來重建它。然而，一個重要的屬性是其他人可以驗證提交的秘密是否已被正確共享，這需要使用更強大的原語，稱為可公開驗證的秘密共享 (PVSS)。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

在第二部分中，我們將討論隨機領導者選舉在共識協議中的具體應用，其設計目標略有不同，因此提出了更多的協議和方法。

本文作者簡介

Joseph Bonneau 是 a16z crypto 的研究合伙人。研究重點是應用密碼學和區塊鏈安全。曾在墨爾本大學、紐約大學、斯坦福大學和普林斯頓大學教授加密貨幣課程，並獲得了劍橋大學的計算機科學博士學位和斯坦福大學的學士/碩士學位。

Valeria Nikolaenko 是 a16z crypto 的研究合伙人。研究重點是密碼學和區塊鏈安全、PoS 共識協議中的遠程攻擊、簽名方案、后量子安全和多方計算等主題。Valeria Nikolaenko 在 Dan Boneh 教授的指導下獲得了斯坦福大學的密碼學博士學位，並作為核心研究團隊的一員從事 Diem 區塊鏈工作。