本期課程構建一套評價體系，並對不同 ECDSA 門限簽名演算法進行橫向比較。

作者：Cobo 密碼學團隊，Cobo Global

原用標題：Cobo 密碼知識講堂|第四講：ECDSA 門限簽名演算法分析與比較

封面：Photo by Michael Dziedzic on Unsplash

隨著香港開始允許散戶交易數字資產，數字資產也在逐步走進每個人的生活，數位資產、數位簽名等新概念層出不窮。 Cobo 密碼知識講堂計劃推出以「門限簽名」為主題的系列科普文章，旨在以深入淺出的方式，帶領讀者瞭解數位簽名中門限簽名的技術本質和應用原理。 該系列科普文章每一篇內容相互獨立又互相補充，涵蓋門限簽名的概念及典型應用、ECDSA 門限簽名的設計及發展現狀、Schnorr 門限簽名的設計及發展現狀、基於門限簽名的帳戶體系構建，以及層級化門限簽名設計等多個該領域的熱點和難點問題，力求通過對技術研究的深層次剖析和解讀，讓讀者對門限簽名領域有更加深刻的理解。

《Cobo 密碼知識講堂|第一講：門限簽名的概念與應用》

《Cobo 密碼知識講堂|第二講：ECDSA 演算法及其門限化設計介紹》

《Cobo 密碼知識講堂|第三講：ECDSA 門限簽名典型演算法介紹》

本講概述：在上一期課程中，我們對已有的 ECDSA 門限簽名演算法技術路線進行了歸納和總結，本期課程將構建一套評價體系，並對不同演算法進行橫向比較。 首先，緊密結合應用需求，提出 ECDSA 門限簽名演算法的衡量指標，並解釋其概念內涵，完成評價體系的構建; 其次，從各衡量指標出發，分析比較各演算法在該指標上的表現; 最後，結合分析比較結果，對未來 ECDSA 門限簽名演算法的設計提供指引方向。

Part 1：ECDSA 門限簽名演算法衡量指標

在區塊鏈領域，ECDSA 門限簽名主要用於分散式場景下的數位資產託管，其核心功能需求為 “高效” 和 “安全”。 “高效” 是指演算法流程簡單，交互次數和計算量較少; “安全” 是指簽名無法偽造，同時惡意節點偏離協議的行為並不會導致任何私鑰資訊的洩漏。 通過對「高效」和「安全」兩個概念的拆解，我們提出 ECDSA 門限簽名演算法的四個關鍵衡量指標，即門限最優、交互輪數、安全性和可審計性，而每個指標內部又可以進行進一步細化，具體見圖 1。

圖 1 ECDSA 門限簽名衡量指標
  • 門限最優
  • 交互輪數

交互輪數是指在簽名過程中節點之間需要進行數據交互的次數，是衡量演算法是否高效的一個核心指標。 在分散式應用場景中，節點地理區域分佈廣泛，節點之間的網路連接存在不穩定性和延遲性，較少的交互次數能夠有效提高演算法運行的成功率。 需要說明的是，目前很多演算法支援預處理階段（Preprocess Stage），即將與待簽名消息無關的計算預先處理，使得線上階段（Online Stage）僅需一輪交互即可完成簽名。 這種設計方式是門限簽名演算法在應用模式上的創新，並不直接反映該演算法的複雜度或者高效性。 因此在本文在統計演算法交互輪數時，不對預處理過程和線上計算過程進行區分。

  • 安全性

演算法的安全性是一個非常綜合的概念，對於 ECDSA 門限簽名而言，安全一般是指簽名不可偽造，相關論文也提供演算法安全性的形式化證明。 為了更加精細化地描述安全性，我們將其拆解為以下三方面內容：

（1）安全假設

