bip322: (another) significant overhaul #1048

apoelstra commented at 2:49 PM on December 21, 2020: contributor

Changes the validation rules to always require (script) standardness checks, except for checking NOPs and version numbers, where incorrect values result in "inconclusive" rather than "invalid". Allow validators to also return "inconclusive" when they encounter a script that they're unable to interpret.

This makes it possible to write a BIP-322 validator using Miniscript, and to write (say) a p2pkwh-only validator while remaining within spec. Both should encourage adoption.

Also removed the to_spend transaction from the wire serialization because it is a pure function of the address and message.

Mailing list discussion: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-December/thread.html

apoelstra force-pushed on Dec 21, 2020

bip-0322: replace motivation, add myself to the "thanks to" list f778098deb

bip-0322: move "legacy" section up, separate "proof of funds", summarize the signature types dbb81b3652

bip-0322: overhaul/rewrite verification rules 9e1beef6ac

bip-0322: remove the 'to_spend' transaction from serialization c624414119

apoelstra force-pushed on Dec 23, 2020

in bip-0322.mediawiki:64 in c624414119

  60 | @@ -41,10 +61,9 @@ The "to_spend" transaction is:
  61 |      vout[0].nValue = 0
  62 |      vout[0].scriptPubKey = message_challenge
  63 |  
  64 | -where message_hash is a BIP340-tagged hash of the message, i.e. sha256_tag(m), where tag = "BIP0322-signed-message", and message_challenge is the to be proven (public) key script.
  65 | -For proving funds, message_challenge shall be simply OP_TRUE.
  66 | +where <code>message_hash</code> is a BIP340-tagged hash of the message, i.e. sha256_tag(m), where tag = <code>BIP0322-signed-message</code>, and <code>message_challenge</code> is the to be proven (public) key script.

kallewoof commented at 2:46 AM on December 24, 2020:

where <code>message_hash</code> is a BIP340-tagged hash of the message, i.e. sha256_tag(m), where tag = <code>"BIP0322-signed-message"</code>, and <code>message_challenge</code> is the to be proven (public) key script.

