树签名，打了鸡血的多重签名
每晚八点，我们在社区分享知识，等你。
NervosFans 微信公号：Nervosfans
入群请加乐乐微信：sensus113 美果大冰微信：xj73226
备注入群，谢谢！
Viewer discretion is advised.
介绍
考虑Alpha侧链中纳入哪些共识改进时，Blockstream开发者添加了一些比特币中曾经有过的简单操作码。 其中一个是OP_CAT，用来连接两个堆栈变量。
这次在脚本中并未考虑MAST（抽象语法Merkle树）。这个想法不算是新概念，但一直没在比特币中实施。简言之，MAST将脚本条件重新排列成树状，仅披露花费人实际用到的那部分（条件）。如此，允许大型复杂脚本，但是需要对脚本语言进行深度重新设计。
Alpha发布之后，开发者意识到由于添加了OP_CAT，Alpha的脚本语言可以实现简单形式的Merkle树验证。 因此，可以模拟MAST子集，而无需对共识规则进行任何更改。 这也使得一些非常大的多重签名构建在成本上非常有优势（成本优势就执行的操作码和链上的大小而言）。
以下为技术、实施细节等。
技术细节
假设，来创建一个1/11多重签名（11个已知公钥）。 先计算出公钥SHA256哈希值，后置于Merkle树中。 下图中，除1之外，所有符号都表示32字节哈希值。无右分叉时，1用作简单常量。
使用Alpha侧链脚本，可以构建出一个将公钥、签名和Merkle路径作为输入的脚本。验证时，使用Merkle路径证明公钥存在于在R根树中，且签名与该公钥相符。
脚本长这样：
8 PICK SHA256 (SWAP IF SWAP ENDIF CATSHA256)*4 EQUALVERIFY CHECKSIG
注：内部6个操作重复4次：树中的每一层一次。
要了解其工作原理，请按照下面的输入执行步骤。表示的是使用第10个密钥（哈希值为K10）的签名。 最后8个条目构成Merkle路径。Merkle树中的每一层，从下到上，都包含与运行哈希组合的条目，加上0或1，表明是左节点还是右节点。
扩展
上文给出了使用Alpha脚本实现1/11多重签名的例子。但是，比特币脚本早就可以实现1/11多重签名了。
该方法的优点是对数式扩展。 有效公钥数量加倍的同时，交易只添加一个40字节常量，且（昂贵的）CHECKSIG数量保持不变。相比之下，在比特币中添加一个公钥就已经增加34个字节了。
由于脚本的操作计数限制，理论上，树签名适用的多重签名范围在1至4294967296间，但是40多亿个签名的时候，树会变得非常大。 一般来说，1到100万这个范围是没问题的。
好比，1/250000方案中需要886字节的Alpha脚本。放在比特币脚本中，大小应该是886*9000 字节。
蜜罐（Honeypots）
能用到这么大型多重签名构造的情形（之一）是蜜罐。好比，Bob运行着一个有10000个服务器的群集，想在每个服务器上留点BTC，希望有攻击者过来盗币，看看集群的安全到底怎样。
再假设，Bob最多愿意丢10 BTC，且需要在每个服务器上单独放个比特币钱包，那么每台机器上的BTC数量就是1 mBTC。
虽说是10BTC分给如此大范围的多重签名脚本，但是每台机器上留下一个公钥即可。 由于所有公钥仍然是独立的，且签名会显示具体使用了哪个密钥，也就是说Bob仍然可以检测到哪台计算机受到了破坏。
上Schnorr
其实还有很多其他大型多重签名构造的用例，不止1/N，还有N/M的。
下面有请Schnorr签名。
树签名可以与Schnorr签名相结合，或者确切的说是与Schnorr签名的一个非常有趣的属性相结合，搞出来一套强技能。好比，一条消息（交易）有许多签名，则可以把签名“加”在一起，获得公钥“总和”的签名。
啥意思呢？ 好比有个3/3多重签名脚本，但是我们把这仨公钥加一块求和，用作普通CHECKSIG的1/1公钥。也就是说，签名者可以单独签署支出交易，然后把他们的签名加在一起，生成公钥总和可验证的签名（和）。
换言之，就区块链来而言，即便是M/M的Schnorr签名，也被简化为1/1了。 这里有个不太方便的地方，就是需要签两轮，因为参与人需要先就签署的随机数达成一致。
现在看明白怎么结合了么。 Merkle树密钥支持大型1/N。
Schnorr签名支持大型M/M。 就是说，若将花费条件写为1/（M-of M的N个种），则可构建一个由Schnorr组合公钥组成的Merkle树。 Merkle树中的每一片叶子都是一组组员全员必须签名的公钥。
例如：密钥A、B、C、D、E的4/5多重签名可写为：
这是个有5片叶子的Merkle树，每片叶子包含4个公钥（之和）。 Alpha中，这波操作需要286个脚本字节；比特币中，4/5的多重签名需要490个字节。
另外，注意，这个方法始终只需一次CHECKSIG操作。比特币脚本中，每个签名者都需要一次CHECKSIG， 好比M/N方案中，需要M个签名，相应的需要M次CHECKSIG。
一通比：
一般门限树
这种叶子代表公钥组合的Merkle数签名方案，其实不局限在M/N。总结起来，任何少量公钥组合中需要组成员全部签名的情形下，均适用。
有一种简单的语言被专门设计来描述公钥组合这种条件，具体为：
十六进制格式的公钥，需要该公钥的签名。
或（a，b，c，...）中a，b，c......为其他描述，要求满足其中一个条件。
且（a，b，c，...）中a，b，c...... 为其他描述，要求满足所有条件。
门限（n，a，b，c，...）中n为数字，a，b，c ......为其他描述，要满足n个条件。
这种语言可以很容易地表达诸如“A或B签名，或C、D和E中两人签名”的条件。
属性
Greg Maxwell列出了该签名方案几（5）个有趣的属性。
1. 问责制：OP_CHECKMULTISIG和树签名允许所有参与者知晓签名人具体是谁。
2. 可组合性：假设两个参与者都要求根据复杂描述签名，能否构建出其中一个签名的描述，并同时拥有知道接下来如何处理的软件？ 树签名在这一点上非常出众。
3. 效率：树签名交易大小及验证性能始终优于OP_CHECKMULTISIG。 但是，签名时间被拉长了。
4. 可用性：树签名要签2轮，因为要先拿到Schnorr签名的随机数。
5. 隐私：树签名中的参与者及其编号更易隐藏，因为添加假人的成本非常低。
实施
支持树签名的Alpha钱包补丁见：https://github.com/ElementsProject/elements/pull/48
结论
对脚本语言稍微一动就能带来意想不到的惊喜。将公钥的Merkle树与Schnorr签名相结合，竟能有效支持大型M/N 多重签名。
厉害了也是，虽说没太看懂吧。。。
Tree Signatureswww.blockstream.com
