如果我們彼此不信任，是否有可能生成隨機數？ 第1部分

嘿哈布爾！

在這篇文章中，我將討論由彼此不信任的參與者產生偽隨機數。 正如我們將在下面看到的，實現一個「幾乎」好的生成器非常簡單，但實現一個非常好的生成器卻很困難。

為什麼有必要在彼此不信任的參與者中產生隨機數？ 應用領域之一是去中心化應用。 例如，接受參與者下注並以 49% 的機率將金額加倍或以 51% 的機率拿走的應用程式只有在能夠無偏見地接收隨機數的情況下才會起作用。 如果攻擊者可以影響隨機數產生器的結果，甚至稍微增加他在應用程式中獲得付款的機會，他將很容易摧毀它。

當我們設計分散式隨機數產生協定時，我們希望它有三個屬性：

1. 他一定是公正的。 換句話說，任何參與者都不應以任何方式影響隨機數產生器的結果。

2. 他一定是難以預測的。 換句話說，任何參與者都不應該能夠在產生數字之前預測將產生什麼數字（或推斷其任何屬性）。

3. 該協議必須是可行的，即能夠抵抗一定比例的參與者與網路斷開連接或故意嘗試阻止該協議的事實。

在本文中，我們將研究兩種方法：RANDAO + VDF 和糾刪碼方法。 在下一部分中，我們將詳細研究基於閾值簽名的方法。

但首先，讓我們來看一個簡單且常用的演算法，它是可行的、不可預測的，但有偏差。

亂道

RANDAO 是一種非常簡單且非常常用的隨機性產生方法。 所有網路參與者首先在本地選擇一個偽隨機數，然後每個參與者發送所選數字的雜湊。 接下來，參與者輪流揭示他們選擇的數字，並對揭示的數字進行異或運算，該運算的結果成為協議的結果。

在洩漏號碼之前發布雜湊值的步驟是必要的，以便攻擊者在看到其他參與者的號碼後無法選擇自己的號碼。 這將使他幾乎能夠單槍匹馬地確定隨機數產生器的輸出。

在協議過程中，參與者需要兩次做出共同決定（所謂的共識）：何時開始透露所選數字，從而停止接受哈希值，以及何時停止接受所選數字併計算生成的隨機數字。 在彼此不信任的參與者之間做出這樣的決定本身並不是一件容易的任務，我們將在以後的文章中回到它；在本文中，我們將假設我們可以使用這樣的共識演算法。

RANDAO 具有我們上面描述的哪些屬性？ 它是不可預測的，與底層共識協議具有同樣的生命力，但它是有偏見的。 具體來說，攻擊者可以觀察網絡，在其他參與者透露他們的號碼後，他可以計算他們的異或，並決定是否透露他的號碼以影響結果。 雖然這可以防止攻擊者單獨確定隨機數產生器的輸出，但仍然給他帶來了 1 位影響力。 如果攻擊者控制多個參與者，那麼他們控制的位元數將等於他們控制的參與者的數量。

透過要求參與者按順序透露數字，可以大大減少攻擊者的影響。 那麼，只有最後打開的情況下，攻擊者才能影響結果。 雖然影響明顯較小，但該演算法仍存在偏差。

蘭道+VDF

使 RANDAO 無偏差的一種方法是：在顯示所有數字併計算 XOR 後，將其結果輸入到函數的輸入中，這需要很長時間來計算，但允許您檢查計算的正確性計算速度非常快。

(vdf_output, vdf_proof) = VDF_compute(input) // это очень медленно
correct = VDF_verify(input, vdf_output, vdf_proof) // это очень быстро

此函數稱為可驗證延遲函數，或 VDF。 如果計算最終結果的時間長於號碼洩漏階段，那麼攻擊者將無法預測顯示或隱藏其號碼的效果，因此他將失去影響結果的機會。

