diff options
| author | Ali Sherief <ali@notatether.com> | 2022-08-20 13:49:05 +0000 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2022-08-20 13:49:19 +0000 |
| commit | 52314d117e131a41d8185412dce812d234c02cc4 (patch) | |
| tree | 0d6e05a425a33616c83813524bad384c52b2bf9a | |
| parent | ef11d5acb0a3a411f621e77e3e57ba4e9fe42b3e (diff) | |
| download | pi-bitcoindev-52314d117e131a41d8185412dce812d234c02cc4.tar.gz pi-bitcoindev-52314d117e131a41d8185412dce812d234c02cc4.zip | |
[bitcoin-dev] [BIP] Implementing Multisig Using Taproot
| -rw-r--r-- | f5/5c33c21b8fcfd26ef9e7287bd5316fd14a4a85 | 336 |
1 files changed, 336 insertions, 0 deletions
diff --git a/f5/5c33c21b8fcfd26ef9e7287bd5316fd14a4a85 b/f5/5c33c21b8fcfd26ef9e7287bd5316fd14a4a85 new file mode 100644 index 000000000..8dbd4849d --- /dev/null +++ b/f5/5c33c21b8fcfd26ef9e7287bd5316fd14a4a85 @@ -0,0 +1,336 @@ +Return-Path: <ali@notatether.com> +Received: from smtp4.osuosl.org (smtp4.osuosl.org [140.211.166.137]) + by lists.linuxfoundation.org (Postfix) with ESMTP id 852CFC002D + for <bitcoin-dev@lists.linuxfoundation.org>; + Sat, 20 Aug 2022 13:49:19 +0000 (UTC) +Received: from localhost (localhost [127.0.0.1]) + by smtp4.osuosl.org (Postfix) with ESMTP id 4BB74417CF + for <bitcoin-dev@lists.linuxfoundation.org>; + Sat, 20 Aug 2022 13:49:19 +0000 (UTC) +DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 4BB74417CF +Authentication-Results: smtp4.osuosl.org; dkim=pass (2048-bit key, + unprotected) header.d=notatether.com header.i=@notatether.com + header.a=rsa-sha256 header.s=protonmail header.b=IZO6HPzQ +X-Virus-Scanned: amavisd-new at osuosl.org +X-Spam-Flag: NO +X-Spam-Score: -2.101 +X-Spam-Level: +X-Spam-Status: No, score=-2.101 tagged_above=-999 required=5 + tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, + DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_MSPIKE_H2=-0.001, + SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no +Received: from smtp4.osuosl.org ([127.0.0.1]) + by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) + with ESMTP id 1FQErtB_s8BD + for <bitcoin-dev@lists.linuxfoundation.org>; + Sat, 20 Aug 2022 13:49:16 +0000 (UTC) +X-Greylist: from auto-whitelisted by SQLgrey-1.8.0 +DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 32DDB417CD +Received: from mail-4317.proton.ch (mail-4317.proton.ch [185.70.43.17]) + by smtp4.osuosl.org (Postfix) with ESMTPS id 32DDB417CD + for <bitcoin-dev@lists.linuxfoundation.org>; + Sat, 20 Aug 2022 13:49:15 +0000 (UTC) +Date: Sat, 20 Aug 2022 13:49:05 +0000 +DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=notatether.com; + s=protonmail; t=1661003352; x=1661262552; + bh=yBzIb6byJFMeVKUeDagenbrQcWsSJEI6YmzoUAE9PUY=; + h=Date:To:From:Cc:Reply-To:Subject:Message-ID:Feedback-ID:From:To: + Cc:Date:Subject:Reply-To:Feedback-ID:Message-ID; + b=IZO6HPzQacEEYzfATxgDXVP6jHm8XERrKnQDphdxEJSMddHTRviSPiJ5xbPf2QbDl + 99pdsbE80PpzhoFXCxIgR0pZjDWv07WTn+fvSnN/tW+L9FahHt65jHZiJbd1CzjGMS + Kq9Ll9tu7iW3V47Clt07S/fMKvpoVJSVkHN9v2g/pys2CCbhPB361+PnWP8uG9Rzek + EPUcTvrYpwIkuHm0t28+uec81HAYHUwAASGcyre+7jUzINjVSLo9pjw1HITDyEvKqc + GS1M0CJIlktl+MWhde9vFYnT1e+qg4KzicWKhrvPdBYSZTYN7+AOigIl9cr4XeXpBZ + FzNxatrCT7yxw== +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 +X-Mailman-Approved-At: Sat, 20 Aug 2022 14:19:29 +0000 +Cc: luke_bipeditor@dashjr.org +Subject: [bitcoin-dev] [BIP] Implementing Multisig Using Taproot +X-BeenThere: bitcoin-dev@lists.linuxfoundation.org +X-Mailman-Version: 2.1.15 +Precedence: list +List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org> +List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, + <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe> +List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/> +List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org> +List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help> +List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, + <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe> +X-List-Received-Date: Sat, 20 Aug 2022 13:49:19 -0000 + +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 ≥ 6'', 3-of-''n'' for= + ''n ≥ 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 > 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 > 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=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 + + |