[bitcoin-dev] A method for BIP322 signing delegation

[bitcoin-dev] A method for BIP322 signing delegation

[Ali Sherief]

[A similar message was posted in the Bitcointalk BIP322 thread.]

OK, I just figured out how to solve the delegation problem. It builds on Jeremy Rubin's transaction delegation post which I linked to a few days ago.

In BIP322, there is a [planned] provision for some person to delegate signing to another person. That means the second person can do all the signing stuff that the first person could do, and the signature is as if the first person signed it.

What this could be useful for?

- L2/Lightning Network, a channel is just 2-of-2 multisig, so a prospective channel co-creator "delegate" signing to the channel itself, by signing a UTXO inside the multisig - signing along with the other party, creating a dummy output (see below), which can be signed to prove liquidity on behalf of the channel, while keeping the channel itself anonymous.
- CoinJoin, To prove that some CoinJoin coordinator is liquid without violating its anonymity by revealing public keys, the person managing the CoinJoins delegates signing from all UTXOs to be used in the CJ, at once, delegating signing to another dummy output.
- By the same token, Mixers can prove their liquidity without revealing their UTXO set.
- Silent Payments, where the public key is not even known in the first place, the address of a silent payment can delegate signing to another dummy output which only the sender and receiver know about.

So how does this delegation work? It's very simple:

1. All UTXOs that want to delegate signing to a different party must sign a preliminary transaction of this format:
- All input/output amounts are zero.
- input 1 is an invalid input of the kind in BIP322
- the rest of the inputs are the UTXOs wanting to delegate signing to a different party, with valid signatures/witness stacks.
- there is only one output, and it is a P2WSH output with the following script:
OP_PUSH <hash-of-address-hash> OP_SWAP OP_HASH160 OP_EQUALVERIFY
- And the witness stack that will "spend" the transaction in the "to_spend" tx is simply:
<address-hash>
- Likewise, the "to_spend" tx has only one input, refering to the txid of the delegating transaction with output point 0 i.e. the UTXO <delegation-txid>:0. Outputs of "to_spend" remain the same.
-- Contrary to the use of Hash160, we are NOT hashing a public key or script. We are hashing an address hash, implying that we are using addresses.

Do you know why I said "delegating to a different party"? Because it could be a functionally different entity, just like how CEO is diffferent from LLC company even if it has only 1 employee. The "address" here represents a kind of company <but is not a smart contract> - it can represent a channel, it can represent a coinjoin, it can represent a silent payment. The channel/CJ/etc. only has to hash the decoded RIPEMD160 of an address, with another SHA256-RIPEMD160, to make an "address" that can be used to sign messages from.

This "address" aka. LLC company can even be encoded with Bech32 to make it look like a real address - obviously don't send any funds directly to that address because they will be lost - and in fact, it *should* be Bech32-encoded when transmitting the Signed Message.

A signed message has these three parts:

Message
Address
Signature

BIP322 specifies the signature is just the raw transaction format of "to_sign". Normally, the address would simply be the address you are signing from, but in the case of delegation, it is desireable for the original addresses to remain anonymous. So since an address must be filled in somewhere, the Bech32 "hash-of-address-hash" created above can be used as a P2WSH address.

Advantages of this scheme:

- The real addresses/UTXOs signing the transaction are only known to each other and whoever is managing the "to_delegate" transaction.
- Only the real signers and the person who is in charge of the P2WSH output can sign the "to_delegate" output and thus sign a message from it (note that they could be the same person).
- There can be an arbitrary number of delegations before the transaction is actually signed (the new person who is in charge of signing, i.e. has the P2WSH output of the "to_delegate" transaction can simply generate another address hash, and delegate to that "address" in another transaction, giving some other person that "address" if they want to)
- Delegated signatures can wrap Full and Full with UTXOs signing formats, so Light clients do not have to directly support those two formats, either for complexity reasons, or because they have no UTXO set.
- And crucially: **There is no on-chain transaction, so the delegation is private and cannot be traced back by the public**.

And there are virtually no disadvantages to this.

I should emphasize that you don't delegate signing to another person, you delegate signing to another party that may just be comprised by one person. I say this because the delegation does not make any new on-chain UTXOs that someone could posess, but it simply creates a hash160 of some address hash that was generated by the delegators, and the hash-of-address-hash does not necessarily have to represent a person, it can also represent a service.

FAQ:

Q: Does this utilize the Full format?
A: Yes.

Q: How to represent the delegation in a signed transaction?
A: Just encode the hash-of-address-hash in Bech32 version 0 and put it in the Address field.

Q: If the delegation is private, then how can the address-hash be known and the transaction signed?
A: The UTXO signers take a random address associated with them <could be one of their own address, could be the address of a multisig that is being used elsewhere etc.> and then make the hash160 of that address. Whoever they give this to, can sign a BIP322 transaction.