開發優秀的 VDF 極為困難。 最近有一些突破，例如 這 и 這， 這使得 VDF 在實踐中更加實用，以太坊 2.0 計劃長期使用 RANDAO 和 VDF 作為隨機數來源。 除了這種方法是不可預測和公正的事實之外，它還有一個額外的好處，即如果網路上至少有兩個參與者可用（假設所使用的共識協議在處理如此少量的參與者時是可行的），那麼它就可行。

這種方法的最大挑戰是設定 VDF，即使參與者擁有非常昂貴的專用硬件，也無法在發現階段結束之前計算 VDF。 理想情況下，該演算法甚至應該具有顯著的安全裕度，例如 10 倍。 下圖顯示了一個攻擊者的攻擊，該攻擊者擁有專門的 ASIC，這使得他能夠比分配給 RANDAO 確認的時間更快地運行 VDF。 這樣的參與者仍然可以使用或不使用他的號碼來計算最終結果，然後根據計算結果選擇是否顯示。

對於上述VDF系列，專用ASIC的效能可以比傳統硬體高100倍以上。 因此，如果部署階段持續10 秒，那麼在此類ASIC 上計算的VDF 必須花費100 秒以上才能具有10 倍的安全裕度，因此在商用硬體上計算的相同VDF 必須花費100x 100 秒= 約3 小時。

以太坊基金會計劃透過創建自己的公開免費 ASIC 來解決這個問題。 一旦發生這種情況，所有其他協議也可以利用該技術，但在此之前，RANDAO+VDF 方法對於無法投資開發自己的 ASIC 的協議來說將不那麼可行。

有關 VDF 的許多文章、影片和其他資訊已收集在 這個網站.

我們使用糾刪碼

在本節中，我們將了解一個隨機數產生協議，該協議使用 清除程式碼。 它可以容忍最多 ⅓ 的攻擊者，同時保持可行，並允許最多 ⅔ 的攻擊者存在，然後才能預測或影響結果。

該協議的主要思想如下。 為簡單起見，我們假設正好有 100 名參與者。 我們也假設所有參與者本地都有一些私鑰，並且所有參與者的公鑰都是所有參與者都知道的：

1. 每個參與者在本地提出一個長字串，將其分成67 個部分，創建糾刪碼以獲得100 個共享，這樣任何67 個共享就足以恢復該字串，將100 個共享中的每一個分配給其中一個參與者，並使用同一參與者的公鑰。 然後發布所有編碼共享。

2. 參與者使用某種共識來就特定 67 個參與者的編碼集達成一致。

3. 一旦達成共識，每個參與者都會獲取用其公鑰加密的 67 個集合中每個集合中的編碼共享，解密所有此類共享，並發布所有此類解密共享。

4. 一旦67 個參與者完成步驟（3），由於糾刪碼的特性，所有商定的集合都可以被完全解碼和重建，並且最終的數字可以通過參與者在（1）中開始的初始行的異或來獲得。

該協議可以被證明是公正且不可預測的。 所產生的隨機數是在共識後確定的，但直到 XNUMX/XNUMX 的參與者解碼使用其公鑰加密的部分之前，任何人都不知道。 因此，隨機數字是在足以重建隨機數的資訊發布之前確定的。

如果在步驟 (1) 中，其中一個參與者向其他參與者發送的編碼共享不是某些字串的正確擦除代碼，會發生什麼情況？ 如果沒有額外的更改，不同的參與者要么根本無法恢復該字串，要么將恢復不同的字串，這將導致不同的參與者收到不同的隨機數。 為了防止這種情況，您可以執行以下操作：每個參與者除了編碼份額之外，還計算 默克拉樹 所有這些份額，並向每個參與者發送編碼份額本身和默克爾樹的根，以及默克爾樹中包含份額的證明。 在步驟（2）中的共識中，參與者不僅就一組集合達成一致，而且還就此類樹的一組特定根達成一致（如果某個參與者偏離了協議，並向不同的參與者發送了不同的默克爾樹根，並且在共識過程中顯示了兩個這樣的根，該行不包含在結果集中）。 共識的結果，我們將擁有67 條編碼線和相應的默克爾樹根，這樣至少有67 個參與者（不一定是提出相應線的同一個人），他們對於67 條線中的每一條都有帶有擦除代碼份額的消息，以及其份額在相應樹中出現的證明消失了。

