門限簽名是如何構(gòu)建隨機(jī)信標(biāo)的

回顧 2015，DFinity 項(xiàng)目提出了令整個(gè)社區(qū)都為之興奮的隨機(jī)信標(biāo)方案 —— 使用 BLS 門限簽名產(chǎn)生隨機(jī)輸出，同時(shí)保證輸出的無偏性及不可預(yù)測(cè)性。然而，時(shí)至 2020 年的今天，構(gòu)建無偏且不可預(yù)測(cè)的隨機(jī)信標(biāo)仍然困難重重，還在研究的項(xiàng)目少之又少。

其實(shí)門限簽名只是構(gòu)建隨機(jī)信標(biāo)的可行方法之一，我們前面發(fā)表過一篇概覽文章，介紹其他可能的解決方法，其中包含本文要重點(diǎn)提到的一種。其他細(xì)節(jié) —— 隨機(jī)信標(biāo)是什么？什么是無偏性及不可預(yù)測(cè)性？除了門限簽名還有什么方法 —— 這些問題都能在上述概覽中得到解答。

經(jīng)過了多次設(shè)計(jì)迭代，我們最終提出類似 DFinity 的方案，這也是我們進(jìn)一步深入理解隨機(jī)信標(biāo)的大好契機(jī)。

本文將以淺顯的形式，講述門限簽名生成隨機(jī)數(shù)的一系列協(xié)議。

密碼學(xué)基礎(chǔ)知識(shí)

為了更好地了解本文中提到的隨機(jī)信標(biāo)，我們需要掌握一些基礎(chǔ)密碼學(xué)知識(shí)。首先，我們必須區(qū)分兩個(gè)概念：1. 在本文中以小寫字母（例如 x、y）表示標(biāo)量，或者說普通常量；2. 用大寫字母表示橢圓曲線上的點(diǎn)（elliptic curve point）。

我們不需要對(duì)橢圓曲線點(diǎn)了解得很透徹，只要掌握下面兩點(diǎn)：

1. 橢圓曲線點(diǎn)可以相加，也可以跟標(biāo)量相乘（本文里用 xG 表示，用 Gx 表示也很常見），然后得到另一個(gè)橢圓曲線點(diǎn)。

2. 即使知道 G 和 xG 的值，也不可能計(jì)算出 x 的值。

在本文中，我們還將用到 k-1 階多項(xiàng)式 p（x） ；關(guān)于 p（x），你不用想太多，只要把它當(dāng)成一個(gè)方程就好，而且：只要你知道在 k 個(gè)不同的 x 下 p（x） 的值，你就能推導(dǎo)出所有 x 的 p（x） 值。

以此類推，對(duì)于同一個(gè)函數(shù) p（x） 和基點(diǎn) G，如果你知道 p（x）G 代入 k 個(gè)不同的 x 值后的值，就可以推導(dǎo)出所有 x 所對(duì)應(yīng)的 p（x）G 值。

只要明白了有關(guān)橢圓曲線點(diǎn)的這些屬性，就能深度理解隨機(jī)信標(biāo)的工作原理了。

隨機(jī)信標(biāo)

假設(shè) 1：系統(tǒng)中有 n 個(gè)參與者，至少需要其中的 k 位才能產(chǎn)生隨機(jī)數(shù)。就算控制其中的 k-1 人，你也不能預(yù)知隨機(jī)信標(biāo)的輸出結(jié)果、無法操縱結(jié)果。

假設(shè) 2：現(xiàn)在有個(gè) k-1 階多項(xiàng)式 p（x），參與者 1 知道 p（1） 的值、參與者 2 知道 p（2） 的值、…… 、參與者 n 知道 p（n） 的值；大家約好使用 G 作為橢圓曲線基點(diǎn)，所有參與者都知道 p（x）G 代入所有 x 的值。我們將 p（i） 視為參與者 i 的 “私人份額（不公開，只有參與者自己知道）” ，而 p（i）G 是其 “公開份額”（所有參與者都能知道這個(gè)值）（回想一下前文，我們說過無法從 p（i）G 倒推出 p（i），所以只有參與者 i 知道 p（i） 的值）

