# 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, as only the chosen branch and its merkle path are needed, instead of all public keys.*log(C(M, N))***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

*.*