近幾年門限密碼學(xué)在區(qū)塊鏈系統(tǒng)里開始逐漸被應(yīng)用，分為門限加密和門限簽名，一般見于隨機(jī)預(yù)言機(jī)、防審查、減少通信復(fù)雜度（HotStuff）、共識(shí)網(wǎng)絡(luò)中防拜占庭（HoneyBadgerBFT 中用于 BA 環(huán)節(jié)的 common coin）以及作為分布式偽隨機(jī)數(shù)生成器（coin tossing）的重要原語，其優(yōu)越的資產(chǎn)協(xié)同防盜特性也慢慢被新興數(shù)字資產(chǎn)托管機(jī)制所重視，今天我們主要討論公鑰密碼學(xué)（PKC）里的門限簽名機(jī)制。一種理想的門限簽名系統(tǒng)是可以在異步的網(wǎng)絡(luò)環(huán)境里做到容錯(cuò)容災(zāi)不可偽造（non-forgeability），并且擁有極度可靠安全的消息傳輸通道，簽名份額的生成和驗(yàn)證是完全非交互式的，在初始密鑰階段具備可以防止拜占庭行為的異步分布式密鑰生成（DKG）機(jī)制。

與基礎(chǔ)簽名機(jī)制類似，門限簽名機(jī)制（Threshold Signature Schemes）也分為兩部分：

門限密鑰生成（Thresh-Key-Gen）：基于安全參數(shù)構(gòu)造一種分布式密鑰生成協(xié)議 DKG，協(xié)議運(yùn)行輸出一個(gè)共同的公鑰 pk 和分屬不同參與方各自所有的私鑰份額 ski，聚集起滿足閾值數(shù)量的私鑰份額可以構(gòu)建出真正的私鑰 sk。

門限簽名（Thresh-Sig）：基于分布式通信網(wǎng)絡(luò)，各參與方通過自己的私鑰份額 ski 完成對(duì)消息 m 的分布式協(xié)作簽署并輸出最終的可驗(yàn)證簽名 Sig(sk, m)，這個(gè)簽名跟單獨(dú)用 sk 私鑰簽出的一模一樣，可以用所基于的基礎(chǔ)簽名機(jī)制里的驗(yàn)證函數(shù)進(jìn)行本地驗(yàn)證，無需走通信交互驗(yàn)證

但是大多數(shù)情況下會(huì)通過使用一個(gè)可信的中心節(jié)點(diǎn)（dealer）來實(shí)現(xiàn)私鑰份額的生成和分發(fā)。沙米爾秘密分享（Shamir Secret Sharing）是最簡單的依賴中心 dealer 節(jié)點(diǎn)的門限密鑰生成方法，基本原理是拉格朗日插值，在 (t, n) 門限構(gòu)造中，dealer 會(huì)選擇一個(gè) (t-1) 次方的隨機(jī)多項(xiàng)式 f，令 f(0)=s，s 即為要分享的秘密值，然后向每個(gè)節(jié)點(diǎn)分發(fā)該多項(xiàng)式曲線上的點(diǎn) si=f(i) 作為各自的秘密份額值，簡單來講，三個(gè)點(diǎn)確定一個(gè)二次方程曲線（Lagrange interpolation formula）。為了解決中心作惡問題，人們又不斷探索了基于承諾（commitment）的可驗(yàn)證秘密分享（VSS、PVSS），以及應(yīng)用于異步網(wǎng)絡(luò)的 VSS（Cobalt BFT 在區(qū)塊鏈系統(tǒng)里也嘗試了結(jié)合 PoW 準(zhǔn)入機(jī)制的 AVSS）。有許多優(yōu)秀成熟的 commitment scheme 可以借鑒應(yīng)用，簡單來講承諾（commitment）算法 [C(M), D(M)]=Com(pk, M, r) 中 pk 是與承諾機(jī)制有關(guān)的公鑰，M 是要承諾的原始值，r 是一個(gè)隨機(jī)骰子，算法輸出的 C 便是 commitment，D 則是需要秘密保管的 decommitment 值，在正式公開 M 之前先公開 M 的承諾 C，即先對(duì)自己要公布的消息做個(gè)上帝擔(dān)保，約束自己無法更換 M，而對(duì)于 M 的受眾或者接收者，它們可以通過之前公布的承諾和驗(yàn)證算法進(jìn)行驗(yàn)證唯一性。這里我們主要關(guān)注非交互式的 VSS 實(shí)現(xiàn)。

