随机数对签名的重要性与伪签名的构造

关于签名算法的一些基本变量定义：

  • G为椭圆曲线
  • 随机值k，R=kG
  • m，待签名消息哈希值
  • 私钥x，公钥P=xG
  • H()，哈希函数
  • r = R.x，表示r为R的x坐标值

Schnorr

  • 签名：(R, s)
  • 生成签名：s = k + H(R||P||m)*x
  • 验证签名：sG = R + H(R||P||m)P

ECDSA

  • 签名：(r, s)
  • 生成签名：s = m/k + r/k*x
  • 验证签名：sR = mG + rP
    • 先求得R值：R = m/s*G + r/s*P
    • 再求得r值：r = R.x ，即R的x坐标值，验证r是否一致

随机值k选取的重要性

Schnorr与ECDSA均对随机值强依赖，若任意两次签名之间采用了相同的随机值k，则暴露出私钥。下面我们演算在随机值相同情况下，各个算法暴露私钥的过程。

Schnorr暴露私钥过程

1
2
3
4
5
6
7
8
9
10
11
12
13
两次签名，随机值k相同，同一个把公钥P，两次签名消息分别为：m1, m2。
令 e1 = H(R||P||m1), e2 = H(R||P||m2)

s1 = k + H(R||P||m1)*x = k + e1*x
s2 = k + H(R||P||m2)*x = k + e2*x

有两个签名：(R, s1), (R, s2)

s1 - s2 = k + e1*x - (k + e2*x)
        = (e1 - e2)*x

那么私钥就可以得出：
x = (s1 - s2) / (e1 - e2)

ECDSA暴露私钥过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
两次签名，随机值k相同，同一个把公钥P，两次签名消息分别为：m1, m2。

s1 = m1/k + r/k*x
s2 = m2/k + r/k*x

有两个签名：(r, s1), (r, s2)

第一步，将上述两个等式相减，先暴露出该随机值k，有：
k = (s1 - s2) / (m1 - m2)

根据k值，计算出其对应的r值：
r = R.x = (kG).x

第二步，反推出私钥：
x = (s1 - m1/k)*k/r 或
x = (s2 - m2/k)*k/r

根据上述过程，得出结论：相同私钥对任意数据签名，若任意两次签名采用相同的随机值，则立即暴露出私钥。

对于软硬件钱包来说，其随机数发生器将是非常重要的基石，绝不能出故障。

伪签名问题

ECDSA伪签名

之所以说是伪签名，因为是可以验证通过的签名，并不是“无效签名”。CSW曾经多次使用此伎俩，制造中本聪公钥对应的伪签名，甚至骗过了一些不太清楚签名机制的人。

生成ECDSA的伪签名的过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ECDSA验证签名的等式为：
R = m/s*G + r/s*P

令 u=m/s, v=r/s
即 R = uG + vP

随机生成u、v的值，则有：
u'G + v'P = R'

得到 r' = R'.x，// 求X坐标
得到 s' = r'/v
得到 m' = u*s'

那么对于消息m'，其签名为：(r', s')。此签名是可以验证通过的，因为验证等式是平衡的。

防范ECDSA伪签名非常简单：不可由签名方提供消息m值，必须由验证方提供。因为在伪签名里，m值是随机生成的，一旦m值由其他人提供，则签名方是无法构造出平衡等式的。或者说伪签名里签名方是提供不了m值的消息原文的。

也就是说，由你写一句话下来，交给CSW去签名，他就无法提供出中本聪公钥下能够验证的签名了。

Schnorr是伪签名免疫的

Schnorr目前是无法构造出伪签名的，因为无法构造出平衡的验证等式。在Schnorr的验证等式中sG = R + H(R||P||m)P：

  • 若尝试随机等式左侧值（即随机s值），则无法找到合适的R’和m’，因为R值在哈希函数里使用了
  • 若尝试随机等式右侧值（随机生成R和m值），sG是椭圆曲线乘法，曲线除法不可逆的情况下是无法找到对应的s’值

因此Schnorr签名算法是无法构造出能验证通过的伪签名的。

参考：

Taproot简介

