我們今天發(fā)表的一篇短論文介紹了 NEAR 協(xié)議所采用的隨機信標。佐餐食用的本博文將著重討論隨機性的重要意義、實現難度以及其它協(xié)議的實現路徑。

包括 NEAR 在內的諸多新型區(qū)塊鏈協(xié)議都高度依賴于隨機性，以抉擇由哪些成員執(zhí)行協(xié)議中的特定操作。如果惡意攻擊者能影響隨機源，他們就有機會增加自己被選中的概率，最終威脅協(xié)議的安全性。

分布式隨機性同樣也是眾多區(qū)塊鏈應用的重要基石。舉例來說，假如某個智能合約接受用戶的賭約，規(guī)則為無偏倚地產生一個隨機數，據此以 49% 的概率返還兩倍押注，51% 的概率沒收賭資。如果惡意攻擊者可以影響或者預測該隨機數，他們就能旱澇保收，并很快搬完合約中所有的資金。

在設計分布式隨機性算法時，我們希望它具備以下屬性：

1. 算法必須公正無偏（unbiasable）。換言之，不允許有任何參與者能絲毫影響隨機數生成器的結果。

2. 算法無法被預測。即在隨機數生成之前，所有的參與者都不知道會生成什么樣的結果（也不能預測到其屬性）。

3. 協(xié)議需要具備在某些節(jié)點掉線時仍保持正常運行的容錯能力，即使有節(jié)點故意阻礙協(xié)議，也可以繼續(xù)運行。

本文將介紹分布式隨機信標的基礎知識，說明為何樸素的技術方案無法達成效果。在最后，我們將介紹 DFinity 、Ethereum Serenity 以及 NEAR 協(xié)議所采用的隨機信標方案，并逐一剖析其優(yōu)越性與不足之處。

RANDAO

RANDAO 非常簡單，因此也是一個十分常見的隨機性實現方案。其大致思想是網絡中的所有人首先各自私下選定某個隨機數，然后向 RANDAO 提交該隨機數的承諾，接著所有人根據一定的共識算法從所有的承諾中選定一組；在參與者揭示這組承諾背后的隨機數之后，大家對該組隨機數達成共識；最后這組隨機數進行異或操作得到的結果就是一輪 RANDO 協(xié)議產生的隨機數。

RANDO 的做法的確讓隨機數難以預測，并且隨機數享有與底層共識協(xié)議一樣的活性，但仍有可以鉆空子的地方。比方說，惡意攻擊者看到網絡中所有其他人揭露各自所選取的隨機數之后，可以根據自身隨機數先執(zhí)行異或運算，并根據結果對自己的利弊來決定是否要揭露自己的隨機數。這種設計使得單個攻擊者就能對輸出造成一定的影響，同時隨著攻擊方所控制的參與者數目增多，他們的破壞性也隨之增強。

RANDAO + VDFs

要增強 RANDAO 的公平性，其中一種辦法是替換掉最后的那個異或計算，將其改變?yōu)閳?zhí)行時間必定長于各方隨機數揭露等待期的操作。如果計算最終結果的時間比隨機數揭露等待期要長，那么惡意攻擊者就無法預先知道自身隨機數揭露與否能給自己帶來好處，因此理論上就無法影響最終結果的屬性了。

雖然需要有一個函數來拖延參與者生成最終結果的時間，但不能因此讓隨機數用戶也耗費巨大的開銷去驗證所生成的隨機數。因此，理想函數應該能讓用戶輕易驗證系統(tǒng)生成的隨機數，而無需重復之前的計算開銷。

上述既需要長時間來計算，同時能輕易驗證計算結果，并且對每一個輸入都有著獨一無二輸出的函數正是可驗證延遲函數（verifiable delay function ，可縮寫作 VDF ），設計一個這樣函數的工作委實艱巨。近來這一領域已經有所突破，比如這個和這個已經可以應用，當前以太坊就計劃應用 RANDAO 和 VDF 來作為其隨機性信標。除此之外，由于這種策略所具備的不可預測性和無偏見性，使得系統(tǒng)甚至能在僅有兩個參與者在線的情況下依然具備活性（假設底層共識協(xié)議的在參與者如此稀少時仍能具備活性）。

VDF 雖好，但目前的最大挑戰(zhàn)在于函數需要足夠健壯，即使某些別有用心者花大價錢配置定制化硬件設備，也無法在揭露等待期結束之前計算出最終結果，理想情況是函數具備有足夠威懾力的安全邊際，例如延遲時間較揭露等待期拖長 10 倍。下圖展示了系統(tǒng)中參與者采用定制化 ASIC 設備所發(fā)起的一次攻擊，攻擊者能夠在各方揭露 RANDAO 承諾之前計算出最終會輸出的隨機數。攻擊者依然能根據計算得到的隨機數結果，以及最終結果對自身收益的利害關系，自主決定是否要揭露所掌握的隨機數。

