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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

比原鏈研究院 劉秋杉