區(qū)塊鏈協(xié)議中的隨機(jī)性的重要性

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

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

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

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

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

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

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

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

RANDAO

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

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

RANDAO + VDFs

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

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

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

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

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

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

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

門限簽名

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

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

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

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

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

RandShare

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

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

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

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

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

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

NEAR 方案

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

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

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

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

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

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

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

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

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

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

結(jié)語(yǔ)

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

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

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

來(lái)源： 以太坊愛好者