(It's a string literal, so I think quotes are good)

harding commented at 5:43 PM on January 1, 2021:

Nit not introduced in this patch: 2/3 items in this list are introduced by "where". It would be better to use where either 1/3 or 3/3 times.

in bip-0322.mediawiki:115 in c624414119

 132 | +## Confirm that the two transactions together satisfy all consensus rules, except for <code>to_spend</code>'s missing input, and except that ''nSequence'' of <code>to_sign</code>'s first input and ''nLockTime'' of <code>to_sign</code> are not checked.
 133 | +# (Optional) If the validator does not have a full script interpreter, it should check that it understands all scripts being satisfied. If not, it should stop here and output ''inconclusive''.
 134 | +# Check the **required rules**:
 135 | +## All signatures must use the SIGHASH_ALL flag.
 136 | +## The use of <code>CODESEPARATOR</code> or <code>FindAndDelete</code> is forbidden.
 137 | +## <code>LOW_S</code>, <code>STRICTENC</code> and <code>NULLFAIL</code>: valid ECDSA signatures must be strictly DER-encoded and have a low-S value; invalid ECDSA signature must be the empty push

kallewoof commented at 2:51 AM on December 24, 2020:

## <code>LOW_S</code>, <code>STRICTENC</code> and <code>NULLFAIL</code>: valid ECDSA signatures must be strictly DER-encoded and have a low-S value; invalid ECDSA signatures must be the empty push

dgpv commented at 9:10 AM on December 24, 2020: contributor

The proposal requires the validator to be able to detect violations of standardness flags (MINIMALDATA, STRICTENC, NULLFAIL, etc). I thought that validators will be able to do verification by using bitcoinconsensus library. The problem is that the library explicitly disallows any standardness flags to be passed to it, only the flags related to consensus is allowed.

While this issue is not directly related to the BIP essense, I think it makes implementation significantly harder, because now the implementors will need to either:

Have their own script interpreter, that may happen to differ with the one from Core;
Pluck script interpreter code out of Core into their own project, and not use libbitcoinconsensus (like libbitcoin-consensus does);
Have their own interpreter, but cross-check with libbitcoinconsensus for consensus violations (still might differ from Core in standardness-related code);
Use Core via rpc

I think all these options may happen to be unsatisfactory for a standalone project due to added maintenance or dependency burden.

The inclusion of these checks into this BIP says that probably these rules are significant, not likely to change in the future, and it would be good to have an access to checking them with the code from Core, but without depending on whole bitcoind

Maybe there should be an API to do standardness checks in libbitcoinconsensus, just as a different API function.

sipa commented at 8:25 PM on December 24, 2020: member

@dgpv I think this is exactly why @apoelstra is suggesting to permit validators to only implement a subset of script, and report inconclusive for others. This means a much smaller scope reimplementation is possible.

You do have a good point though, that the inclusion of these rules in the BIP make them sort of canonical. Perhaps there is a way to see it differently. It is not so much that such scripts are not relayed on the network, or even that they're intended for future extensions that matters - it is the fact that they are all effectively "anyone can spend" (as far as the verifier knows) - and thus a signature can't really have any meaning.

Could the rule just be that any script that doesn't perform any signature check at all, is "inconclusive"? That's very concrete, not tied to policy on the network, and perhaps easier to have exported from libbitcoinconsensus too as it doesn't incur the risk of making people building things that depend on the network's policy rules.

apoelstra commented at 11:59 PM on December 24, 2020: contributor

I agree that these checks are difficult to implement, but without them every BIP322 signature will be extremely malleable.

apoelstra commented at 12:01 AM on December 25, 2020: contributor

But I also agree that these rules are "significant", in the sense that in a perfect world they would have always been part of consensus, I can't imagine any reason they would ever be relaxed (indeed, in Taproot I think they have all made it into consensus), and I wish that libbitcoinconsensus exposed a way to enforce them. But that discussion would be much wider scope than this BIP..

dgpv commented at 6:42 AM on December 25, 2020: contributor

I agree that these checks are difficult to implement, but without them every BIP322 signature will be extremely malleable.

They are difficult to implement and at the same time required by the spec ("If any of the above steps failed, the validator should stop and output the ''invalid'' state."), making it difficult for implementation to conform to the spec at all.

apoelstra commented at 3:55 PM on December 25, 2020: contributor

Well, for what it's worth, these rules are very easy to enforce for the common types of signatures that incomplete validators are likely to template-match on: for p2pkwh signatures it requires your scriptSig be empty and witness stack consist of a pubkey and valid signature and nothing else, etc.

So ironically, I think deliberately incomplete implementations will have an okay time of this, while people who try to implement complete validators will not.

Semi-relatedly, I just realized that I dropped NULLDUMMY (extra CHECKMULTISIG stack item needs to be the empty push).

apoelstra commented at 3:55 PM on December 25, 2020: contributor

I wonder if, assuming this PR is accepted, Core would accept a PR to add a flag to libbitcoinconsensus specifically for BIP322 validation.

dgpv commented at 4:05 PM on December 25, 2020: contributor

a flag to libbitcoinconsensus specifically for BIP322 validation.

or a separate function, verify_script_bip322 or the like, that could also take a version of bip322 as a paremeter, and set the flags for VerifyScript accordingly. This way, if the bip would ever be updated with new required flags, the version of the bip will need to be bumped and the verify_script_bip322 function would recognize the new version and would choose the right combination of flags

dgpv commented at 4:11 PM on December 25, 2020: contributor

That assumes that the "version of the combination of flags" would be the part of the bip, of course. There might not ever be the need for this, but what if there are ? What if the need to enforce certain new flag will emerge ?

Of course such version wouldn't be needed if the caller could just specify their combination of flags, and then would update their code after new flags are included in the BIP

dgpv commented at 4:32 PM on December 25, 2020: contributor

What I wanted to say, if the "bip322-related" flags are bundled inside libbitcoinconsensus via a single "bip322" flag or inside a "bip322-specific" function, there could be a potential problem between the software that expects to verify with newer set of flags, and the library that bundles the old set of flags. Of course libbitcoinconsensus has an api version, but is the single added flag a good reason to bump it ? So either the flags shouldn't be bundled, or the bundling itself need to be versioned.

(please excuse the slightly off-topic discussion, but since it may influence the BIP itself (adding version/revision ?), it may be relevant)

apoelstra commented at 6:25 PM on December 25, 2020: contributor

Agreed on all counts.

I think a "reference implementation" of this BIP should include (a) a patch to Bitcoin Core which adds sign/verify RPCs; (b) a patch to libbitcoinconsensus to add a verify_script_322 method; (c) a small C program which uses libbitcoinconsensus to sign and verify a message.

kallewoof commented at 10:58 AM on December 27, 2020: member

Sounds good to me!

kallewoof commented at 11:58 PM on December 31, 2020: member

@luke-jr This is good to merge. It's been discussed on the ML and comments have been addressed.

in bip-0322.mediawiki:32 in c624414119

  35 | +This BIP specifies three formats for signing messages: ''legacy'', ''simple'' and ''full''. Additionally, a variant of the ''full'' format can be used to demonstrate control over a set of UTXOs.
  36 |  
  37 | -The "to_spend" transaction is:
  38 | +=== Legacy ===
  39 | +
  40 | +New proofs should use the new format for all invoice address formats, including P2PKH.

harding commented at 3:01 PM on January 1, 2021:

This recommendation seems to needlessly create compatibility issues similar to those in @kallewoof's original PR for generic signmessage: https://github.com/bitcoin/bitcoin/pull/16440#pullrequestreview-267525062

If the default is to create legacy proofs for P2PKH, then it's possible to implement BIP322 as a simple backwards-compatible extension to existing interfaces like Bitcoin Core's signmessage RPC and GUI window. But, if devs adopt the recommendation here to default to using the new proof format, then they'll need to deprecate the old RPC default for P2PKH output and add a checkbox to the GUI for legacy vs new (like is done for selecting between legacy/bech32 addresses).

[Edited to correct attribution]

kallerosenbaum commented at 3:36 PM on January 1, 2021:

Wrong Kalle I guess. But always flattering to be mistaken for @kallewoof

apoelstra commented at 7:26 PM on January 4, 2021:

Yeah I think this is reasonable.

My personal preference would be to deprecate the old base64 signmessage format but it's needlessly breaking to recommend people shift away from it for pkh addresses (which I'd also like to see go away :))

