許多現(xiàn)代的區(qū)塊鏈協(xié)議，包括near，都依賴隨機性的來源來選擇在協(xié)議中執(zhí)行某些操作的參與者。如果惡意參與者能夠影響這種隨機性源，他們就可以增加被選中的機會，并可能危及協(xié)議的安全性。

分布式隨機性也是構建在區(qū)塊鏈上的許多分布式應用程序的重要組成部分。例如，一個智能合約接受參與者的下注，并以49%的比例支付兩倍的金額，而以51%的比例不支付，它假設它可以得到一個不可破解的隨機數(shù)。如果惡意參與者能夠影響或預測隨機數(shù)，他們就可以增加在智能合約中獲得付款的機會，并將其耗盡。

當我們設計分布式隨機性算法時，我們希望它有三個屬性：

1. 它必須是不操控的。換句話說，任何參與者都不能以任何方式影響隨機生成器的結果。

2. 它必須是不可預測的。換言之，任何參與者都不能預測在生成數(shù)字之前將生成什么數(shù)字（或其任何屬性的原因）。

3. 協(xié)議需要容忍一定比例的參與者離線或故意拖延協(xié)議。

在本文中，我們將介紹分布式隨機信標的基礎知識，討論為什么簡單的方法不起作用。最后，我們將介紹dfnity、ethereum serenity和near使用的方法，并討論它們的優(yōu)缺點。

RANDAO

Randao是一種非常簡單的隨機性方法，因此非常常用。一般的想法是網(wǎng)絡的參與者首先私下選擇一個偽隨機數(shù)，提交對這種私人選擇的數(shù)字的承諾，所有人都使用一些共識算法就一些承諾達成一致，然后全部顯示他們選擇的數(shù)字，達到一個 對顯示的數(shù)字達成共識，并將顯示數(shù)字的XOR作為協(xié)議的輸出。

這是不可預測的，與基礎共識協(xié)議具有相同的活力，但是可偏倚的。具體來說，一旦其他人開始透露他們的數(shù)字，惡意的參與者就可以觀察網(wǎng)絡，并根據(jù)目前觀察到的數(shù)字的異或來選擇透露或不透露他們的數(shù)字。這允許一個惡意參與者對輸出產(chǎn)生一點影響，而控制多個參與者的惡意參與者的影響程度與其控制的參與者數(shù)量相同。

RANDAO + VDF

為了使RANDAO不可替換，一種方法是使輸出不僅僅是XOR，而是需要花費更多時間來執(zhí)行而不是分配時間來顯示數(shù)字。如果最終輸出的計算花費的時間長于揭示階段，則惡意行為者無法預測它們顯示或不顯示其數(shù)量的影響，因此不能影響結果。

雖然我們希望計算隨機性的函數(shù)為生成隨機數(shù)的參與者花費很長時間，但我們希望隨機數(shù)的用戶不必再次執(zhí)行相同的昂貴函數(shù)。因此，他們需要以某種方式能夠快速驗證隨機數(shù)是否正確生成，而無需重新進行昂貴的計算。

這種計算時間長、驗證計算速度快、每個輸入都有唯一輸出的函數(shù)稱為可驗證延遲函數(shù)（簡稱vdf），結果表明設計一個延遲函數(shù)非常復雜。最近有了多項突破，即這一次和這次突破使得它成為可能，以太坊目前計劃使用RANDAO和VDF作為隨機信標。除了這種方法不可預測和不可替代的事實之外，即使只有兩個參與者在線，它還具有活力的額外優(yōu)勢（假設基礎共識協(xié)議具有如此少的參與者的活力）。

這種方法最大的挑戰(zhàn)是，需要以這樣的方式配置vdf：即使是擁有非常昂貴的專用硬件的參與者也無法在顯示階段結束之前計算vdf，理想情況下，具有一些有意義的安全邊際，比如10倍。下圖顯示了具有專用ASIC的參與者的攻擊，該ASIC允許他們比分配用于顯示RANDAO承諾的時間更快地運行VDF。這樣的參與者仍然可以在有和沒有共享的情況下計算最終輸出，并根據(jù)這些輸出選擇顯示或不顯示：

對于上面的VDF系列，專用ASIC可以比傳統(tǒng)硬件快100倍。因此，如果顯示階段持續(xù)10秒，則在這樣的ASIC上計算的VDF必須花費超過100秒才能具有10倍的安全深度，因此在傳統(tǒng)硬件上計算的相同VDF需要花費100 x 100秒= 約3小時。

以太坊基金會計劃解決的方法是設計自己的ASIC，并免費公開發(fā)布。一旦發(fā)生這種情況，所有其他協(xié)議都可以利用這項技術，但在此之前，RANDAO + VDFs方法對于無法投資設計自己的ASIC的協(xié)議來說并不可行。

門限簽名BLS

由Dfinity開創(chuàng)的另一種隨機性方法是使用所謂的門限BLS簽名。

