From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp4.osuosl.org (smtp4.osuosl.org [140.211.166.137]) by lists.linuxfoundation.org (Postfix) with ESMTP id 852CFC002D for ; 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 ; 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 ; 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 ; 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 Reply-To: Ali Sherief 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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'''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.: # 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.'''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. =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'''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.. 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 p1] OP_CHECKSIG [PubKey p2] OP_CHECKSIGADD ... [PubKey pK<= /sub>] OP_CHECKSIGADD OP_[K] OP_NUMEQUAL"'''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. Where the list p1 ... pK 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'''''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., 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= K] [Signature sK-1] ... [Signature s0]" Where the list s1 ... sK are the Schnorr signatures c= orresponding to the public keys p1 ... pK. 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'''''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.. # 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''.'''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. The following Python 3.8 code an be used to calculate transaction sizes for= ''K > 0'', ''N > 0'', and ''N ≥ K'': >>> import math >>> txsize =3D lambda n,k : 32*math.ceil(math.log2(math.comb(n, k))) + 33*k= + 35 >>> txsize(1,1) 68 # ... =3D=3D Rationale =3D=3D =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