Schnorr Multi-Signatures

Table of Contents

1. 简介

本文介绍一些 Schnorr 多签协议。多签协议只支持 n-of-n 签名方案，可以认为是 t-of-n 门限签名的一种特殊情况。如果想寻找更通用的 Schnorr 门限签名协议，可以参考 FROST，不过本文不介绍它。

1.1. 记号说明

在描述 Schnorr 签名时，有乘法群和加法群两种形式。如果是乘法群，从私钥推导出公钥的公式为 \(X=g^x\) ；如果是加法群，从私钥推导出公钥的公式为 \(X = x G\) 。论文 BN06/MuSig/MuSig2 中使用的是 \(X=g^x\) 形式；论文 MuSig-DN 中使用的是 \(X = x G\) 形式。本文将采用 \(X = x G\) 形式。

1.2. Schnorr 签名

下面回顾一下 Schnorr 签名。

设椭圆曲线定义在有限素数域 \(\mathbb{F}_{p}\) 上，椭圆曲线的 Generator 为 \(G\) ，用户的私钥和公钥分别为 \((x, X)\) ，记待签名的消息为 \(m\) ，则生成 Schnorr 签名的过程如下：

  1. 随机选择 \(r \in \mathbb{F}_p\)
  2. 计算 \(R = rG\)
  3. 计算 \(c = \text{H}(X, R, m)\)
  4. 计算 \(s = r + c x \bmod p\)
  5. 输出签名 \((R, s)\)

签名验证时，如果 \((R, s)\) 满足下面等式则通过验证： \[s G \stackrel{?}{=} R + \text{H}(X, R, m) X\]

2. Naive Way（Unsafe）

\(n\) 个参与者本地随机生成各自的私钥 \(x_1,x_2,\cdots,x_n\) ，则它们的公钥为 \(X_1 = x_1 G,X_2 = x_2 G,\cdots,X_n = x_n G\) 。下面是最简单的 Schnorr 多签方案（但它不安全）：

  1. \(n\) 个参与者各自选择一个随机数，如 \(r_1,r_2,\cdots,r_n\) ，计算 \(R_1=r_1G,R_2=r_2G,\cdots,R_n=r_nG\) ；
  2. 第 \(i\) 个参与者把 \(X_i,R_i\) 发送给其它所有参与者；
  3. 记 \(\tilde{X} = \sum_{i=1}^n X_i, \tilde{R} = \sum_{i=1}^n R_i\) ，计算 \(c=\text{H}(\tilde{X}, \tilde{R}, m)\)
  4. 第 \(i\) 个参与者计算 \(s_i = r_i + c x_i \bmod p\) ，并发送 \(s_i\) 给其它所有参与者；
  5. 每个参与者收到别人发来的 \(s_i\) 后，都可以计算出 \(s=\sum_{i=1}^{n} s_i \bmod p\) ；总体签名数据就是 \((\tilde{R},s)\)

校验 \((\tilde{R},s)\) 签名是否正确时，和校验标准的 Schnorr 签名一样，校验下面式子是否成立即可： \[s G \stackrel{?}{=} \tilde{R} + \text{H}(\tilde{X}, \tilde{R}, m) \tilde{X}\] 这种方式，相当于群体的私钥为 \(x=\sum_{i=1}^n x_i\) ，而群体公钥为 \(xG=(x_1+x_2+\cdots+x_n)G= x_1G+x_2G+\cdots+x_nG = \sum_{i=1}^n X_i\) ，也就是前面的记号 \(\tilde{X}\) 。

这种方案是不安全的，下文将介绍它容易遭受 Rogue-key 攻击。

2.1. Rogue-key 攻击

前面介绍的 Naive Way 是不安全的，容易遭受 Rogue-key 攻击。 具体来说，假设第 1 个参与者是个恶意攻击者，他先不给其它参与者发送他的公钥 \(x_1G\) ，而是收到所有其它参与者发来的公钥后，把 \(x_1G - \sum_{i=2}^n X_i\) 作为他的公钥发送给其它参与者。从而，群体的公钥就是 \((x_1G - \sum_{i=2}^n X_i) + X_2 + \cdots + X_n = x_1G\) ，换句话说这时 \(x_1\) 就是群体私钥了，也就是说第 1 个参与者可以代表群体独自完成签名了，这显然违背了多签的意图。

