[bitcoin-dev] [BIP] Implementing Multisig Using Taproot

[Ali Sherief <ali@notatether.com>]

Greetings list.

Following the discussions I made about BIP322 delegation on this mailing list and in other places, I have decided that that delegation depends on a very similar problem that arises when writing contracts and commitments. That problem is how to implement private Multisig.

Of course, this can already be done using Taproot. But I doubt that many people know how to do it using script paths. BIP342 briefly touches on the subject but leaves it open. So I wrote a BIP to plug this hole, that precisely follows the guidelines hinted by BIPs 341 and 342, for creating and spending Multisig outputs.

I also managed to figure out the formula that BIP342 vaguely hinted at for figuring out "cost-effective multisignatures" (hint: it's not quadratic).

As far as I can tell, such a BIP hasn't been advanced before, so there should be no problem of "try working on the other BIP".

Use cases:

- Layer 2 protocols that use multisig (e.g. LN, Discrete Log Contracts)
- BIP322 message signatures, if it is decided that UTXO delegation is desireable.

I'm pasting the draft of the BIP below, with the metadata shaved off, but references are left intact. I haven't uploaded it to Github yet.

--------

== Summary ==

This document defines the proper way to construct Multisig outputs and spends that utilize the privacy provided by Taproot script paths.

== Copyright ==

This document is licensed under the 2-clause BSD license.

== Abstract ==

A Multisignature (also called Multisig) unspent transaction output (UTXO) attached to an address allows two or more parties to restrict the spending of the UTXO inside the address until a specified number of parties sign the output spending it. Multisig UTXOs are extremely useful for creating contracts, and is therefore used in many applications where delegation of funds to a committee is required, such as in Lightning Network channels, in DLCs (Discrete Log Contracts), and in other kinds of contracts.

== Motivation ==

OP_CHECKMULTISIG has the disadvantage of revealing all co-signer public keys involved in a transaction. This compromises the privacy of those signers. Additionally, this construct is not compatible with Taproot because OP_CHECKMULTISIG is disabled in TapScript, thus those applications are unable to make use of Pay-to-Taproot (P2TR) addresses.

Constructing a Multisig output on Taproot is technically possible, but its implementation has not been specified by any existing BIP, to the author's knowledge. Additionally, most developers of Bitcoin applications do not know how to construct Multisig Taproot outputs.

== Design ==

Taproot gives us three different options for implementing Multisig, each with their own advantages and disadvantages<ref>'''Multisig implementation options reference''' The options were originally enumerated in [https://jimmysong.github.io/taproot-multisig Jimmy Song's slideshow] in a more detailed manner.</ref>:
# Single-leaf with a TapScript implementing K-of-N Multisig. This is functionally equivalent to legacy OP_CHECKMULTISIG, and shares all its advantages and disadvantages. In particular, all public keys of signers are revealed in the TapScript embedded in the first element of the witness program, so the privacy advantages of Taproot are compromised.
# Multiple leaves, each with a TapScript implementing K-of-K Multisig.
# Multiple leaves, each with a TapScript implementing MuSig of K keys (i.e. aggregate of K public keys).

This document uses the second option for implementing Multisig, because it only reveals the public keys of those who sign the transaction.<ref>'''Why wasn't MuSig considered?''' Although MuSig provides even more privacy by not revealing any original public keys all together, it is a cumbersome process to create since K parties must be online not only at one point to create the aggregated keys, but also at another point to create a signature. There is the problem of who will be the trustee of the MuSigs themselves, as opposed to just the delegated UTXOs. Also, There is no BIP that implements MuSig, to the author's knowledge.</ref>

== Specification ==

Notations used here are specified in [[bip-0340.mediawiki#design|BIP340]].

''taproot_output_script'' and ''taproot_sign_script'' refers to the Python functions of [[bip-0341.mediawiki|BIP341]] with the same name.

=== Constructing K-of-N Multisig outputs ===

All of the participating TapScripts must be collected together at construction-time. This implies that all signers must know each other beforehand<ref>'''Why should all signers know each other beforehand?''' Knowing all possible signers of a multisignature is required for many instances of delegation, so that an unknown party cannot insert a rogue signature at spending-time.</ref>.

The algorithm takes as inputs:
* An integer value  ''m'', greater than 0
* An array ''scripts'' of ''m'' TapScripts as byte-arrays.
** The scripts must be written in the following format: "[PubKey p<sub>1</sub>] OP_CHECKSIG [PubKey p<sub>2</sub>] OP_CHECKSIGADD ... [PubKey p<sub>K</sub>] OP_CHECKSIGADD OP_[K] OP_NUMEQUAL"<ref>'''1-of-N Multisig TapScripts''', it is possible to save two bytes in each script by dropping "OP_[K] OP_NUMEQUAL" from the end of each script. Since OP_CHECKSIG will return 1 on success and the empty array on failure, and the script interpreter considers a final stack of truthy values such as 1 as the script succeeding, and likewise for falsy values such as the empty array, the additional OP_NUMEQUAL comparison and associated number push is redundant.</ref>
Where the list p<sub>1</sub> ... p<sub>K</sub> represents a unique combination of K public keys from the total set of N public keys. In this way, each TapScript is a K-of-K multisig, requiring the signatures of all parties participating in the TapLeaf.

And returns as the outputs:
* The scriptPubKey, including the hash of the generated withness program and the push bytes.

Algorithm steps:
# Generate a random private key ''p'', in the range ''[0, n-1]''.
# Set the internal key ''internal_pubkey'' to ''lift_x(0x0250929b74c1a04954b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0) + p*G''<ref>'''Why is an arbitrary public key used for signing and spending?''' All possible combinations of multisignature spends are already enumerated in the script path, so the internal public key is not only redundant, but a security hazard since it must be specified. Values that will make Taproot validation fail cannot be used. BIP341 advises that in such cases, an internal public key with unknown discrete logarithm should be used.</ref>, where ''G'' is the secp256k1 generator point.
# Set ''script_tree'' to the empty list.
# For each script (''i'' in the range ''[0,m-1]'', convert it into a tuple with first element a byte 0xc0 and second element the script itself, and append it to ''script_tree''.
# Return the result of ''taproot_output_script(internal_pubkey, script_tree)''.


=== Spending K-of-N Multisig outputs ===

Only one of the multisignature TapScripts will be spent in a K-of-N Taproot Multisig.

The algorithm takes as inputs:
* An integer value  ''m'', greater than 0
* An array ''scripts'' of ''m'' TapScripts as byte-arrays, in the format taken by the Multisig Construction algorithm
* An integer value ''j'', greater than 0 and less than ''m'', that indicates which multisignature TapScript will be used to spend the output.
* The witness stack ''inputs'' of the script ''scripts[i]'', as an array of byte-arrays.
** The witness stack must be written in the following format: "[Signature s<sub>K</sub>] [Signature s<sub>K-1</sub>] ... [Signature s<sub>0</sub>]"
Where the list s<sub>1</sub> ... s<sub>K</sub> are the Schnorr signatures corresponding to the public keys p<sub>1</sub> ... p<sub>K</sub>. Note that the list of signatures is coded in the reverse order, because the script interpreter will pop the left-most byte-array as the first stack element, the second-left-most byte array as the second stack element, and so on.

And returns as the outputs:
* The witness, that can spend the scriptPubKey returned by the Multisig Construction algorithm.

Algorithm steps:
# Generate a random private key ''p'', in the range ''[0, n-1]''.
# Set the internal key ''internal_pubkey'' to ''lift_x(0x0250929b74c1a04954b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0) + p*G''<ref>'''Why is an arbitrary public key used for signing and spending?''' All possible combinations of multisignature spends are already enumerated in the TapLeaves, so the internal public key is not only redundant, but a security hazard since it must be specified. Values that will make Taproot validation fail cannot be used. BIP341 advises that in such cases, an internal public key with unknown discrete logarithm should be used.</ref>.
# Set the internal key ''internal_pubkey'' to ''lift_x(0x0250929b74c1a04954b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0) + p*G'', where ''G'' is the secp256k1 generator point.
# Set ''script_tree'' to the empty list.
# For each script (''i'' in the range ''[0,m-1]'', convert it into a tuple with first element a byte 0xc0 and second element the script itself, and append it to ''script_tree''.
# Return the result of ''taproot_sign_script(internal_pubkey, script_tree, j, inputs)''.

== Notes ==

[[bip342.mediawiki|BIP342]] mentions that a complete TapBranch of ''k-of-k'' multisignature leaves are "only more cost effective for small values of ''k'' (1-of-''n'' for any ''n'', 2-of-''n'' for ''n &ge; 6'', 3-of-''n'' for ''n &ge; 9'', ...)". Since the scripts are all of fixed size, and the number of TapLeaves can similarly be calculated, it is possible to derive a formula for the relative size in (v)bytes of a spent Multisig Taproot output.
* The size of each script is ''33*K + 2''.
* The size of the control block is ''33 + 32 * ceil(log2(nCr(N,K)))'', where ''nCr'' computes the binomial coefficient of ''N'' and ''K''.
* Therefore, the size of the witness inside the output is ''32*ceil(log2(nCr(N,K))) + 33*K + 35''. A table of output sizes is provided for the first few values of N and K.

N,K,Size (vbytes)
1,1,68
2,1,100
2,2,101
3,1,132
3,2,165
3,3,134
4,1,132
4,2,197
4,3,198
4,4,167
5,1,164
5,2,229
5,3,262
5,4,263
5,5,200
6,1,164
6,2,229
6,3,294
6,4,295
6,5,296
6,6,233

The data shows that 1-of-N Multisig TapScripts have the smallest witness output, and K-of-N Multisig Tapscripts with ''K &gt; 1'' and progressively increasing to ''N-1'' have increasingly larger sizes. Where the K-of-N combination has a smaller size than the equivalent N-of-N combination, it is deemed to be cost-efficient. Hence, since 2 cosigners out of a maximum of 6 makes a transaction size smaller than 6-of-6, 2-of-6 multisig is the largest cost-effective combination for ''N = 6''. If the data is extended, it can similary be proven that 3-of-9 multisig is the largest cost-effective combination for ''N = 9''.<ref>'''Cost-effective delegations''' Several delegation schemes such as Lightning Network channels use only a combination of 1-of-N and N-of-N multisig transactions, with small N &gt; 1.</ref>

The following Python 3.8 code an be used to calculate transaction sizes for ''K &gt; 0'', ''N &gt; 0'', and ''N &ge; K'':

<source lang="python">
>>> import math
>>> txsize = lambda n,k : 32*math.ceil(math.log2(math.comb(n, k))) + 33*k + 35
>>> txsize(1,1)
68
# ...
</source>


== Rationale ==

<references />

== Acknowledgements ==

Thanks to garlonicon, vjudeu, and Ali Ashraf for providing feedback about multisignatures while this document was being written.

--------

I appreciate any comments about this, especially from the BIP editors.

- Ali