主持人 > 博客 > 管理 > 隨機數與去中心化網路：實現

隨機數與去中心化網路：實現

介紹

function getAbsolutelyRandomNumer() {
        return 4; // returns absolutely random number!
}

與密碼學中絕對強密碼的概念一樣，真正的「公開可驗證隨機信標」（以下簡稱 PVRB）協議只是嘗試盡可能接近理想方案，因為在實際網路中，它不以其純粹的形式適用：必須嚴格同意一位，必須有很多輪，並且所有訊息必須非常快並且始終傳遞。 當然，實際網路中並非如此。 因此，在為現代區塊鏈中的特定任務設計PVRB時，除了無法控制由此產生的隨機性和加密強度之外，還會出現更多純粹的架構和技術問題。

對於PVRB來說，區塊鏈本身本質上是一種通訊媒介，其中訊息=交易。 這允許您部分地從網路問題、訊息未傳遞、中間件問題中抽像出來 - 所有這些風險都由去中心化網路承擔，並且它對 PVRB 的主要價值是無法撤銷或破壞已發送的交易 - 這確實不允許參與者拒絕參與協議，除非他們對共識進行了成功的攻擊。 這種安全等級是可以接受的，因此 PVRB 應該能夠像主區塊鏈一樣抵抗參與者的串通。 此外，這也暗示，如果網路就主區塊鏈達成一致，即使它也同意唯一公平的隨機結果，PVRB 也必須成為共識的一部分。 或者，PVRB 只是一個由智能合約實現的獨立協議，該協議相對於區塊鏈和區塊非同步工作。 兩種方法都有其優點和缺點，它們之間的選擇非常重要。

PVRB的兩種實作方式

讓我們更詳細地描述實現PVRB 的兩種選項：獨立版本，使用獨立於區塊鏈的智能合約進行工作；以及共識集成版本，內置於協議中，根據該版本，網絡就區塊鏈和協議達成一致。交易納入其中。 在所有情況下，我指的是流行的區塊鏈引擎：以太坊、EOS 以及所有在託管和處理智慧合約方面與它們類似的引擎。

獨立合約

在這個版本中，PVRB 是一個智能合約，它接受隨機生產者（以下簡稱 RP）的交易，對其進行處理，組合結果，並最終得出任何用戶可以從該合約接收的某個值。 該值可能不會直接儲存在合約中，而是僅由資料表示，從中可以確定性地獲得結果隨機的一個且僅一個值。 在這個方案中，RP是區塊鏈的用戶，任何人都可以參與生成過程。

獨立合約的選項很好：

  • 可移植性（合約可以從區塊鏈拖到區塊鏈）
  • 易於實施和測試（合約易於編寫和測試）
  • 實施經濟方案的便利性（很容易製作自己的代幣，其邏輯服務於PVRB的目的）
  • 在已經運行的區塊鏈上啟動的可能性

它也有缺點：

  • 對運算資源、交易量和儲存（即cpu/mem/io）的嚴格限制
  • 合約內操作的限制（不是所有指令都可用，很難連接外部庫）
  • 無法比區塊鏈中包含的交易更快地組織訊息傳遞

此選項適合實現需要在現有網路上運作、不包含複雜的密碼學且不需要大量互動的PVRB。

共識整合

在此版本中，PVRB 在區塊鏈節點程式碼中實現，內建或與區塊鏈節點之間的訊息交換並行運行。 協定的結果直接寫入產生的區塊中，協定訊息透過節點之間的 p2p 網路發送。 由於協議產生的數字要寫入區塊中，因此網路必須就它們達成共識。 這意味著 PVRB 訊息與交易一樣，必須由節點驗證並包含在區塊中，以便任何網路參與者都可以驗證是否符合 PVRB 協議。 這自然而然地為我們帶來了顯而易見的解決方案——如果網路就一個區塊及其中的交易達成共識，那麼 PVRB 應該成為共識的一部分，而不是一個獨立的協議。 否則，有可能一個區塊從共識的角度來看是有效的，但沒有遵循PVRB協議，從PVRB的角度來看該區塊不能被接受。 因此，如果選擇「共識整合」選項，PVRB 就成為共識的重要組成部分。