在演算法安全性形式化證明中，會將某些困難問題的求解過程規約為該演算法的攻擊過程。 一旦該演算法是不安全的，那麼一定能夠構造出解決某些困難問題的方法，而該問題是公認的難解或不可解問題，因此被證明演算法是安全的。 而這些問題就是該演算法的安全假設。 安全假設越少或者越弱，說明演算法的安全依賴少，安全性更高。

（2）攻擊模型

攻擊模型中，我們重點關注惡意節點對誠實節點的腐化能力（Corruption），具體可以分為靜態模型（Static）和動態模型（Adaptive）兩種。 在靜態模型下，惡意節點需要在簽名開始之前，確定需要腐化的節點，且在簽名開始后不可以更換或者新增; 在動態模型下，惡意節點可以根據數據發送情況，在簽名過程中重新確定腐化節點。 顯然，動態模型下的安全性更高，但是由於存在通用方法能夠將靜態安全轉化為動態安全，因此二者沒有根本性區別。

（3）通用組合

通用組合模型（Universal Composability）是基於類比（Simulation）的安全範式，強調已經證明安全的協議組合后形成的高級協議同樣能保證安全。 可以說 UC 安全不僅僅局限於演算法本身，而且上升到複雜系統中的安全性，因此比普通安全性級別更高。

  • 可審計性

可審計性（Auditability）是指節點在簽名過程中發送數據的合法性是可驗證的，能夠精準定位在簽名過程中發送錯誤數據從而導致簽名失敗的惡意節點，因此該性質也稱為可驗證退出（Identifiable Abort）。 這一性質在 ECDSA 門限簽名演算法實際應用場景中非常必要，保證能夠及時識別惡意節點，排除安全隱患，確保簽名過程安全順暢。

Part 2：ECDSA 門限簽名演演算法比較

根據上一部分內容所提出的 ECDSA 門限簽名演算法的四個關鍵衡量指標及其拆解細化結果，我們對各演算法進行了詳細比較。 除此之外，為方便門限簽名相關領域工程師更好的完成技術選型，我們新增一個指標「演算法熱度」。，去衡量該演算法目前開源庫的多樣性、在產業中的應用範圍以及受認可程度。 具體比較結果見表 1。

表 1 ECDSA 門限簽名演算法比較

演算法協定門限最優輪數安全性可審計性演算法熱度
安全假設攻擊模型UC

GJK96		否81) Standard ECDSA Security靜態否否低
GGN16是61) Standard ECDSA Security2) Strong RSA靜態否否低
BGG17是41) Standard ECDSA Security2) Strong RSA靜態否否低
GG18是91) Standard ECDSA Security2) DDH3) Strong RSA靜態否否高
GG20是71) Enhanced ECDSA Security2) DDH3) Strong RSA靜態否是高
LNR18是81) Standard ECDSA Security2) DDH3) Paillier Indistinguishability靜態是否高
CCLST20是81) Standard ECDSA Security2) Low Order Assumption3) Strong Root Assumption靜態是否中
CMP20是41) Enhanced ECDSA Security2) DDH3)Strong RSA動態是否中
CGGMP21是41) Standard ECDSA Security2) DDH3) Strong RSA動態是是低
DKLs20是6+lgot1) Standard ECDSA Security2) ECDH靜態是否高

（1）門限最優

除了最早 ECDSA 門限簽名演算法 GJK96 不滿足以外，其餘演算法均滿足該性質。 這側面表明門限最優是目前 ECDSA 門限簽名設計的基本需求，而設計難點也集中在這裡。 需要說明的是，GGN16 首次提出門限最優的性質，並給出了明確定義，也是首個滿足門限最優的 ECDSA 門限簽名演算法。

（2）交互輪數

（3）安全假設

