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

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

當(dāng)我們?cè)O(shè)計(jì)分布式隨機(jī)性算法時(shí)，我們希望它有三個(gè)屬性：

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

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

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

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

RANDAO

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

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

RANDAO + VDF

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

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

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

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

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

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

門限簽名BLS

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

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

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

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

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

RandShare

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

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

· 影響輸出的好處可能大大超過(guò)拖延隨機(jī)性的好處。

· 如果一個(gè)參與者在Randshare中控制了超過(guò)1/3的參與者，并使用它來(lái)影響結(jié)果輸出，那么它就不會(huì)留下任何痕跡。因此，一個(gè)惡意的行動(dòng)者可以在不被揭露的情況下做到這一點(diǎn)。拖延共識(shí)自然是顯而易見(jiàn)的。

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

NEAR Approach

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

然而，與RandShare不同，它可以容忍最多2/3惡意行為者，然后才能影響輸出。這對(duì)于實(shí)際應(yīng)用來(lái)說(shuō)是明顯更好的閾值。

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

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

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

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

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

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

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

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