要設(shè)計(jì)好的隨機(jī)信標(biāo)，最困難的部分，就是要找到這么一個(gè)多項(xiàng)式，使得每個(gè)參與者都能知道自己的私人份額，但是無法知道他人的私人份額——這也被稱為分布式密鑰生成（DKG，Distributed Key Generation）。DKG 會(huì)放在下個(gè)章節(jié)討論，現(xiàn)在就先假設(shè)存在這么個(gè)多項(xiàng)式，而所有人都知道各自的私人份額。

我們接著討論，如何使用這套假設(shè)在區(qū)塊鏈協(xié)議中產(chǎn)生一個(gè)隨機(jī)信標(biāo)？假設(shè)網(wǎng)絡(luò)產(chǎn)生一個(gè)區(qū)塊，區(qū)塊哈希為 h。現(xiàn)在參與者們想用 h 作為種子以生成隨機(jī)數(shù)，首先用約定好的函數(shù)，將 h 轉(zhuǎn)換為某條橢圓曲線上的一個(gè)點(diǎn)：

H = scalarToPoint（h）

對(duì)于參與者 i 來說，因?yàn)樗?p（i） 和 H，所以可以自行計(jì)算出 H_i = p（i）H。對(duì)外公布 H_i 并不會(huì)導(dǎo)致參與者 i 的私人份額 p（i） 暴露，因此在每個(gè)區(qū)塊中都能重用同樣的私人份額，因此 DKG 只需要進(jìn)行一次。

根據(jù)前面提到的第三點(diǎn)特性，當(dāng)至少有 k 位參與者公布他們各自的 H_i = p（i）H 之后，其他人就能知道代入任何一個(gè) x 之后，H_x = p（x）H 是什么。然后所有參與者都可以在自己本地計(jì)算 H_0 = p（0）H，并以這個(gè)結(jié)果的哈希值作為隨機(jī)信標(biāo)的輸出；請(qǐng)注意，因?yàn)闆]有參與者知道 p（0），所以唯一能得到 p（0）H 的方法就是對(duì)p（x）H 進(jìn)行內(nèi)插法（intepolate）計(jì)算，要完成內(nèi)插計(jì)算需要知道至少 k 個(gè)p（i）H 的值。如果公布的人不足 k 位，則其他人無法推出 p（0）H 的值。

基于此技術(shù)構(gòu)建的信標(biāo)延續(xù)了這些我們所需的特性：如果攻擊者只掌控了少于 k-1 位參與者，則他無法操控隨機(jī)信標(biāo)的輸出；其他 k 位參與者才能計(jì)算出最終輸出，他們的子集或其他更多的參與者，都能得出相同的輸出。

我們還忽略了一件事。為了使用插值法計(jì)算 p（0）H，必須保證參與者 i 所公開的 H_i 真的等于 p（i）H。但是因?yàn)槌藚⑴c者 i，其他參與者都不知道 p（i） 是什么，所以沒法直接驗(yàn)證參與者 i 公布的 H_i 是否的確等于 p（i）H；如果不要求為 H_i 附上密碼學(xué)證明，攻擊者可以直接聲稱某個(gè) H_i 的值，而其他人沒有辦法辨別真?zhèn)巍?/p>

有至少兩種密碼學(xué)證明辦法，可以用來判別 H_i 的真?zhèn)?。我們?huì)在聊完 DKG 之后介紹。

分布式密鑰生成（DKG）

根據(jù)前面章節(jié)對(duì)隨機(jī)信標(biāo)的介紹，我們需要 n 位參與者共同使用某個(gè) k-1 階多項(xiàng)式 p（x），使得每個(gè)參與者 i 知道自己的 p（i），而其他人無法得知。下一步，需要所有參與者都知道：給定 G 時(shí)，所有的 x 所對(duì)應(yīng)的 p（x）g 值。