此外，在過往的研究里，簽名（Sig）的生成和驗(yàn)證大多是交互式的，并且依賴一個(gè)同步通信網(wǎng)絡(luò)和廣播通道（broadcast channel），節(jié)點(diǎn)們?cè)谀撤N設(shè)定下接收到特定消息后便同時(shí)啟動(dòng)簽名協(xié)議，并嚴(yán)格遵循超時(shí)機(jī)制。而在互聯(lián)網(wǎng)環(huán)境和區(qū)塊鏈網(wǎng)絡(luò)里，對(duì)網(wǎng)絡(luò)假設(shè)的限定是有限的，所以門限系統(tǒng)要成功運(yùn)作除了需要構(gòu)造真正的 DKG 協(xié)議和非交互式簽名機(jī)制外，還需要具備商用級(jí)的網(wǎng)絡(luò)系統(tǒng)以及被驗(yàn)證過的成熟代碼實(shí)現(xiàn)。這里我們（Bytom）嘗試提出并構(gòu)建一種弱同步網(wǎng)絡(luò)假設(shè)下的門限簽名分布式系統(tǒng)，主要對(duì)網(wǎng)絡(luò)模型、DKG 構(gòu)建、簽名機(jī)制進(jìn)行一些創(chuàng)新結(jié)合和應(yīng)用，探索在實(shí)際網(wǎng)絡(luò)環(huán)境里最小可實(shí)用的門限簽名系統(tǒng)原型。

門限系統(tǒng)是一種（t, k, n）型 fault-tolerance 系統(tǒng)，t 代表網(wǎng)絡(luò)最大容錯(cuò)，k 代表最小門限值，n 是節(jié)點(diǎn)數(shù)，一般設(shè)定 k>=t+1，但這種對(duì)網(wǎng)絡(luò)分區(qū)（network partition）是無能為力的，所以在一個(gè)異步拜占庭網(wǎng)絡(luò)里我們依然選用經(jīng)典設(shè)定 k=n-t & t<n/3 去達(dá)成系統(tǒng)里的一個(gè)大多數(shù)共識(shí)。

門限網(wǎng)絡(luò)或者通信模型是實(shí)現(xiàn)可實(shí)用門限系統(tǒng)需要認(rèn)真考量的一個(gè)關(guān)鍵點(diǎn)。像 HoneyBadgerBFT 所構(gòu)建的接近異步通信網(wǎng)絡(luò)在現(xiàn)實(shí)案例中是少見的，一般會(huì)增加消息復(fù)雜度和通信輪次，異步網(wǎng)絡(luò)模型主要依賴所接收到的消息類型和數(shù)量進(jìn)行判斷，因?yàn)闀r(shí)間因子（time-based）并不能區(qū)分誰是慢節(jié)點(diǎn)誰是惡意節(jié)點(diǎn)。但在這里我們更傾向采用高效的弱同步網(wǎng)絡(luò)假設(shè)，即消息延遲和時(shí)鐘偏移有上限（實(shí)際可接受）但未知，延遲的漸進(jìn)是合理的，保障 liveness（safety 可以采用妥協(xié)的方法處理）；能夠?qū)?crash、network failure、byzantine 等不同情況盡量做到分開處理，比如設(shè)置規(guī)定時(shí)間內(nèi)可容忍的 crash 閾值，對(duì)于誠實(shí)節(jié)點(diǎn)發(fā)生 crash 后能夠從一個(gè)規(guī)定的狀態(tài)恢復(fù)等；并且假設(shè)網(wǎng)絡(luò)故障總能被修復(fù)、遭受的 DoS 攻擊總會(huì)停止；最后在構(gòu)建通信通路上可以借助 PKI 和外部 CA 構(gòu)建 TLS 鏈接，以及借助經(jīng)典的 RBC 協(xié)議（reliable broadcast channel）。

