Threshold Signature Scheme (ECDSA) 介紹
目錄
- 為什麼我們需要 Secret Sharing Scheme?
- ECDSA 簡介
- Threshold Signature Scheme 符號解釋
- Shamir Secret Sharing Scheme
- Additive Secret Sharing
- Shamir 和 Additive Sharing Scheme 的結合
為什麼我們需要 Secret Sharing Scheme?
管理用戶私鑰的方法大致分為兩類。 一類是服務提供商為用戶持有私鑰（託管，CEXes），另一類是離線生成私鑰並讓用戶自行管理（非託管，大多數錢包產品如 MetaMask），這兩種方法都存在一些缺陷。 雖然託管解決方案提供了更好的用戶體驗，但它依賴於服務提供商的誠實、安全和負責任。 對於非託管解決方案，用戶保護和保管自己的私鑰需要很高的知識門檻。
Secret Sharing Scheme 使用多方計算（MPC）密碼學技術將私鑰分成幾個可重組的份額 (share)，分別分發給用戶和服務提供者。 這樣用戶可以降低對提供商的信任，也可以降低失去自己份額的風險。 可以創建更多份額並將其分配給更多方以管理對帳戶的控制並創建 Threshold Signature Scheme（TSS）。 此外，當部分份額被盜用時，還可以刷新所有份額以確保帳戶安全。 本文將概述其背後的數學原理，討論 Shamir Secret Sharing 和 Additive Secret Sharing。
ECDSA 簡介
為了完整性，稍微提一下關於 ECDSA 的基本操作，以便稍後更好地解釋這些運算。 本文不會介紹 ECDSA 的細節，只是簡單描述一下運算規則。
私鑰和公鑰
ECDSA 定義了點的特殊操作，並提供了強大的 trapdoor function。 對於點 G（生成元）和隨機整數 x，我們可以得到點 P，其中 P = x*G。 trapdoor function 特性使得從 x 得到 P 很容易，但通過知道 P 得到 x 卻非常困難。在實作中，x 將是私鑰，點 P（x 坐標）將是公鑰。
簽名和驗證
簽名
1. 輸入參數：隨機生成數 k, 訊息 msg , 私鑰 private_key，橢圓曲線使用的質數 p
2. 計算點 R = k*G
3. 將 r 設置為 R 點的 x 坐標
4. 計算值 s
5. r, s 為簽名結果
驗證
1. 輸入參數：訊息 msg, 公鑰 public_key point(P), r, s 值
2. 計算點 Q
3. 驗證 Q 的 x 坐標等於 r
Threshold Signature Scheme 符號解釋
先解釋一下文章中使用的一些符號。
(t, n) secret sharing：共有 n 方參與私鑰分享，所以總共會產生 n 個份額。 在 n 份中，最多可以洩露 t 份。生成簽名時，需要 t+1 個份額。
補充：需注意在有的論文中 t 是代表可產生簽名的最低門檻，最多可洩漏 t-1 份，需依上下文而定。
Shamir Secret Sharing Scheme
Shamir Secret Sharing Scheme (SSSS) 可以輕鬆創建 (t, n) 方案，也能夠引入新的份額並進行私鑰刷新。 主要缺點是在生命週期當中私鑰會被還原，因此需要一個誠實的角色 (dealer) 來做這件事，實務上可以放在客戶端。
原理
為了構建 SSSS，先定義一個 t 次多項式。 常數項 a0 為私鑰。
對於任意多項式，它可以用 x-y 平面上的曲線表示。 而對於一個 t 次多項式，需要 t+1 個點來確定唯一的多項式曲線。 即解出多項式 (a0, a1, … at) 的係數。
讓第 i 方持有 f(i) 的價值作為他們的秘密份額。 第一方知道 f(1)，第二方知道 f(2)，…… 第 n 方知道 f(n)。 當各方想要生成簽名時，他們中的任何 t+1 人都可以提供他們的份額來重建多項式，從而重建私鑰，產生簽名。
示例
- 誠實的 dealer 創建多項式：f(x)=x+2
- 私鑰是 2
- 第一方獲得 f(1) = 3，第二方獲得 f(2) = 4
- 要求解的方程式 f(x)=ax+b
f(1)=a+b=3
f(2)=2a+b=4
解出 b = 2（私鑰）
延伸討論
- 我們可以輕鬆創建更多份額。 只需在多項式曲線上的取更多點。 對於上面的示例，取 f(3) = 5、f(4) = 6，依此類推。 其中任意兩個都可以生成簽名。
- 私鑰在生命週期中會重構（私鑰創建時、每次創建簽名時）。 因此需要一個誠實的 dealer。
- 份額刷新可以通過保持常數項不變並刷新其他係數來實現。 例子：更新f(x) = 2x + 2 生成 f(1)=4, f(2)=6, f(3)=8 分發給各方。
- 使用 SSSS 的一個例子是 Web3Auth (Torus)。
Additive Secret Sharing
Additive Secret Sharing 的優點是讓私鑰在整個生命週期當中都不會被還原，各方獨自生成自己分祕密份額，並透過 Multiplicative to Additive (MtA，下面會介紹) 的技巧直接算出簽名。缺點是要生成簽名時所有人都要參加，無法達成 threshold signing 的功能。
公鑰和私鑰
party i 生成他們自己的祕密份額 x_i ，最終對應到的私鑰是總和
公鑰 P 點
Multiplicative to Additive (MtA)
我們想要把一般的 ECDSA 改造成多方 ECDSA 。目的是讓參與的各方在不揭露自己祕密的情況下能算出總體的簽名值。在產生簽名的過程，我們需要各方祕密值的乘積。橢圓曲線可以讓我們算出祕密值的加總，但祕密值的乘積則需要用乘法加法轉換 (Multiplicative to Additive, MtA) 的技巧來操作。
在解釋之前，先介紹一下「同態加密」(homomorphic encryption) 的概念，它允許在不知道祕密本身的情況下對加密的值進行一些數學計算。 以 Paillier 為例：
補充：MtA 不是一定要使用同態加密的實現，Oblivious Transfer (OT) 也是一個方式。
下面解釋 MtA 的過程。參考下面的投影片
我們要計算的值是 s = a * b，其中 Alice 有她的祕密值 a，Bob 有他的祕密值 b。 MtA 的目標是通過 Alice 和 Bob 之間的一些互動，Alice可以得到一個新的祕密 a’，Bob 得到 b’，使得 a’+b’ 得到 s，而在互動過程中，他們都不會知道 s。流程如下：
- Alice 用她自己的公鑰加密 a 並生成 c1 = E(a)。 與 Bob 共享 c1
- Bob 隨機生成一個秘密數 m，並計算 E(ab+m) 的值，利用同態加密的特性 c2 = E(ab+m) = E(a)^b*E(m)。 傳遞給 Alice
- Alice 可以用自己的私鑰解密 c2，得到 ab+m 的值。 請注意，Alice 只知道 ab+m 的值，但不知道 b 或 m 的值。
- 令 a’ = ab+m, b’ = -m，可得 a’ + b’ = ab = s
讓我們將案例擴展到 n 方運算。
- 第 i 方生成 2 個秘密值 ai 和 bi。 目標是讓構建整個祕密的一部分是 a = a1 + a2 + … + an，另一部分是 b = b1 + b2 +…+ bn。 我們要計算的值是 a * b
- 根據分配律 a * b 將是 ai*bj 加起來的組合。 a1*b1, a2*b2 … 可以由每一方計算。 對於其他 ai*bj，我們可以應用上面的 MtA 操作，其中 ai*bj = a’ij + b’ji。 一方持有 a’ij，另一方持有 b’ji。
- 最後第 i 方會算出下面的值作為份額
如果我們將所有份額加在一起，結果將是 a*b
產生簽名
簽名生成的過程就像下面的截圖，解釋一下其中的符號意義與運算規則，應該就能理解了。
- [k]：k 是聯合祕密值。 k = k1 + k2 +…+ kn。 其中方括號的 [k] 表示各方持有自己的份額 ki 且未揭露
- sk 為對應的聯合賬戶私鑰
- [k] ← Rand()：每一方隨機生成自己的秘密值 ki
- [s] ← Mul([a], [b]): 每一方都用自己的秘密 ai 和 bi 並進行 MtA 操作。 結束後每一方都獲得了他們的新份額 [s]，其中 s = a*b
- a ← Open([a])：每一方都公開他們的值 ai。 相加得到 a
- [P] ← Convert([k])：各方進行橢圓曲線陷阱門運算。 Pi = ki * G
- [b] ← c * [a]: c 是一個公開值。 每一方使用他們的份額 ai 得到 bi = c * ai
整個過程結束後，各方可以在不知道其他各方的秘密數 k 和私鑰份額的情況下計算 r、s 的值。 驗證簽名和普通驗證過程相同，直接拿公鑰驗證即可。
延伸討論
- Additive Secret Sharing 最重要的特點是不需要一個誠實的角色處理私鑰。 從私鑰生成到創建簽名，私鑰不會被還原出來或存在於任何一個位置。
- 份額刷新是可能的。 各方可以拆分手上的值，分配給其他各方，只要私鑰的總和不變即可。 例子：
- 沒有產生 threshold signing 的能力。所有份額都需要參與才能生成簽名。
Shamir 和 Additive Sharing Scheme 的結合
Additive Sharing 無信任操作的優點，和 Shamir threshold signing 的優點可以被結合。需要 1. 從 Shamir 到 Additive 的轉換，以及 2. 分散式的多項式設置。直接用示例解釋會最清楚：
Shamir 到 Additive 的轉換示例
使用拉格朗日插值多項式 (Lagrange interpolating polynomial)。 給定 SSSS 的多項式
3 方各有份額
使用拉格朗日插值多項式我們可以得到以下方程式
回想一下，在 Shamir 方案中，常數項就是私鑰，即 f(0)
注意第一項只能由第一方計算，第二項由第二方計算，第三項由第三計算，三項加起來就是聯合私鑰，這就是 Additive Sharing 的格式 (private_key = x1 + x2 + x3)。例如第一方的份額在 Shamir 下是 f(1) ，在 Additive 變成 f(1)(0–2)(0–3)/(1–2)(1–3)。
t=1, n=3 ，Shamir 和 Additive Sharing 結合的設置示例
我們有 3 個角色 Alice、Bob 和 Carol。 想法是讓 3 方「共同」創建一個次數為 t 的多項式。 首先讓他們生成自己的多項式
- 聯合多項式為 f(x) + g(x) + h(x)，對應的聯合私鑰為 f(0) + g(0) + h(0) （注意這個值不會被算出來）
- Alice 保留 f(1)，將 f(2) 傳遞給 Bob，將 f(3) 傳遞給 Carol。
- Bob 保留 g(2)，將 g(1) 傳遞給 Alice，將 g(3) 傳遞給 Carol。
- Carol 做相同的操作
- 現在 Alice 有 f(1), g(1), h(1)。 Alice 的份額將是總和 f(1)+g(1)+h(1)，Bob 有 f(2)+g(2)+h(2)， Carol 有 x=3 的值
透過這種設置，任何一方都不知道聯合多項式，並且任何兩方都包含原本的聯合多項式足夠的訊息。 在簽名創建過程中，他們將使用上述拉格朗日多項式將手上的 f(i)+g(i)+h(i) 轉換成 Additive Sharing 進行計算。 所以私鑰也沒有被重建。
依此類推，要構建一個 (t, n) secret sharing 的方式就是請 n 方各自生成一個 t 次多項式，並以上面的方式構建多項式以及簽名即可。
參考資料
- ECDSA: https://www.instructables.com/Understanding-how-ECDSA-protects-your-data/
- A Survey of ECDSA Threshold Signing: https://eprint.iacr.org/2020/1390
- Youtube video from the presentation of Prof. Rosario Gennaro: https://youtu.be/PdfDZIwuZm0