Taproot的概念由Gregory Maxwell在2018年01月提出，Taproot: Privacy preserving switchable scripting，这个概念主要是他研究一番MAST后，发现可以与Schnorr签名一起构成一个特别简洁的输出模式。

定义

Taproot定义了一个输出，两个执行路径的实现方式。

  • N个参与方，构成组公钥C：C = A + B + … + N
  • N + 1个参与方，构成输出组公钥P：P = C + H(C||S)G
    • 多出的一个参与方是：H(C||S)，组公钥C和脚本S的组合哈希。
  • 交易输出中填入组公钥P，格式类似Segwit：[ver] [P]
    • ver=0，segwit已经使用了。Taproot可用ver=1，软分叉来实现。
  • 花费路径有两个，二选一：
    1. 签名模式：N+1参与方全部签名
      • 可以聚合出组公钥P的签名。验证签名后即可花费，无需暴露脚本
    2. 脚本模式：N个参与方里，任意一个或以上拒绝签名。则走脚本模式：
      • 提供：组公钥C、脚本S、以及脚本S相应的数据，即可以花费

示例说明

为了搞清楚运作过程，我们举例说明一下。

  • 两个参与方，分别持有公钥A、B。那么其组公钥（聚合公钥）就是：C = A + B。

  • 定义脚本S：<timeout> OP_CSV OP_DROP B OP_CHECKSIGVERIFY，这个脚本的含义是“N天过后，B一个人签名就可以花掉这个输出”。

那么把上面几个东西拧一起，定义一个新的公钥：P = C + H(C||S)G。

放到输出里，[version] [P]:

  • version，版本号，用于表示taproot的版本
  • P：公钥

令：d = H(C||S)，则有H(C||S)G = dG = D 。那么：

1
2
3
4
P = C + H(C||S)G
  = C + D
  = A + B + D
  = aG + bG + dG

本例其实是三个私钥在参与，只是第三个私钥d是双方共同持有的，外界仅知道组公钥P。

Taproot的签名算法采用Schnorr Signature，然后定义两个花掉此输出的方式。

方式一、签名模式花费

合作模式利用了Schnorr签名的线性特性，若P = A + B + D，则公钥A、B、D的单独签名叠加起来就是公钥P的签名。

A、B都签名（D必然签名，因为私钥d是双方共享的，任何一方都可完成D签名），那么把A、B、D三个签名加起来就是P的签名。

双方合作的话，外界看上去就是一个正常的P的签名一样，这个交易也与普通的转账完全一样。其脚本信息则完全隐蔽掉了。

当然，参与方不限定两个，可以是N个。

方式二、脚本模式花费

若A或者B任何一方拒绝签名，则无法产生（叠加出）公钥P的签名（此时仅有A+D的签名，或者B+D的签名），也就无法花费此输出。

假设A拒绝提供签名，那么B就无法合成出P的签名，但B可选择执行脚本进行花费。B需要提供的有：

  • 公钥C
  • 脚本S
  • 符合脚本S的执行数据DATA（本例是B的签名）

其他节点收到这样一笔交易后，验证过程：

1
2
3
4
5
6
7
8
9
10
11
1. 计算出私钥d: d = H(C||S)

2. 计算出d的公钥: D = dG

3. 验证公钥: P == C + D

4. 构建出完整脚本：DATA || S

5. 执行脚本，并判断结果是否为True

// 上述过程都顺利通过的，则可以花费。

通常，脚本通常都是带延迟条件的，具备一定惩罚性质，例如N天后可以花费，或者多少高度后才可以进块等。当然，也可以不设置延迟条件，脚本内容是没有任何限定的。

总结

Taproot只有在非合作时下才会暴露并执行脚本，签名模式下看上去就是一个再普通不过的公钥签名交易而已。

  • 在Taproot里，是N方参与，N通常>=2。（N=1技术上可行，但没有太大意义）
    • N方参与，则必须有N方签名，签名数量小于N则无法验证通过。缺任意签名则合作模式失败。
  • 两个分支其实已经可以覆盖很多场景，甚至大部分场景。
  • 一般来说，N方大概率都是合作的。

Taproot一个典型应用场景就是闪电网络的交易。当然，Taproot是灵活的，更多应用场景等待挖掘。

参考：