DKG 是門限簽名最為核心的環(huán)節(jié)也是第一階段，負(fù)責(zé)完成門限密鑰的生成和分發(fā)。VSS 是 DKG 的重要組成部分。上面提到 VSS 的基本原理是承諾機(jī)制，一般基于 Pedersen commitment，構(gòu)造形如 C=mG+nH 的承諾（這里我們省去了一些對(duì)橢圓曲線群運(yùn)算特征定義和假設(shè)，可以簡單理解為橢圓曲線計(jì)算），其中 m 來自密鑰構(gòu)造多項(xiàng)式 f(x) 系數(shù)，而 n 來自 dealer 另外構(gòu)造的一個(gè)隨機(jī)多項(xiàng)式 h(x) 的系數(shù)，承諾集合 {Ci, 0<i<t} 是一種公開可獲取的系數(shù)“證據(jù)”，用于證明 dealer 只承認(rèn)一個(gè)合法的密鑰多項(xiàng)式。各個(gè)參與方在獲得 dealer 分發(fā)給自己的密鑰份額 f(i) 和秘密值份額 h(i) 后，計(jì)算 f(i)G+h(i)H，如果與對(duì)應(yīng)的承諾值（多項(xiàng)式計(jì)算）相等，則認(rèn)為合法，如果不一致，則認(rèn)為 dealer 出現(xiàn)作惡行為，開始向網(wǎng)絡(luò)提交自己的抗議 complaint，其他人可以進(jìn)行驗(yàn)證，如果發(fā)現(xiàn)事實(shí)如此，則立即停止協(xié)議，如果其他人驗(yàn)證后發(fā)現(xiàn)該 complaint 不合法，則發(fā)起 complaint 的節(jié)點(diǎn)會(huì)被標(biāo)記不可信。VSS 過程簡單來講包括中心初始化密鑰分發(fā)、構(gòu)建承諾和重建密鑰三部分內(nèi)容，整個(gè)網(wǎng)絡(luò)交互存在兩輪（synchronous）全網(wǎng)廣播（all-to-all）達(dá)成一致，最終將密鑰份額和承諾傳遞給每個(gè)參與節(jié)點(diǎn)，這里我們會(huì)定義三種消息類型用于標(biāo)記多輪消息序列并攜帶足夠的信息用于計(jì)算門限密鑰。

真正的 DKG 是需要去掉 VSS 里的那個(gè)中心，在分布式協(xié)作下生成秘密，避免單點(diǎn)泄漏風(fēng)險(xiǎn)，其原理也很簡單，相當(dāng)于 n 個(gè)節(jié)點(diǎn)同時(shí)各自選擇秘密值并運(yùn)行自己的 VSS，每個(gè)節(jié)點(diǎn)收集來自其他節(jié)點(diǎn)的秘密份額完成組裝，組裝后的結(jié)果便是真正私鑰的份額，而各個(gè)合法節(jié)點(diǎn)各自分發(fā)的秘密值聚合起來便是最終的構(gòu)造私鑰，最后在進(jìn)行承諾驗(yàn)證。這似乎很像一個(gè) Multi-valued Validated Byzantine Agreement (MVBA) protocol （一種被廣泛研究的可以對(duì)多種提案高效率達(dá)成共識(shí)的一致性協(xié)議算法，存在多個(gè)變種，比如異步公共子集 Common Subset）。

不過我們盡量避免這種復(fù)雜的實(shí)現(xiàn)，一般通過選舉出 Leader 節(jié)點(diǎn)，統(tǒng)一協(xié)調(diào)處理這些 VSS 的完成情況和最終共識(shí)，定義序列，當(dāng)大多數(shù)節(jié)點(diǎn)（n-t）完成各自的 VSS 階段并被其他所有誠實(shí)節(jié)點(diǎn)所確認(rèn)后，Leader 將這些已完成的 VSS 信息進(jìn)行收集并重組提案，再經(jīng)過兩輪全網(wǎng)廣播后，每個(gè)節(jié)點(diǎn)便會(huì)確定下各自最終的秘密份額，因此保障 liveness 對(duì)于我們的系統(tǒng)是十分關(guān)鍵的。如果 DKG 協(xié)議里任何一方出現(xiàn)惡意行為，協(xié)議都會(huì)立即停止，即 DKG 需要確保所有參與方的誠實(shí)行為。至此，一把公共的門限公鑰和分屬不同參與方的門限私鑰份額便構(gòu)造完畢。

