NEAR：區塊鏈協議中的隨機性
Last updated
Last updated
我們今天發表了一篇簡短的論文，描述了 NEAR 協議中使用的隨機信標。在這篇隨附的博客文章中，我們討論了為什麼隨機性很重要，為什麼它很難，以及它在其他協議中是如何解決的。
許多現代區塊鏈協議，包括 NEAR，都依賴隨機源來選擇在協議中執行某些操作的參與者。如果惡意行為者可以影響這種隨機性來源，他們可以增加被選中的機會，並可能危及協議的安全性。
分佈式隨機性也是構建在區塊鏈上的許多分佈式應用程序的關鍵組成部分。例如，接受參與者投注並支付兩倍金額的 49% 而沒有支付 51% 的智能合約假設它可以獲得一個無偏的隨機數。如果惡意行為者可以影響或預測隨機數，他們可以增加在智能合約中獲得支付的機會，並將其耗盡。
當我們設計一個分佈式隨機算法時，我們希望它具有三個屬性：
它必須是不偏不倚的。換句話說，任何參與者都不能以任何方式影響隨機發生器的結果。
它需要是不可預測的。換句話說，任何參與者都不能在生成之前預測將生成什麼數字（或對其任何屬性的推理）。
協議需要容忍一定比例的參與者離線或試圖故意停止協議。
在本文中，我們將介紹分佈式隨機信標的基礎知識，討論為什麼簡單的方法不起作用。最後，我們將介紹 DFinity、Ethereum Serenity 和 NEAR 使用的方法，並討論它們的優缺點。
RANDAO 是一種非常簡單且因此非常常用的隨機性方法。總體思路是，網絡的參與者首先都私下選擇一個偽隨機數，向這個私下選擇的數字提交一個承諾，所有人都使用某種共識算法就一組承諾達成一致，然後都透露他們選擇的數字，達成一個對顯示的數字達成共識，並將顯示的數字的 XOR 作為協議的輸出。
它是不可預測的，並且具有與底層共識協議相同的活性，但有偏見。具體來說，一旦其他人開始透露他們的號碼，惡意行為者就可以觀察網絡，並根據迄今為止觀察到的號碼的異或來選擇透露或不透露他們的號碼。這允許單個惡意行為者對輸出產生一點影響，而控制多個參與者的惡意行為者俱有與他們控制的參與者數量一樣多的影響。
為了使 RANDAO 無偏見，一種方法是使輸出不僅僅是 XOR，而是比分配的顯示數字所需的時間更多的執行時間。如果最終輸出的計算時間比揭示階段的時間長，則惡意行為者無法預測他們揭示或不揭示其數量的效果，因此無法影響結果。
雖然我們希望計算隨機性的函數為生成隨機數的參與者花費很長時間，但我們希望隨機數的用戶不必再次執行相同的昂貴函數。因此，他們需要以某種方式快速驗證隨機數是否正確生成，而無需重新進行昂貴的計算。
這種計算時間長、計算驗證速度快、每個輸入都有唯一輸出的函數稱為可驗證延遲函數（簡稱VDF），事實證明設計一個非常複雜。最近有多項突破，即這一突破和這一突破，以太坊目前計劃使用帶有 VDF 的 RANDAO 作為他們的隨機信標。除了這種方法不可預測且無偏見之外，它還有一個額外的優勢，即即使只有兩個參與者在線也具有活躍性（假設底層共識協議在參與者很少的情況下具有活躍性）。
這種方法的最大挑戰是 VDF 需要以這樣一種方式進行配置，即使是擁有非常昂貴的專用硬件的參與者也無法在揭示階段結束之前計算 VDF，並且理想情況下具有一些有意義的安全餘量，例如 10 倍。下圖顯示了一個參與者的攻擊，該參與者擁有一個專門的 ASIC，允許他們運行 VDF 的速度比分配給揭示 RANDAO 承諾的時間快。這樣的參與者仍然可以計算有和沒有他們的份額的最終輸出，並根據這些輸出選擇顯示或不顯示：
對於鏈接在專用 ASIC 之上的 VDF 系列，其速度可能比傳統硬件快 100 倍以上。因此，如果揭示階段持續 10 秒，則在此類 ASIC 上計算的 VDF 必須花費超過 100 秒才能獲得 10 倍的安全裕度，因此在傳統硬件上計算的相同 VDF 需要花費 100 x 100 秒 = ~3 小時.
以太坊基金會計劃解決這個問題的方式是設計自己的 ASIC 並免費公開提供。一旦發生這種情況，所有其他協議都可以利用該技術，但在此之前，RANDAO + VDF 方法對於無法投資設計自己的 ASIC 的協議來說並不可行。
由 Dfinity 開創的另一種隨機性方法是使用所謂的閾值 BLS 簽名。 （有趣的是，Dfinity 僱傭了 BLS 中的 L 人物 Ben Lynn）。
BLS 簽名是一種允許多方在消息上創建單個簽名的結構，通常用於通過不需要發送多個簽名來節省空間和帶寬。區塊鏈中 BLS 簽名的常見用法是在 BFT 協議中籤名塊。假設 100 名參與者創建了區塊，如果其中 67 人簽署了一個區塊，則該區塊被認為是最終的。他們都可以提交自己的部分 BLS 簽名，然後使用某種共識算法對其中的 67 個達成一致，然後將它們聚合成一個 BLS 簽名。任何 67 個部分都可用於創建累積簽名，但生成的簽名將不同，具體取決於聚合的 67 個簽名。
事實證明，如果參與者使用的私鑰是以特定方式生成的，那麼無論聚合什麼 67 個（或更多，但不是更少）簽名，生成的多重簽名都是相同的。這可以用作隨機性的來源：參與者首先同意他們將簽署的一些消息（它可能是 RANDAO 的輸出，或者只是最後一個塊的哈希，只要它是每次都不同並達成一致），並在其上創建多重簽名。在 67 名參與者提供他們的零件之前，輸出是不可預測的，但即使在提供第一部分之前，輸出已經預先確定並且不受任何參與者的影響。
這種隨機性方法是完全無偏見且不可預測的，並且只要 2/3 的參與者在線（儘管可以針對任何閾值進行配置），它就會一直存在。雖然 ⅓ 離線或行為不端的參與者可能會停止算法，但至少需要 ⅔ 參與者合作才能影響輸出。
但是，有一個警告。上面，我提到這個方案的私鑰需要以特定的方式生成。密鑰生成過程，稱為分佈式密鑰生成，簡稱 DKG，非常複雜，是一個積極研究的領域。在最近的一次會談中，Dfinity 提出了一種非常複雜的方法，其中涉及 zk-SNARKs，這是一種非常複雜且未經時間測試的加密結構，作為其中的步驟之一。一般來說，對閾值簽名，尤其是 DKGs 的研究還沒有處於可以輕鬆應用於實踐的狀態。
NEAR 方法受到另一種稱為RandShare的算法的影響。 RandShare 是一種無偏見且不可預測的協議，可以容忍多達 1/3 的參與者是惡意的。它相對較慢，並且鏈接的論文還描述了兩種加速方法，稱為 RandHound 和 RandHerd，但與 RandShare 本身不同，RandHound 和 RandHerd 相對複雜，而我們希望協議非常簡單。
RandShare 的普遍問題除了交換的大量消息（參與者將一起交換 O(n^3) 條消息）外，事實上，雖然 ⅓ 在實踐中是一個有意義的活躍度閾值，但影響的能力卻很低。輸出。有幾個原因：
影響輸出的好處可能大大超過停止隨機性的好處。
如果參與者控制了超過 1/3 的 RandShare 參與者並使用它來影響輸出，則不會留下任何痕跡。因此，惡意行為者可以在不被發現的情況下做到這一點。拖延共識是自然可見的。
某人控制 1/3 的算力/權益的情況並非不可能，並且鑑於上述 (1) 和 (2)，擁有此類控制權的人不太可能試圖阻止隨機性，但可以並且可能會嘗試影響它。
我們最近發表的一篇論文中描述了 NEAR 方法。它是無偏見且不可預測的，並且可以容忍多達 1/3 的惡意行為者的活躍性，即如果有人控制 1/3 或更多的參與者，他們可以停止協議。
但是，與 RandShare 不同的是，它最多可以容忍 ⅔ 的惡意行為者，然後才能影響輸出。這對於實際應用來說是明顯更好的閾值。
該協議的核心思想如下（為簡單起見，假設正好有 100 個參與者）：
每個參與者拿出他們自己的輸出部分，將其分成 67 個部分，對其進行擦除編碼以獲得 100 個共享，這樣任何 67 個都足以重建輸出，將 100 個共享中的每一個分配給一個參與者並用該參與者的公鑰。然後他們共享所有編碼的共享。
參與者使用一些共識（例如 Tendermint）來就這些來自 67 個參與者的編碼集達成一致。
一旦達成共識，每個參與者都會獲取以這種方式發布的 67 個集合中的每個集合中的編碼共享，這些共享是用他們的公鑰編碼的，然後解碼所有這些共享並立即發布所有這些解碼的共享。
一旦至少有 67 名參與者完成了步驟 (3)，所有商定的集合都可以被完全解碼和重建，最終的數字可以作為參與者在 (1) 中提出的初始部分的 XOR 獲得。
該協議為何無偏見和不可預測的想法類似於 RandShare 和閾值簽名的想法：最終輸出是在達成共識後決定的，但直到 ⅔ 的參與者解密用他們的公鑰加密的共享時，任何人都不知道。
處理所有極端情況和可能的惡意行為使其稍微複雜一些（例如，參與者需要處理步驟（1）中有人創建無效糾刪碼的情況），但總的來說整個協議非常簡單，例如用所有證明、相應的密碼原語和參考來描述它的整篇論文只有 7 頁長。如果您想閱讀更正式的算法描述，或者對其活性和抗影響性的分析，請務必查看它。
利用糾刪碼的類似想法已經在 NEAR 的現有基礎設施中使用，其中特定時期的塊生產者創建所謂的塊，其中包含特定分片的所有事務，並分發這些塊的糾刪碼版本向其他區塊生產者提供 merkle 證明，以確保數據可用性。
