許多現(xiàn)代的區(qū)塊鏈協(xié)議，包括near，都依賴隨機性的來源來選擇在協(xié)議中執(zhí)行某些操作的參與者。如果惡意參與者能夠影響這種隨機性源，他們就可以增加被選中的機會，并可能危及協(xié)議的安全性。
分布式隨機性也是構(gòu)建在區(qū)塊鏈上的許多分布式應用程序的重要組成部分。例如，一個智能合約接受參與者的下注，并以49%的比例支付兩倍的金額，而以51%的比例不支付，它假設(shè)它可以得到一個不可破解的隨機數(shù)。如果惡意參與者能夠影響或預測隨機數(shù)，他們就可以增加在智能合約中獲得付款的機會，并將其耗盡。
當我們設(shè)計分布式隨機性算法時，我們希望它有三個屬性：
1. 它必須是不操控的。換句話說，任何參與者都不能以任何方式影響隨機生成器的結(jié)果。
2. 它必須是不可預測的。換言之，任何參與者都不能預測在生成數(shù)字之前將生成什么數(shù)字（或其任何屬性的原因）。
3. 協(xié)議需要容忍一定比例的參與者離線或故意拖延協(xié)議。
在本文中，我們將介紹分布式隨機信標的基礎(chǔ)知識，討論為什么簡單的方法不起作用。最后，我們將介紹dfnity、ethereum serenity和near使用的方法，并討論它們的優(yōu)缺點。
RANDAO
Randao是一種非常簡單的隨機性方法，因此非常常用。一般的想法是網(wǎng)絡(luò)的參與者首先私下選擇一個偽隨機數(shù)，提交對這種私人選擇的數(shù)字的承諾，所有人都使用一些共識算法就一些承諾達成一致，然后全部顯示他們選擇的數(shù)字，達到一個 對顯示的數(shù)字達成共識，并將顯示數(shù)字的XOR作為協(xié)議的輸出。
這是不可預測的，與基礎(chǔ)共識協(xié)議具有相同的活力，但是可偏倚的。具體來說，一旦其他人開始透露他們的數(shù)字，惡意的參與者就可以觀察網(wǎng)絡(luò)，并根據(jù)目前觀察到的數(shù)字的異或來選擇透露或不透露他們的數(shù)字。這允許一個惡意參與者對輸出產(chǎn)生一點影響，而控制多個參與者的惡意參與者的影響程度與其控制的參與者數(shù)量相同。
RANDAO + VDF
為了使RANDAO不可替換，一種方法是使輸出不僅僅是XOR，而是需要花費更多時間來執(zhí)行而不是分配時間來顯示數(shù)字。如果最終輸出的計算花費的時間長于揭示階段，則惡意行為者無法預測它們顯示或不顯示其數(shù)量的影響，因此不能影響結(jié)果。
雖然我們希望計算隨機性的函數(shù)為生成隨機數(shù)的參與者花費很長時間，但我們希望隨機數(shù)的用戶不必再次執(zhí)行相同的昂貴函數(shù)。因此，他們需要以某種方式能夠快速驗證隨機數(shù)是否正確生成，而無需重新進行昂貴的計算。
這種計算時間長、驗證計算速度快、每個輸入都有唯一輸出的函數(shù)稱為可驗證延遲函數(shù)（簡稱vdf），結(jié)果表明設(shè)計一個延遲函數(shù)非常復雜。最近有了多項突破，即這一次和這次突破使得它成為可能，以太坊目前計劃使用RANDAO和VDF作為隨機信標。除了這種方法不可預測和不可替代的事實之外，即使只有兩個參與者在線，它還具有活力的額外優(yōu)勢（假設(shè)基礎(chǔ)共識協(xié)議具有如此少的參與者的活力）。
這種方法最大的挑戰(zhàn)是，需要以這樣的方式配置vdf：即使是擁有非常昂貴的專用硬件的參與者也無法在顯示階段結(jié)束之前計算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小時。
以太坊基金會計劃解決的方法是設(shè)計自己的ASIC，并免費公開發(fā)布。一旦發(fā)生這種情況，所有其他協(xié)議都可以利用這項技術(shù)，但在此之前，RANDAO + VDFs方法對于無法投資設(shè)計自己的ASIC的協(xié)議來說并不可行。
門限簽名BLS
由Dfinity開創(chuàng)的另一種隨機性方法是使用所謂的門限BLS簽名。
BLS簽名是一種允許多方在消息上創(chuàng)建單個簽名的結(jié)構(gòu)，通常用于通過不需要發(fā)送多個簽名來節(jié)省空間和帶寬。區(qū)塊鏈中BLS簽名的常見用法是在BFT協(xié)議中對塊進行簽名。假設(shè)100個參與者創(chuàng)建了區(qū)塊，并且如果其中67個塊在其上簽名則認為該區(qū)塊是最終的。他們都可以提交他們的BLS簽名部分，然后使用一些共識算法來同意其中的67個，然后將它們聚合成單個BLS簽名。任何67個部分都可用于創(chuàng)建累積簽名，但是根據(jù)匯總的67個簽名，生成的簽名將不相同。
事實證明，如果參與者使用的私鑰是以特定方式生成的，那么無論聚合的是多過67個（或更多，但不是更少）簽名，所得到的多重簽名都是相同的。這可以用作隨機源：參與者首先同意他們將簽署的一些消息（它可能是RANDAO的輸出，或者只是最后一個區(qū)塊的散列，只要它是真的無關(guān)緊要每次都不同并達成一致），并在其上創(chuàng)建多重簽名。直到67個參與者提供他們的部分，輸出是不可預測的，但即使在提供第一部分之前，輸出已經(jīng)預先確定并且不受任何參與者的影響。
這種隨機性方法是完全不可替代且不可預測的，并且只要有2/3的參與者在線（但可以針對任何閾值進行配置），這種方法是有效的。雖然1/3離線或行為不端的參與者可能會停止算法，但至少需要2/3參與者合作才能影響輸出。
不過有一個警告。上面，我提到過這個方案的私鑰需要以特定的方式生成。密鑰生成的過程稱為分布式密鑰生成（簡稱DKG），它非常復雜，是一個非?；钴S的研究領(lǐng)域。在最近的一次談話中，Dfinity提出了一個非常復雜的方法，其中涉及zk-SNARKs，這是一個非常復雜且沒有時間測試的加密結(jié)構(gòu)，作為其中一個步驟。通常對閾值簽名BLS和DKG的研究并不處于可以在實踐中容易應用的狀態(tài)。
RandShare
NEAR方法受另一種稱為RandShare的算法的影響。Randshare是一個不可抗拒的、不可預測的協(xié)議，它可以容忍多達_的行為體是惡意的。本文還描述了兩種加快速度的方法，稱為randhound和randhound，但與randshare本身不同，randhound和randhound相對復雜，而我們希望協(xié)議非常簡單。
RandShare的一般問題除了交換的大量消息（參與者一起交換O（n^3）消息）之外，事實上雖然1/3是實踐中活躍度的有意義閾值，但影響輸出能力卻很低 。有幾個原因：
· 影響輸出的好處可能大大超過拖延隨機性的好處。
· 如果一個參與者在Randshare中控制了超過1/3的參與者，并使用它來影響結(jié)果輸出，那么它就不會留下任何痕跡。因此，一個惡意的行動者可以在不被揭露的情況下做到這一點。拖延共識自然是顯而易見的。
· 控制1/3的hashpower/staking情況并非不可能，考慮到（1）和（2）以上的控制者不太可能試圖阻止這種隨機性，但能夠并且可能會試圖影響這種隨機性。
NEAR Approach
NEAR方法在我們最近發(fā)表的論文中有所描述。這是不可避免的，不可預測的，并且可以容忍1/3惡意行為者的活力，即如果有人控制1/3或更多的參與者，他們可以停止協(xié)議。
然而，與RandShare不同，它可以容忍最多2/3惡意行為者，然后才能影響輸出。這對于實際應用來說是明顯更好的閾值。
該協(xié)議的核心思想如下（為簡單起見，假設(shè)有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)有基礎(chǔ)設(shè)施中使用，其中特定時期的塊生成器創(chuàng)建包含特定分片的所有事務(wù)的所謂塊，并且分發(fā)這樣的塊的擦除編碼版本。 merkle向其他區(qū)塊生產(chǎn)商提供證據(jù)以確保數(shù)據(jù)可用性。
下載文檔
