SF Bitcoin Devs Seminar: Key Tree Signatures

Pieter Wuille, Bitcoin Core Developer and Blockstream Co-Founder, spoke about Key Tree Signatures.

Bitcoin supports multisig transaction outputs, which require more than a single signature to unlock. These can be used for low-trust escrow, two-factor security (signatures by two devices) and funds with shared control.

However, Bitcoin’s multisig support is based on OP_CHECKMULTISIG internally, which has significant limitations. For one, it only supports up to 15 keys, and has a high verification cost to the network.

If we restrict the problem to 1-of-N multisig (as opposed to K-of-N), all we need is to be able to cheaply prove that a particular given key is part of a set that is known in advance, plus verify a signature by that key. For the first part, we could use a Merkle tree, if we could implement Merkle branch verification inside script. This is not possible in Bitcoin because it needs OP_CAT which was disabled years ago. In Elements Alpha, a first demo sidechain by Blockstream, this opcode was reenabled, making cheap 1-of-N possible.

Alpha has another change, namely using Schnorr signatures rather than ECDSA signatures. Schnorr signatures support native K-of-K multisig, with the same efficiency as a single 1-of-1 key.

We can combine these two changes to support K-of-N: build a Merkle tree where every leaf is a Schnorr combination of a set of K of the N keys. This results in signatures that are at worst half the size as OP_CHECKMULTISIG ones, and are far faster to verify,

We can even go further, and introduce a small language for describing sets of permissible keys for signing, as the approach above is not limited to just K-of-N.

For more information see: https://blockstream.com/2015/08/24/treesignatures/