Schnorr 签名

为了简便起见这里都用大整数取模运算下的方式来说明签名、验证过程，签名算法也可以同样地在椭圆曲线上实现

签名及验证

Schnorr 签名的单一签名过程较为简单，它涉及到的函数只有哈希函数 $H$ 将消息映射为一个大整数，同时所有的运算在群 $G_p$ 下完成，$p$ 是一个大素数，$G_p$ 的生成元是 $g$

签名流程

Schnorr 签名方随机选取一个大整数 $x \in G_p$ 作为私钥，在群 $G_p$ 上运算 $y=g^x$ 作为它的公钥，同时签名方为消息 $m$ 进行签名

签名方选取随机数 $r \in G_p$，计算 $R = g^r$
签名方计算哈希值 $e = H(y||m)$
通过 $r$ 和 $h$，计算 $s=r+ex$
最后得到签名为 $\sigma = (R,s)$

这个过程表示为 $\sigma \leftarrow Sign(x,m,r,pp)$，$pp$ 是公开参数，包括群的相关信息以及哈希函数

签名验证

在签名验证方，它所具备的公开信息有签名方的公钥 $y=g^x$，签名消息 $m$ 以及签名 $\sigma=(R,s)$，因此验证方可以通过验证下列等式是否成立来验证签名的有效性
$$
g^s \overset{\text{?}}{=} R \cdot y^e
$$
在这个等式中，$e = H(y||m)$ 可以通过公开的参数来得到，将它展开，实际上是在验证
$$
g^{r+ex} \overset{\text{?}}{=} g^r \cdot (g^x)^e
$$
在正确的私钥和签名过程下，这个等式是必然成立的，如果签名私钥不对或签名运行过程有误，该等式无法成立

这个过程表示为 $\{0,1\} \leftarrow Verify(y,m,\theta,pp)$

签名聚合

签名聚合依赖于 Schnorr 签名的可加性，考虑两个签名者对同一条消息 $m$ 进行签名，得到

$$
\begin{split}
\sigma_1 \leftarrow Sign(x_1,m,r_1,pp) \\\
\sigma_2 \leftarrow Sign(x_2,m,r_2,pp)
\end{split}
$$

根据签名流程，$\sigma$ 实际上是两个数值 $\sigma = (g^r,s)$，所以有

$$
\begin{split}
(R_1,s_1) = (g^{r_1}, r_1+ex_1) \\\
(R_2,s_2) = (g^{r_2}, r_2+ex_2)
\end{split}
$$

对 $R$ 进行相乘，$s$ 进行相加，可以得到聚合签名，它在形式上为 $\sigma_{12} \leftarrow Sign((x_1+x_2),m,(r_1+r_2),pp)$，即下列等式

$$
\sigma_{12} = (g^{r_1+r_2},(r_1+r_2) + e(x_1+x_2))
$$

warning

这样的签名相加方式只是为了展示签名的可加性，以此来达到签名聚合的目的，实际上存在安全问题（密钥抵消攻击^[1]），不能在实际场景中使用。

基于这样的签名聚合方式，它可以被用于多签交易中，这可以使得多重签名锁定的脚本中不需要包含所有的公钥，进一步保证了交易的隐私性。并且也降低了签名的长度和所需要的参数，在实际的 P2TR 交易中降低了发送者的开销。

Taproot 地址

尽管在 Bitcoin 支付方式及地址类型中提到了 taproot 地址的生成、编码方式，但是没有具体涉及到 tweak 公钥的生成是如何实现的，这个公钥基于以下公式
$$
Q = P + tG
$$
其中，$Q$ 是 tweak 公钥，$P$ 是椭圆曲线上的公钥，$T=tG$ 代表的是脚本路径映射到椭圆曲线上的点

在这里，$t = TaggedHash(‘TapTweak’, P||merkleRoot)$，它对公钥和脚本构造形成的 MAST 根哈希值进行进一步的映射，得到一个小于 SECP256K1 曲线的阶的自然数 $t$，然后再将它乘以椭圆曲线的基点 $G$ 映射到椭圆曲线上，得到 $T=tG$

这个过程可以参考 Taproot 及 MuSig2 回顾^[4] 对地址生成过程的说明

最后这个 tweak 在进行编码后可以得到 taproot 地址，即主网上常见的 bc1p 开头的地址

默克尔抽象语法树

如 Bitcoin 支付方式及地址类型中所描述到的，Taproot 升级中将支付到地址哈希和支付到脚本两种方式整合到了一起

在 Taproot 中，这被称为私钥路径（Key Path）和脚本路径（Script Path），脚本路径中的脚本通过默克尔抽象语法树（Merklized Abstract Syntax Trees, MAST）来实现脚本哈希值的计算，这种方式使得用户只需要给出单一脚本路径上的代码就可以完成完整的验证。而这里要说明的 MAST 的根哈希值，就是 Taproot 地址生成中所需要的 $t$，它参与到 tweak 公钥的生成

在这里，考虑下面的脚本（也是大多数讲解 MAST 的文章引用的脚本，它来源于 What is a Bitcoin Merklized Abstract Syntax Tree (MAST)?^[5]）

OP_IF
	<Alice's pubkey> OP_CheckSig
OP_ELSE
	"3 months" OP_CSV OP_DROP
	2 <Bob's pubkey> <Charlie's pubkey> 2 OP_CHECKMULTISIG
OP_ENDIF

MAST 的一个思想是抽象语法树（Abstract Syntax Trees, AST），AST 通过树状结构来表示源代码，通过分支、函数调用来划分代码的各部分，例如上述脚本的 AST 可以构造为如下的方式

而 MAST 的另外一个思想则是是 Merkle 树，它以此将内容组织为一个二叉树，然后依次对子节点进行哈希运算，最终得到一个根节点哈希，如果要验证一个元素是否在一颗 Merkle 树中，只需要将这个元素和它沿途路径上的哈希值给出即可。根据这样的特性，Merkle 树也是一种密码累加器，成员证明过程在密码累加器中进行了简单的描述

结合这两种树状结构，如果以 AST 的方式来划分不同的代码片，然后放入到 Merkle 树的叶子节点的内容中，依次哈希就可以得到一个根哈希值（它就是上面公式中的 $t$）。最后，得到的 Merkle 树就是一个 MAST，在运行脚本代码的时候可以只给出一部分叶子节点上的脚本内容以及对应的成员证明即可（即沿途路径上的子节点哈希值）。

例如，最初脚本中的 MAST 可以构造为如下结构，Alice 可以使用签名脚本，并给出 Hash 2的值；或者由他的好友 Bob 和 Charlie 在三个月后给出第二个脚本，并且给出 Hash 1 的值就可以使用脚本