阈值签名实战 — FROST、GG20、Lit Protocol

日期: 2027-01-06 方向: 隐私技术 / FHE/MPC/TEE 阶段: Phase 4 - FHE & MPC & TEE (Day 244-258) 标签: #ThresholdSig #FROST #GG20 #LitProtocol #MPCWallet

---

今日目标

---

1. 阈值签名 (Threshold Signature) 概述

1.1 定义

• t-of-n: $n$ 方共持私钥，任意 $t$ 方协作即可签名
• 不可分：从外部看与单方签名完全相同（同公钥、同签名格式）
• 私钥永不重组：通过MPC直接产生签名

1.2 主要方案对比

关键：Schnorr因线性结构，threshold简单；ECDSA因 $k^{-1}$ 和乘法，threshold复杂得多。

---

2. FROST协议 (Komlo-Goldberg 2020)

2.1 背景

• Flexible Round-Optimized Schnorr Threshold
• 2020年由Chelsea Komlo (Waterloo) 和 Ian Goldberg提出
• IETF标准化进行中（draft-irtf-cfrg-frost）
• 2024年新版本: FROST3 (single-round)

2.2 数学背景：Schnorr签名

Schnorr签名（在曲线 $E$ 上， 基点 $G$ 阶 $q$）：

• 私钥 $d \in \mathbb{Z}_q$，公钥 $Y = d \cdot G$
• 签名 $(m, Y) \to (R, z)$:
  1. 选随机 $k \xleftarrow{$} \mathbb{Z}_q$
  2. $R = k \cdot G$
  3. $c = H(R | Y | m)$
  4. $z = k + c \cdot d \mod q$
  5. 输出 $(R, z)$
• 验证：$z \cdot G \stackrel{?}{=} R + c \cdot Y$

线性性：$z$ 关于 $k$ 和 $d$ 线性 → 直接Shamir分享。

2.3 FROST完整协议

Phase 0: DKG (Distributed Key Generation, 一次性)

• 每方 $P_i$ 选随机 $(t-1)$ 次多项式 $f_i(x) = a_{i,0} + a_{i,1}x + ...$
• 个人secret $d_i = a_{i,0}$（贡献到全局sk的部分）
• 互相发送 share $f_i(j)$ 给 $P_j$
• 每方累加: $d_j' = \sum_i f_i(j)$ — 这是全局多项式 $f(x) = \sum_i f_i(x)$ 在 $j$ 的值
• 全局公钥 $Y = \sum_i a_{i,0} \cdot G = f(0) \cdot G$
• 验证用Feldman commitments

Phase 1: Preprocessing (生成nonce commitments)

• 每方 $P_i$ 生成 $L$ 对随机 $(d_i^{(\ell)}, e_i^{(\ell)})$
• 计算 $D_i^{(\ell)} = d_i^{(\ell)} G, E_i^{(\ell)} = e_i^{(\ell)} G$
• 发布 ${D_i^{(\ell)}, E_i^{(\ell)}}_{\ell}$ 到聚合者

Phase 2: Sign Round

1. Coordinator 选 $t$ 方 $S = {i_1, ..., i_t}$，挑一组 $(D_i, E_i)$
2. 计算 $\rho_i = H_1(i, m, B)$ 其中 $B = {(j, D_j, E_j)}_{j \in S}$
3. 每方 $P_i$ 计算自己的nonce: $k_i = d_i + \rho_i \cdot e_i$
4. 全局 $R = \sum_{i \in S} (D_i + \rho_i E_i)$
5. challenge $c = H(R | Y | m)$
6. 每方计算partial signature: $$z_i = k_i + \lambda_i \cdot d_i' \cdot c \mod q$$ 其中 $\lambda_i = \prod_{j \ne i} \frac{x_j}{x_j - x_i}$ 是Lagrange系数
7. Coordinator聚合: $z = \sum_{i \in S} z_i$
8. 输出 $(R, z)$ — 与单方Schnorr完全相同的格式

验证（外人视角）

$z \cdot G \stackrel{?}{=} R + c \cdot Y$ — 不知道这是threshold签的！

2.4 安全性证明

• 半诚实下：基于Discrete Log Assumption
• 恶意下：增加commitment + ZK proof of knowledge of $d_i$
• ROM (Random Oracle Model) 下安全规约到Schnorr的IND-CMA

2.5 性能

• DKG (1次): ~1s for n=5
• Preprocessing: ~0.1s 一次性生成 ~100对nonces
• Sign: ~10ms per signer (1次 round trip), 总 < 50ms

---

3. 完整Rust Demo: 3-of-5 FROST Ed25519

3.1 项目结构

frost_demo/
├── Cargo.toml
├── src/
│   ├── main.rs
│   └── frost.rs
└── README.md