在本章節(jié)，我們假設(shè)每個(gè)人都有自己的私鑰 x_i，而且其他人都知道 x_i 對(duì)應(yīng)的公鑰 X_i。

那么運(yùn)行 DKG 的一種方式如下：

1. 每個(gè)參與者 i 在本地運(yùn)行 k-1 階多項(xiàng)式 p_i（x） 的計(jì)算。接著用公鑰 X_j 將每個(gè) p_i（j） 加密（ j≠i ）， 并發(fā)送給對(duì)應(yīng)的參與者 j 。如此一來，只有參與者 j 能解密出 p_i（j）；參與者 i 還要公布所有 p_i（j）G ，j∈1~k。

2. 所有參與者要對(duì)一個(gè)至少由 k 個(gè)多項(xiàng)式組成的集合達(dá)成共識(shí)。因?yàn)橛行﹨⑴c者可能掉線，所以他們不可能等到 n 個(gè)驗(yàn)證者都作出如此承諾再進(jìn)行下一步；只要至少 k 個(gè)驗(yàn)證者都作出 “收到至少 k 個(gè)這樣的多項(xiàng)式” 的承諾之后，他們就可以使用某種形式的共識(shí)算法（如，Tendermint）對(duì)他們所收到多項(xiàng)式的子集 Z 達(dá)成共識(shí)（Z 包含至少 k 個(gè)多項(xiàng)式）。

3. 所有參與者共同驗(yàn)證加密的 p_i（j） 與公開的 p_i（j）G 是否對(duì)應(yīng)，并從 Z 中移除不合格的多項(xiàng)式。

4. 對(duì)于集合 Z 中的每個(gè)多項(xiàng)式 p_i（x） ，每個(gè)參與者 j 自行計(jì)算 p_i（j） 的總和作為私人份額 p（j） ；同樣的，對(duì)于集合 Z 中的每個(gè) p_i（x）G ，參與者可以計(jì)算 p_i（x）G 的總和作為公開份額 p（x）G。

因?yàn)?p（x） 是每個(gè)獨(dú)立的 p_i（x） 的總和，每個(gè) p_i（x） 都是 k-1 階多項(xiàng)式，所以要觀察 p（x） 是否也是 k-1 階多項(xiàng)式。其次要注意，每個(gè)參與者 j 只知道 p（j） 的值，但不知道其他 p（x） （x ≠ j ）的值。實(shí)際上，為了知道 p（x）的值，TA 需要知道所有的 p_i（x），只要至少一個(gè)被承諾多項(xiàng)式的值屬于未知，TA 就不可能知道 p（x）。

上述步驟組成了完整的 DKG 過程。步驟 1、2、4 相對(duì)直觀，但第 3 步就比較復(fù)雜了。

具體來解釋第三步 —— 我們需要找個(gè)方法，證明每個(gè)加密的 p_i（j） 與公開的 p_i（j）G 存在對(duì)應(yīng)關(guān)系。如果沒有這種驗(yàn)證，攻擊者 i 可以向參與者 j 胡亂發(fā)送消息，而不是發(fā)送正確的加密 p_i（j），導(dǎo)致參與者 j 無法進(jìn)一步計(jì)算自己的私人份額。

雖然有辦法可以制作出加密份額的形式正確性密碼學(xué)證明。但是，這樣的證明數(shù)據(jù)過大，并且要向全網(wǎng)公布這樣的證明，時(shí)間復(fù)雜度可能高達(dá) O（nk），證明的 size 是嚴(yán)重的瓶頸。

