介紹
“隨機數字生成太重要了，不能靠運氣。”
羅伯特·卡維，1970
本文致力於在不可信環境中使用集體隨機數產生的解決方案的實際應用。 簡而言之，如何以及為什麼在區塊鏈中使用隨機數，以及如何區分「好」隨機數和「壞」隨機數。 即使在一台電腦上，產生真正的隨機數字也是一個極其困難的問題，密碼學家長期以來一直在研究這個問題。 那麼，在去中心化網路中，隨機數的產生就更加複雜和重要。
正是在參與者彼此不信任的網路中，產生無可爭議的隨機數的能力使我們能夠有效地解決許多關鍵問題並顯著改進現有方案。 此外，對於沒有經驗的讀者來說，賭博和彩票並不是這裡的首要目標。
隨機數生成
電腦本身無法產生隨機數；它們需要外部幫助才能做到這一點。 電腦可以從例如滑鼠移動、使用的記憶體量、處理器引腳上的雜散電流以及許多其他稱為熵源的源中獲取一些隨機值。 這些值本身並不是完全隨機的，因為它們在一定範圍內或具有可預測的變化模式。 為了將這些數字變成給定範圍內的真正隨機數，可以對它們應用加密變換，以從熵源的不均勻分佈值產生均勻分佈的偽隨機值。 所得的值稱為偽隨機，因為它們不是真正隨機的，而是確定性地從熵導出的。 任何好的加密演算法在加密資料時都會產生密文，這些密文在統計上應該與隨機序列無法區分，因此為了產生隨機性，您可以採用熵來源，即使在小範圍內，熵也只能提供良好的重複性和不可預測性，剩下的工作是分散和混合比特，結果值將由加密演算法接管。
為了完成一個簡短的教育計劃，我要補充一點，即使在一台設備上生成隨機數也是確保數據安全的支柱之一。生成的偽隨機數用於在各種網絡中建立安全連接時，以生成加密金鑰，用於負載平衡、完整性監控以及更多應用程式。 許多協議的安全性取決於生成可靠的、外部不可預測的隨機數、儲存它並且在協議的下一步之前不洩露它的能力，否則安全性將受到損害。 對偽隨機值產生器的攻擊極為危險，會立即威脅到所有使用隨機產生的軟體。
如果您學過密碼學基礎課程，您應該了解所有這些，所以讓我們繼續討論去中心化網路。
區塊鏈中的隨機性
首先，我會談論支持智能合約的區塊鏈；它們是能夠充分利用高品質、不可否認的隨機性所提供的機會的區塊鏈。 此外，為了簡潔起見，我將這項技術稱為“可公開驗證的隨機信標”或PVRB。 由於區塊鏈是任何參與者都可以驗證資訊的網絡，因此其名稱的關鍵部分是“可公開驗證”，即任何人都可以使用計算來獲得證據，證明發佈在區塊鏈上的結果數字具有以下屬性：
- 結果必須具有可證明的均勻分佈，即基於可證明的強密碼學。
- 無法控制結果的任何位元。 因此，結果無法提前預測。
- 您不能透過不參與協議或透過攻擊訊息使網路過載來破壞生成協議
- 上述所有內容都必須能夠抵禦允許數量的不誠實協議參與者（例如 1/3 的參與者）的串通。
少數參與者串通產生受控偶數/奇數隨機的任何可能性都是一個安全漏洞。 該組織阻止隨機發布的任何能力都是一個安全漏洞。 總的來說，問題很多，而且這個任務也不是一件容易的事…
看來PVRB最重要的應用是各種遊戲、彩票以及區塊鏈上的任何類型的賭博。 確實，這是一個重要的方向，但區塊鏈中的隨機性還有更重要的應用。 讓我們看看它們。
共識算法
PVRB 在組織網路共識方面發揮巨大作用。 區塊鏈中的交易受到電子簽名的保護，因此「對交易的攻擊」始終是在一個區塊（或多個區塊）中包含/排除交易。 而共識演算法的主要任務就是就這些交易的順序以及包含這些交易的區塊的順序達成一致。 此外，真正的區塊鏈的一個必要屬性是最終性——網路能夠同意直到最終確定的區塊的鏈都是最終的，並且永遠不會因為新分叉的出現而被排除。 通常，為了同意一個區塊是有效的，最重要的是，是最終的，需要收集大多數區塊生產者（以下簡稱BP——區塊生產者）的簽名，這至少需要交付區塊鏈給所有BP，並在所有BP之間分發簽名。 隨著BP 數量的增長，網路中必要的訊息數量呈指數級增長，因此，需要最終性的共識演算法（例如Hyperledger pBFT 共識中使用的）無法以所需的速度運行，從幾十個BP 開始，需要大量的連接。
如果網路中存在不可否認且誠實的 PVRB，那麼，即使是最簡單的近似，人們也可以根據它選擇區塊生產者，並在一輪協議中任命他為「領導者」。 如果我們有 N 區塊生產者，其中 M: M > 1/2 N 是誠實的，不審查交易，也不分叉鏈來進行“雙花”攻擊，那麼使用均勻分佈的不受挑戰的 PVRB 將允許以概率選擇一個誠實的領導者 M / N (M / N > 1/2)。 如果每個領導者都被分配了自己的時間間隔，在此期間他可以產生一個區塊並驗證該鏈，並且這些時間間隔在時間上相等，那麼誠實節點的區塊鏈將比惡意節點形成的鏈更長，並且共識演算法依賴於鏈的長度。將簡單地丟棄“壞”鏈。 這種為每個BP 分配相等時間片的原則首先應用於Graphene（EOS 的前身），並允許大多數區塊透過單一簽名關閉，這大大減少了網路負載，並使這種共識能夠極快地發揮作用。穩步。 然而，EOS網路現在必須使用特殊的區塊（最後不可逆區塊），這些區塊由2/3 BP的簽章確認。 這些區塊用於確保最終性（鏈分叉不可能在最後一個不可逆區塊之前開始）。
此外，在實際實現中，協議方案更加複雜- 對提議區塊的投票分幾個階段進行，以在丟失區塊和網絡問題的情況下維護網絡，但即使考慮到這一點，使用PVRB 的共識算法也需要BP 之間的訊息顯著減少，這使得它們比傳統的 PVFT 或其各種修改更快。
此類演算法最突出的代表： 來自卡爾達諾團隊，據說可以在數學上證明反對 BP 串通。
在 Ouroboros 中，PVRB 用於定義所謂的「BP 時間表」——根據該時間表，每個 BP 被分配自己的時隙來發佈區塊。 使用 PVRB 的一大優勢是 BP 完全「平等」（根據其資產負債表的規模）。 PVRB 的完整性保證了惡意節點無法控制時隙的調度，因此無法透過提前準備和分析鏈的分叉來操縱鏈，而選擇分叉只需依靠分叉的長度即可。鏈，無需使用棘手的方法來計算BP 的「效用」及其區塊的「權重」。
一般來說，在去中心化網路中需要選擇隨機參與者的所有情況下，PVRB 幾乎總是最佳選擇，而不是基於區塊雜湊等的確定性選項。 如果沒有 PVRB，影響參與者選擇的能力會導致攻擊，攻擊者可以從多個 future 中進行選擇，以選擇下一個腐敗參與者或同時選擇多個參與者，以確保在決策中獲得更大份額。 PVRB 的使用使這些類型的攻擊變得不可信。
擴展和負載平衡
PVRB 在減少負載和擴展支付等任務中也有很大好處。 首先，熟悉一下是有意義的 Rivesta「電子彩票以小額支付」。 總體思路是，您可以玩誠實的彩票，獎金為100$ = 1c，而不是從付款人向收款人支付1 筆100c 的款項，其中付款人每人向銀行提供1 張“彩票”中的一張100c 付款。 其中一張彩券贏得了一罐 1 美元，接收者可以將這張彩券記錄在區塊鏈中。 最重要的是，剩餘的 99 張門票可以在沒有任何外部參與的情況下，透過私人管道以任何所需的速度在接收方和付款方之間轉移。 可以閱讀 Emercoin 網路上基於此方案的協議的詳細描述 .
該方案存在一些問題，例如接收者在收到中獎彩券後可能會立即停止為付款人提供服務，但對於許多特殊應用，例如按分鐘計費或電子訂閱服務，這些可以忽略不計。 當然，主要要求是彩票的公平性，而為了實現它，PVRB 是絕對必要的。
隨機參與者的選擇對於分片協議也極為重要，其目的是水平擴展區塊鏈，允許不同的節點只處理自己範圍內的交易。 這是一項極其困難的任務，特別是在合併分片時的安全性方面。 公平選擇隨機 BP 來分配負責特定分片的人員（如共識演算法中）也是 PVRB 的任務。 在集中式系統中，分片由平衡器分配；它只是根據請求計算哈希值並將其發送到所需的執行器。 在區塊鏈中，影響此分配的能力可能會導致對共識的攻擊。 例如，交易的內容可以由攻擊者控制，他可以控制哪些交易進入他控制的分片並操縱其中的區塊鏈。 您可以閱讀有關在以太坊中使用隨機數進行分片任務的問題的討論
分片是區塊鏈領域最雄心勃勃、最嚴重的問題之一；它的解決方案將允許建立具有出色性能和容量的去中心化網路。 PVRB只是解決這個問題的重要模組之一。
遊戲、經濟協議、仲裁
隨機數在遊戲產業中的作用很難被高估。 對於去中心化網路來說，線上賭場中的明確使用以及計算玩家行為影響時的隱式使用都是極其困難的問題，因為去中心化網路無法依賴隨機性的中央來源。 但隨機選擇也可以解決許多經濟問題，並有助於建立更簡單、更有效率的協議。 假設在我們的協議中存在關於某些廉價服務的支付的爭議，並且這些爭議很少發生。 在這種情況下，如果存在無爭議的 PVRB，則客戶和賣家可以同意以給定的機率隨機解決爭議。 例如，客戶獲勝的機率為 60%，賣方獲勝的機率為 40%。 從第一個角度來看，這種方法是荒謬的，但它允許您以精確可預測的勝負份額自動解決爭議，這對雙方都有利，無需任何第三方的參與，也不會浪費不必要的時間。 此外，機率比可以是動態的並且取決於一些全域變數。 例如，如果一家公司經營狀況良好，爭議數量較少且盈利能力較高，那麼該公司可以自動將解決爭議的機率轉向以客戶為中心，例如70/30或80/20，反之亦然，如果糾紛花了很多錢並且是欺詐性的或不充分的，你可以將機率轉向另一個方向。
許多有趣的去中心化協議，例如代幣策劃的註冊中心、預測市場、聯合曲線等等，都是經濟遊戲，其中良好行為得到獎勵，不良行為受到懲罰。 它們通常包含保護措施相互衝突的安全問題。 受到數十億代幣「鯨魚」（「大權益」）攻擊的保護，很容易受到數千個小餘額帳戶（「女巫權益」）的攻擊，以及針對單一攻擊採取的措施，例如非為使大量股份無利可圖而產生的線性費用通常會因另一次攻擊而失去信譽。 由於我們討論的是經濟博弈，因此可以提前計算出相應的統計權重，並簡單地將佣金替換為具有適當分佈的隨機佣金。 如果區塊鏈具有可靠的隨機性來源並且不需要任何複雜的計算，那麼這種機率性佣金的實施就非常簡單，這使得鯨魚和女巫的生活變得困難。
同時，有必要繼續記住，控制這種隨機性中的單位元可以讓您作弊，將機率減少或增加一半，因此誠實的 PVRB 是此類協議中最重要的組成部分。
哪裡可以找到合適的隨機數？
理論上，去中心化網路中的公平隨機選擇使得幾乎任何協議都可以證明是安全的，並且可以防止串通。 基本原理非常簡單 - 如果網絡就單個 0 或 1 位達成一致，並且不到一半的參與者不誠實，那麼，經過足夠的迭代，網絡就可以保證以固定的概率就該位達成共識。 原因很簡單，因為誠實的隨機抽樣者在 51% 的情況下會從 100 名參與者中選擇 51 名。 但這是理論上的，因為… 在實際網路中，為了確保文章中的安全級別，需要主機之間的許多訊息、複雜的多通道加密技術，並且協議的任何複雜性都會立即增加新的攻擊向量。
這就是為什麼我們在區塊鏈中還沒有看到經過驗證的抗PVRB，它已經使用了足夠的時間來通過真實應用程序、多次審計、負載，當然還有真實攻擊進行測試，沒有它就很難稱之為產品真正安全。
然而，有幾種有前途的方法，它們在許多細節上有所不同，其中之一肯定能解決問題。 借助現代計算資源，密碼理論可以非常巧妙地轉化為實際應用。 未來，我們將很樂意談論 PVRB 實作：現在有幾種實現，每個實作都有自己的一組重要屬性和實作功能，每個實作背後都有一個好主意。 參與隨機化的團隊不多，每個人的經驗對其他人來說都極為重要。 我們希望我們的資訊能讓其他團隊借鏡前輩的經驗，更快行動。
來源： www.habr.com