在網路共識層級描述 PVRB 實作時，無論如何都無法避免最終性問題。 最終性是確定性共識中使用的機制，它鎖定最終的區塊（以及通往該區塊的鏈），即使發生並行分叉，也永遠不會被丟棄。 例如，在比特幣中就沒有這樣的機制——如果你發布了一條更複雜的鏈，它將取代任何不太複雜的鏈，無論鏈的長度如何。 以 EOS 為例，最後的區塊是所謂的最後不可逆區塊，平均每 432 個區塊出現一次（12*21 + 12*15，預投票 + 預先提交）。 這個過程本質上是在等待2/3的區塊生產者（以下簡稱BP）簽署。 當出現比最後一個 LIB 更舊的分叉時，它們會被簡單地丟棄。 這種機制可以保證交易被包含在區塊鏈中並且永遠不會回滾，無論攻擊者擁有什麼資源。 此外，最終的區塊是由 Hyperledger、Tendermint 和其他基於 pBFT 的共識中的 2/3 BP 簽署的區塊。 此外，制定一個確保最終性的協議作為共識的附加組件也是有意義的，因為它可以與區塊的生產和發布非同步工作。 這是一個很好的 文章 關於以太坊的最終性。

最終性對於用戶來說極其重要，如果沒有最終性，他們可能會發現自己是「雙花」攻擊的受害者，其中BP「持有」區塊，並在網路「看到」良好交易後發布它們。 如果沒有最終確定性，則發布的分叉會將具有「好」交易的區塊替換為來自「壞」分叉的另一個區塊，其中相同的資金被轉移到攻擊者的地址。 就PVRB而言，最終性的要求更加嚴格，因為為PVRB構建分叉意味著攻擊者有機會準備多個隨機選項以發布最有利可圖的選項，並且限制可能的攻擊時間是一種選擇好的解決方案。

因此，最好的選擇是將PVRB和最終性結合到一個協議中——然後最終確定的區塊=最終確定的隨機數，而這正是我們需要得到的。 現在玩家將在 N 秒內收到保證的隨機數，並且可以確定不可能回滾或再次重播。

共識集成選項很好：

  • 與區塊的生成相關的非同步實現的可能性 - 區塊像往常一樣生成，但同時，PVRB 協定可以工作，這不會為每個區塊產生隨機性
  • 能夠實施重型加密技術，而不受智能合約的限制
  • 組織訊息交換的速度比區塊鏈中包含的交易更快，例如，協議的一部分可以在節點之間工作，而無需透過網路分發訊息

它也有缺點：

  • 測試和開發方面的困難 - 您將不得不模擬網路錯誤、遺失節點、網路硬分叉
  • 實作錯誤需要網路硬分叉

這兩種實現 PVRB 的方法都具有生命權，但現代區塊鏈中智能合約的實現在計算資源方面仍然相當有限，而且向嚴格的密碼學的任何過渡通常都是不可能的。 我們將需要嚴格的密碼學，如下所示。 雖然這個問題顯然是暫時的，但需要在合約中進行嚴格的密碼學來解決許多問題，並且它正在逐漸出現（例如，以太坊中 zkSNARKs 的系統合約）

區塊鏈提供了透明且可靠的協議訊息傳遞通道，但它並不是免費的。 任何去中心化協議都必須考慮到 Sybil 攻擊的可能性；任何行動都可以透過多個帳戶的協同力量來完成，因此，在設計時，需要考慮到攻擊者創建任意數量協議的能力參與者串通一氣。

PVRB 和區塊變數。

當我說還沒有人在區塊鏈中實施經過許多賭博應用程式測試的良好 PVRB 時，我並沒有撒謊。 那麼以太坊和EOS上這麼多的賭博應用程式從哪裡來呢？ 這讓我感到驚訝，也讓你感到驚訝，他們從哪裡在完全確定性的環境中獲得如此多的「持久」隨機數？

在區塊鏈中獲得隨機性的最喜歡的方法是從區塊中獲取某種「不可預測」的信息，並根據它生成一個隨機資訊 - 只需對一個或多個值進行散列即可。 關於此類方案問題的好文章 這裡。 你可以取區塊中任何「不可預測」的值，例如區塊哈希、交易數量、網路複雜度以及其他提前未知的值。 然後對它們進行哈希處理，一個或多個，理論上，你應該得到一個真正的隨機數。 您甚至可以在白皮書中添加您的方案是「後量子安全」的（因為存在量子證明雜湊函數:)）。