在 NEAR 協(xié)議中，我們不去證明 p_i（j） 與公開的 p_i（j）G 的關(guān)系，而是在 DKG 過程中給予每個(gè)參與者充分的時(shí)間（也就是對(duì)多項(xiàng)式集合 Z 取得共識(shí)、到最終聚合出私有份額，兩個(gè)事件之間的時(shí)間間隔），去證明“他們收到的 p_i（j） 與公開廣播的 p_i（j）G 對(duì)不上”。協(xié)議中假設(shè)每個(gè)參與者在窗口期內(nèi)（大約半天）至少會(huì)上線一次，而他們提交的挑戰(zhàn)就能進(jìn)入?yún)^(qū)塊鏈。對(duì)于區(qū)塊生產(chǎn)者來說，這兩個(gè)假設(shè)都很合理，因?yàn)橐鰠^(qū)塊生產(chǎn)者，一般來說在整個(gè) epoch 中都要在線；如果大多數(shù)區(qū)塊生產(chǎn)者密謀不接收這條消息，其實(shí)整個(gè)系統(tǒng)就已經(jīng)不安全，攻擊者其實(shí)有更好的方式攻擊整個(gè)系統(tǒng)（而不僅僅是拒收挑戰(zhàn)消息）。

假如某個(gè)區(qū)塊生產(chǎn)者收到無效的公開份額，而且沒有及時(shí)在 DKG 過程中提出挑戰(zhàn)，則該礦工也無法在該時(shí)段中參與隨機(jī)數(shù)生成。請(qǐng)注意，只要其他 k 個(gè)誠(chéng)實(shí)的參與者都能正確計(jì)算出份額（通過不接收任何無效份額，或及時(shí)挑戰(zhàn)所有無效份額），協(xié)議仍將正常運(yùn)作。

證明

還剩下最后一個(gè)問題：我們?nèi)绾我圆煌嘎?p（i） 為前提，證明自己公布的 H_i 等于 p（i）H？

回想一下，每個(gè)參與者都知道 H、G 、p（i）G 的值。在給定 p（i）G 和 G 的情況下回推 p（i） 的運(yùn)算被稱為離散對(duì)數(shù)問題，又簡(jiǎn)稱為 dlog 。那么每個(gè)參與者想做的都是：既能向他人證明 dlog（p（i）G， G） = dlog（H_i， H），又不會(huì)透露 p（i）。的確存在這么一種方法構(gòu)建上述證明，其中之一就是 —— Schnorr 協(xié)議；通過 Schnorr 協(xié)議，參與者能在發(fā)布 H_i 時(shí)附上 H_i 的正確性證明。

回想一下，隨機(jī)信標(biāo)連的輸出是 H_0 的內(nèi)插值（interpolated value）。對(duì)于沒有參與生成隨機(jī)信標(biāo)輸出的人來說，除了 H_0，還需要哪些信息來驗(yàn)證這個(gè)值的正確性？因?yàn)槊總€(gè)人都能自行在本地計(jì)算中加入 G_0，所以只要證明 dlog（G_0， G） = dlog（H_0， H） 就行了。但因?yàn)樾艠?biāo)的特性，我們無法得知 p（0），也就無法通過 Schnorr 協(xié)議生成這樣的證明。所以如果你要向其他人證明 H_0 的正確性，就必須保留所有 H_i 的值及其相應(yīng)的證明。

不過，好消息是，如果有些計(jì)算類似于橢圓曲線點(diǎn)乘法，則只需驗(yàn)證 H_0 × G = G_0 × H 即可證明 H_0 的計(jì)算正確無誤。

如果所選的橢圓曲線支持橢圓曲線配對(duì)運(yùn)算（elliptic curve pairings），則這種證明是可行的。在這種情況下，任何知道 G，H 和 G_0 的人都可以核實(shí) H_0（隨機(jī)信標(biāo)的輸出）；而且 H_0 也可視作一個(gè)集體的多重簽名，證明區(qū)塊 n 的正確性得到至少 k 位參與者的檢查認(rèn)證。

目前我們還未在 NEAR 中使用橢圓曲線配對(duì)運(yùn)算，但未來我們可能會(huì)使用，然后利用上文討論的小技巧取代我們當(dāng)前使用的單一簽名方法。另一方面，DFinity 使用 BLS 簽名，可以利用配對(duì)運(yùn)算來實(shí)現(xiàn)上述簽名。