和 VDF 家族關聯的特制 ASIC 設備會比傳統(tǒng)硬件的計算速度快 100 倍。因此，如果揭露等待期耗時 10 秒，同時為了達成理想的 10 倍安全邊際，需要保證 ASIC 設備至少花 100 秒才計算出最終結果，由此換算到普通硬件設備上則需 100 x 100 秒，即約 3 個小時來得到輸出結果。

針對這一問題，以太坊基金會的做法是設計自己的 ASIC 設備并開源。一旦上述設想落地，以太坊之外的其它協(xié)議也能把真正的隨機數用起來了。不給過在那個時刻到來之前，無力投資研發(fā)自己 ASIC 設備的協(xié)議們還是沒法應用 RANDAO + VDF 的解決方案。

這個網站收錄了許多關于 VDF 的文章、視頻以及其它資訊。

門限簽名

Dfinity 團隊正倡導并研究的的門限 BLS 簽名是隨機性的又一實現方案。（題外話，Dfinity 的研究員 Ben Lynn 就是 BLS 中的 L 本尊）

BLS 簽名用于多方對一則消息構建一條聚合簽名，由于無需額外的簽名通信，因此常用于節(jié)省空間和帶寬。在區(qū)塊鏈里，BFT 共識協(xié)議的區(qū)塊簽名通常就使用 BLS 簽名。例如在一個有 100 個節(jié)點的區(qū)塊鏈系統(tǒng)中，當其中的 67 個節(jié)點都對某個區(qū)塊進行了簽名時，就可以認定這個區(qū)塊已經上鏈。每一個節(jié)點都可以提交自己那片 BLS 簽名，系統(tǒng)根據某些共識算法選出其中 67 片簽名來聚合成一條 BLS 簽名。雖然任意 67 片簽名都能組成一條聚合簽名，但不同的簽名輸入不會聚合成相同的 BLS 簽名。

其實如果系統(tǒng)中參與者持有的私鑰是通過某種特殊方式生成的，那無論選擇哪 67 片（可以更多，但不能更少）簽名，都能輸出一樣的聚合簽名。這種特性可以用來產生隨機性：系統(tǒng)中參與者首先對某則他們未來會進行簽名的信息達成一致（可以是 RANDAO 的輸出，也可以是最近一個區(qū)塊的哈希，只要是每次都不一樣的值就可以了），然后就此產生一個聚合簽名。在 67 個參與者揭露自身簽名之前，沒有人能預測輸出結果，同時由于大家在第一片簽名披露之前就認定完了輸出結果，因此任何參與者都無法再對輸出產生影響。

上述隨機性實現方案具備無偏見性和不可預測性，只要網絡中有 2/3 參與者在線就能維持運行（這個門限當然也可以設置成其它數值）。即使 1/3 的節(jié)點掉線或篡謀發(fā)起攻擊，他們也只能讓系統(tǒng)停滯，因為要想對最終結果產生影響，需要至少 2/3 的節(jié)點。

看起來一切都很完美，但是，依然有一個但是。前文我曾提及私鑰需要按某種特殊方式生成，這種被稱為分布式密鑰生成的技術（常簡稱為 DKG ）事實上十分復雜并且仍處于探索階段。在最近的一些公開演講中，Dfinity 提出了使用 zk-SNARKs 來實現 DKG，但是 zk-SNARKs 十分復雜，并且這種構造方法還沒有經過時間檢驗?？偟膩碚f，門限簽名和 DKG 技術尚未發(fā)展到能落地應用的階段。

RandShare

目前為止，NEAR 受到的最大影響來自于另一種算法：RandShare 。

RandShare 是一個無偏見且不可預測的協(xié)議，支持 1/3 惡意節(jié)點容錯。其速度相對較慢，在對應論文中雖然提到了 RandHound 和 RandHerd 兩種加速方法，然而和 RandShare 本身相比還是太過復雜，我們想要的理想協(xié)議應該簡潔優(yōu)美。

除了較大的通信壓力（各節(jié)點需要進行 O（n^3） 級別的消息通信），RandShare 面臨的另一個問題在于雖然 1/3 的容錯門限能保證協(xié)議在應用中的活性，但這個門限難以震懾別有用心者對輸出結果發(fā)起攻擊。具體原因有以下幾點：

