Schnorr 签名
单签
Schnorr 签名是一种数字签名方案，由德国密码学家 Claus-Peter Schnorr 提出，最早在 1989 年的一篇论文中(Efficient Signature Generation by Smart Cards)被描述，文中提出了一种身份认证方案，再通过Fiat-Shamir变换 (How To Prove Yourself: Practical Solutions to Identification and Signature Problems,1986) 转变成签名方案，它基于离散对数困难问题，具有高效性、安全性等优点，在区块链等领域有重要应用。\
下面给出在椭圆曲线加法群中构造的算法流程。
$\text{KeyGen}:$\
生成随机数 $x \xleftarrow{R}[1,N-1]$作为私钥，计算$Y=xG$作为公钥。\
其中$G$是椭圆曲线群的生成元，$N$是椭圆曲线群的阶，是一个大素数。
$\text{Sign}:$\
生成随机数 $r \xleftarrow{R}[1,N-1]$ 作为临时私钥，计算承诺$R=rG$。\
计算$e=H(m,R,Y)$作为随机挑战。\
计算$s=r+e*x$。\
$\sigma=(R,s)$ 作为消息 $m$ 签名 。\
一定要注意：先计算承诺后计算随机挑战，承诺一定要作为哈希函数的输入。
$\text{Verify}:$\
验证 $sG\xlongequal{?}R+H(m,R,Y)Y$
分析一下，对每一个签名，签名者都生成一个随机的一次性私钥 $r$，然后计算出$r$ 的公钥 $R$，一般称它为承诺。接下来，我们用$m,R,Y$作为输入计算哈希值，有时候也可以用$m,R$作为输出，有一点很重要就是一定将$R$作为输入。最后使用私钥$x$进行签名，就是做到隐藏私钥无法恢复私钥，一定是用一次性私钥$r$加上随机挑战$e$乘以私钥$x$。$(R,s)$ 就是签名。
在实现schorr签名算法时一定要注意以下几个陷阱：
-
承诺重复使用 \
假设对两个消息$m_0,m_1$进行签名时，使用了同一个承诺$R$，那么根据签名算法我们得到
$$
\begin{aligned}
s_0=r+H(m_0,R,Y)x \
s_1=r+H(m_1,R,Y)x
\end{aligned}
$$
将上面两个等式相减得到，$x=\frac{s_0-s_1}{H(m_0,R,Y)-H(m_1,R,Y)}$，就能恢复出私钥，这样就不安全了。
-
随机挑战的生成未使用承诺作为输入
这种情况在计算$s$时，就变成了$s=r+H(m,Y)*x$，两边都乘以$G$得到$sG=R+H(m,Y)Y$，可以看出只要随机选择一个$s$，计算$R=sG-H(m,Y)Y$，于是$(R,s)$就是在不知道私钥的情况下伪造出来一个签名，也就是说，我们可以生成任意的 $s$ 值，然后根据这个值来计算 $R$ 值，只用到了$(m,Y)$的信息，就可以任意创建有效的数字签名，这样就不安全了。
我们发现，这个情况还是可以避免的，我们只需要稍微调整一些东西来打破这种攻击。但是在 Schnorr 签名安全性证明的论文中介绍了它的真正本质，也许能让调整理解起来更加容易自然。
可以尝试的思路是使得 $s$ 依赖于承诺 $R$，从而打破等式 $R=sG–H(m)Y$，就是在我们计算随机挑战时哈希函数的输入包含承诺 $R$，即 $s=r+H(m,R,Y)*x$。这就打破了伪造任意签名的攻击，因为给定一个随机的 $s$，找出一个 $R$ 使得 $R=sG–H(m,R,Y)Y$ 成立是很难的，因为 $R$ 要先参与哈希值的生成，除了暴力破解之外，没有更好的办法来找出合适的 $R$。
schnorr 签名有以下两个主要优点
所以在实现签名算法的时候，一定要深入理解算法本身，不能想当然去认为，否则会发生非常糟糕的事情。
schnorr 签名是基于群上离散对数困难问题来设计的，依赖于安全的伪随机函数、安全的 hash 函数
多签名-MultiSig
schnorr 的多签名方案，在这篇论文 (Simple Schnorr Multi-Signatures with Applications to Bitcoin) 中提出。顾名思义，多签名方案就是一组签名私钥 $(x_1,x_2, … , x_n)$ 共同为一条消息生成一个签名。在普通的签名方案（比如 Schnorr 和 ECDSA）中，最简单的多签名方案就是把每一个签名者（对给定的一条消息）的单签名串联起来 $s=(\sigma_1,\sigma_2,\dots,\sigma_n)$ ，比特币已经支持这种串联多签方案了，实际上还支持创建 $n$ 个参与者中任意 $t$ 个（$t$ 小于 $n$）即可花费资金的地址，但我们不在这里讨论这种阈值签名，本篇只讨论 $n$ 个参与者一致参与的情形，即 $n$-$n$ 形式的多签。
虽然串联多签是一种正确的多签名方案，但是它有一些严重的缺陷：在 $n$-$n$ 的多签名方案中，签名的大小是普通单签名的 $n$ 倍，而且它要把 $n$ 个签名和公钥都暴露在链上，同样验证多签名也是验证单签名的时间的 $n$ 倍。它没有隐私特性，因为所有的参与者都是公开参与，用来验证签名。
schnorr 多签名方案就能很好的解决这些问题，无论签名的参与者有多少个，都只产生一个签名，且该签名与常规的 schnorr 单签名没有形式上的区别。此外，它还支持密钥聚合，所以签名私钥都可以保持隐私。具体来说，如果有 $n$ 个签名者 $Y_1,Y_2,\dots,Y_n$，要签名的消息记为 $m$，那么多签方案可以生成一个 schnorr 签名 (R, s)，该签名对应的验证公钥是 $Y=agg(Y_1,Y_2,\dots,Y_n)$ 聚合公钥，这让多签名的输出与标准的输出看起来没有分别，一模一样。
未完待续