3.2 Cargo.toml

[package]
name = "frost_demo"
version = "0.1.0"
edition = "2021"

[dependencies]
frost-ed25519 = "2.0"          # ZcashFoundation/frost
ed25519-dalek = "2.1"
rand_core = "0.6"
hex = "0.4"
serde = { version = "1.0", features = ["derive"] }
serde_json = "1.0"

3.3 src/main.rs — 完整可运行代码

use frost_ed25519 as frost;
use rand_core::OsRng;
use std::collections::BTreeMap;

const MIN_SIGNERS: u16 = 3;
const MAX_SIGNERS: u16 = 5;

fn main() -> Result<(), Box<dyn std::error::Error>> {
    println!("=== FROST 3-of-5 Threshold Ed25519 Demo ===\n");
    let mut rng = OsRng;

    // ============ Phase 1: Trusted Dealer Key Generation ============
    // 实际生产用 DKG (frost::keys::dkg)，此处用 trusted dealer 简化
    println!("[Phase 1] Trusted Dealer Key Generation");
    let (shares, pubkey_package) = frost::keys::generate_with_dealer(
        MAX_SIGNERS,
        MIN_SIGNERS,
        frost::keys::IdentifierList::Default,
        &mut rng,
    )?;

    println!("  Group public key: {}", hex::encode(pubkey_package.verifying_key().serialize()?));
    println!("  Generated {} shares (threshold {}/{})", 
        shares.len(), MIN_SIGNERS, MAX_SIGNERS);

    // 转换为 KeyPackage（每方需要的）
    let key_packages: BTreeMap<_, _> = shares.into_iter()
        .map(|(id, secret_share)| {
            let kp = frost::keys::KeyPackage::try_from(secret_share)?;
            Ok::<_, frost::Error>((id, kp))
        })
        .collect::<Result<_, _>>()?;

    // ============ Phase 2: Round 1 — Nonce commitments ============
    println!("\n[Phase 2] Round 1: Generate signing nonces");
    let mut nonces = BTreeMap::new();
    let mut commitments = BTreeMap::new();

    // 选择前 MIN_SIGNERS=3 个签名者参与
    let participating_ids: Vec<_> = key_packages.keys()
        .take(MIN_SIGNERS as usize).cloned().collect();

    for id in &participating_ids {
        let kp = &key_packages[id];
        let (nonce, commitment) = frost::round1::commit(kp.signing_share(), &mut rng);
        nonces.insert(*id, nonce);
        commitments.insert(*id, commitment);
        println!("  Signer {:?}: nonce committed", id);
    }

    // ============ Phase 3: Coordinator builds SigningPackage ============
    println!("\n[Phase 3] Coordinator builds signing package");
    let message = b"Hello from threshold sig world!";
    let signing_package = frost::SigningPackage::new(commitments, message);
    println!("  Message: {:?}", std::str::from_utf8(message)?);
    println!("  Signing package built with {} signers", participating_ids.len());

    // ============ Phase 4: Round 2 — Each signer creates partial signature ============
    println!("\n[Phase 4] Round 2: Generate partial signatures");
    let mut signature_shares = BTreeMap::new();

    for id in &participating_ids {
        let kp = &key_packages[id];
        let nonce = &nonces[id];
        let sig_share = frost::round2::sign(&signing_package, nonce, kp)?;
        signature_shares.insert(*id, sig_share);
        println!("  Signer {:?}: partial sig generated", id);
    }

    // ============ Phase 5: Aggregator combines into final signature ============
    println!("\n[Phase 5] Aggregate final signature");
    let group_signature = frost::aggregate(&signing_package, &signature_shares, &pubkey_package)?;
    let sig_bytes = group_signature.serialize()?;
    println!("  Final signature ({} bytes): {}", sig_bytes.len(), hex::encode(&sig_bytes));

    // ============ Phase 6: Anyone can verify ============
    println!("\n[Phase 6] Verify (looks like a single Ed25519 signature)");
    let verify_result = pubkey_package.verifying_key().verify(message, &group_signature);
    match verify_result {
        Ok(_) => println!("  ✓ VALID — verifier sees same as a single-key Ed25519 sig"),
        Err(e) => println!("  ✗ INVALID: {:?}", e),
    }

    // ============ Negative test: Try with insufficient signers ============
    println!("\n[Negative Test] Try with only 2 signers (below threshold)");
    let two_ids: Vec<_> = key_packages.keys().take(2).cloned().collect();
    let mut nonces2 = BTreeMap::new();
    let mut commitments2 = BTreeMap::new();
    for id in &two_ids {
        let kp = &key_packages[id];
        let (n, c) = frost::round1::commit(kp.signing_share(), &mut rng);
        nonces2.insert(*id, n);
        commitments2.insert(*id, c);
    }
    let pkg2 = frost::SigningPackage::new(commitments2, message);
    let mut shares2 = BTreeMap::new();
    for id in &two_ids {
        let kp = &key_packages[id];
        let nonce = &nonces2[id];
        let s = frost::round2::sign(&pkg2, nonce, kp)?;
        shares2.insert(*id, s);
    }
    // aggregate还会"完成"，但产生的签名无效
    let bad_sig = frost::aggregate(&pkg2, &shares2, &pubkey_package);
    match bad_sig {
        Ok(s) => {
            let v = pubkey_package.verifying_key().verify(message, &s);
            println!("  Aggregated below-threshold sig verifies? {:?}", v);
            if v.is_err() {
                println!("  ✓ Correctly rejected (sig produced but invalid)");
            }
        }
        Err(e) => println!("  Aggregate failed: {:?}", e),
    }

    println!("\n=== Demo complete ✓ ===");
    Ok(())
}

