Since I mailed the original scheme, some people have suggested to me that this delegation scheme can be written in TapScript, to avoid revealing the unspent public keys. I think that is a good idea.
Here is a very helpful slideshow about implementing Multisig scripts in Taproot 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 approach 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, footnote 5, which itself has nearly all of the properties of the original CHECKMULTISIG opcode[2]. In other words, it won't hide the non-signing public keys (the TapScript is literally "<PubKey 1> OP_CHECKSIG ... <PubKey N> OP_CHECKSIGADD OP_<N> OP_NUMEQUAL", so it doesn't solve the privacy problem. That leaves Multi-leaf k-of-k multisig. Now to my understanding, in every TapLeaf/Branch, there is going to be a K-of-K TapScript similar to the one constructed 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 of 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 here though, decreasing the raw transaction size of 'to_sign' is a net positive for space reasons). In other words, every TapScript is just <PubKey> OP_CHECKSIG OP_1 OP_NUMEQUAL, which can be simplified to just <PubKey> 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 requirement, 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 envision uses for delegation beyond BIP 322 anyway. At this point, the witness stack of 'to_sign' will have one of these TapScripts, and an appropriately constructed BIP 341 control block. Obviously 'to_spend''s output scriptPubKey will push the SHA256 hash of the witness program. 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 transaction still has to be verified, but now Address can be empty since the public 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 addresses). - No new opcodes are introduced, and no existing ones are redefined so no soft-forks are necessary. Advantages for all applications of this BIP : - Only the delegatee who actually signs the message has a revealed public key, 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 replaced 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 would defeat the whole purpose of signing by making it vulnerable to the aforementioned "signature fraud"]. My grasp on Taproot constructs is not 100%. So feel free to point out any errors 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_ref-5-0 On Tue Aug 16 04:38:47 UTC 2022, a...@notatether.com wrote: >(Note: I'm going to stick with this thread for all proposals for BIP322 >polishing, not just delegation - unless the subject matter changes radically >as other people discuss it.) > >Instead of the admittingly complicated scheme using transactions, I've created >one that utilizes multisig to make the possible delegatees known at signing >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 about 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 scriptPubKeys* >[sic] for privacy purposes. > >*Here, I use P2WPKH addresses, under the assumption that the delegatees are >people. If the delegatees are just some automated scripts or processes [as was >mentioned in the BIP], then this scheme is equally valid with P2WSH >multisignatures 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 P2WPKH >multisig. N is the number of people you want to be able to create the >signature, and their respective pubkeys are included in the script. >-- In this way the possible delegatees are fixed at signature creation time >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 <pub1> <pub2> >... <pubn> 1 <a-signature> 0 >-- The signature is generated as if it were for a real P2WPKH-multisig >transaction. [the zero at the end is due to a bug in OP_CHECKMULTISIG that >pops 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 sign >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 keys of >Alice and Bob are already in the signature]. Required, to avoid signature >fraud. >- The Address field is not used when delegating, so the engine can actually >print which (compressed) public key it is signed against - i.e. the address >verification is provable, as opposed to reactive Legacy signatures. >-- Additionally, they will all be Segwit Bech32 addresses so it can just >derive and print the corresponding bc1 address instead. >- There is no opcode or new algorithm introduced, so no soft-fork is required. > >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 >non-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 >opinion about this scheme will clarify a lot of things about this problem. > >- Ali _______________________________________________ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
