Tree Signatures
We present an efficient implementation of multisig with enhanced privacy, using a technique called tree signature. In contrast with the original tree signature¹, our implementation does not require any changes to the Bitcoin protocol.
Tree Signatures
In a standard M-of-N multisig, M signatures are needed to move funds. All N public keys have to be exposed on the blockchain. This quickly bloats Script size when N is big, for example, in a 1-of-100 multisig.
To solve this issue, tree signature organizes keys in a Merkle tree. Each leaf represents a specific combination of M keys of N. There are C(M, N)² leaves in total. In the degenerate case where M is 1, there are N leaves and each leaf is simply a unique key.
Tree signature brings several salient benefits over standard multisig, especially when the number of combinations M-of-N is large.
- Scalable: Script size scales at log(C(M, N)), as only the chosen branch and its merkle path are needed, instead of all public keys.
- Private: Only the public keys used in signing are published on chain, all others are hidden.
An example implementation when M = 3 is shown below.
Advanced Usage
Subset of M-of-N
A straightforward way to extend a standard tree signature is choosing an arbitrary strict subset of M-of-N key combinations as leaves, instead of all M-of-N combinations. For example, in a 2-of-3 scheme, (key1, key2) and (key2, key3) are included, but (key1, key3) is not. This offers more flexibility than a standard multisig.
Composability
We can even merge multiple signature trees into a single tree, which can be unlocked by signatures from keys in any leaf in the original subtrees.
[1] Pieter Wuille, Tree Signatures, 2015
[2] C(M, N) is N choose M.
