BIP118 signatures should commit to full path to tapleaf

[ajtowns]

Standard BIP342 tapscript signatures suffer from a malleability issue: if a taproot address contains two identical script paths, eg:

  TapBranch(
     TapLeaf(A),
     TapBranch(
         TapLeaf(B),
         TapBranch( TapLeaf(C), TapLeaf(A) )
     )
  )

Then you can replace the single-entry path (B,CA) with the three-entry path (A), (B), (C) without invalidating any signatures, and decreasing the fee rate of the transaction due to the fee staying the same while the witness data increases.

To remedy this, BIP118 should be changed to commit to the full merkle path being used to reach the leaf unless ANYPREVOUTANYSCRIPT is specified (in which case the tapleaf is not committed to either).

[ajtowns]

Context: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-February/021452.html

[instagibbs]

If we want to solve exactly the issue of variable length control blocks working for a single non-APOAS signature, an alternative could be to commit to the number merkle hashes in the control block directly, aka m from must have length 33 + 32m in BIP341.

This would be very simple to implement, and is a single byte(since m is a number between 0 and 128) instead of a variable buffer, which would make library support simpler.

[roconnor-blockstream]

FWIW, just signing m would still leave the witness data, and hence wtxID malleable. I don't know how bad that is. Probably not very bad, but generally I think if it can be avoided it should be avoided.

[instagibbs]

Right. If we more generally care about that kind of malleability, we should tighten it down.

On Sun, Feb 12, 2023, 7:41 PM roconnor-blockstream @.***> wrote:

FWIW, just signing m would still leave the witness data, and hence wtxID malleable. I don't know how bad that is. Probably not very bad, but generally I think if it can be avoided it should be avoided.

— Reply to this email directly, view it on GitHub https://github.com/bitcoin-inquisition/bitcoin/issues/19#issuecomment-1427183512, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABMAFU5ESXFEEVS7N2J4PLLWXF7KJANCNFSM6AAAAAAUZEIWTI . You are receiving this because you commented.Message ID: @.***>

[ariard]

To remedy this, BIP118 should be changed to commit to the full merkle path being used to reach the leaf unless ANYPREVOUTANYSCRIPT is specified (in which case the tapleaf is not committed to either).

For vault/payment pools use-cases leveraging script mechanism like TAPROOT_LEAF_UPDATE_VERIFY, where the validity of your signature for withdrawal should be maintained across the sequential on-chain spends from the root utxo while your spending location in the merkle tree changes, I think this is still okay as those spends should commit under ANYPREVOUTANYSCRIPT so at first sight I can't see how this new malleability restriction constraint those use-cases.

[ajtowns]

If we want to solve exactly the issue of variable length control blocks working for a single non-APOAS signature,

It seems to me that trying to solve exact issues is what causes these things to be missed in the first place, so better to just sign everything...

a single byte(since m is a number between 0 and 128) instead of a variable buffer, which would make library support simpler.

I think you'd probably be better to add uint256 m_tapleaf_path_sha256 to ScriptExecutionData, defined as sha256(m, path...). The path should already be available in a PSBT via PSBT_IN_TAP_LEAF_SCRIPT which includes the entire control block.

[naumenkogs]

FWIW, just signing m would still leave the witness data, and hence wtxID malleable. I don't know how bad that is. Probably not very bad, but generally I think if it can be avoided it should be avoided.

To be clear, the issue is the same script in different leaves of the same height?

[instagibbs]

Correct. It doesn't bind the signature to the specific leaf position.

You could obviously also sign the leaf index in the tree, but then the question is what's easiest. I think either sha2-ing the entire serialized control block is simplest, or what AJ suggested in https://github.com/bitcoin-inquisition/bitcoin/issues/19#issuecomment-1427418549

[naumenkogs]

I'm not sure whether this makes a difference, but obtaining an index requires a tree traversal while the path doesn't?

[instagibbs]

Is there a situation where a signer might need to sign a tapscript but not have access to the internal pubkey? It's implicitly committed to, of course, in the utxo being spent, more a question of interface I guess.

[instagibbs]

Do we want to also commit to all input annexes?

[roconnor-blockstream]

I would recommend signing all input annexes where appropriate. I believe sipa agreed with me that it was desirable.

[instagibbs]

the one caveat being key spends would still be exposed, but maybe annex usage can be unrestricted in tapascript spend by policy only

[ajtowns]

Do we want to also commit to all input annexes?

I guess that would mean something like:

• for each input, annex_cmt[i] = "0x00" if it has no witness elements, or the first witness element does not start with 0x50, otherwise annex_cmt[i] = first witness element, preceded by its length
• commit to sha256( annex_cmt[0], annex_cmt[1], ... )

but presumably you wouldn't do that for ANYONECANPAY or ANYPREVOUT/ANYPREVOUTANYSCRIPT signatures.

If the annex is defined and working, I think you could achieve a similar result that works with ACP/APO/APOAS if you have an annex entry committing to a maximum size of the tx.

[ajtowns]

Is there a situation where a signer might need to sign a tapscript but not have access to the internal pubkey? It's implicitly committed to, of course, in the utxo being spent, more a question of interface I guess.

For APOAS the internal pubkey is intentionally malleable (though I'm not sure if there's a use case where that's actually helpful); for everything else it's not malleable due the scriptPubKey commitment, so probably fine?

[instagibbs]

I only have experience using APOAS personally, where generating all witness data(except the signature itself) is done at the very last second.

[ajtowns]

the one caveat being key spends would still be exposed, but maybe annex usage can be unrestricted in tapascript spend by policy only

• commit to sha256( annex_cmt[0], annex_cmt[1], ... )

but presumably you wouldn't do that for ANYONECANPAY or ANYPREVOUT/ANYPREVOUTANYSCRIPT signatures.

It seems like committing to all inputs' annexes via non-ACP/APO/APOAS bip118 sigs would only be a pretty limited solution here -- so probably this would be better solved by also supporting an annex entry that asserts "this tx's weight is no more than X".

[instagibbs]

This definitely wouldn't fix malleability in the case where you're explicitly allowing it; for anti-pinning we have to look elsewhere.