kallewoof commented at 4:58 AM on January 7, 2021:

FWIW, I chose to be backwards compatible, but later several people suggested we should recommend using the new format so we can sunset the old one at some point.

harding commented at 2:23 AM on January 11, 2021:

@kallewoof legacy format will be automatically sunset when almost nobody uses P2PKH any more. At that point, it won't be disruptive to deprecate legacy proof generation and verification code. Until then, I think BIP322 needs all the support it can get and maintaining backwards compatibility with the tools people already use is one way to attract support.

harding commented at 3:02 PM on January 1, 2021: contributor

Partial review (ran out of time).

in bip-0322.mediawiki:36 in c624414119

  39 | +
  40 | +New proofs should use the new format for all invoice address formats, including P2PKH.
  41 | +
  42 | +The legacy format MAY be used, but must be restricted to the legacy P2PKH invoice address format.
  43 | +
  44 | +=== Simple ===

harding commented at 5:33 PM on January 1, 2021:

Nit: I think I'd find this document easier to follow if the Simple section followed the Full (proof of funds) section. It's not possible to understand what Simple is doing until you've learned about the fields described in Full.

in bip-0322.mediawiki:48 in c624414119

  51 | +
  52 | +and then proceed as they would for a full signature.
  53 | +
  54 | +=== Full ===
  55 | +
  56 | +Full signatures follow an analogous specification to the BIP-325 challenges and solutions used by Signet.