3.4 编译运行

cd frost_demo
cargo run --release

3.5 预期输出

=== FROST 3-of-5 Threshold Ed25519 Demo ===

[Phase 1] Trusted Dealer Key Generation
  Group public key: 4a3c8e72...
  Generated 5 shares (threshold 3/5)

[Phase 2] Round 1: Generate signing nonces
  Signer Identifier(1): nonce committed
  Signer Identifier(2): nonce committed
  Signer Identifier(3): nonce committed

[Phase 3] Coordinator builds signing package
  Message: "Hello from threshold sig world!"
  Signing package built with 3 signers

[Phase 4] Round 2: Generate partial signatures
  Signer Identifier(1): partial sig generated
  Signer Identifier(2): partial sig generated
  Signer Identifier(3): partial sig generated

[Phase 5] Aggregate final signature
  Final signature (64 bytes): 9af3e11b...

[Phase 6] Verify (looks like a single Ed25519 signature)
  ✓ VALID — verifier sees same as a single-key Ed25519 sig

[Negative Test] Try with only 2 signers (below threshold)
  Aggregated below-threshold sig verifies? Err(...)
  ✓ Correctly rejected (sig produced but invalid)

=== Demo complete ✓ ===

---

4. GG20协议（Gennaro-Goldfeder 2020）

4.1 背景与意义

• 第一个实用的 dishonest majority + malicious-safe threshold ECDSA
• Bitcoin/Ethereum的custody (Fireblocks, Coinbase Custody) 标配
• 2020年发表，2022年发现 TS Sec attack (Skip leak)，2023年GG20-fix

4.2 复杂性来源

ECDSA签名 $s = k^{-1}(m + r \cdot d) \mod q$ 含 $k^{-1}$ 和乘法 — 不是线性的。

→ 需要MPC计算 $k^{-1} \cdot d$ 在分享形式下，常用：

• MtA (Multiplicative-to-Additive): 把 $a \cdot b$（每方各持一factor）转换成 $\alpha + \beta = ab$ 的additive分享
• 用 Paillier homomorphic encryption 或 Class group encryption
• 大量 ZK proofs 防恶意

4.3 协议轮次（典型MPC-CMP流程，9-10轮）

1. KeyGen (DKG with proofs) — 6轮
2. Pre-signing (生成 $k$ 和 $r$ 的分享) — 4轮
3. Online sign — 2轮

4.4 著名漏洞

• TSSHOCK / Skip-Leak (2022): Fireblocks研究员发现GG20的MtA实现可被恶意方"skip"某轮泄漏分片sk
• 修复：增加 ZK proof 防止skip

---

5. Lit Protocol — 生产案例

5.1 概述

• Lit Protocol（前 LitProtocol Inc）：2020成立，分布式key management
• 2024 Mainnet "Habanero"，2025 升级 "Datil"
• ~50个节点跑MPC + threshold ECDSA/BLS签名
• TVL不直接对应（不锁资产），但接入项目超100+
• Token: $LITKEY (TGE 2025 Q3)，FDV ~$100M

5.2 架构

┌─────────────────────────────────────────────────┐
│  User signs request: "decrypt this message"     │
│                  ┌─────────────────┐            │
│                  │ Lit Action       │           │
│                  │ (JS smart contract)│         │
│                  └─────────────────┘            │
└────────────────────────┬───────────────────────┘
                         │
                         ▼
┌─────────────────────────────────────────────────┐
│ Lit Network (50+ nodes, threshold 2/3)          │
│  ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐            │
│  │node1 │ │node2 │ │node3 │ │ ... │             │
│  └──────┘ └──────┘ └──────┘ └──────┘            │
│   sk_share sk_share sk_share                    │
│                                                  │
│  - Verify access conditions (on-chain etc)      │
│  - Threshold ECDSA sign (BLS for some)         │
│  - Threshold decryption (BLS-based KEM)        │
└─────────────────────────────────────────────────┘
                         │
                         ▼
            Signature returned (single sig, looks normal)