共性方面，所有 ECDSA 門限簽名演算法都是以 ECDSA 簽名演算法本身的安全性為基礎，但是對於有預計算的協定（如 GG20、CMP20），標準的 ECDSA 安全性（Standard ECDSA Security）是不足的，需要依賴於增強 ECDSA 簽名演算法（Enhanced ECDSA Security），即在攻擊者預先知道 R 的情況下，簽名仍保持安全。 個性方面，不同 ECDSA 門限簽名演算法的安全假設與其使用的核心密碼學技術高度相關，如 GG18、GG20、CMP20 等演算法使用了 Paillier 同態加密演算法，都需要依賴於 Strong RSA 假設，如 CCLST20 使用的 CL 同態加密演算法，則需依賴 Low Order Assumption。

（4）攻擊模型

攻擊模型方面，CMP20 和 CGGMP21 支援動態腐化（Adaptive Corruption），而其餘演算法均為靜態腐化（Static Corruption）。 鑒於已經存在通用演算法完成靜態腐化安全到動態腐化安全的轉化，我們認為所有演算法在該指標下都是同等安全的。

（5）UC 安全

CMP20 和 CGGMP21 明確給出了演算法 UC 安全的形式化證明; DKLs20 中使用的零知識證明協定如果滿足 UC 安全，那麼 DKLs20 也是 UC 安全的; 其他演算法雖然大部分都是基於 Simulation-based 安全定義下完成的安全性證明，但是並沒有證明是 UC 安全的。

（6）可審計性

GG20 和 CGGMP21 明確給出了演算法在不同中止情況下對作惡者身份的揭示方法，主要依賴於零知識證明和挑戰驗證兩種模式完成; 其他演算法並沒有直接給出類似的機制，但是我們不排除個別演算法在相關步驟增加零知識證明后，也滿足該性質。

（7）演算法熱度

目前業內熱度較高的演算法為 GG18、GG20、LNR18、CGGMP21、DKLs20，這些演算法有豐富的開源庫可供選擇，同時根據公開消息已經被多個公司採用用於數字資產的安全託管; 而演算法 GJK96、GGN16、BGG17 熱度較低，GJK96 是由於非門限最優不滿足應用場景需求，而 GGN16 和 BGG17 則是由於門限化同態加密演算法構建的複雜性導致實用性較低。 當前典型的開源庫及其實現的演算法見附錄。

Part 3：ECDSA 門限簽名演演算法設計方向

以上兩部分分別介紹了 ECDSA 門限簽名演算法的衡量指標和各演算法在該評價體系下的分析與比較。 綜合以上結果，未來 ECDSA 門限簽名演算法的設計中，要以門限最優為基本要求，通過協定的巧妙設計，盡可能較低交互輪數（4 輪或以下），在依賴較少安全假設下（最好僅需 Standard ECDSA Security），保證 UC 安全，且具備可審計性。

附錄：典型演算法開源庫匯總

代碼庫實現演算法
https://github.com/ZenGo-X/multi-party-ecdsaGG18/GG20
https://github.com/coinbase/kryptologyGG20/DKLs20
https://github.com/bnb-chain/tss-libGG18
https://gitlab.com/thorchain/tssGG20
https://github.com/ing-bank/threshold-signaturesGG18
https://github.com/taurusgroup/multi-party-sigCGGMP21
https://github.com/SwingbyProtocol/tss-libGG20
https://github.com/axelarnetwork/tofnGG20
https://github.com/0xEigenLabs/tss-wasmGG18
https://gitlab.com/neucrypt/mpecdsaDKLs20
https://github.com/IoFinnet/threshlibGG18
https://github.com/getamis/aliceGG18/CCLST20/CGGMP21
https://github.com/Safeheron/multi-party-ecdsa-cppGG18/GG20/CMP20

免責聲明：作為區塊鏈資訊平臺，本站所發佈文章僅代表作者及嘉賓個人觀點，與 Web3Caff 立場無關。 本文內容僅用於資訊分享，均不構成任何投資建議及要約，並請您遵守所在國家或地區的相關法律法規。

欢迎加入 Web3Caff 官方社群：X(Twitter)账号丨微信读者群丨微信公众号丨Telegram订阅群丨Telegram交流群