Date: Fri, 19 Aug 2022 06:23:38 +0000
To: bitcoin-dev@lists.linuxfoundation.org
From: Ali Sherief <ali@notatether.com>
Reply-To: Ali Sherief <ali@notatether.com>
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
Subject: Re: [bitcoin-dev] A method for BIP322 signing delegation
Precedence: list

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 "<PubKey 1> OP_CHECKSIG ... <PubKey N> OP_CH=
ECKSIGADD 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 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 <PubKey> OP_CHECKSIG OP_1 OP_NUMEQU=
AL, 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 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 <pub1>=
 <pub2> ... <pubn> 1 <a-signature> 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