实验 02：Shamir 秘密共享与拉格朗日插值

Shamir 秘密共享把秘密分成份额；它本身不是门限签名。真正的 TSS 签名过程中不应先重构完整私钥。

目标

在实验 01 的 F17 上实现一个确定性的 2-of-3 Shamir 示例，随后扩展为一般的 t-of-n：

用多项式在不同非零横坐标上生成份额；
用任意达到门限的份额在 x = 0 处恢复秘密；
拒绝重复参与者编号、编号 0 和份额不足；
理解“知道少于 t 个点”为什么无法唯一确定秘密。

前置知识

已完成实验 01，有限域加、减、乘、求逆测试全部通过；
能计算一次函数或多项式在某个点的值；
知道两个不同的点确定一条直线。

建议 API 与文件

建议文件：

src/toy_field.rs：复用实验 01；
src/shamir.rs：份额、求值、拆分与恢复；
tests/shamir_toy.rs：已知答案测试。

第一阶段不要加入随机数。让调用者显式提供系数，这样每个结果都可以手算：

#![allow(unused)]
fn main() {
use crate::toy_field::Fp;

pub type F17 = Fp<17>;

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Share {
    pub id: u64,
    pub value: F17,
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub enum ShamirError {
    InvalidThreshold,
    NotEnoughShares,
    ZeroParticipantId,
    DuplicateParticipantId,
}

/// coefficients[0] 是秘密，后面依次是 x、x^2 ... 的系数。
pub fn evaluate_polynomial(coefficients: &[F17], x: F17) -> F17 {
    todo!("使用 Horner 法，从最高次系数向常数项折叠")
}

pub fn split_with_coefficients(
    coefficients: &[F17],
    participant_ids: &[u64],
) -> Result<Vec<Share>, ShamirError> {
    todo!("验证参数，再计算每个 f(id)")
}

pub fn combine(shares: &[Share], threshold: usize) -> Result<F17, ShamirError> {
    todo!("计算每个份额在 x=0 处的拉格朗日权重")
}
}

这是可编译骨架。本实验中 coefficients.len() 就是门限 t；实现时应拒绝空系数数组以及 t = 0。

分步任务

1. 手工生成 2-of-3 份额

取秘密 s = 5、斜率 a = 3，在 F17 中定义：

\[ f(x)=s+ax \]

分别计算 f(1)、f(2)、f(3)。把三个点画在普通坐标纸上时，它们看起来是一条直线；但要提醒自己，实际运算是在模 17 的域上。

2. 用 Horner 法求值

不要为一次、二次、三次多项式分别写分支。实现：

\[ a_0+x(a_1+x(a_2+\cdots)) \]

先写一个二次多项式测试，确认系数遍历方向没有颠倒。

3. 验证参与者编号

在生成和恢复两侧都检查：

编号不能是 0，因为 f(0) 就是秘密；
同一组中编号不得重复；
编号进入域后也不得碰撞。对 F17 而言，编号 1 和 18 会映射到同一横坐标，因此也应被视为重复。

最后一点很容易漏掉。建议比较 F17::new(id) 的值，而不只比较原始 u64。

4. 推导拉格朗日权重

对选中的参与者集合 S，在 x = 0 恢复：

\[ f(0)=\sum_{i\in S}\lambda_i f(x_i) \]

从拉格朗日基函数开始，自行推导 lambda_i 的分子与分母。写代码前，用参与者 1 和 2 的份额手算一次，并检查结果为 5。

实现时，每个分母都必须通过有限域求逆；任何求逆失败都代表前面的 ID 验证存在漏洞，不应 unwrap 掩盖。

5. 推广到 t-of-n

令系数数组长度为 t，生成 n 个点。用 t = 3, n = 5 再做一组固定系数实验，并遍历所有 3 人组合恢复秘密。

6. 迁移到 Ristretto255 标量域

小域版本完全通过后，再建立 src/scalar_shamir.rs：

用 curve25519_dalek::scalar::Scalar 替代 F17；
用 Scalar::from(id) 表示参与者横坐标；
用 Scalar::random(&mut OsRng) 生成非恒定项系数；
继续拒绝 ID 0 和重复 ID。

不要删除 F17 版本。它是后面排查公式和符号错误的“透明参照物”。

建议依赖版本：

[dependencies]
curve25519-dalek = { version = "4", features = ["rand_core"] }
rand_core = { version = "0.6", features = ["getrandom"] }

验收测试

以下已知答案测试应先通过：

#![allow(unused)]
fn main() {
#[test]
fn known_two_of_three_example_matches_by_hand() {
    let coefficients = [F17::new(5), F17::new(3)];
    let shares = split_with_coefficients(&coefficients, &[1, 2, 3]).unwrap();

    assert_eq!(shares[0].value, F17::new(8));
    assert_eq!(shares[1].value, F17::new(11));
    assert_eq!(shares[2].value, F17::new(14));

    assert_eq!(combine(&shares[0..2], 2).unwrap(), F17::new(5));
    assert_eq!(combine(&shares[1..3], 2).unwrap(), F17::new(5));
    assert_eq!(combine(&[shares[0], shares[2]], 2).unwrap(), F17::new(5));
}

#[test]
fn rejects_invalid_sets() {
    let duplicate = [
        Share { id: 1, value: F17::new(8) },
        Share { id: 18, value: F17::new(8) },
    ];
    assert_eq!(combine(&duplicate, 2), Err(ShamirError::DuplicateParticipantId));
    assert_eq!(combine(&duplicate[..1], 2), Err(ShamirError::NotEnoughShares));
}
}

还需自行增加：

所有 3-of-5 组合均恢复同一秘密；
修改一个份额后，恢复值不再等于秘密；
ID 为 0 时明确报错；
系数为空、门限为 0、门限大于份额数时明确报错；
Scalar 版本的随机 2-of-3 往返测试至少运行 100 组。

完成标准：除了测试通过，还能在不看代码的情况下解释恢复公式中每个权重为何依赖“本次实际参与签名的人”。

观察记录

问题	你的记录
三个已知份额分别是多少？
只拿到一个份额时，有多少个秘密仍与它相容？
ID 1 和 18 为什么会冲突？
修改一个份额后为什么通常仍能算出一个值，却不能发现作弊？
F17 与 `Scalar` 版本的 API 有哪些相同和不同？

进阶挑战

遍历 F17，展示单个份额对秘密没有偏好：固定一个份额后，每个可能秘密都能对应某个斜率。
实现份额刷新：加入常数项为 0 的随机多项式，使秘密不变而份额改变。
添加 Feldman VSS 承诺 A_j = a_j G，验证 s_i G 是否等于承诺多项式在 ID i 的点值。
用组合迭代器测试所有恰好 t 人和多于 t 人的子集。

安全警告

“把份额收集到一台机器再恢复私钥”破坏了 TSS 的核心安全边界。这里只为理解 Shamir 才执行恢复。
玩具域份额可被穷举；固定系数、日志和测试向量都不是秘密材料。
生产系统必须使用密码学安全随机数生成多项式系数，并安全擦除临时秘密；测试 RNG 不得进入生产路径。
纯 Shamir 无法检测恶意 Dealer 发放不一致份额。进入 DKG 前需要 VSS、身份认证和一致的参与者集合。

Keyboard shortcuts

TSS 从理论到 Rust 实现