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.

A Merkle Tree and a Merkle Path

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.

Tree Signature Contract

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.

Merge Two Signature Trees

[1] Pieter Wuille, Tree Signatures, 2015

[2] C(M, N) is N choose M.

--

--

--

sCrypt Inc (https://scrypt.io) is a company with a mission to provide integrated on-chain smart contracting solutions using the original BitCoin Protocol on BSV

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Progress Report 2 September 2019

AMA by Tony Tao, Founder of X-Order

MILLET Token white paper

Diamond in the Rough: An Interview with Apeiron CTO Gem Ng

Dvision Network BSC bridge runs with Ankr Nodes

Permissioned Blockchains: uncoupling themselves from real change

Corda reimagined...

ErgoPad — BlitzTCG Partnership

Join the Talent Revolution @ Bondex !

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
sCrypt

sCrypt

sCrypt Inc (https://scrypt.io) is a company with a mission to provide integrated on-chain smart contracting solutions using the original BitCoin Protocol on BSV

More from Medium

Bitcoin Transactions

An Introduction to “White Paper 42” — Secret Value Distribution

Re: Moxie on Web3

STASIS Opens Corporate Onboarding