但唉，即使是後量子安全哈希也是不夠的。 秘訣在於PVRB的要求，讓我從上一篇文章提醒您：

  1. 結果必須具有可證明的均勻分佈，即基於可證明的強密碼學。
  2. 無法控制結果的任何位元。 因此，結果無法提前預測。
  3. 您不能透過不參與協議或透過攻擊訊息使網路過載來破壞生成協議
  4. 上述所有內容都必須能夠抵禦允許數量的不誠實協議參與者（例如 1/3 的參與者）的串通。

在這種情況下，只滿足要求1，不滿足要求2，透過對區塊中不可預測的值進行散列，我們將得到均勻的分佈和良好的隨機性。 但英國石油公司至少可以選擇「是否發布該區塊」。 因此，BP 至少可以從兩個隨機選項中進行選擇：「它自己的」和如果其他人出塊就會出現的選項。 BP 可以提前「窺探」如果他發布了一個區塊將會發生什麼，並簡單地決定做或不做。 因此，例如，當玩輪盤賭中的“奇數”或“紅/黑”時，只有當他看到勝利時，他才能發佈區塊。 這也使得使用「來自未來」的區塊哈希等策略變得不可行。 在這種情況下，他們說「將使用隨機數，它是透過對當前資料和高度為 N + 42 的未來區塊的哈希值進行哈希而獲得的，其中 N 是當前區塊的高度。 這稍微加強了該計劃，但仍然允許 BP（儘管是在未來）選擇持有區塊還是發布區塊。

在這種情況下BP軟體變得更加複雜，但也不是很多。 簡而言之，當驗證交易並將其包含在區塊中時，會快速檢查是否會獲勝，並且可能會選擇交易參數以獲得較高的獲勝機率。 同時，要抓住一個聰明的 BP 進行此類操縱幾乎是不可能的；每次你都可以使用新地址並一點點獲勝而不引起懷疑。

因此使用來自區塊的資訊的方法不適合作為PVRB的通用實作。 在有限版本中，由於賭注大小、玩家數量和/或 KYC 註冊限制（以防止一名玩家使用多個地址），這些方案可以適用於小型遊戲，但僅此而已。

PVRB 和提交顯示。

好的，這要歸功於散列以及至少塊散列和其他變數的相對不可預測性。 如果你解決了搶先交易礦工的問題，你應該會得到更合適的東西。 讓我們將使用者新增至該方案 - 讓他們也影響隨機性：任何技術支援員工都會告訴您，IT 系統中最隨機的事情是使用者的操作:)

當使用者簡單地發送隨機數字並且將結果計算為例如其總和的雜湊時，天真的方案是不合適的。 在這種情況下，最後一個玩家可以透過選擇自己的隨機數來控制結果。 這就是使用廣泛使用的提交-顯示模式的原因。 參與者首先發送隨機數中的雜湊值（提交），然後自己打開隨機數（顯示）。 「揭示」階段僅在收集了必要的提交後才開始，因此參與者可以準確地發送他們之前發送的隨機雜湊值。 現在，讓我們將所有這些與一個區塊的參數放在一起，這比從未來獲取的參數更好（隨機性只能在未來的區塊之一中找到），瞧 - 隨機性已經準備好了！ 現在，任何玩家都可以影響由此產生的隨機性，並且可以通過用自己的、事先未知的隨機性覆蓋它來“擊敗”惡意BP……您還可以通過在揭示階段不打開協議來添加針對破壞協議的保護- 簡單地要求在提交交易時附加一定金額的保證金，該保證金僅在披露過程中才會退還。 在這種情況下，承諾而不透露將是無利可圖的。

這是一個很好的嘗試，這樣的方案也存在於遊戲 DApp 中，但可惜，這又是不夠的。 現在不僅是礦工，協議的任何參與者都可以影響結果。 仍然可以控制價值本身，變化性較小且有一定成本，但是，就像礦工的情況一樣，如果抽獎結果比參與 PVRB 協議的費用更有價值，那麼隨機-生產者（RP）可以決定是否公開，並且仍然可以從至少兩個隨機選項中進行選擇。
但懲罰那些犯下罪行但不透露的人成為可能，這個計劃將會派上用場。 它的簡單性是一個重要的優勢——更嚴格的協定需要更強大的計算。