Q: How can the public verify a delegated BIP322 transaction if the address-hash is private?
A: The hash-of-address-hash is revealed in the Address, not in the Signature. BIP322 states that the signature only contains the "to_sign" transaction, which does not contain the witness stack of "to_spend" that has the hash-of-address-hash (because THAT was already spent in "to_spend") therefore the address hash is Bech32 (version 0) encoded and can be decoded to re-construct "to_spend" transaction and from there "to_sign".

Q: How to differentiate between non-delegated and delegated signatures?
A: You can't. But then again, BIP322 doesn't differentiate between "message signatures from an address" and a signature from a set of UTXOs so it wouldn't be able to identify a delegated transaction anyway.
Rather, a full-blown verification software should present a list-box or a set of radio buttons, that toggles between "Legacy", "Simple", "Full", "Full with UTXOs" and "Full with Delegation" - Each of these controls the content in the Address field - this would already be required to support validating Legacy signatures anyway, which are otherwise incompatible with the transaction-based signing (and this is the workaround BIP322 specifies to support that).

Q: What if the verifier does not have a UTXO set (light clients)?
A: Then present three toggles or radio buttons: "Legacy", "Simple", and "Delegated" - each of these options only require a single encoded address to be specified in the field, and Full, and Full With UTXOs signatures can be wrapped with a delegation to support a single address. Consequentially, these control how the signed transaction is [re]constructed for sign/verify.

CC'ing Kalle as he might be interested in this.

- Ali

Re: [bitcoin-dev] A method for BIP322 signing delegation

[Ali Sherief]

(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

Re: [bitcoin-dev] A method for BIP322 signing delegation

[Ali Sherief]

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

Re: [bitcoin-dev] A method for BIP322 signing delegation

[Ali Sherief]

This message relates to an edge case which BIP322 only partially solves, and that is Proof of Payment.

When you make a transaction to any business, it keeps the transaction in its records and generates an invoice so anyone can verify the transaction took place.

When you do a P2P transaction, whether on the blockchain or with paper money, there is always the risk that the other party will be dishonest, act in their own interest to convince people that they did not receive the transaction. Nobody has been able to completely get rid of this.

But in cryptocurrencies, this type of dispute is rampant, because it's also a scam attempt, to extract more money from the buyer. Legacy signed message isn't even enough to prove the transction took place - they can just claim (falsely) the address in the transaction is not theirs.

It usually happens like this:

1. Alice wants to buy something from Bob and sends bitcoins.
2. Bob denies receiving payment.
3. Alice publishes the txid of the transaction.
4. Bob denies that the address in the transaction belongs to him.

BIP322 signed messages only go half-way there: They can prove that the UTXO(s) belong to the buyer, and any good block explorer will show you the UTXOs that are being spent. So it can be independently established that Alice sent money, but not *who* it was sent to. That is where BIP322 falls short - there is no mechanism that forces Bob to sign a BIP322 message from the UTXO(s) he has just received, before the transaction is complete.

---

What should be done about this situation?

I propose using P2WSH 2-of-2 multisig to solve this problem. The script challenge will consist of something like OP_SHA256 <sha256 hash> OP_EQUAL[1][2]

[1]I don't even know if there is a standalone SHA256 opcode.
[2]OP_CHECKMULTISIG and OP_CHECKSIG both take public keys from the stack in addition to signatures, but we have arbitrary byte arrays and their SHA256 hashes, not public keys and signatures. How can we make this work?

Now on the witness stack, is pushed the BIP322 signature. Both of the signatures are then published on the blockchain. The catch is that both of the signatures are requires to be supplied

We don't want the signatures to be hidden using Taproot script paths or anything because whole point of this scheme is to make it verifiable to the public.

But I think that this idea can seriously work out in practice:

- Alice starts a P2P payment with Bob (let's just call this whole scheme "P2P payments")
- Alice sends bitcoin to the 2-of-2 multisig address generated by the P2P payment.
- Alice signs a BIP322 message from a UTXO (or address, but preferably a UTXO) and provides one of the signatures.
- Bob is forced to sign another BIP322 message from his address if he wants his money, and provides another signature.
- One of them broadcasts the multisig transaction, and Bob gets his money.

Advantages:
- The signatures in the Multisig transaction are two BIP322 signatures, which prove who has control of which inputs.
-- Consequentially, it can be proven who paid who. It is like an invoice, but it cannot be doctored like company invoices and databases.

Disadvantages:
- If Bob chickens out at this point, the money in the P2P payment is lost forever.
-- So, it is in the buyer's best interest to cooperate, and also in the seller's interest, but not particularly the best one - Until Bob provides a service, he doesn't lose anything except for time.

What do you guys think about this scheme?

- Ali