5.3 用例

• Web3 access control：解密文件需链上条件（如持有NFT）
• MPC wallet (PKPs - Programmable Key Pairs)
• Cross-chain messaging：Lit网络threshold签消息
• AI Agent控制：Agent通过Lit get key permissions

---

6. MPC钱包生态

---

7. 性能基准

---

8. 常见陷阱

1. DKG vs Trusted Dealer — 生产必须用DKG；trusted dealer是单点风险
2. Nonce reuse — FROST每对(d,e)只用一次！否则导致sk提取（与Schnorr相同陷阱）
3. Identifier collisions — 两方用相同id → DKG失败
4. ECDSA threshold的TSSHOCK — 2022年GG20 MtA漏洞（已修）
5. Aborts与公平性 — 恶意方可能在最后步abort让其他方"白干"
6. Replay — 同一message + nonce组合重放 → 必须含timestamp或nonce id
7. ZK proof验证缺失 — 生产实现中省略恶意安全的ZK会被攻破

---

9. 真实事件 / 案例

9.1 TSSHOCK (Aug 2022)

Fireblocks研究员发现：GG20的 Multiplicative-to-Additive (MtA) 子协议没有充分验证 ZK proofs → 恶意方可"skip"某些check泄漏victim的sk分片。

• 影响：早期实现 ZenGo, BoltLabs, Webb 都受影响
• 修复：增加zk_pdl_with_slack proof + paillier modulus check

9.2 ed25519的小子群攻击

某些threshold Ed25519实现忘记 cofactor clear → 8-torsion子群攻击。FROST正确实现避免。

9.3 Lit Protocol Mainnet Bug (2024)

节点同步问题导致部分签名延迟，无安全损失。

---

10. 合规视角

• NIST SP 800-57 Rev 5 推荐 threshold key management
• FIPS 140-3 Level 4 — threshold sigs可作为"split knowledge"实现
• 金融行业：Fireblocks/BitGo MPC 托管已成机构标配 ($5T+ AUM)
• 欧盟MiCA Art.71 — 加密资产服务商需"安全保管" → MPC符合
• 中国《商用密码管理条例》 — threshold密钥管理符合"密钥分散"原则

---

11. 关键速查

---

12. 面试题

Q1：为什么FROST比threshold ECDSA简单很多？

Schnorr签名 $s = k + cd$ 是 $k, d$ 的线性组合 → 直接Shamir分享并相加即可。ECDSA 含 $s = k^{-1}(m+rd)$，模逆 + 乘法让线性失效，需要复杂MPC（MtA + Paillier或class group + 大量ZK proofs）。结果：FROST 2轮，GG20 9轮。

Q2：threshold sig vs multisig链上区别？

链上 multisig（如Gnosis Safe）：链上有 $n$ 个pubkey和阈值规则；外部可见这是multisig；每签需要 $t$ 个独立签名，gas开销 $\propto t$。Threshold sig：链上只有1个pubkey；外部不可见这是threshold；off-chain聚合，链上只1个签名，gas与单签同。Bitcoin Taproot的MuSig2是threshold-style但限n-of-n。

Q3：DKG vs Trusted Dealer？

Trusted dealer知道完整sk → 单点风险（被攻击/作恶则全失）。DKG让 $n$ 方各自贡献多项式，没人单独知道sk。生产MPC必须DKG。FROST/GG20都有完整DKG子协议，但比trusted dealer慢（多轮通信）。

Q4：FROST的preprocessing作用？

Round 1（preprocessing）让每方提前生成nonce commitment $(D_i, E_i)$。这步不依赖message → 可批量预生成。Sign时只需1轮（公开 $\rho_i$ 和 $z_i$），降低latency。FROST3 (2024) 进一步消除preprocessing做到纯1轮。

Q5：threshold sig在Web3最大用例？

(1) MPC wallets (Fireblocks/ZenGo/Coinbase) — 机构$5T+ AUM；(2) 跨链桥安全 (Wormhole曾用multisig被hack后转向threshold)；(3) Validator key management — Ethereum/Cosmos validator用threshold避免单key被盗；(4) Bitcoin Taproot multisig — MuSig2；(5) Lit Protocol/Web3Auth — embedded wallet社交恢复。

---

13. 明日预告

Day 251：Week 37复习 — FHE/MPC/TEE/ZK四大隐私技术trade-off全面对比矩阵，构建决策框架。

---

今日产出: frost_demo (Cargo project, 完整Rust ~200行可运行) + frost.md(本文 ~700行) Lines: ~700