path: root/43/d8a1f1269b1d97c18ddc07665a20d6be49f29d

Return-Path: <ali@notatether.com>
Received: from smtp1.osuosl.org (smtp1.osuosl.org [140.211.166.138])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 4E952C002D
 for <bitcoin-dev@lists.linuxfoundation.org>;
 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 <bitcoin-dev@lists.linuxfoundation.org>;
 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 <bitcoin-dev@lists.linuxfoundation.org>;
 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 <bitcoin-dev@lists.linuxfoundation.org>;
 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 <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
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 <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=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 "<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