PVRB 和確定性簽名。

還有另一種方法可以強制 RP 提供偽隨機數，如果提供“原像”，則它無法影響該偽隨機數 - 這是確定性簽名。 這樣的簽章例如是RSA，而不是ECS。 如果RP 有一對金鑰：RSA 和ECC，並且他用自己的私鑰簽署某個值，那麼在RSA 的情況下，他將獲得一個且只有一個簽名，在ECS 的情況下，他可以產生任意數量的簽名不同的有效簽名。 這是因為在建立 ECS 簽章時，會使用由簽署者選擇的隨機數，並且可以以任何方式選擇該隨機數，從而使簽署者有機會選擇多個簽名之一。 對於 RSA：「一個輸入值」+「一個金鑰對」=「一個簽章」。 無法預測另一個 RP 將獲得什麼簽名，因此可以透過組合簽署相同值的多個參與者的 RSA 簽名來組織具有確定性簽名的 PVRB。 例如之前的隨機。 這個方案節省了大量的資源，因為簽章既是根據協議對正確行為的確認，也是隨機性的來源。

然而，即使具有確定性簽名，該方案仍然容易受到「最後參與者」問題的影響。 最後一個參與者仍然可以決定是否公開簽名，從而控制結果。 你可以修改方案，在其中添加區塊哈希，進行輪次，這樣結果就無法提前預測，但所有這些技術，即使考慮到許多修改，仍然沒有解決單個參與者對集體的影響問題導致環境不受信任，只能在經濟和時間限制下工作。 此外，RSA金鑰的大小（1024和2048位元）相當大，區塊鏈交易的大小是一個極為重要的參數。 顯然沒有簡單的方法可以解決這個問題，讓我們繼續吧。

PVRB 和秘密共享方案

在密碼學中，有一些方案可以允許網路就一個且僅有一個PVRB值達成一致，同時這種方案可以抵抗某些參與者的任何惡意行為。 沙米爾的秘密共享方案是一項值得您熟悉的有用協議。 它的作用是將一個秘密（例如，一個秘密金鑰）分成幾個部分，並將這些部分分發給N個參與者。 秘密的分佈方式使得 N 中的 M 部分足以恢復它，而這些可以是任何 M 部分。 如果在手指上，則有一個未知函數的圖形，參與者在圖形上交換點，收到M點後，可以恢復整個函數。
給了很好的解釋 維基 但是實際使用它以便在你的頭腦中播放協議對於以下方面很有用： 演示 頁。

如果 FSSS（Fiat-Shamir 秘密共享）方案以其純粹的形式適用，它將是一個堅不可摧的 PVRB。 最簡單的協定可能如下所示：

  • 每位參與者產生自己的隨機數並將其分配給其他參與者
  • 每位參與者都透露了其他參與者的秘密
  • 如果某位參與者擁有M股以上，則可以計算出該參與者的數量，且該參與者的數量是唯一的，與顯示的參與者集合無關
  • 顯示的隨機數的組合是所需的 PVRB

在這裡，個別參與者不再影響協議的結果，除非隨機性揭露閾值的實現僅取決於他。 因此，如果有所需比例的 RP 在協議上工作並且可用，則該協議可以工作，實現加密強度的要求，並抵抗「最後參與者」問題。

這可能是個理想的選擇，這個基於 Fiat-Shamir 秘密共享的 PVRB 方案例如在 此 文章。 但是，如上所述，如果你嘗試在區塊鏈中正面應用它，就會出現技術限制。 以下是 EOS 智能合約中協議的測試實現範例及其最重要的部分 - 檢查已發布的份額參與者： 碼。 從程式碼可以看出，證明驗證需要多次標量乘法，而且使用的數字非常大。 需要理解的是，在區塊鏈中，驗證發生在區塊生產者處理交易的那一刻，一般來說，任何參與者都必須輕鬆驗證協議的正確性，因此對驗證功能的速度要求非常嚴格。 在此選項中，該選項被證明是無效的，因為驗證不符合交易限制（0.5 秒）。

