From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.osuosl.org (smtp1.osuosl.org [140.211.166.138]) by lists.linuxfoundation.org (Postfix) with ESMTP id 4E952C002D for ; Fri, 19 Aug 2022 06:23:50 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp1.osuosl.org (Postfix) with ESMTP id 9F3AF8134E for ; Fri, 19 Aug 2022 06:23:49 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org 9F3AF8134E Authentication-Results: smtp1.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=a4XpbT/U X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -2.1 X-Spam-Level: X-Spam-Status: No, score=-2.1 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, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no Received: from smtp1.osuosl.org ([127.0.0.1]) by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id EOiZb_k9QPFN for ; Fri, 19 Aug 2022 06:23:47 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.8.0 DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org 1CA668133A Received: from mail-4018.proton.ch (mail-4018.proton.ch [185.70.40.18]) by smtp1.osuosl.org (Postfix) with ESMTPS id 1CA668133A for ; Fri, 19 Aug 2022 06:23:47 +0000 (UTC) Date: Fri, 19 Aug 2022 06:23:38 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=notatether.com; s=protonmail; t=1660890224; x=1661149424; bh=nC281eVjas1idA2BRZ7iXzjNUqn5t5l571wD8y7mzvc=; h=Date:To:From:Reply-To:Subject:Message-ID:Feedback-ID:From:To:Cc: Date:Subject:Reply-To:Feedback-ID:Message-ID; b=a4XpbT/U0CQ6G7zEtzgk5QtF75mQk79R4igSu86TtGKT2jzpRymQ4xZSMLrRrHbdo bblRgR/XAHdV9wN0hftTwZUZUSSSdKO9GEdU1D0Wxi3chgUubS1+ZaXdQN2SPt8yFt axXKkjPjUN5U1PeeJP+0q1FoqEh05c3BoveO7IdmFZTsrUciDbsBT+SDvUJDqtbSWE 0lk6Mn+yIrfKQijMcaA7iD4B/OWFT3XCLNZzxt/jvCuLkEZkPGtKv5ldASc9M1mlnh 3rv5GYV8bQZVyNjyoXA20iEuhWtTSiWYGN2zdfR4zaUwffzJV4LbgAQNHDa/mk0+6I ZKWbors0ytIzA== To: bitcoin-dev@lists.linuxfoundation.org From: Ali Sherief Reply-To: Ali Sherief Message-ID: <20220819062332.ua6kwrx5a36kw7zm@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: Fri, 19 Aug 2022 08:55:10 +0000 Subject: Re: [bitcoin-dev] A method for BIP322 signing delegation 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: Fri, 19 Aug 2022 06:23:50 -0000 Since I mailed the original scheme, some people have suggested to me that t= his delegation scheme can be written in TapScript, to avoid revealing the u= nspent public keys. I think that is a good idea. Here is a very helpful slideshow about implementing Multisig scripts in Tap= root by Jimmy Song[1] - specifically, I have looked into "Single leaf k-of-= n multisig" and "Multi-leaf k-of-k multisig". I have not considered the app= roach with MuSig, considering there is not even a BIP for that. To my understanding, Single leaf k-of-n multisig is functionally identical = to "Using a single OP_CHECKSIGADD-based script" described in BIP 0342, foot= note 5, which itself has nearly all of the properties of the original CHECK= MULTISIG opcode[2]. In other words, it won't hide the non-signing public ke= ys (the TapScript is literally " OP_CHECKSIG ... OP_CH= ECKSIGADD OP_ OP_NUMEQUAL", so it doesn't solve the privacy problem. That leaves Multi-leaf k-of-k multisig. Now to my understanding, in every T= apLeaf/Branch, there is going to be a K-of-K TapScript similar to the one c= onstructed above. In each leaf there will be a combination of K public keys= , so the number of leaves is going to be equal to nCr(n,k). No wonder why BIP 342 says that it's only cost-effective for small values o= f k, because the number of leaves and thus the transaction size swells as k= increases. Fortuantely, for the purposes of delegation, K will always be 1, because we= only utilize 1-n multisig signatures as per my previous message. Thus the = fee rate will be economical for all values of N i.e. number of delegatees. = This enables this scheme to have a wider use case than just BIP322 (even he= re though, decreasing the raw transaction size of 'to_sign' is a net positi= ve for space reasons). In other words, every TapScript is just OP_CHECKSIG OP_1 OP_NUMEQU= AL, which can be simplified to just OP_CHECKSIG since OP_CHECKSIG = failure in a TapScript returns the empty vector (false) on failure, and 1 (= true) on success. I wrote the longer script merely because it's consistent = with the script format in [2], but since it's by no means a standardness re= quirement, we can save 2*N bytes in the entire transaction. So, for small numbers of delegates, these savings are not very eye-watering= , but if fees become larger then every byte will matter. After all, I envis= ion uses for delegation beyond BIP 322 anyway. At this point, the witness stack of 'to_sign' will have one of these TapScr= ipts, and an appropriately constructed BIP 341 control block. Obviously 'to= _spend''s output scriptPubKey will push the SHA256 hash of the witness prog= ram. Use cases: - BIP 322 (obviously) - Any L2 protocol where participants' funds must be delegated to a comittee= e.g. LN channels - which, in fact, are still using OP_CHECKMULTISIG. -- Where such a protocol requires the joint consensus of all participants, = such as an LN channel closing gracefully, K can be modified appropriately, = but this is beyond the scope of this scheme. Make a BOLT or the appropriate= standard proposal if this affects your L2 network. Advantages where they are relevant for BIP 322 : - Signature fraud is still impossible to carry out (the entire to_sign tran= saction still has to be verified, but now Address can be empty since the pu= blic key is in the control block which is in the 'to_sign' witness, and the= spent TapScript is also in the 'to_sign' witness). - Delegated signers still use standard address type (Bech32m Taproot addres= ses). - No new opcodes are introduced, and no existing ones are redefined so no s= oft-forks are necessary. Advantages for all applications of this BIP : - Only the delegatee who actually signs the message has a revealed public k= ey, the others' are hidden - a major privacy advantage. - Signers must be determined beforehand. Jimmy Song actually lists this as = a disadvantage, but I disagree. For L2 delegation, it is necessary to know = the other parties to avoid a MITM attack where one of the signers is replac= ed by a rogue signer - through non-cryptographic methods of course (e.g. a = computer hack). Disadvantages : - Taproot is not widely deployed in applications yet? - I can't think of any others, unless you consider the signer's public key = being revealed a disadvantage [I wouldn't, because if it were hidden, it wo= uld defeat the whole purpose of signing by making it vulnerable to the afor= ementioned "signature fraud"]. My grasp on Taproot constructs is not 100%. So feel free to point out any e= rrors in my reasoning for this scheme if you spot any. - Ali [1] - https://jimmysong.github.io/taproot-multisig [2] - https://github.com/bitcoin/bips/blob/master/bip-0342.mediawiki#cite_r= ef-5-0 On Tue Aug 16 04:38:47 UTC 2022, ali@notatether.com wrote: >(Note: I'm going to stick with this thread for all proposals for BIP322 po= lishing, not just delegation - unless the subject matter changes radically = as other people discuss it.) > >Instead of the admittingly complicated scheme using transactions, I've cre= ated one that utilizes multisig to make the possible delegatees known at si= gning time. I had a discussion with vjudeu, garlonicon, and aliashraf about= this over the past week or so, and while we did not reach a consensus abou= t the solution to use, I feel that this scheme requires the least amount of= modifications to BIP322 draft. > >The problem being solved is how to delegate signatures to other scriptPubK= eys* [sic] for privacy purposes. > >*Here, I use P2WPKH addresses, under the assumption that the delegatees ar= e people. If the delegatees are just some automated scripts or processes [a= s was mentioned in the BIP], then this scheme is equally valid with P2WSH m= ultisignatures with appropriately constructed scriptPubKeys. > >What's about to follow was copied almost word-for-word from my forum post = with extraneous paragraphs removed: > >--- > >It is extremely simple and doesn't require any additional transactions: > >- Replace the message challenge of "to_spend" with a 1-of-N standard P2WPK= H multisig. N is the number of people you want to be able to create the sig= nature, and their respective pubkeys are included in the script. >-- In this way the possible delegatees are fixed at signature creation tim= e and cannot be extended by creating more transactions. >- Replace the challenge solution in "to_sign" (it's the input that spends = the output we made in "to_spend") with a witness stack containing: n = ... 1 0 >-- The signature is generated as if it were for a real P2WPKH-multisig tra= nsaction. [the zero at the end is due to a bug in OP_CHECKMULTISIG that pop= s an extra element]. > >appendix - don't mix up this delegation and Full with UTXOs together - it = increases the numebr of permutations that implementations have to verify. > >Pros: > >- No recursive transactions. >- If Alice and Bob are the two delegates of a signature (and one of them s= ign it), Carol does not know any of the private keys or challenge solutions= and thus cannot claim the script was signed by her [besides the public key= s of Alice and Bob are already in the signature]. Required, to avoid signat= ure fraud. >- The Address field is not used when delegating, so the engine can actuall= y print which (compressed) public key it is signed against - i.e. the addre= ss verification is provable, as opposed to reactive Legacy signatures. >-- Additionally, they will all be Segwit Bech32 addresses so it can just d= erive and print the corresponding bc1 address instead. >- There is no opcode or new algorithm introduced, so no soft-fork is requi= red. > >Cons: > >- Everyone knows the public keys of the delegators, so there is no privacy= [then again, in light of the signature fraud problem, this is possibly a n= on-issue]. > >--- > >I'd like to hear everyone's opinions about this. > >I don't know who suggested the idea of delegation in the first place, but = CCing luke-jr because he participated in that Github discussion, so his opi= nion about this scheme will clarify a lot of things about this problem. > >- Ali