這是不可預測的,與基礎共識協議具有相同的活力,但是可偏倚的。具體來說,一旦其他人開始透露他們的數字,惡意的參與者就可以觀察網路,並根據目前觀察到的數字的異或來選擇透露或不透露他們的數字。這允許一個惡意參與者對輸出產生一點影響,而控制多個參與者的惡意參與者的影響程度與其控制的參與者數量相同。
RANDAO + VDF
為了使RANDAO不可替換,一種方法是使輸出不僅僅是XOR,而是需要花費更多時間來執行而不是分配時間來顯示數字。如果最終輸出的計算花費的時間長於揭示階段,則惡意行為者無法預測它們顯示或不顯示其數量的影響,因此不能影響結果。
雖然我們希望計算隨機性的函式為生成隨機數的參與者花費很長時間,但我們希望隨機數的使用者不必再次執行相同的昂貴函式。因此,他們需要以某種方式能夠快速驗證隨機數是否正確生成,而無需重新進行昂貴的計算。
這種計算時間長、驗證計算速度快、每個輸入都有唯一輸出的函式稱為可驗證延遲函式(簡稱vdf),結果表明設計一個延遲函式非常複雜。最近有了多項突破,即這一次和這次突破使得它成為可能,以太坊目前計劃使用RANDAO和VDF作為隨機信標。除了這種方法不可預測和不可替代的事實之外,即使只有兩個參與者線上,它還具有活力的額外優勢(假設基礎共識協議具有如此少的參與者的活力)。
這種方法最大的挑戰是,需要以這樣的方式配置vdf:即使是擁有非常昂貴的專用硬體的參與者也無法在顯示階段結束之前計算vdf,理想情況下,具有一些有意義的安全邊際,比如10倍。下圖顯示了具有專用ASIC的參與者的攻擊,該ASIC允許他們比分配用於顯示RANDAO承諾的時間更快地執行VDF。這樣的參與者仍然可以在有和沒有共享的情況下計算最終輸出,並根據這些輸出選擇顯示或不顯示:
對於上面的VDF系列,專用ASIC可以比傳統硬體快100倍。因此,如果顯示階段持續10秒,則在這樣的ASIC上計算的VDF必須花費超過100秒才能具有10倍的安全深度,因此在傳統硬體上計算的相同VDF需要花費100 x 100秒= 約3小時。
以太坊基金會計劃解決的方法是設計自己的ASIC,並免費公開發布。一旦發生這種情況,所有其他協議都可以利用這項技術,但在此之前,RANDAO + VDFs方法對於無法投資設計自己的ASIC的協議來說並不可行。
門限簽名BLS
由Dfinity開創的另一種隨機性方法是使用所謂的門限BLS簽名。
BLS簽名是一種允許多方在訊息上建立單個簽名的結構,通常用於透過不需要傳送多個簽名來節省空間和頻寬。區塊鏈中BLS簽名的常見用法是在BFT協議中對塊進行簽名。假設100個參與者建立了區塊,並且如果其中67個塊在其上簽名則認為該區塊是最終的。他們都可以提交他們的BLS簽名部分,然後使用一些共識演算法來同意其中的67個,然後將它們聚合成單個BLS簽名。任何67個部分都可用於建立累積簽名,但是根據彙總的67個簽名,生成的簽名將不相同。
事實證明,如果參與者使用的私鑰是以特定方式生成的,那麼無論聚合的是多過67個(或更多,但不是更少)簽名,所得到的多重簽名都是相同的。這可以用作隨機源:參與者首先同意他們將簽署的一些訊息(它可能是RANDAO的輸出,或者只是最後一個區塊的雜湊,只要它是真的無關緊要每次都不同並達成一致),並在其上建立多重簽名。直到67個參與者提供他們的部分,輸出是不可預測的,但即使在提供第一部分之前,輸出已經預先確定並且不受任何參與者的影響。
這種隨機性方法是完全不可替代且不可預測的,並且只要有2/3的參與者線上(但可以針對任何閾值進行配置),這種方法是有效的。雖然1/3離線或行為不端的參與者可能會停止演算法,但至少需要2/3參與者合作才能影響輸出。
不過有一個警告。上面,我提到過這個方案的私鑰需要以特定的方式生成。金鑰生成的過程稱為分散式金鑰生成(簡稱DKG),它非常複雜,是一個非常活躍的研究領域。在最近的一次談話中,Dfinity提出了一個非常複雜的方法,其中涉及zk-SNARKs,這是一個非常複雜且沒有時間測試的加密結構,作為其中一個步驟。通常對閾值簽名BLS和DKG的研究並不處於可以在實踐中容易應用的狀態。
RandShare
NEAR方法受另一種稱為RandShare的演算法的影響。Randshare是一個不可抗拒的、不可預測的協議,它可以容忍多達_的行為體是惡意的。本文還描述了兩種加快速度的方法,稱為randhound和randhound,但與randshare本身不同,randhound和randhound相對複雜,而我們希望協議非常簡單。
RandShare的一般問題除了交換的大量訊息(參與者一起交換O(n^3)訊息)之外,事實上雖然1/3是實踐中活躍度的有意義閾值,但影響輸出能力卻很低 。有幾個原因:
· 影響輸出的好處可能大大超過拖延隨機性的好處。
· 如果一個參與者在Randshare中控制了超過1/3的參與者,並使用它來影響結果輸出,那麼它就不會留下任何痕跡。因此,一個惡意的行動者可以在不被揭露的情況下做到這一點。拖延共識自然是顯而易見的。
· 控制1/3的hashpower/staking情況並非不可能,考慮到(1)和(2)以上的控制者不太可能試圖阻止這種隨機性,但能夠並且可能會試圖影響這種隨機性。
NEAR Approach
NEAR方法在我們最近發表的論文中有所描述。這是不可避免的,不可預測的,並且可以容忍1/3惡意行為者的活力,即如果有人控制1/3或更多的參與者,他們可以停止協議。
然而,與RandShare不同,它可以容忍最多2/3惡意行為者,然後才能影響輸出。這對於實際應用來說是明顯更好的閾值。
該協議的核心思想如下(為簡單起見,假設有100個參與者):
1. 每個參與者提出他們的部分輸出,將其分成67個部分,擦除程式碼以獲得100個份額,使得任何67個足以重建輸出,將100個份額中的每一個分配給其中一個參與者並使用這種參與者的公鑰。然後他們共享所有的編碼。
2. 參與者使用一些共識(如:tendermint)從67名參與者中就這些編碼集達成一致。
3. 一旦達成一致意見,每個參與者將以公開金鑰編碼的方式釋出的67個集合中的每一個集合中的編碼共享,然後解碼所有這些共享,並立即釋出所有這些解碼共享。
4. 一旦至少67個參與者完成了步驟(3),所有商定的集合可以被完全解碼和重建,並且最終的數量可以作為參與者在(1)中提出的初始部分的XOR獲得。
這個協議不可破解和不可預測的原因類似於隨機共享和門限簽名:一旦達成共識,就可以決定最終的輸出,但直到有個參與者解密用其公鑰加密的共享,任何人都不知道最終的輸出。
處理所有極端情況和可能的惡意行為使其稍微複雜一些(例如,當步驟(1)中的某個人建立了無效的擦除程式碼時,參與者需要處理這種情況),但總的來說整個協議非常簡單,用所有證明描述它的整篇論文,相應的加密原語和參考只有7頁長。
類似的利用糾刪碼的想法已經在NEAR的現有基礎設施中使用,其中特定時期的塊生成器建立包含特定分片的所有事務的所謂塊,並且分發這樣的塊的擦除編碼版本。 merkle向其他區塊生產商提供證據以確保資料可用性。