簽名階段簡單來講是基于上面得到的密鑰份額各自完成簽署自己的簽名份額，最后再完成統(tǒng)一組裝，得到最終門限簽名。Thresh-Sig 階段的具體實(shí)現(xiàn)與所基于的數(shù)字簽名算法有很大關(guān)系，例如 Schnorr 算法在計(jì)算簽名 s 值時(shí)所依賴的秘密值 k 在常數(shù)項(xiàng)，s=k-z(H(K||M))，所以可以簡單的將秘密值份額相組。而 ECDSA 中秘密值 k 是非線性的，即 s=(H(M)+zr)/k（其中 r 也是由 k 經(jīng)過指數(shù)運(yùn)算得來），存在兩個(gè)秘密值（k 和 z）的乘運(yùn)算，所以各個(gè)節(jié)點(diǎn)不能僅通過擁有 k 秘密值份額來完成最終簽名值的組裝，需要對(duì)公式進(jìn)行變形，重新定義組合秘密值 kz，并分布式完成 kz 的秘密份額計(jì)算以及分發(fā)，甚至需要借助安全多方計(jì)算（在不泄漏各自 k 和 z 份額的前提下，完成 kz 的結(jié)果計(jì)算并輸出 kz 的秘密份額給相應(yīng)參與方）、同態(tài)加密機(jī)制以及零知識(shí)證明（range proof），因此多方的 ECDSA 門限簽名在實(shí)現(xiàn)和效率上會(huì)比較復(fù)雜，現(xiàn)階段以可實(shí)用的 2-2 方案研究居多。

不論是采用 ECDSA 還是 Schnorr 算法，最核心的問題依然是基于 DKG 和多方計(jì)算的原理去生成和分發(fā)簽名算法中需要的秘密值，每個(gè)參與方基于各自的密鑰份額和秘密值份額完成自己的簽名過程，最后通過整體的交互組裝獲得最終的合法簽名。同樣的，如果無法達(dá)到足夠門限閾值數(shù)量的合法簽名方，簽名協(xié)議也會(huì)立即停止。根據(jù)不同的應(yīng)用場景需求，我們需要認(rèn)真研究用于實(shí)現(xiàn)門限簽名機(jī)制的底層簽名算法，比如 ECDSA、EdDSA、Schnorr、BLS 等，不同的簽名算法對(duì)應(yīng)的門限機(jī)制實(shí)現(xiàn)復(fù)雜度和效率是不同的。

此外，一個(gè)完整的門限系統(tǒng)可能會(huì)有成員變更的需求，原有的密鑰份額隨之需要新一輪變更，最直觀的做法是引入周期的概念，通過同步網(wǎng)絡(luò)和共識(shí)協(xié)議發(fā)起新一輪密鑰生成，產(chǎn)生新的主公鑰和私鑰份額，用超時(shí)機(jī)制防止阻塞。成員變更和 DKG 是一種比較精細(xì)（或脆弱）的系統(tǒng)，任何一個(gè)成員 fail 或者 fault 都會(huì)引發(fā)狀況外。在實(shí)現(xiàn)上我們用狀態(tài)機(jī)復(fù)制原理構(gòu)建門限（DKG）節(jié)點(diǎn)，基于消息輸入更換自身狀態(tài)（例如 node_remove，leader_change，group_update）。

門限密碼學(xué)隨著結(jié)合應(yīng)用場景的需求研究增多，不斷完善自身成熟度，尤其是隨著高度可靠的代碼實(shí)現(xiàn)增多，隨著復(fù)雜網(wǎng)絡(luò)環(huán)境里的系統(tǒng)架構(gòu)成熟，有希望在價(jià)值網(wǎng)絡(luò)里扮演“門神”的重大作用，同時(shí)會(huì)促進(jìn)對(duì)零知識(shí)證明、同態(tài)加密技術(shù)的進(jìn)一步場景化應(yīng)用，是當(dāng)下區(qū)塊鏈新技術(shù)領(lǐng)域?yàn)閿?shù)不多值得深入研究和實(shí)戰(zhàn)的研究方向?，F(xiàn)代密碼學(xué)與價(jià)值網(wǎng)絡(luò)相輔相成，前者給予后者“上帝保障”，后者給予前者“偉大戰(zhàn)場”。

比原鏈研究院 劉秋杉