當在步驟 (4) 中參與者破解某個字串的 67 個節拍並嘗試從中重建原始字串時，可能有以下選項之一：

1. 恢復字串，然後再次進行擦除編碼，並針對本地計算的份額計算 Merkle 樹，則根與達成共識的根一致。

2. 該行已恢復，但本地計算的根與達成共識的根不符。

3. 該行未恢復。

容易證明，如果上述選項（1）至少發生在一名參與者身上，則選項（1）發生在所有參與者身上，反之亦然，如果選項（2）或（3）發生在至少一名參與者身上，則對所有參與者，選項 (2) 或 (3) 都會發生。 因此，對於集合中的每一行，要么所有參與者都將成功恢復它，要么所有參與者都將無法恢復它。 產生的隨機數只是參與者能夠恢復的行的異或。

閾值簽名

另一種實現隨機性的方法是使用所謂的 BLS 閾值簽章。 基於門限簽章的隨機數產生器具有與上述基於糾刪碼的演算法完全相同的保證，但對於每個產生的數字，透過網路發送的漸近訊息數量明顯較低。

BLS 簽章是一種允許多個參與者為一則訊息建立一個公共簽章的設計。 這些簽名通常用於節省空間和頻寬，因為不需要發送多個簽名。 

BLS 簽章在區塊鏈協定中的一個常見應用，除了產生隨機數之外，就是 BFT 協定中的區塊簽章。 假設有 100 名參與者創建區塊，如果有 67 名參與者簽署，則該區塊被視為最終區塊。 他們都可以提交自己的 BLS 簽章部分，並使用某種共識演算法就其中 67 個部分達成一致，然後將它們合併為一個 BLS 簽章。 任何67 個（或更多）部分都可以用於創建最終簽名，這將取決於組合了哪67 個簽名，因此可能會有所不同，儘管67 個參與者的不同選擇將創建不同的簽名，但任何此類簽名都將是有效的區塊的簽名。 然後，其餘參與者只需透過網路接收和驗證每個區塊的一個簽名，而不是 67 個簽名，這大大減少了網路的負載。

事實證明，如果參與者使用的私鑰是以某種方式產生的，那麼無論聚合哪 67 個（或更多，但不能更少）簽名，得到的簽名都是相同的。 這可以用作隨機性的來源：參與者首先同意他們將簽署的一些訊息（這可能是 RANDAO 的輸出或只是最後一個區塊的哈希值，只要它每次都會改變，這並不重要且是一致的）並為其建立BLS 簽章。 在 67 個參與者提供他們的部分之前，產生的結果將是不可預測的，之後輸出已經被預先確定，並且不能依賴任何參與者的行為。

只要至少 XNUMX/XNUMX 的線上參與者都遵循協議，這種隨機方法就是可行的，並且只要至少 XNUMX/XNUMX 的參與者遵循協議，這種隨機方法就是公正且不可預測的。 值得注意的是，控制超過 ⅓ 但少於 XNUMX/XNUMX 參與者的攻擊者可以阻止協議，但無法預測或影響其輸出。

閾值簽名本身是一個非常有趣的話題。 在本文的第二部分中，我們將詳細分析它們是如何運作的，以及如何準確地產生參與者金鑰，以便將門限簽名用作隨機數產生器。

總之

本文是技術部落格文章系列的第一篇 NEAR。 NEAR 是一個用於開發去中心化應用程式的區塊鏈協議和平台，重點是易於開發且易於最終用戶使用。

協議代碼是開放的，我們的實作是用Rust寫的，可以找到 這裡.

您可以查看 NEAR 的開發情況並在線上 IDE 中進行實驗 這裡.

您可以關注俄語的所有新聞： 電報群 和 VKontakte 群組，以及官方的英文 嘰嘰喳喳.

待會見！

來源： www.habr.com