一般來說，驗證效率是在區塊鏈中使用任何高級加密方案的最重要要求之一。 創建證明、準備訊息——這些過程可以脫鏈並在高效能電腦上執行，但無法繞過驗證——這是 PVRB 的另一個重要要求。

PVRB 和門限簽名

熟悉秘密共享方案後，我們發現了一整類由關鍵字「閾值」聯合起來的協議。 當某些資訊的揭露需要 N 個誠實參與者中的 M 個參與，並且誠實參與者的集合可以是 N 的任意子集時，我們稱之為「閾值」方案。 正是它們讓我們能夠處理「最後一個參與者」的問題，現在如果攻擊者不透露他的部分秘密，另一個誠實的參與者將為他做這件事。 這些方案允許就一種且僅一種含義達成一致，即使協議被某些參與者破壞。

確定性簽章和閾值方案的結合使得開發一種非常方便且有前途的方案來實現PVRB成為可能——這些是確定性閾值簽章。 這裡 文章 關於門限簽名的各種用途，這是另一個很好的用途 longread 來自達世幣。

上一篇文章介紹了 BLS 簽名（BLS 代表 Boneh-Lynn-Shacham， 這裡 文章），這對程式設計師來說有一個非常重要且極其方便的品質- 公鑰、秘密、公鑰和BLS 簽名可以使用簡單的數學運算相互組合，而它們的組合仍然有效的密鑰和簽名，使您可以輕鬆聚合許多簽名合為一個，多個公鑰合為一個。 它們也是確定性的，對於相同的輸入資料會產生相同的結果。 由於這種特性，BLS 簽名的組合本身就是有效的金鑰，這允許實現一種選項，其中N 個參與者中的M 個產生一個且僅有一個簽名，該簽名是確定性的、可公開驗證的且不可預測，直到第M 個參與者打開它為止。參與者。

在具有閾值 BLS 簽章的方案中，每位參與者都使用 BLS 簽署某些內容（例如先前的隨機數），而公共閾值簽章是所需的隨機數。 BLS 簽章的加密屬性符合隨機品質的要求，閾值部分可防止“最後參與者”，而金鑰的獨特組合性使實現許多更有趣的演算法成為可能，例如，允許協定訊息的有效聚合。

因此，如果您在區塊鏈上建立 PVRB，您很可能最終會得到 BLS 閾值簽署方案，有幾個項目已經在使用它。 例如，DFinity（這裡 實現電路的基準測試，以及 這裡 可驗證秘密共享的範例實作），或 Keep.network（這是他們的隨機信標 黃皮書， 和這裡 例子 服務於協議的智能合約）。

實施PVRB

不幸的是，我們仍然沒有看到在 PVRB 區塊鏈中實現的現成協議已證明其安全性和穩定性。 儘管協議本身已經準備就緒，但從技術上將它們應用到現有解決方案中並不容易。 對於中心化系統來說，PVRB沒有意義，而去中心化系統在所有運算資源上都受到嚴格限制：CPU、記憶體、儲存、I/O。 設計 PVRB 是不同協議的組合，以便創建至少滿足某些可行區塊鏈的所有要求的東西。 一種協議計算效率更高，但需要 RP 之間的更多訊息，而另一種協議需要很少的消息，但創建證明可能是一項需要數十分鐘甚至數小時的任務。

我將列出您在選擇優質 PVRB 時必須考慮的因素：

  • 加密強度。 您的 PVRB 必須嚴格無偏，無法控制單一位元。 在某些方案中並非如此，因此請致電密碼學家
  • 「最後一個演員」問題。 您的 PVRB 必須能夠抵禦控制一個或多個 RP 的攻擊者可以選擇兩種結果之一的攻擊。
  • 協議破壞問題。 您的 PVRB 必須能夠抵禦控制一個或多個 RP 的攻擊者決定是否隨機的攻擊，並且可以保證或以給定的機率影響這一點
  • 訊息數量問題。 您的 RP 應向區塊鏈發送最少的訊息，並儘可能避免同步操作，例如「我發送了一些訊息，我正在等待特定參與者的回應」之類的情況。 在 p2p 網路中，尤其是地理位置分散的網路中，您不應指望快速回應
  • 計算複雜度問題。 PVRB 鏈上任何階段的驗證都應該非常容易，因為它是由網路的所有完整客戶端執行的。 如果使用智能合約來實現，那麼速度要求非常嚴格
  • 可訪問性和活躍性問題。 您的 PVRB 應努力對部分網路在一段時間內不可用且部分 RP 完全停止工作的情況具有彈性
  • 可信任設定和初始金鑰分發問題。 如果您的 PVRB 使用協議的主要設置，那麼這是一個單獨的大而嚴肅的故事。 這裡 例子。 如果參與者必須在啟動協議之前告訴對方他們的密鑰，那麼如果參與者的組成發生變化，這也是一個問題
  • 發展問題。 所需語言的庫的可用性、其安全性和性能、宣傳、複雜測試等。