要防止 Rogue-key 攻击，一种常用的思路是参与者提供零知识证明，以证明他确实拥有公钥背后的私钥（Knowledge Of Secret Key, KOSK）。比如，上面例子中第 1 个参与者发送 \(x_1G - \sum_{i=2}^n X_i\) 给其它参与者时，他还必须证明他拥有这个公钥所对应的私钥，显然第 1 个参与者无法提供这个证明，因为他并不知道 \(x_1-\sum_{i=2}^n x_i\) 的值。

2.2. KOSK 有不足

前面提到，基于 KOSK 可以避免 Rogue-key 攻击。不过，基于 KOSK 有一些不足，RY07 中对此进行了总结：

Unfortunately, there are substantial drawbacks to using the KOSK assumption. Bellare and Neven discuss this in [BN06]; we briefly recall some of their discussion. First and foremost, the KOSK assumption is not realized by existing public key infrastructures (PKI). Registration protocols specified by the most widely used standards (RSAPKCS#10, RFC 4210, RFC 4211) do not specify that CA’s should require proofs of knowledge. Thus, to use schemes proven secure under the KOSK assumption, one would be faced with the daunting task of upgrading existing (and already complex) PKI. This would likely require implementing clients and CA’s that support zero-knowledge (ZK) proofs of knowledge that have extraction guarantees in fully concurrent settings. Non-interactive ZK proofs of knowledge could also be utilized, but these are more computationally expensive.

除了后面的 MOR01 协议可以认为是在 Keygen 阶段进行 KOSK 外，本文介绍的其它协议都不是基于 KOSK 来避免 Rogue-key 攻击，而是使用其它手段来避免 Rogue-key 攻击。

3. MOR01（Dedicated Keygen）

2001 年，Silvio Micali, Kazuo Ohta, Leonid Reyzin 在论文 Accountable-Subgroup Multisignatures 中提到了一种多签方案。

MOR01 协议的 Keygen 阶段要求各个参与者使用各个的私钥进行一次常规的 Schnorr 签名，其它参与者会进行签名校验，这样可确保每个参与者确实知道其公钥所对应的私钥。

MOR01 协议的签名过程和 Naive Way 一样，但它不会遭受 Rogue-key 攻击，这是因为每个参与者在 MOR01 的 Keygen 阶段已经通过常规的 Schnorr 签名证明他确实知道其公钥所对应的私钥。

在本文介绍的所有协议中，MOR01 协议的 Keygen 是最复杂的，其它协议的 Keygen 都是每个参与者本地产生一个公私钥对即可，不需要额外操作。

4. BN06

2006 年，Mihir Bellare 和 Gregory Neven 在论文 Multi-Signatures in the Plain Public-Key Model and a General Forking Lemma 中提出了一种多签方案。

\(n\) 个参与者本地随机生成各自的私钥 \(x_1,x_2,\cdots,x_n\) ，则它们的公钥为 \(X_1 = x_1 G,X_2 = x_2 G,\cdots,X_n = x_n G\) ，记公钥列表为 \(L=\{X_1,X_2,\cdots,X_n\}\) ，公钥列表的唯一编码（比如排序后进行编码以确保唯一）为 \(\langle L \rangle\) 。

下面以第 1 个参与者（ \(P_1\) ）的视角（每个参与者都执行相同的协议）来介绍 BN06 协议：

  1. 选择一个随机数 \(r_1\) ，计算 \(R_1 = r_1 G\) ，计算 \(t_1 = \text{H}_0(R_1)\) ，把 \(t_1\) 发送给其它的参与者（这个 \(t_1\) 可看作是 \(R_1\) 的 Commitment）；
  2. 当收到参与者 \(P_i\) 发来的 \(t_i\) 后，才把自己的 \(R_1\) 发送给 \(P_i\) （也就是说收到 \(R_i\) 的 Commitment 后，才发送自己的 \(R_1\) ，这样其它参与者无法根据 \(R_1\) 来构造他的 \(R_i\) 了）；
  3. 从 \(P_i\) 处收到了 \(R_i\) 后，校验 \(t_i = \text{H}_0(R_i)\) 是否成立，如果不成立就退出协议。计算： \[\begin{aligned} \tilde{R} & = \sum_{i=1}^n R_i \\ c_1 &= \text{H}_1(\langle L \rangle, X_1, \tilde{R}, m) \\ s_1 &= r_1 + c_1 x_1 \bmod p \end{aligned}\] 发送 \(s_1\) 给其它参与者；
  4. 每个参与者收到别人发来的 \(s_i\) 后，计算 \(s = \sum_{i=1}^n s_i \bmod p\) ，群体签名就是 \((\tilde{R}, s)\) 。

校验 \((\tilde{R},s)\) 签名是否正确时，验证者计算 \(c_i = \text{H}_1(\langle L \rangle, X_i, \tilde{R}, m)\) ，校验下面式子是否成立即可： \[s G \stackrel{?}{=} \tilde{R} + \sum_{i=1}^nc_i X_i\]

BN06 协议如图 1 所示。

schnorr_mulsig_bn06.gif

Figure 1: BN06 协议

BN06 的缺点是， 在校验群体签名时，已经不是标准的 Schnorr 签名校验了（因为每个 \(X_i\) 前的 \(c_i\) 都不相同，找不到群体公钥），不支持 Key Aggregation。

5. MuSig

2018 年，Gregory Maxwell, Andrew Poelstra, Yannick Seurin, and Pieter Wuille 在论文 Simple Schnorr Multi-Signatures with Applications to Bitcoin 中提出了一种多签方案。它可以看作是 BN06 的增强，解决了 BN06 不支持 Key Aggregation 的缺点。

MuSig 协议和 BN06 协议很像，只是它们在计算 \(c_i\) 的方式上有区别，MuSig 中把 \(c_i\) 变为了 \(P_i\) 特有的数 \(a_i\) 和一个公共常数 \(c\) 之积，如表 1 所示。经过这个改变之后，可以把 BN06 群体签名的校验过程变为标准的 Schnorr 签名校验。

Table 1: MuSig 协议和 BN06 协议在计算 \(c_i\) 时有不同
BN06 MuSig
\(c_i = \text{H}_1(\langle L \rangle, X_i, \tilde{R}, m)\) \(c_i=\text{H}_{\text{agg}}(\langle L \rangle, X_i) \cdot \text{H}_{\text{sig}}( \tilde{X},\tilde{R},m) = a_i \cdot c\)

上面式子中， \(\langle L \rangle\) 是公钥列表的唯一编码，其它记号如下： \[\begin{aligned} \tilde{R} & = \sum_{i=1}^n R_i \\ a_i & = \text{H}_{\text{agg}}(\langle L \rangle, X_i) \\ \tilde{X} &= \sum_{i=1}^n a_i X_i \\ c &= \text{H}_{\text{sig}}( \tilde{X},\tilde{R},m) \end{aligned}\]

校验 \((\tilde{R},s)\) 签名是否正确时，校验下面式子是否成立即可： \[s G \stackrel{?}{=} \tilde{R} + \sum_{i=1}^n c_i X_i = \tilde{R} + \sum_{i=1}^n a_i c X_i = \tilde{R} + c \tilde{X}\] 这种方式，相当于群体的私钥为 \(x = \sum_{i=1}^n a_i x_i\) ，而群体公钥为 \(\tilde{X} = \sum_{i=1}^n a_i X_i\) 的标准 Schnorr 签名校验了。

MuSig 协议如图 2 所示。

schnorr_mulsig_mulsig1.gif

Figure 2: MuSig 协议

6. MuSig-DN

在 Schnorr 签名中，由于有随机产生的 nonce 值（即 \(r\) 值），会导致对相同的数据进行多次签名时，得到的签名结果不一样。

2020 年，Jonas Nick, Tim Ruffing, Yannick Seurin, and Pieter Wuille 在论文 MuSig-DN: Schnorr Multi-Signatures with Verifiably Deterministic Nonces 中提出了名为 MuSig-DN 的方案，它是一种确定性 nonce 值的方案，对同一个消息进行多次签名得到的签名结果会相同。

6.1. 不安全的做法

假设 Alice 和 Bob 的私钥和公钥分别为 \((x_1, X_1)\) 和 \((x_2, X_2)\) 。要确定性地生成 nonce 值，一种直观的想法是 Alice 通过某个函数 \(F(x_1, m)\) 唯一地推导出 nonce 值 \(r_1\) ，Bob 通过函数 \(F(x_2, m)\) 唯一地推导出 nonce 值 \(r_2\) ，剩下和流程和 MuSig 类似。 Alice 计算 \(s_1 = r_1 + c a_1 x_1 \bmod p\) 发送给 Bob，Bob 计算 \(s_2 = r_2 + c a_2 x_2 \bmod p\) 发送给 Alice。

上面这种方法是不安全的。下面介绍一种攻击方法：Bob 通过两次签名可以获得 Alice 的私钥。第一次签名时，Alice 发送了 \(s_1\) 给 Bob，Bob 收到后不发送 \(s_2\) ，而是直接退出协议。Alice 以为 Bob 离线了，再次尝试。第二次签名时，还是对同一消息进行签名，Alice 把 \(R_1\) 发送给 Bob，而 Bob 发给 Alice \(R'_2 \neq R_2\) （Alice 期望 Bob 发送 \(R_2\) 给她，但 Bob 发送的是另一个数 \(R'_2\) ）。Alice 计算 \(\tilde{R'} = R_1+R'_2, s'_1=r_1+c' a_1 x_1 \bmod p\) 其中 \(c' = \text{H}_{\text{sig}}( \tilde{X},\tilde{R'},m)\) ，发送 \(s'_1\) 给 Bob。这样，Bob 利用两次签名的数据就可以得到 Alice 的私钥了 \(x_1 = (s_1 - s'_1) /(a_1(c-c'))\) 。

显然，如果 Alice 可以检测出 Bob 发送给他的 \(R'_2\) 是错误的，那么 Alice 可以退出协议，保护自己的私钥。

6.2. MuSig-DN 主要思想

MuSig-DN 是 MuSig 的一种变种，它的主要思想是使用零知识证明来强制所有参与者确定性地生成他们的 nonce 值。

具体来说， 每个参与者都有一个 nonce key \(u_i\) ，使用这个 nonce key 根据函数 \(F(x_i, m)\) 来确定地生成 \(r_i\) ，然后计算 \(R_i=r_iG\) ，且生成能证明 \(R_i\) 满足要求的零知识证明，别人利用 host key \(U_i = u_i G\) 可以校验 \(R_i\) 确实是按要求生成的。

这个场景和 Verifiable Random Function（VRF）有点像，但其实不然。因为使用 VRF 生成结果 \(r_i\) 后，要公开 \(r_i\) 给别人验证。但在多签协议中， \(r_i\) 是个私密值，不能公开的，公开的是 \(R_i=r_iG\) ，所以 VRF 不能直接拿来使用。

如果不考虑性能，可以直接使用 HMAC 或者 AES 来实现 \(F\) ，但是 HMAC 或者 AES 对应的算术电路很复杂，生成和校验零知识证明时性能较差。MuSig-DN 在论文中提出了一种性能更好的被称为 Purify 的构造，这里不详细介绍。

7. MuSig2

2020 年，Jonas Nick, Tim Ruffing, and Yannick Seurin 在论文 MuSig2: Simple Two-Round Schnorr Multi-Signatures 中提出了 MuSig2。和 MuSig 相比， MuSig2 的轮次更少，只需要 2 轮，而 MuSig 需要 3 轮。

和 MuSig 相比 ，MuSig2 主要有下面不同：

  1. 去掉了提交 Commitment 的第 1 轮（即去掉了提交 \(t_i\) 的那轮）。
  2. 一次生成两个 nonce 值（即图 3 中的记号 \(r'_i,r''_i\) ），而 MuSig 中只有一个 nonce 值。

MuSig2 协议如图 3 所示。

schnorr_mulsig_mulsig2.gif

Figure 3: MuSig2 协议

8. 总结

本文介绍的各种多签方案的对比如表 2 所示。

Table 2: 各种多签方案的对比
Scheme Dedicated Keygen Sign Rounds Key Aggregation Deterministic Nonce Implementation Complexity
MOR01 Yes 3 Yes No Low
BN06 No 3 No No Low
MuSig No 3 Yes No Low
MuSig-DN No 2 Yes Yes High
MuSig2 No 2 Yes No Low

9. 参考

  1. MOR01 Paper: Accountable-Subgroup Multisignatures
  2. BN06 Paper: Multi-Signatures in the Plain Public-Key Model and a General Forking Lemma
  3. MuSig Paper: Simple Schnorr Multi-Signatures with Applications to Bitcoin
  4. MuSig-DN Paper: MuSig-DN: Schnorr Multi-Signatures with Verifiably Deterministic Nonces
  5. MuSig2 Paper: MuSig2: Simple Two-Round Schnorr Multi-Signatures

Author: cig01

Created: <2023-06-30 Fri>

Last updated: <2023-09-24 Sun>

Creator: Emacs 27.1 (Org mode 9.4)