MPC và Threshold Signature
Là Gì? Giải Thích Kỹ Thuật

Ý tưởng: Chia secret (private key) thành n shares sử dụng polynomial interpolation, sao cho bất kỳ t shares nào cũng đủ để reconstruct secret, nhưng t-1 shares bất kỳ không tiết lộ bất kỳ thông tin gì về secret (information-theoretically secure). Đây là scheme (t, n)-threshold: threshold t, tổng số shares n.

Cơ chế: Với secret s, chọn polynomial ngẫu nhiên bậc t-1 với hệ số tự do = s: f(x) = s + a₁x + a₂x² + ... + aₜ₋₁xᵗ⁻¹. Tính n điểm (1, f(1)), (2, f(2)), ..., (n, f(n)) — đây là n shares. Để reconstruct: dùng Lagrange interpolation với bất kỳ t điểm nào để tìm lại polynomial và lấy hệ số tự do (= secret s).

// SSS (2,3) scheme example
// Secret: private_key = 42
// Polynomial degree 1: f(x) = 42 + 7x (random coeff)

// Shares:
// share_1 = f(1) = 42 + 7*1 = 49
// share_2 = f(2) = 42 + 7*2 = 56
// share_3 = f(3) = 42 + 7*3 = 63

// Reconstruct from (share_1, share_2) using Lagrange:
// f(0) = 49 * (0-2)/(1-2) + 56 * (0-1)/(2-1) = 42 ✓

Giới hạn quan trọng: Để ký transaction, t shareholders phải gửi shares đến một dealer, dealer reconstruct full key, sign, rồi discard. Tại thời điểm reconstruct, full key tồn tại ở một điểm. Dealer là single point of failure khi signing. SSS bảo vệ key khi nghỉ ngơi (at rest) — nhưng không khi đang dùng (in use).

Ý tưởng tổng quát: n parties, mỗi party có input riêng (x₁, x₂, ..., xₙ), muốn cùng compute function f(x₁, x₂, ..., xₙ) mà không tiết lộ input của mình cho bất kỳ party nào khác. Ví dụ kinh điển: "Millionaire problem" — n người muốn biết ai giàu nhất mà không ai muốn tiết lộ tài sản của mình.

Trong crypto key management: Mỗi party giữ một key share (sₙ). Khi cần sign: các parties interact để jointly compute signature σ = Sign(combined_secret, message) — mà không bên nào cần biết combined_secret. Full private key không bao giờ tồn tại ở bất kỳ điểm nào — chỉ tồn tại "ảo" trong protocol tính toán.

Protocols phổ biến: GG20 (Genaro-Goldfeder 2020) và CGGMP21 cho threshold ECDSA, FROST cho threshold Schnorr/EdDSA. GG20 được dùng nhiều nhất trong production custodian và tBTC v2.

TSS là gì: TSS là ứng dụng cụ thể của MPC cho bài toán signing. Với (t, n)-TSS: n parties cùng giữ key shares, bất kỳ t parties nào cũng có thể collaborate để tạo ra signature hợp lệ, mà không party nào biết full private key. Signature output là một chữ ký duy nhất — không khác gì signature từ single key. Bên ngoài (chain, verifier) không biết đây là threshold signature.

Quy trình signing với TSS:

1. Có message M cần sign (ví dụ: Bitcoin transaction để move custodied BTC)
2. t parties communicate theo protocol (GG20 / CGGMP21 / FROST)
3. Mỗi party tính partial signature từ key share của mình và random nonce share
4. Partial signatures được combine thành full signature σ
5. σ verify với public key như bình thường — chain không biết threshold

Tính chất quan trọng: Không có bất kỳ party nào biết full key. Không có thời điểm nào full key tồn tại ở một điểm. Tấn công phải compromise ít nhất t parties đồng thời trong cùng một signing session — khó hơn nhiều so với tấn công một custodian đơn.

Vấn đề: Để dùng TSS, cần generate key pair (public key, distributed shares) — nhưng không có trusted dealer. Nếu có dealer, dealer biết full key trong lúc generate — dealer là single point of failure. DKG giải quyết điều này: các parties jointly generate key pair mà không bên nào biết full private key, thậm chí ngay khi generate.

Cơ chế DKG (Pedersen/Feldman): Mỗi party i chạy Shamir's Secret Sharing với secret tự chọn sᵢ, gửi shares đến các parties khác. Các parties combine: final key share của party i = tổng của tất cả shares nhận được. Public key = tổng của public keys tương ứng với sᵢ của từng party. Kết quả: tất cả biết public key chung, không ai biết private key.

// Simplified DKG (3 parties)
// Each party i picks secret s_i, runs SSS(s_i, t, n)
// Party 1: s_1=10, sends shares: f_1(1)=12, f_1(2)=14, f_1(3)=16
// Party 2: s_2=20, sends shares: f_2(1)=22, f_2(2)=24, f_2(3)=26  
// Party 3: s_3=30, sends shares: f_3(1)=32, f_3(2)=34, f_3(3)=36

// Final key share of party 1:
//   x_1 = f_1(1) + f_2(1) + f_3(1) = 12+22+32 = 66
// Combined secret (never known): s_1+s_2+s_3 = 10+20+30 = 60
// Public key = (s_1+s_2+s_3) * G (on elliptic curve)

Tầm quan trọng của DKG ceremony: Nếu DKG bị compromise — ví dụ một party gian lận trong quá trình setup — key shares tạo ra không an toàn. Protocol tốt phải có verification: mỗi party publish commitment trước khi reveal, và các parties verify consistency. DKG ceremony là bước security-critical nhất trong toàn bộ quy trình MPC setup.