1. 攻擊輸出結果所帶來的收益要遠遠大于拖滯隨機數生成帶來的收益。

2. 如果某一方控制了 RandShare 中超過 1/3 的節(jié)點并試圖操縱輸出結果，這種攻擊甚至不會留下任何痕跡。與光天化日之下拖滯隨機數生成相比，操縱輸出結果根本就是悶聲發(fā)大財。

3. 從現實考量，某勢力操縱超過 1/3 的 哈希算力/權益 并非天方夜譚，而且根據（1）（2）兩點，具備實力的攻擊者基本不會選擇拖滯隨機數生成，而是傾向于暗地操縱輸出結果。

NEAR 方案

我們最近發(fā)表的一篇論文介紹了 NEAR 方案。這是一個無偏見且不可預測的協(xié)議，其活性具備 1/3 節(jié)點的容錯能力，即攻擊方只有控制了全局 1/3 及以上的節(jié)點才能阻塞協(xié)議。

然而和 RandShare 不同，NEAR 能保證 2/3 惡意節(jié)點的容錯。這個門限對實際應用來說顯然更為優(yōu)越。

NEAR 協(xié)議的核心思想如下（為了方便表述，此處假設正好有 100 個節(jié)點）：

1. 每一個節(jié)點首先提出自己的輸出片，將其分成 67 份，再用糾刪碼將其編碼為 100 份，這一過程需要保證任意 67 份數據都可以恢復輸出片，然后使用其它各節(jié)點的公鑰對每一份數據簽名并轉發(fā)，這樣一來，各節(jié)點互相持有加密片。

2. 系統(tǒng)中各節(jié)點使用某種共識算法（例如 Tendermint）選出特定 67 個節(jié)點所生成的加密片。

3. 一旦達成共識，各個節(jié)點根據步驟 （2） 的結果，從本地取出被自身公鑰簽名過的加密片，解碼揭露數據后立即廣播。

4. 一旦有 67 個節(jié)點完成了步驟 （3） ，系統(tǒng)就有了足夠的信息解碼重構出原始數據，最終結果可以由 （1） 中各節(jié)點輸出片的簡單異或操作得到。

上述協(xié)議具備無偏見性和不可預測性的道理和 RandShare 以及門限簽名都類似：一旦達成共識，輸出已經被確定了，只不過要等到至少 2/3 的節(jié)點用各自公鑰將加密的那部分揭露，大家才能看到輸出結果。

如果要考慮一些特殊情況以及可能的惡意攻擊，協(xié)議可能變得稍稍復雜（舉例來說，如果步驟（1）中有節(jié)點生成無效的糾刪碼，系統(tǒng)需要有能力應對），但總的來說整個協(xié)議還是十分清爽，涵蓋了所有證明和相關密碼學原語和引用的論文篇幅僅 7 頁長。如果你想了解算法更為規(guī)范的描述，或是對其活性和防御性的分析，請務必閱讀我們的論文。

當前 NEAR 協(xié)議架構已經應用了類似的糾刪碼思想，系統(tǒng)中區(qū)塊生產者會在特定時期內創(chuàng)建一些分塊，其中包含了對于某一特定分片的所有交易，然后將分塊進行糾刪碼編碼后的版本附帶默爾克證明發(fā)送給其它區(qū)塊生產者，以保證數據可用性。

結語

我們正在努力編寫一組主題為區(qū)塊鏈協(xié)議及相關內容的高質量技術文章，本文是其中一篇。除此之外，我們還制作了一系列面向其它協(xié)議創(chuàng)始人和核心開發(fā)者的視頻，目前已經錄制了針對包括 Ethereum Serenity、Cosmos、Polkadot、Ontology、QuarkChain 在內多個項目的視頻。為了便于查看，所有視頻都已經被打包進了這個播放列表。

如果你對 NEAR 協(xié)議背后的技術感興趣，請務必研讀上文提到的那篇分片論文。NEAR 是少數幾個在分片中解決狀態(tài)驗證和數據可用性矛盾的協(xié)議，并且該論文在給出我們的解決方案之外，還提供了一個針對分片的更為開闊、通用的視角。

今時今日，雖然擴容是區(qū)塊鏈中的大挑戰(zhàn)，但可用性難題或許更值得大家關注。我們團隊對此傾注了大量資源，努力構建更可用的區(qū)塊鏈系統(tǒng)。最近我們發(fā)表了一篇概覽，介紹了當今區(qū)塊鏈協(xié)議面臨的種種可用性挑戰(zhàn)，以及對應的探索路線。

來源： 以太坊愛好者