L10d 门限签名:2f+1 份部分签名合成一个签名
从零讲 HotStuff 里 QC 背后的门限签名:模运算和逆元、Shamir 秘密分享、Schnorr 签名,再用拉格朗日系数把 2-of-3 的部分签名合成一个普通签名。
一句话版
一张 QC 要证明「2f+1 个节点投过票」,却只装一个签名。办法是把一把私钥拆成很多份,每个节点只拿一份;凑够门限数量的部分签名,加起来就得到一个普通签名,验证者用一把公钥一次验完。
前面三页反复说「QC 是门限签名合成的」。这一页把它拆开:先补模运算,再讲拆秘密、讲签名,最后讲怎样合成。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| 模运算 | mod p | 算完只留除以 p 的余数 |
| 逆元 | a⁻¹ | 和 a 相乘余 1 的那个数,用来做「除法」 |
| 秘密分享 | Shamir secret sharing | 把秘密拆成多份,凑够门限才能还原 |
| 份额 | share | 每个参与者手里那一份 |
| Schnorr 签名 | Schnorr signature | 一种「签名 = 随机数 + 挑战 × 私钥」的签名 |
| 拉格朗日系数 | Lagrange coefficient | 把几份份额加权合成秘密时用的权重 |
| 门限 | threshold | 至少要几份才能完成,比如 2-of-3 里的 2 |
一个类比:保险柜的几把钥匙
一个保险柜的密码被拆成三份,分给三个经理。规定任意两个人到场就能开,一个人开不了。
Shamir 秘密分享负责「怎么拆」:拆法要保证两份能还原、一份什么也看不出。
门限签名更进一步:两个经理不用把各自那份交出来拼成完整密码。他们各自在文件上盖半个章,两个半章合起来,和用完整密码盖的章一模一样。外人拿公章样本一比就能验,看不出是谁盖的。
类比在哪里失效:
- 真实的保险柜密码可以被某个经理偷记下来;数学上,一份份额对秘密完全不泄露信息。
- 「半个章」在协议里是一个数 s_i,合成用的是加法和权重,不是物理拼接。
- 课件的例子是 2-of-3;HotStuff 里门限是 2f+1,原理一样。
从零讲起
1. 模运算和逆元
它解决什么问题
后面所有公式都写着「mod p」,系数里还出现 2⁻¹ 这种写法。在模运算里没有小数,「除以 2」要换成「乘以 2 的逆元」。先把这一步弄熟,后面的算式才看得懂。
从哪来(补充)
a 模 m 的逆元,是满足 ax ≡ 1 (mod m) 的 x,当且仅当 a 和 m 的最大公约数是 1 时存在。
出处:Wikipedia: Modular multiplicative inverse
直觉
模运算像钟表:时针走过 12 又从头开始,只看余数。在这样的世界里,乘法照常做,加减照常做,算完取余数就行。
除法不能直接做。「3 除以 2」在整数余数里没有对应的数,但可以找一个数 b,使 2 × b 的余数是 1。乘以 b 就相当于除以 2。这个 b 就是 2 的逆元,写成 2⁻¹。
p 取质数时,除了 0 以外每个数都有逆元,所以密码学里常用质数做模数。
一步一步看
目标:在 mod 11 里亲手找出 2 和 −2 的逆元,看「除以 2」怎样换成「乘以逆元」。
-
以 mod 11 为例找 2 的逆元:依次试 2 × 1、2 × 2、……,看哪个余 1。
b 2 × b 除以 11 的余数 4 8 8 5 10 10 6 12 1 -
2 × 6 = 12 ≡ 1 (mod 11),所以 2⁻¹ = 6。
-
负数先换成正的余数:−2 ≡ 9 (mod 11)。
-
找 9 的逆元:9 × 5 = 45 = 44 + 1 ≡ 1,所以 (−2)⁻¹ = 5。
-
「3/2」在 mod 11 里就是 3 × 2⁻¹ = 3 × 6 = 18 ≡ 7。
怎么算
a⁻¹ 满足 a × a⁻¹ ≡ 1 (mod p)
a / b 在 mod p 里写成 a × b⁻¹
意思是:模运算里的「除以 b」,就是乘上和 b 相乘余 1 的那个数。
常见误解
以为 2⁻¹ 就是小数「二分之一」
在模运算里没有小数。2⁻¹ 是一个整数,比如 mod 11 时是 6,因为 2 × 6 余 1。
以为任何数都有逆元
要和模数互质才有。比如 mod 10 时 2 没有逆元,2 乘任何数都是偶数,余数不可能是 1。
试一下
mod 11 时,3 的逆元是多少?
4。3 × 4 = 12 ≡ 1。
mod 7 时,「5/3」等于多少?
3⁻¹ = 5(3 × 5 = 15 ≡ 1),5 × 5 = 25 ≡ 4。
2. Shamir 秘密分享:两点定一条直线
它解决什么问题
要让多个节点合起来签名,先得把私钥拆开,每人只拿一份,且少于门限的份额什么也看不出。Shamir 用多项式做到了这一点。
从哪来(补充)
Adi Shamir 1979 年提出,论文「How to share a secret」发表在 Communications of the ACM。原理是 k 个点唯一确定一个次数不超过 k−1 的多项式。
出处:Wikipedia: Shamir’s secret sharing
直觉
2-of-3 用的是一条直线 f(x) = s + a1·x。秘密 s 是直线在 x = 0 处的高度,a1 是随便选的斜率。
给三个人各发直线上的一个点:f(1)、f(2)、f(3)。只有一个点时,过它的直线有无数条,在 x = 0 处可以截出任何高度。有两个点,直线就定死了,往左一延就读出 s。
一步一步看
目标:看只拿一份份额为什么猜不出秘密,拿到两份又怎样把 s 读出来。
用普通实数举例,秘密 s = 5,斜率 a1 = 2,直线 f(x) = 5 + 2x。
-
拿到一份 (1, 7)。过它的直线有无数条,猜不出 s。
-
再拿到一份 (3, 11)。两点只定一条直线,斜率 (11 − 7) / (3 − 1) = 2。
-
往左延到 x = 0:f(0) = 7 − 2 = 5,就是秘密 s。
-
实际使用时所有计算都在 mod p 下做,原理不变,只是除法换成乘逆元。
怎么算
f(x) = s + a1·x mod p,份额 f(1)、f(2)、f(3)
用份额 i、j 恢复:s = f(0) = f(i)·j/(j−i) + f(j)·i/(i−j)
意思是:两份份额各乘一个权重再相加,就得到直线在 0 处的高度。权重只和参与者编号有关,和秘密无关。
常见误解
以为一份份额能透露秘密的一部分
一个点配上不同斜率,可以截出任何 s,所以一份份额对秘密没有任何信息。
以为门限高了就要用更长的直线
门限是 k 就用次数 k−1 的多项式。2-of-3 用一次多项式(直线),3-of-n 就要用二次曲线。
试一下
直线 f(x) = 5 + 2x,参与者 2 的份额是多少?
f(2) = 5 + 4 = 9。
只拿到 (2, 9) 和 (3, 11),秘密是多少?
斜率 2,f(0) = 9 − 2 × 2 = 5。
3. Schnorr 签名
它解决什么问题
拆好私钥后,还要一种签名算法,它的签名能被「拆开来签、加起来合并」。Schnorr 签名的形式 s = r + cx 是线性的,正好适合。
从哪来(补充)
Claus Schnorr 提出,见他 CRYPTO ’89 的论文和 1991 年 Journal of Cryptology 的论文。美国专利 4,995,082 于 2010 年 2 月到期,比特币在 Taproot 升级后用上了它(BIP 340)。
出处:Wikipedia: Schnorr signature
直觉
签名者有私钥 x,公钥是 X = xG。G 是椭圆曲线上公开的一个点,由 X 反推 x 算不出来。
签名时先选一个随机数 r,公开 R = rG。再把 R、X 和消息 m 一起哈希,得到挑战 c。签名就是 s = r + cx。
验证者没有 x,但可以检查 sG 是否等于 R + cX。两边都只用公开的东西算。
一步一步看
目标:走一遍签名和验证,看验证者手里没有私钥 x,为什么照样能确认 sG = R + cX。
-
签名者选随机数 r,算 R = rG。
-
算挑战 c = H(R‖X‖m)。
-
算 s = r + cx,发出签名 (R, s)。
-
验证者自己重算 c,检查 sG = R + cX,成立就收下。
-
为什么成立:sG = (r + cx)G = rG + c·xG = R + cX。
怎么算
签:R = rG,c = H(R‖X‖m),s = r + cx
验:sG = R + cX
意思是:s 里混着私钥 x,但乘上 G 之后,x 只以公钥 X 的形式出现,验证者不用知道 x。
常见误解
以为验证者能从 s 算出私钥 x
s = r + cx 里还有随机数 r,验证者不知道 r,解不出 x。
以为 c 是签名者随便选的
c 是哈希出来的,验证者会重算一遍。签名者改不了 c,否则验证不过。
试一下
签名 (R, s) 里,为什么要把 R 也发出去?
验证者重算 c 要用 R,检查等式右边也要用 R。
如果两条不同的消息用了同一个 r 会怎样?
两个 s 相减得 (c1 − c2)x,c1、c2 公开,x 就被算出来了。每次签名都要用新的随机数。
4. 门限 Schnorr:部分签名加起来
它解决什么问题
把前两节合在一起:私钥 x 用 Shamir 拆成份额,每个参与者用自己的份额签一份部分签名,凑够门限后加起来,得到一个和完整私钥签出的一样的签名。这就是 QC 里那一个签名的来历。
从哪来(补充)
合并时用的权重叫拉格朗日系数。Lagrange 1795 年发表这一插值公式,Edward Waring 1779 年更早发现过,它也是 Euler 1783 年一个公式的推论。
出处:Wikipedia: Lagrange polynomial
直觉
Shamir 告诉我们:份额乘上拉格朗日系数再相加,就是秘密 x。
Schnorr 签名 s = r + cx 对 x 是线性的。所以每人用「系数 × 份额」代替 x 签一份,加起来,c 后面那部分正好凑成 cx,整体就是一个普通的 Schnorr 签名。
谁也没有在任何时候拿到完整的 x。
一步一步看
目标:跟着参与者 1 和 3 各签一份,看两份部分签名加起来为什么正好是一个普通的 Schnorr 签名。
课件的例子:2-of-3,参与者 1 和 3 签名。
-
份额:x1 = f(1) = x + a1,x3 = f(3) = x + 3a1。
-
系数:l1 = 3/(3−1) = 3·2⁻¹,l3 = 1/(1−3) = (−2)⁻¹。
-
各自选随机数,算 R1 = r1G、R3 = r3G,合成 R = R1 + R3,再算 c。
-
各自签:s1 = r1 + c·l1·x1,s3 = r3 + c·l3·x3。
-
合并:s = s1 + s3 = r1 + r3 + c(l1·x1 + l3·x3) = r1 + r3 + cx,验证 sG = R + cX 照样成立。
怎么算
验算系数:l1·x1 + l3·x3 = (3/2)(x + a1) − (1/2)(x + 3a1) = x
合并:s = s1 + s3 = r1 + r3 + cx
意思是:两个系数把 a1 那部分正好抵消,只剩 x。所以部分签名相加后,和用完整私钥签的签名一模一样。
常见误解
以为 QC 里装着 2f+1 个签名
装的是合并后的一个签名。验证者用一把公钥 X 验一次,成本不随节点数增长。
以为系数和秘密有关,每次都要重新算
系数只和参与者编号有关。参与者 1 和 3 一组时,系数固定是 3·2⁻¹ 和 (−2)⁻¹。
试一下
换成参与者 1 和 2 签名,系数是多少?
l1 = 2/(2−1) = 2,l2 = 1/(1−2) = −1。
验算参与者 1、2 的系数:l1·x1 + l2·x2 是否等于 x?
2(x + a1) − (x + 2a1) = x,成立。
把它们串起来
QC 要证明 2f+1 个节点投过票,又只能装一个签名,这一页给出了做法。
模运算里没有小数,除法换成乘逆元,后面的系数才能写成 3·2⁻¹ 这样的整数。Shamir 用一条直线把秘密拆成多个点,一个点什么也看不出,两个点就能还原。Schnorr 签名 s = r + cx 对私钥是线性的,所以可以拆开签。
门限签名把它们接起来。每人用「拉格朗日系数 × 自己的份额」签一份部分签名,加起来后,系数让多余的项抵消,结果和用完整私钥签的一样。leader 收够部分签名就合成一张 QC,任何人用一把公钥就能验,伪造则需要凑够门限数量的份额。
下一页回到共识本身:三轮投票每块要走三遍,Chained HotStuff 怎样把它们叠成流水线。
课件里的坑
- [读图提醒] 门限签名几页里的 n 指椭圆曲线群的阶,不是节点数,别和 n = 3f+1 混了(p.19–23)。
- [读图提醒] 系数写成 3/(3−1) 这样的分数,在 mod 运算里要换成乘逆元:3·2⁻¹(p.21–23)。
- [读图提醒] Shamir 那页只给了 2-of-3 的直线。门限换成 k 时多项式次数是 k−1(p.18)。
课后 10 分钟:考点复习
这 10 分钟怎么用:先合上页面,写出 Schnorr 的签名式和验证式;再推一遍 l1·x1 + l3·x3 = x;然后用 mod 11 做完整例题。
必背
- Shamir 2-of-3:f(x) = s + a1·x mod p,份额 f(1)、f(2)、f(3);任意 2 份可恢复 s = f(0),1 份不行
- Schnorr:私钥 x,公钥 X = xG;随机 r,R = rG;c = H(R‖X‖m);s = r + cx;验证 sG = R + cX
- 2-of-3 门限 Schnorr(参与者 1、3):l1 = 3·2⁻¹,l3 = (−2)⁻¹,s = s1 + s3 = r1 + r3 + cx,验证 sG = R + cX
- 拉格朗日系数的验算:l1·x1 + l3·x3 = x,所以合并出的签名和用完整私钥签的一样
- QC 里只放一个签名,验证成本不随 n 增长;p.19–23 的 n 指椭圆曲线群的阶,不是节点数
课件例题
例 1(课件 p.18):Shamir 2-of-3
f(x) = s + a1·x mod p,三个人各拿 f(1)、f(2)、f(3)。为什么 2 份能恢复 s,1 份不行?
提示
f 是一条直线,s 是它在 0 处的高度。
解答
两点唯一确定一条直线,恢复后取 f(0) = s。一个点可以配任何斜率,s 可以是任何值,所以 1 份不行。
例 2(课件 p.21–23):2-of-3 门限 Schnorr,参与者 {1, 3}
写出两人的份额、拉格朗日系数、部分签名,以及合并后为什么能通过验证。
提示
先写 x1、x3 关于 x 和 a1 的式子,再算系数,最后把 s1 + s3 展开。
解答
份额 x1 = x + a1,x3 = x + 3a1。系数 l1 = 3/(3−1) = 3·2⁻¹,l3 = 1/(1−3) = (−2)⁻¹。验算 l1·x1 + l3·x3 = (3/2)(x + a1) − (1/2)(x + 3a1) = x。各自 R_i = r_iG,s1 = r1 + c·l1·x1,s3 = r3 + c·l3·x3。合并 R = R1 + R3,s = s1 + s3 = r1 + r3 + cx,所以 sG = R + cX 成立。QC 里只放这一个签名。
完整例题
题目:在 mod 11 下做一遍 2-of-3 Shamir 恢复。私钥 x = 4,斜率 a1 = 3。参与者 1 和 3 合作,求他们的份额、拉格朗日系数,并验证 l1·x1 + l3·x3 ≡ x。
解法:
第一步,算份额。x1 = 4 + 3 × 1 = 7;x3 = 4 + 3 × 3 = 13 ≡ 2 (mod 11)。
第二步,算逆元。2 × 6 = 12 ≡ 1,所以 2⁻¹ = 6;−2 ≡ 9,9 × 5 = 45 ≡ 1,所以 (−2)⁻¹ = 5。
第三步,算系数。l1 = 3 × 6 = 18 ≡ 7;l3 = 5。
第四步,验算。l1·x1 + l3·x3 = 7 × 7 + 5 × 2 = 49 + 10 = 59 = 55 + 4 ≡ 4 = x。
要点:分数一律换成乘逆元;负数先加上模数变成正的余数。
答题格式:份额 → 逆元 → 系数 → 加权求和 → 和 x 对上。
变式题(先自己做)
1. 同样 mod 11、x = 4、a1 = 3,改成参与者 1 和 2 合作。求系数并验算。(改编自课件 p.21–23)
提示
l1 = 2/(2−1),l2 = 1/(1−2)。
判分点与答案(非官方评分标准)
l1 = 2,l2 = −1。份额 x1 = 7,x2 = 4 + 6 = 10。2 × 7 − 10 = 4 = x。判分点:系数写对;份额 x2 = 10;验算结果为 4。
2. 自编情境:某个 leader 只收到 2f 份部分签名就想合成 QC,能成功吗?为什么?
提示
门限是 2f+1。少一份时,系数还能把 a1 那些项抵消吗?
判分点与答案(非官方评分标准)
不能。门限 2f+1 对应次数 2f 的多项式,2f 份只确定不了它,合成的 s 里会残留随机系数的项,验证 sG = R + cX 不成立。判分点:说出门限与多项式次数的关系;结论是验证不过。
闪卡自测
1. mod 11 下 2⁻¹ 是多少?
6,因为 2 × 6 = 12 ≡ 1。
2. Shamir 2-of-3 用什么函数?秘密在哪?
直线 f(x) = s + a1·x,秘密是 f(0)(p.18)。
3. 为什么 1 份份额猜不出秘密?
过一个点的直线有无数条,f(0) 可以是任何值(p.18)。
4. Schnorr 的签名式和验证式?
s = r + cx;sG = R + cX(p.19–20)。
5. c 怎么算?
c = H(R‖X‖m)(p.19–20)。
6. 参与者 1、3 的拉格朗日系数?
l1 = 3·2⁻¹,l3 = (−2)⁻¹(p.21–23)。
7. 门限签名的验证式和普通 Schnorr 一样吗?
一样,合并后 sG = R + cX(p.20–23)。
8. 门限签名几页里的 n 指什么?
椭圆曲线群的阶,不是节点数(p.19–23)。
下一讲
下一页是 L10e Chained HotStuff:每个新块顺带推进前面三个块,三轮投票叠成流水线。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。