← COMP5567 全部讲次
L10d · 第 10 周

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」怎样换成「乘以逆元」。

  1. 以 mod 11 为例找 2 的逆元:依次试 2 × 1、2 × 2、……,看哪个余 1。

    b 2 × b 除以 11 的余数
    4 8 8
    5 10 10
    6 12 1
  2. 2 × 6 = 12 ≡ 1 (mod 11),所以 2⁻¹ = 6。

  3. 负数先换成正的余数:−2 ≡ 9 (mod 11)。

  4. 找 9 的逆元:9 × 5 = 45 = 44 + 1 ≡ 1,所以 (−2)⁻¹ = 5。

  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. 拿到一份 (1, 7)。过它的直线有无数条,猜不出 s。

    坐标图上只有一个点 (1, 7),四条灰色虚线都穿过它,斜率不同,在 x = 0 处截出不同的高度,说明一份份额猜不出秘密 s

  2. 再拿到一份 (3, 11)。两点只定一条直线,斜率 (11 − 7) / (3 − 1) = 2。

  3. 往左延到 x = 0:f(0) = 7 − 2 = 5,就是秘密 s。

    坐标图上两个点 (1, 7) 和 (3, 11),过它们只有一条黑色直线 f(x) = 5 + 2x,延到 x = 0 处截出 5,青绿圈标出 f(0) = s = 5

  4. 实际使用时所有计算都在 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。

  1. 签名者选随机数 r,算 R = rG。

  2. 算挑战 c = H(R‖X‖m)。

  3. 算 s = r + cx,发出签名 (R, s)。

  4. 验证者自己重算 c,检查 sG = R + cX,成立就收下。

    左框是签名者:选随机数 r 算 R = rG,c = H(R‖X‖m),s = r + cx,发出 (R, s)。右框青绿是验证者:重算 c,检查 sG = R + cX,成立就收下,验证者没用到私钥 x

  5. 为什么成立: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 签名。

  1. 份额:x1 = f(1) = x + a1,x3 = f(3) = x + 3a1。

  2. 系数:l1 = 3/(3−1) = 3·2⁻¹,l3 = 1/(1−3) = (−2)⁻¹。

  3. 各自选随机数,算 R1 = r1G、R3 = r3G,合成 R = R1 + R3,再算 c。

  4. 各自签:s1 = r1 + c·l1·x1,s3 = r3 + c·l3·x3。

    左右两个框是参与者 1 和 3:份额 x1 = x + a1、x3 = x + 3a1,系数 l1 = 3·2⁻¹、l3 = (−2)⁻¹,各自算 R_i 和 s_i,两条箭头汇到下方青绿框:R = R1 + R3,s = s1 + s3

  5. 合并: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 做完整例题。

必背

  1. Shamir 2-of-3:f(x) = s + a1·x mod p,份额 f(1)、f(2)、f(3);任意 2 份可恢复 s = f(0),1 份不行
  2. Schnorr:私钥 x,公钥 X = xG;随机 r,R = rG;c = H(R‖X‖m);s = r + cx;验证 sG = R + cX
  3. 2-of-3 门限 Schnorr(参与者 1、3):l1 = 3·2⁻¹,l3 = (−2)⁻¹,s = s1 + s3 = r1 + r3 + cx,验证 sG = R + cX
  4. 拉格朗日系数的验算:l1·x1 + l3·x3 = x,所以合并出的签名和用完整私钥签的一样
  5. 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:每个新块顺带推进前面三个块,三轮投票叠成流水线。

下一讲 →
L10e L10e Chained HotStuff:每个新块顺手推进前面三个块

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。