作者 | 邱飛暘
來源 | NPC源計劃
Algorand
Algorand 項目使用了基於 PoS 的混合共識協議，其共識過程利用了隨機抽籤。它的隨機抽籤所依賴的種子，從本質上講，是通過取前 t (t = 1) 個輸入來生成的，對應 v3.0b 版本的第一種方式。如圖 1 所示，Algorand 的共識過程要求節點先在本地抽籤，即通過一個可驗證隨機函數 (Verifabale Random Function, VRF) 在節點的本地算出來一個可驗證的確定的隨機數。VRF 可以被看作是一種特殊的偽隨機數發生器。需要補充的一點是，這裡的“確定”指的是，這樣的隨機數是無法被用戶操縱的，因為輸入是被唯一確定不受用戶控制的。這是由於，其輸入是根據上一輪隨機數生成過程的公共信息以及每個節點自己的私鑰。其中私鑰是可以被公鑰驗證的；公共信息是每個人都可以看到，是唯一確定的，並且可被其他人驗證。
本地抽籤得到本地隨機數之後，每個人會立馬知道自己是否被選中（結果是否落在某些區間內）。之後，被選中的人廣播抽籤結果、證明和候選區塊到全網節點，根據區塊的 quality 大小，選出來候選區塊，而確定哪個區塊的 quality 更大是需要做拜占庭共識的。這個時候，就需要再進行一輪本地抽籤，所有的節點會自己知道是否被選中去做 BA*（一個拜占庭類型的共識協議），即投票選自己認為的 quality 最高的候選區塊，投票會進行很多輪，每一輪都要重新進行一次本地抽籤，以增加安全性。可以看出，Algorand 共識的本質就是我們每個人都生成一個確定的隨機數。但是我們最終只想要一個隨機數，這樣我們才能根據最後確定的唯一的隨機數去決定哪個塊會被全網接受。這個時候的方案就是根據某種確定的規則從眾多備選結果中取一個，方法是通過拜占庭共識達成一致。
圖 1：Algorand 的共識協議
圖 2：VR
Cardano
Cardano 是基於 Ouroboros 的一個項目，採用了基於 PoS 的共識協議。Ouroboros 這篇論文給出了一個可證明安全的 PoS 協議框架，但是並沒有給出具體的實現，實現由 Cardano 完成。因此這裡主要講解 Cardano 在工程上採用的一個具體的方案。Cardano 所採用的方案也在第一篇所講的三種方式之中。如圖 4 所示，它的方案其實就是就是無分發者的秘密分享 + 承諾。圖 3 簡單描述了它的共識協議，在它的 Genesis Block 裡面會初始化一個隨機數，這樣就可以利用確定的抽籤算法以這個隨機數作為隨機信標來確定誰的區塊會在之後的某個 slot 裡被接受。slot 的數量是固定的，因此，有可能有的 slot 中會有不止一個節點被抽中，也有可能沒有節點被抽中，具體解決方案不在本文討論範圍內。那麼，初始化的隨機數是怎麼生成的呢？Cardano 協議首先採用了標準的承諾-揭示方案，不過在之後多了一個將隨機數做一次無分發者的公開可驗證秘密分享 (Publicly Verifiable Secret Sharing, PVSS) 的步驟。即分發碎片並且廣播證明之後揭示隨機數。這時也許有參與者會跑路，沒有揭示隨機數，但是沒有關係，這個時候剩下的參與者可以通過廣播碎片把跑路的參與者的隨機數恢復了。因此，這是一個有一定冗餘度的隨機數生成機制，但是同時帶來了一定的健壯性。通過這個機制，只要惡意節點不超過一半，一定可以生成一個隨機數。
圖 3：Cardano 的共識協議
圖 4：Cardano 的 DRB 模型
Dfinity
Dfinity 的共識算法和 Algorand 很像，如圖 5 所示，協議裡同樣需要選舉一個委員會，委員會會運行分佈式隨機信標 (Distributed Randomness Beacon, DRB) 協議得到隨機數種子。至於這個協議我們後文會講，為了理清共識協議的基本步驟，我們先假設 DRB 協議可以達成這些功能。通過這個隨機數種子，加上每個節點自己的私鑰，每個節點通過運行可驗證隨機函數 (VRF) 就可以算出自己的排名（這一點和 Algorand 一樣）。同時，由於所有節點都會被分組，那麼每一個節點應該被分配到哪一個組也是由隨機數種子決定的。在所有的組中，再次通過隨機數種子（上一輪）隨機挑選出一個組，稱之為該輪的委員會。每個節點有了自己的節點排名後，所有節點都可以提交候選區塊，廣播給所有的節點，但是大家在廣播的過程中，誠實節點就會根據排名，給目前為止它收到的最高的塊簽名，簽好後，廣播給所有的節點，如果某一個區塊獲得 1⁄2以上的合法簽名，這個區塊被稱之為已驗證的區塊。一旦誠實節點收到已驗證的區塊，這一輪就會立馬結束，並將這個已驗證區塊廣播給所有其他節點。
圖 5: Dfinity 的共識協議
由此可見，DRB 協議生成的隨機數種子至關重要。Dfinity 所採用的 DRB 協議實際上就是 v3.0b 的第三種方法——分佈式密鑰生成 + 門限簽名。首先要有一個 DKG 協議來生成符合一定要求的總密鑰對和密鑰對份額，這個協議同樣可以是 (t,n) 門限的。通過這個協議，每個人獲得密鑰對份額，但是沒有人知道總私鑰是什麼。每個節點使用自己的私鑰份額對再上一個輪次的隨機數和輪次進行簽名，簽完名將簽名結果廣播，每個節點都可以用總公鑰驗證每個簽名。然後通過門限簽名的恢復算法使用 t 個簽名恢復出來這一輪的總簽名（相當於是使用總密鑰對直接進行簽名的結果）。整個過程的算法都是完全確定的，唯一不確定的是每個節點不知道其他節點的私鑰份額是什麼。Dfinity 比較特殊的地方在於採用基於 BLS 的門限簽名，比起其他的門限簽名方案，好處有兩個。第一個好處就是一次購買，終生免費。協議只需要在一開始的階段運行一次 DKG，進行密鑰生成。之後的階段只需要 n 個人中 t 個人提交有效的簽名就可以生成隨機數，協議就可以運行下去，這個過程是異步的。第二個好處就是確定性，無論哪 t 個人提交，最後生成的隨機數都是一樣的確定的結果，沒有節點可以操縱最後的結果（不超過安全邊界的情況下）。
圖 6: Dfinity 的 DRB 模型
Randao
Randao 是基於以太坊合約的，用於在鏈上生成智能合約可用的隨機數的一個項目。它採用的是 v3.0a 的方案。每個人在提交承諾的時候，都需要提交 m 個 ETH 的押金，揭示過程會持續 w 個區塊時間。這裡有三件事需要說明。第一點是，同一個地址的多個承諾只接受第一次。第二點是收集的全網提交的承諾數有最小數量的要求，如果沒有收集到最夠的數量，整個協議就會以失敗的狀態結束，然後再重新開始。第三點就是不按時揭示的地址的押金會被沒收，並且一旦有人不揭示，協議就會以失敗的狀態結束，這樣做為了確保隨機數的公平性。協議的最後一步是 Randao 特別加入的——返還押金，給參與者獎勵的步驟，其目的是給出激勵，構建生態。
圖 7：Randao 的 DRB 模型
隨機數與共識
隨機數生成與共識協議有著千絲萬縷的關係，主要體現為以下兩點。
防止女巫攻擊的方法之一是不可預測的隨機抽籤。不論是 PoW，還是 PoS，我們都可以理解為一種隨機抽籤的方法。不管公有鏈上的共識協議再怎麼設計，包括BTC在內，都是在通過某種方式產生一定的隨機性。礦工通過 PoW 競爭出塊，使得出塊的人變得不確定，從而防止了通過偽裝大量節點獲利的女巫攻擊。
區塊鏈上的隨機數安全依賴於共識協議。以 Randao 為例，針對 Fomo3D 的攻擊同樣對 Randao 有效。由於以太坊的激勵機制和共識協議的特點，礦工會優先打包手續費高的交易，所以攻擊者可以通過 Censorship Attack，人為調整打包區塊時包含的交易，或者製造高手續費的垃圾交易，迅速的把區塊的 Gas Limit 耗光，阻止其他人的特定交易上鍊。當 Randao 即將計算出的結果不理想時，可以通過這種方式強行將協議終止，令無辜的節點蒙受損失，自己從中獲利。儘管這樣的手段有時成本較高，但這樣的攻擊仍然有無法忽略的可能性發生，而這樣的攻擊之所以成立的原因，實際上根植於共識協議的設計。再例如 Grinding Attack。Fomo3D 採用了取上一個塊的哈希值作為種子的方法生成隨機數。這種情況下，礦工可以把所有的區塊組織的可能性都試驗出來，然後選擇一種對自己最有利的方式打包交易。這種攻擊手段就是 Grinding Attack。儘管這樣的攻擊手段有一定的成本，但是如果隨機數所牽涉的利益足夠，例如用在某些賭博遊戲裡，礦工想要從中獲利非常容易。
因此，區塊鏈上隨機數的生成是需要上下文環境的，必須要給定情景。拿 Randao 來講，如果它的某一個隨機數的生成，只和 0.01 個 ETH 相關，那麼攻擊者將沒有足夠的理由去破壞它的公平性。如果押金不夠多，那麼 Randao 就有可能是不安全的。
- END -
閱讀更多 加密谷 的文章