harding commented at 5:39 PM on January 1, 2021:

Nit: this is the only case in the document where the format "BIP-nnn" is used. In the rest of the paragraph text, "BIPnnn" is used.

in bip-0322.mediawiki:125 in c624414119

 142 | +# Check the **upgradeable rules**
 143 | +## The version of <code>to_sign</code> must be 0 or 2.
 144 | +## The use of NOPs reserved for upgrades is forbidden.
 145 | +## The use of segwit versions greater than 0 are forbidden.
 146 | +## If any of the above steps failed, the validator should stop and output the ''inconclusive'' state.
 147 | +# Let ''T'' by the nLockTime of <code>to_sign</code> and ''S'' be the nSequence of the first input of <code>to_sign</code>. Output the state ''valid at time T and age S''.

harding commented at 5:59 PM on January 1, 2021:

Is it actually supposed to say "at time T and age S" if no locktime was used? E.g., if the case of nLockTime = 0; nSequence = 0xffffffff, is it supposed to say "valid at time block 0 and age same block as parent"?

harding commented at 6:12 PM on January 1, 2021:

Also, I just realized that the default here is for nSequence to be 0 in both psuedo-transactions instead of the usual wallet default for nSequence to be set to its IsFinal() value of 0xffffffff. Since version >= 2 is required to get BIP68 behavior, that seems fine, but I don't know if it could cause a problem for any PSBT signers (e.g. my Trezor model T warns me about the non-zero nLockTimes created by Bitcoin Core's anti-fee sniping; I don't know how it handles nSequences below 0xfffffffe).

apoelstra commented at 7:27 PM on January 4, 2021:

Ah! Yes, I forgot that nSequence has non-timelock values. I will update the text to reflect this.

harding commented at 6:13 PM on January 1, 2021: contributor

A couple comments and some nits.

kallewoof commented at 7:49 AM on February 1, 2021: member

@apoelstra Did you get a chance to address feedback on this? Would love to get this merged so we avoid multiple specifications for too long (PR vs master).

luke-jr merged this on Feb 3, 2021

luke-jr closed this on Feb 3, 2021

apoelstra commented at 12:43 AM on February 4, 2021: contributor

I did not but I'll try to open a followup PR in the next week.

apoelstra deleted the branch on Feb 4, 2021

in bip-0322.mediawiki:106 in c624414119

 123 | +Validation consists of the following steps:
 124 |  
 125 | -The legacy format MAY be used, but must be restricted to the legacy P2PKH invoice address format.
 126 | +# Basic validation
 127 | +## Compute the transaction <code>to_spend</code> from ''m'' and ''A''
 128 | +## Decode ''s'' as the transaction <code>to_sign</code>

sanket1729 commented at 1:52 AM on March 16, 2021:

I think this needs the following note: "In case of p2sh wrapped segwit scripts, the validator should compute the scriptsig based on witness script"

in bip-0322.mediawiki:109 in c624414119

 126 | +# Basic validation
 127 | +## Compute the transaction <code>to_spend</code> from ''m'' and ''A''
 128 | +## Decode ''s'' as the transaction <code>to_sign</code>
 129 | +## If ''s'' was a full transaction, confirm all fields are set as specified above; in particular that
 130 | +##* <code>to_sign</code> has at least one input and its first input spends the output of </code>to_spend</code>
 131 | +##* <code>to_sign</code> has exactly one output, as specified above

sanket1729 commented at 1:58 AM on March 16, 2021:

This would not work for covenants because fixed validation rules like input spent must be at index 0 etc.

All we really care about is that we are spending the input, we don't really care about the position of the input and output. This is futuristic but worth highlighting and not complicated to implement.

kiwidream cross-referenced this on May 24, 2023 from issue WIP bip322 verification by utxo-detective