From: Ali Sherief <ali@notatether•com>
To: bitcoin-dev@lists•linuxfoundation.org
Subject: Re: [bitcoin-dev] A method for BIP322 signing delegation
Date: Fri, 19 Aug 2022 06:23:38 +0000 [thread overview]
Message-ID: <20220819062332.ua6kwrx5a36kw7zm@artanis> (raw)
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, ali@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
next reply other threads:[~2022-08-19 6:23 UTC|newest]
Thread overview: 4+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-08-19 6:23 Ali Sherief [this message]
-- strict thread matches above, loose matches on Subject: below --
2022-08-22 7:56 Ali Sherief
2022-08-16 4:38 Ali Sherief
2022-08-14 4:25 Ali Sherief
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20220819062332.ua6kwrx5a36kw7zm@artanis \
--to=ali@notatether$(echo .)com \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox