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

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

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

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

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

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

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

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

RANDAO

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

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

RANDAO + VDFs

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

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

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

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

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

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

這個網(wǎng)站收錄了許多關(guān)于 VDF 的文章、視頻以及其它資訊。

門限簽名

Dfinity 團(tuán)隊正倡導(dǎo)并研究的的門限 BLS 簽名是隨機(jī)性的又一實現(xiàn)方案。（題外話，Dfinity 的研究員 Ben Lynn 就是 BLS 中的 L 本尊）

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

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

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

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

RandShare

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

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

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

1. 攻擊輸出結(jié)果所帶來的收益要遠(yuǎn)遠(yuǎn)大于拖滯隨機(jī)數(shù)生成帶來的收益。

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

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

NEAR 方案

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

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

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

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

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

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

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

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

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

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

結(jié)語

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

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

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

來源： 以太坊愛好者