Date: Sat, 20 Aug 2022 13:49:05 +0000
To: bitcoin-dev@lists.linuxfoundation.org
From: Ali Sherief <ali@notatether.com>
Reply-To: Ali Sherief <ali@notatether.com>
Message-ID: <20220820134850.ofvz7225zwcyffit@artanis>
Feedback-ID: 34210769:user:proton
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Cc: luke_bipeditor@dashjr.org
Subject: [bitcoin-dev] [BIP] Implementing Multisig Using Taproot
Precedence: list

Greetings list.

Following the discussions I made about BIP322 delegation on this mailing li=
st and in other places, I have decided that that delegation depends on a ve=
ry 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 pe=
ople know how to do it using script paths. BIP342 briefly touches on the su=
bject but leaves it open. So I wrote a BIP to plug this hole, that precisel=
y follows the guidelines hinted by BIPs 341 and 342, for creating and spend=
ing 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 shou=
ld 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 desir=
eable.

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

--------

=3D=3D Summary =3D=3D

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

=3D=3D Copyright =3D=3D

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

=3D=3D Abstract =3D=3D

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

=3D=3D Motivation =3D=3D

OP_CHECKMULTISIG has the disadvantage of revealing all co-signer public key=
s involved in a transaction. This compromises the privacy of those signers.=
 Additionally, this construct is not compatible with Taproot because OP_CHE=
CKMULTISIG 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 kno=
w how to construct Multisig Taproot outputs.

=3D=3D Design =3D=3D

Taproot gives us three different options for implementing Multisig, each wi=
th their own advantages and disadvantages<ref>'''Multisig implementation op=
tions reference''' The options were originally enumerated in [https://jimmy=
song.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 functi=
onally 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 t=
he 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 no=
t revealing any original public keys all together, it is a cumbersome proce=
ss 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. Ther=
e is the problem of who will be the trustee of the MuSigs themselves, as op=
posed to just the delegated UTXOs. Also, There is no BIP that implements Mu=
Sig, to the author's knowledge.</ref>

=3D=3D Specification =3D=3D

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.

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

All of the participating TapScripts must be collected together at construct=
ion-time. This implies that all signers must know each other beforehand<ref=
>'''Why should all signers know each other beforehand?''' Knowing all possi=
ble signers of a multisignature is required for many instances of delegatio=
n, so that an unknown party cannot insert a rogue signature at spending-tim=
e.</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</s=
ub>] 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 consider=
s a final stack of truthy values such as 1 as the script succeeding, and li=
kewise 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 combinat=
ion 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 pa=
rticipating in the TapLeaf.

And returns as the outputs:
* The scriptPubKey, including the hash of the generated withness program an=
d 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(0x0250929b74c1a04954=
b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0) + p*G''<ref>'''Why is an =
arbitrary public key used for signing and spending?''' All possible combina=
tions of multisignature spends are already enumerated in the script path, s=
o the internal public key is not only redundant, but a security hazard sinc=
e it must be specified. Values that will make Taproot validation fail canno=
t be used. BIP341 advises that in such cases, an internal public key with u=
nknown discrete logarithm should be used.</ref>, where ''G'' is the secp256=
k1 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 ap=
pend it to ''script_tree''.
# Return the result of ''taproot_output_script(internal_pubkey, script_tree=
)''.


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

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 ta=
ken by the Multisig Construction algorithm
* An integer value ''j'', greater than 0 and less than ''m'', that indicate=
s 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 c=
orresponding 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 in=
terpreter 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 Con=
struction algorithm.

Algorithm steps:
# Generate a random private key ''p'', in the range ''[0, n-1]''.
# Set the internal key ''internal_pubkey'' to ''lift_x(0x0250929b74c1a04954=
b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0) + p*G''<ref>'''Why is an =
arbitrary public key used for signing and spending?''' All possible combina=
tions 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 unk=
nown discrete logarithm should be used.</ref>.
# Set the internal key ''internal_pubkey'' to ''lift_x(0x0250929b74c1a04954=
b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0) + p*G'', where ''G'' is t=
he 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 ap=
pend it to ''script_tree''.
# Return the result of ''taproot_sign_script(internal_pubkey, script_tree, =
j, inputs)''.

=3D=3D Notes =3D=3D

[[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 numb=
er of TapLeaves can similarly be calculated, it is possible to derive a for=
mula 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)))'', wher=
e ''nCr'' computes the binomial coefficient of ''N'' and ''K''.
* Therefore, the size of the witness inside the output is ''32*ceil(log2(nC=
r(N,K))) + 33*K + 35''. A table of output sizes is provided for the first f=
ew 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 ou=
tput, and K-of-N Multisig Tapscripts with ''K &gt; 1'' and progressively in=
creasing to ''N-1'' have increasingly larger sizes. Where the K-of-N combin=
ation has a smaller size than the equivalent N-of-N combination, it is deem=
ed to be cost-efficient. Hence, since 2 cosigners out of a maximum of 6 mak=
es a transaction size smaller than 6-of-6, 2-of-6 multisig is the largest c=
ost-effective combination for ''N =3D 6''. If the data is extended, it can =
similary be proven that 3-of-9 multisig is the largest cost-effective combi=
nation for ''N =3D 9''.<ref>'''Cost-effective delegations''' Several delega=
tion 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=3D"python">
>>> import math
>>> txsize =3D lambda n,k : 32*math.ceil(math.log2(math.comb(n, k))) + 33*k=
 + 35
>>> txsize(1,1)
68
# ...
</source>


=3D=3D Rationale =3D=3D

<references />

=3D=3D Acknowledgements =3D=3D

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

--------

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

- Ali