例如，閾值 BLS 簽名有一個重大問題 - 在開始工作之前，參與者必須相互分發金鑰，組織一個閾值將在其中起作用的群組。 這意味著去中心化網路中至少一輪交換必須等待，並且考慮到生成的蘭特在遊戲中是必需的，幾乎是即時的，這意味著現階段有可能破壞協議，閾值方案的優點就喪失了。 這個問題已經比以前的問題簡單了，但仍然需要開發一個單獨的程序來形成閾值組，必須通過向不遵循規則的參與者存款和提取資金（削減）來在經濟上得到保護。協議。 此外，具有可接受安全性等級的 BLS 驗證根本不適合（例如）標準 EOS 或以太坊交易 - 根本沒有足夠的時間進行驗證。 合約代碼是WebAssembly或EVM，由虛擬機器執行。 加密函數尚未在本機實現，且工作速度比傳統加密庫慢數十倍。 許多協定僅根據金鑰大小並不能滿足要求，例如RSA的1024和2048位，比比特幣和以太坊中的標準交易簽章大4-8倍。

不同程式語言的實作也發揮了作用——這種實作很少，特別是對於新協定。 整合到共識中的選項需要使用平台語言編寫協議，因此您必須在Go 中尋找程式碼（用於geth）、在Rust 中尋找程式碼（用於Parity）、在C++ 中尋找程式碼（用於EOS） 。 每個人都必須尋找 JavaScript 程式碼，並且由於 JavaScript 和密碼學並不是特別親密的朋友，WebAssembly 將提供幫助，它現在無疑聲稱是下一個重要的網路標準。

結論

我希望在上一篇中 文章 我設法讓您相信，在區塊鏈上產生隨機數對於去中心化網路生活的許多方面都至關重要，並且透過本文，我表明這項任務非常雄心勃勃且困難，但已經存在良好的解決方案。 一般來說，協議的最終設計只有在進行大量測試之後才有可能，這些測試考慮到從設置到故障模擬的各個方面，因此您不太可能在團隊白皮書和文章中找到現成的配方，我們當然也不會決定在未來一兩年內寫下「這樣做，完全正確」。

再見，我們正在開發的區塊鏈PVRB 哈亞，我們決定使用閾值 BLS 簽名，我們計劃在共識層級實施 PVRB，因為尚不可能在智慧合約中進行具有可接受安全等級的驗證。 我們有可能同時使用兩種方案：首先，昂貴的秘密共享來創建長期的 random_seed，然後我們將其用作使用確定性閾值 BLS 簽名的高頻隨機生成的基礎，也許我們會將自己限制為僅其中一項計劃。 不幸的是，不可能提前說出協議是什麼；唯一的好處是，就像在科學中、在工程問題中一樣，負面結果也是結果，解決問題的每一次新嘗試都是解決問題的又一步。涉及該問題的每個人的研究。 為了滿足業務需求，我們解決一個具體的實際問題——為遊戲應用提供可靠的熵源，所以我們也要關注區塊鏈本身，特別是鏈終結性和網路治理的問題。

儘管我們還沒有在區塊鏈中看到經過驗證的抗PVRB，它已經被使用了足夠的時間來透過真實應用程式、多次審計、負載，當然還有真實攻擊進行測試，但可能的路徑數量證實了這一點存在解決方案，以及這些演算法中的哪些最終可以解決問題。 我們很樂意分享結果，並感謝其他也在解決此問題的團隊提供的文章和程式碼，使工程師不必兩次踩同一個耙子。

所以，當你遇到設計去中心化隨機的程式設計師時，要細心和關懷，必要時提供心理幫助:)

來源： www.habr.com

添加評論