隨機事件在我們身邊無處不在。比如，運氣、概率和命運就與隨機性密不可分。人類不理解或無法預測的一切事物往往被歸類為隨機事件。物理世界中也有許多隨機事件，比如雲的運動、粒子和波的軌跡等。然而，儘管它是那麼的令人熟悉，人類卻很難將周圍的隨機性轉化為計算機可以計算的東西。本文作者Aparna Krishnan，由格密鏈社羣的周志強翻譯。當我們談論計算機系統中的隨機性時，我們指的是偽隨機性，這是一種對現實世界隨機性的模擬產物。不過，這兩種隨機性很難區分。我們在這裡要討論的是非常強大的模擬性隨機（偽隨機）。隨機性在隱私技術和密碼學中發揮著重要作用。值得驚歎的是透過一個隨機值與一條資訊就能提供一種簡單而強大的加密方案。比如對稱金鑰加密技術，兩方進行交流時需要事先共享一個保密金鑰，但即使是進行最簡單的交流也需要確保共享金鑰是隨機的。如果此共享金鑰不隨機，則任何人都可以透過已知的密碼演算法與資訊內容竊取保密金鑰，加密也就失去了意義。隨機性的作用：利用隨機性可以在兩個人之間構建一個安全的通訊渠道，也可以用來確認通訊雙方的身份。此外，如果同時有很多人想透過有限頻寬的通訊渠道彼此通訊，則可以使用隨機性來公平地確定訊息傳遞的順序。隨機性也可以用來幫助一群人或計算機達成一致。隨機共識協議就是這樣一個例子。這篇文章將探討隨機性在區塊鏈中的作用。區塊鏈是幫助多方在全球層面上就某種程度的更新達成共識的完美例子。更新通常按照回合的方式完成，每個回合是一個週期性的離散時間段。一般限制共識的的因素有兩個：吞吐量（在網際網路上的特定時間段內可以傳送的訊息數量上限）以及延遲（訊息透過網際網路傳送所需的時間）。任何區塊鏈共識協議的目標都是克服上述限制因素達成共識。在公鏈中，數千個節點參與維護區塊鏈，如果每個節點都需要向其他所有節點傳送訊息並等待來自所有其他節點的響應，吞吐量與延遲將會讓達成共識的成本大幅增加。成本高昂是因為一個回合中傳遞的資訊數量太過龐大，因此為了達成共識而最佳化網路溝通方案的一個方式就是削減資訊的數量。比特幣達成共識的方式（中本聰共識）是使用工作量證明（PoW）作為隨機源確定每輪中哪一個區塊將被新增到區塊鏈中，從而減少訊息傳遞的開銷。因為PoW的計算非常複雜，且只有第一個解決難題的人擁有記賬的權利，再加之多人同時解答出難題的概率極低，PoW機制就透過這種方式限制了網路中的資訊數量。當然，任何試圖取代PoW的共識機制同樣需要一種方法來限制網路傳遞的訊息。大多數的權益證明協議（PoS）解決此問題的方法是選擇驗證者（即維護/管理區塊鏈的節點），並根據他們抵押代幣的數量成立一個委員會小組。然後，該驗證小組可以在網路限制下合理地來回通訊，最終高效地達成共識。什麼是理想的隨機源：當然，為了公平地選擇這個委員會小組的成員並且保證沒有人提前知道成員名單，演算法必須要得到一些公平且不可篡改的隨機源。一旦該驗證小組在新區塊上達成一致，該區塊就會被廣播給網路中的其他所有節點。PoS協議中用於選擇委員會成員的理想隨機源應確保不可被篡改，隨機性協議則需要確保以下兩點：i）隨機性函式持續有輸出ii）隨機性函式的輸出尚未被操縱（注意：我們將在以後的文章中探討如何平衡第一第二點，以及這與網路同步模型的關係）我們機械實驗室（Mechanism Labs）分析了當下所有的委員會成員選舉協議，結論是沒有一個協議能同時實現高效能與不可篡改。我們的看法是，鑑於上述權衡，區塊鏈共識協議應選擇一個始終有輸出的隨機源，而不是單單產生無篡改輸出的隨機源。這是因為區塊鏈協議需要確保鏈持續增長且不能讓隨機源成為限制發展的因素。即使對於一致性協議，隨機源也不應該是限制區塊鏈發展的原因。總之，隨機源應該為協議減輕負擔，使協議能夠專注於減輕其他攻擊，如針對委員會小組的DoS攻擊。如果區塊鏈由於隨機性函式停止輸出而完全停止，在社會層面上將需要巨大的協調成本來重新啟動區塊鏈。社群需要花費大量的時間透過外部社交媒體平臺就區塊鏈的形式達成一致，這樣做的成本與解決DAO駭客的成本相當。這種鉅額成本也會動搖社羣對區塊鏈協議安全性的信心。另一方面，只要偏差很小並且存在修正偏差的機制，僅僅幾輪的輕微偏差帶給區塊鏈安全性的影響也會很小。這是因為在每一輪公共區塊鏈協議中給予驗證者的協議內獎勵相對較小。但是由於每輪或每個時期（一組輪次）都會選擇新的小組委員，因此在隨機性函式中總會存在某個顯著的偏差，讓驗證者可以鑽空子賺錢並導致區塊鏈協議的安全性降低。此外，主打隨機性的彩票遊戲需要確保隨機源不被操縱，因為即使一點偏差也會改變彩票的贏家。這是因為篡改彩票結果的效果是巨大的，可以獲得了大量的即時獎勵。因此，這樣的遊戲適合僅保證無篡改輸出的隨機性函式，即使這意味著隨機函式的輸出有時會停止。不可篡改隨機源的重要性：接下來我們將討論在設計區塊鏈協議時不可篡改的隨機源的重要性。下文開始，我們提到的協議預設都是不會停止的協議。理想的委員會選舉方案須具備以下兩點：1.不可篡改2.只在新一輪的開始時顯示隨機種子。鑑於上述兩點，隨機函式也需要具有不可篡改性。如果隨機性可以被操縱（並且存在協議獎勵分配機制），就會導致獎勵的不公平分配。不公平的獎勵分配意味著一些人獲得更多的獎勵。由於只有那些有抵押的人才能成為驗證者，並且投票權與驗證者所擁有的權益資產成正比，結果將導致區塊鏈最終被某些人掌控。可以說，哪個協議抗篡改的程度高，它就能在長遠中獲得維持部分網路的權力。另外，在新一輪迴合開始之前公佈種子的時間提前量決定了誰可以首先成為網路的一部分。因此，上述兩個屬性將決定區塊鏈的去中心化程度。用於選擇委員會小組的協議是每一輪或每幾輪執行的，因此從該隨機函式的輸出釋出的時間到回合開始的時間是至關重要的。在此時間範圍內，攻擊者可以使用隨機函式的輸出來確定哪個驗證節點會被選中。如果這個輸出被隱藏，則試圖攻擊區塊鏈協議的攻擊者將無法提前確定驗證節點。此時間範圍的長度決定了協議可以承受的攻擊者的強度。強大的攻擊者（即具有更多算力和資源攻擊網路的人）能夠在很短的時間內算出驗證節點。如果攻擊者有足夠的時間，透過委員會成員選擇演算法和給定輪次的隨機種子，就能夠確定驗證節點。確定驗證節點後，攻擊者就能夠對驗證節點發起DoS攻擊，從而導致空塊以及步驟缺失。區塊鏈即使只停止一輪也會有非常可怕的後果。想想如果世界上所有人在幾個小時內無法進行任何交易，比特幣會發生什麼！因此，應該選擇抗DoS攻擊的節點成為驗證節點。另一方面，提前揭示隨機種子意味著共識協議只能抵抗較弱的攻擊，這減弱了區塊鏈的去中心化屬性。現有隨機性生成機制：下面我們將詳細介紹各種隨機性生成機制。以下內容基於我們在《替代共識協議的元分析》中分析的區塊鏈協議：TendermintTendermint共識機制使用確定性迴圈協議方案來選擇提議者; 協議不具有隨機性，提議者基於投票權和被選為驗證者的次數確定。攻擊者只能透過繫結或解除繫結權益對協議施加影響，因為這是對於協議的唯一輸入手段。同時，協議不會在短時間內出現偏差，因為驗證者需要很長時間才能繫結（即向系統抵押保證金）或者解除繫結（即從系統中撤回保證金）。不過，在這種機制下攻擊者可以提早很久作出計劃，誤導提議者作出錯誤選擇。使用確定性隨機演算法意味著在每輪投票之前可以公開隨機種子，不過提議者也會被提前確定。AlgorandAlgorand共識機制中的隨機性方案如下：每輪被選為驗證者的v會為回合r計算出種子，公式為<seedr, π > ← VRFskv (seedr−1||r)，公式中skv是驗證者v的金鑰，seedr−1是前一輪的隨機種子。r-1輪接受的塊中包含VRF證明π和r輪的種子。如果給定的VRF證明未驗證給定的種子，每個人將用加密雜湊函式來計算新一輪的種子，公式為seedr=H (seedr-1) || r)。這意味著每位驗證者必須選擇好自己的金鑰，以確保種子不會發生偏差。當網路不是強同步時，如果攻擊者完全地控制住訊息傳遞連結，進而刪除區塊提議並強制使用者就空塊達成一致，就能借此計算出後續的隨機種子。因此，Algorand需要弱同步，即在每個長度為u的週期中，必須存在長度為s <u的強同步週期，使協議具有抗偏差性。只要強同步時期s足夠長使得b時間段內產生至少一個誠實的區塊，選擇金鑰的攻擊者v'就不能使r輪的隨機性種子產生偏差。只有當一個塊被提出時，新種子和VRF證明才會去公開地驗證它。這確保了提議者和隨機種子不會提前洩露。這確保Algorand能夠抵禦針對提議者的DoS攻擊，並且在擦除與瞬時腐化中保持自適應安全性。Dfinity:在幾個協議中，攻擊者通常會透過中止協議來呼叫回退機制，從而引入偏差。Dfinity使用的閾值方案是抗偏差的，因為閾值的選擇是為了防止攻擊者透過阻止闕值簽名（闕值簽名是隨機種子的創造來源）來中止協議。這使得闕值需要符合以下公式：t∈[f + 1，n - f] 其中f是攻擊者控制的簽名數，n是方案中的簽名總數，t是生成隨機性所需的簽名閾值。符合條件的閾值確保了攻擊者無法預測簽名建立的結果，更無法阻止簽名的建立。需要注意的是，如果攻擊者擁有任何BLS方案中所有存款的50％以上，就能夠操縱最終的簽名和隨機性。但是，如果攻擊者真的擁有如此大的股權佔比，他們也會有其他的攻擊選擇，這就打破了Dfinity協議的基本假設。只要有誠實的驗證者前進到第r輪，隨機種子就會被公佈。雖然誠實的驗證者到達r輪與新一輪正式啟動之間的時間差距很小，但這個差距足以讓擁有大量算力的攻擊者找到提議者併發起DoS攻擊。這就是Dfinity只能承受輕度適應性攻擊而不能承受瞬時腐化的原因。Thunderella:在雜湊函式例項化的隨機預言方案中，提議者由以下公式確定：H_nonce(pk，q)<Dp 其中H是作為隨機預言的雜湊函式，pk是驗證者的公鑰，q是給定的時間步驟，而nonce是雜湊函式的熵來源。nonce由前一個塊的提議者決定。設定難度引數D_p使得在單個時間步驟中，委員會成員被選為提議者的概率為w。如果攻擊者提出了一個塊，他就可以影響下一輪雜湊函式的熵來源（nonce），進而影響下一個塊中選出的提議者。這種情況下，為了減少隨機性方案的偏差值，雜湊函式會使用相同的熵來源選擇r輪的提議者而不是下一輪提議者。因此攻擊者很難暴力改變熵來源，也就無從成為下一輪的提議者。不過這種策略僅能保證多項式安全損失，它伴隨著對可預測的妥協，這一點將在後文討論。總之，該方案導致這個協議僅能夠承受慢速適應攻擊。在上述演算法中，當重複使用相同的熵來源為雜湊函式提供種子時，會導致攻擊者能夠提前預測出提議者。在一個時期內相同的熵來源被重新用作熵，會導致隨機種子在新一輪的開始之前被洩露。造成的後果為攻擊者可以腐化提議者或者發起DoS攻擊。Casper FFG:Casper FFG計劃使用的randao方案採用以下演算法：在輪次開始時每個驗證者都提交H(H(H(... Sv))))，其中S是驗證者提交的種子。R：=R⊕雙層雜湊表內層的原像。在一個回合中，驗證者可以生成或中止一個區塊。如果在回退機制中不具有隨機性，這似乎是比隨機性可預測或可偏差更嚴重的問題，因為那樣你不再需要1/3的惡意節點才能中止協議，而是1個人就足夠。只需要滿足，那個人驗證者當前是提議者，且下一輪的種子已經公佈，即可1個人中止協議。隨機性是密碼學和區塊鏈的關鍵部分。不良的隨機性方案造成的後果有兩個：1.中止區塊鏈協議2.導致中心化，這些後果可能顛覆區塊鏈的所有安全概念。因此，瞭解隨機性在區塊鏈協議中的作用有助於真正理解區塊鏈安全性的本質。
更多區塊鏈資訊：www.qukuaiwang.com.cn/news