BLS簽名是一種允許多方在消息上創(chuàng)建單個簽名的結構，通常用于通過不需要發(fā)送多個簽名來節(jié)省空間和帶寬。區(qū)塊鏈中BLS簽名的常見用法是在BFT協(xié)議中對塊進行簽名。假設100個參與者創(chuàng)建了區(qū)塊，并且如果其中67個塊在其上簽名則認為該區(qū)塊是最終的。他們都可以提交他們的BLS簽名部分，然后使用一些共識算法來同意其中的67個，然后將它們聚合成單個BLS簽名。任何67個部分都可用于創(chuàng)建累積簽名，但是根據(jù)匯總的67個簽名，生成的簽名將不相同。

事實證明，如果參與者使用的私鑰是以特定方式生成的，那么無論聚合的是多過67個（或更多，但不是更少）簽名，所得到的多重簽名都是相同的。這可以用作隨機源：參與者首先同意他們將簽署的一些消息（它可能是RANDAO的輸出，或者只是最后一個區(qū)塊的散列，只要它是真的無關緊要每次都不同并達成一致），并在其上創(chuàng)建多重簽名。直到67個參與者提供他們的部分，輸出是不可預測的，但即使在提供第一部分之前，輸出已經(jīng)預先確定并且不受任何參與者的影響。

這種隨機性方法是完全不可替代且不可預測的，并且只要有2/3的參與者在線（但可以針對任何閾值進行配置），這種方法是有效的。雖然1/3離線或行為不端的參與者可能會停止算法，但至少需要2/3參與者合作才能影響輸出。

不過有一個警告。上面，我提到過這個方案的私鑰需要以特定的方式生成。密鑰生成的過程稱為分布式密鑰生成（簡稱DKG），它非常復雜，是一個非?；钴S的研究領域。在最近的一次談話中，Dfinity提出了一個非常復雜的方法，其中涉及zk-SNARKs，這是一個非常復雜且沒有時間測試的加密結構，作為其中一個步驟。通常對閾值簽名BLS和DKG的研究并不處于可以在實踐中容易應用的狀態(tài)。

RandShare

NEAR方法受另一種稱為RandShare的算法的影響。Randshare是一個不可抗拒的、不可預測的協(xié)議，它可以容忍多達_的行為體是惡意的。本文還描述了兩種加快速度的方法，稱為randhound和randhound，但與randshare本身不同，randhound和randhound相對復雜，而我們希望協(xié)議非常簡單。

RandShare的一般問題除了交換的大量消息（參與者一起交換O（n^3）消息）之外，事實上雖然1/3是實踐中活躍度的有意義閾值，但影響輸出能力卻很低 。有幾個原因：

· 影響輸出的好處可能大大超過拖延隨機性的好處。

· 如果一個參與者在Randshare中控制了超過1/3的參與者，并使用它來影響結果輸出，那么它就不會留下任何痕跡。因此，一個惡意的行動者可以在不被揭露的情況下做到這一點。拖延共識自然是顯而易見的。

· 控制1/3的hashpower/staking情況并非不可能，考慮到（1）和（2）以上的控制者不太可能試圖阻止這種隨機性，但能夠并且可能會試圖影響這種隨機性。

NEAR Approach

NEAR方法在我們最近發(fā)表的論文中有所描述。這是不可避免的，不可預測的，并且可以容忍1/3惡意行為者的活力，即如果有人控制1/3或更多的參與者，他們可以停止協(xié)議。

然而，與RandShare不同，它可以容忍最多2/3惡意行為者，然后才能影響輸出。這對于實際應用來說是明顯更好的閾值。

該協(xié)議的核心思想如下（為簡單起見，假設有100個參與者）：

1. 每個參與者提出他們的部分輸出，將其分成67個部分，擦除代碼以獲得100個份額，使得任何67個足以重建輸出，將100個份額中的每一個分配給其中一個參與者并使用這種參與者的公鑰。然后他們共享所有的編碼。

2. 參與者使用一些共識（如：tendermint）從67名參與者中就這些編碼集達成一致。

3. 一旦達成一致意見，每個參與者將以公開密鑰編碼的方式發(fā)布的67個集合中的每一個集合中的編碼共享，然后解碼所有這些共享，并立即發(fā)布所有這些解碼共享。

4. 一旦至少67個參與者完成了步驟（3），所有商定的集合可以被完全解碼和重建，并且最終的數(shù)量可以作為參與者在（1）中提出的初始部分的XOR獲得。

這個協(xié)議不可破解和不可預測的原因類似于隨機共享和門限簽名：一旦達成共識，就可以決定最終的輸出，但直到有個參與者解密用其公鑰加密的共享，任何人都不知道最終的輸出。

處理所有極端情況和可能的惡意行為使其稍微復雜一些（例如，當步驟（1）中的某個人創(chuàng)建了無效的擦除代碼時，參與者需要處理這種情況），但總的來說整個協(xié)議非常簡單，用所有證明描述它的整篇論文，相應的加密原語和參考只有7頁長。

類似的利用糾刪碼的想法已經(jīng)在NEAR的現(xiàn)有基礎設施中使用，其中特定時期的塊生成器創(chuàng)建包含特定分片的所有事務的所謂塊，并且分發(fā)這樣的塊的擦除編碼版本。 merkle向其他區(qū)塊生產(chǎn)商提供證據(jù)以確保數(shù)據(jù)可用性。