This is a BIP I made that specifies how Multisig outputs should be created when Taproot is used. It also demonstrates how to spend those outputs. This BIP gives guidance to implement Multisig using Taproot with script paths to provide maximum privacy. Multisig Taproot addresses are created almost the same way as Native Segwit addresses, except with a different derivation path. I have not seen any previous official guidelines that attempt to explain how to create Multsig outputs properly.
If it is desired for MuSig[2] to be used in place of Multisig, then I might revise this BIP to be “Standard” and create BIPs named something like “Musig signatures”, “opcodes for Musig signatures”, etc.
<pre>
BIP: notatether-multisigtaproot
Layer: Applications
Title: Implementing Multisig Using Taproot
Author: Ali Sherief <ali@notatether.com>
Comments-Summary: No comments yet.
Comments-URI: https://github.com/ZenulAbidin/bips/wiki/Comments:BIP-notatether-multisigtaproot
Status: Draft
Type: Informational
License: BSD-2-Clause
Created: 2022-08-19
Requires: 341, 342
</pre>
== 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 ≥ 6'', 3-of-''n'' for ''n ≥ 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 > 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 > 1.</ref>
The following Python 3.8 code an be used to calculate transaction sizes for ''K > 0'', ''N > 0'', and ''N ≥ 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.
