Re: [bitcoin-dev] CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

From: "Russell O'Connor" <roconnor@blockstream•com>
To: Jeremy <jlrubin@mit•edu>,
	 Bitcoin Protocol Discussion
	<bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin
Date: Sat, 3 Jul 2021 13:50:21 -0400	[thread overview]
Message-ID: <CAMZUoK=-jrH+fr=tUTHmLojm2-Ff99KYm9H97yhd=7bcOVG=fg@mail.gmail.com> (raw)
In-Reply-To: <CAD5xwhjmu-Eee47Ho5eA6E6+aAdnchLU0OVZo=RTHaXnN17x8A@mail.gmail.com>

[-- Attachment #1: Type: text/plain, Size: 14032 bytes --]

Hi Jermy,

As you are aware, we, and by we I mean mostly Sanket, are developing an
updated OP_CHECKSIGFROMSTACK implementation for tapscript on elements.  The
plan here would be to effectively support the an interface to the
variable-length extension of BIP-0340 schnorr signatures.

BIP-0340 would dispense with DER encoding (good riddance).
BIP-0340 signatures are batch verifiable along with other BIP-0340
transaction signatures and taproot tweak verification.
Support for variable length messages in BIP-0340 has been discussed in <
https://github.com/sipa/bips/issues/207> and an implementation has recently
been merged in <https://github.com/bitcoin-core/secp256k1/pull/844>.  The
BIP has not yet been updated but the difference is that the message m does
not have to be 32-bytes (it is recommended that the message be a 32-bit
tagged hash or a message with a 64-bit application specific prefix). The
CHECKSIGFROMSTACK operation (in tapscript) would use a stack item for this
m value to BIP-0340 signature verification and would not necessarily have
to be 32 bytes.

I think this design we are aiming for would be perfectly suited for Bitcoin
as well.

On Sat, Jul 3, 2021 at 12:32 PM Jeremy via bitcoin-dev <
bitcoin-dev@lists•linuxfoundation.org> wrote:

> Reproduced below is the BIP text from Bitcoin Cash's (MIT-Licensed)
> specification for "CheckDataSig", more or less the same thing as
> CHECKSIGFROMSTACK
> https://github.com/bitcoincashorg/bitcoincash.org/blob/master/spec/op_checkdatasig.md.
> In contrast to Element's implementation, it does not have Element's bugs
> around verify semantics and uses the nullfail rule, and there is a
> specification document so it seemed like the easiest starting point for
> discussion v.s. drafting something from scratch.
>
> Does anyone have any issue with adapting this exact text and
> implementation to a BIP for Bitcoin using 2 OP_SUCCESSX opcodes?
>
> Note that with *just* CheckSigFromStack, while you can do some very
> valuable use cases, but without OP_CAT it does not enable sophisticated
> covenants (and as per
> https://www.wpsoftware.net/andrew/blog/cat-and-schnorr-tricks-i.html just
> CAT alone enables such uses).
>
> Design questions worth considering as modifications:
>
> 1. Should CSFS require some sort of tagged hash? Very likely answer is no
> – tags interfere with certain use cases
> 2. Should CSFS split the signature’s R & S value stack items for some
> applications that otherwise may require OP_CAT? E.g. using a pinned R value
> allows you to extract a private key if ever double signed, using 2 R values
> allows pay-to-reveal-key contracts. Most likely answer is no, if that is
> desired then OP_CAT can be introduced
> 3. Should CSFS support a cheap way to reference the taproot internal or
> external key? Perhaps, can be handled with undefined upgradeable keytypes.
> One might want to use the internal key, if the signed data should be valid
> independent of the tapscript tree. One might want to use the external key,
> if the data should only be valid for a single tapscript key + tree.
> 4. Should invalid public keys types be a NOP to support future extended
> pubkey types?
>
>
>
> Best,
>
>
> Jeremy
>
>
> ---
> layout: specification
> title: OP_CHECKDATASIG and OP_CHECKDATASIGVERIFY Specification
> category: spec
> date: 2018-08-20
> activation: 1542300000
> version: 0.6
> ---
>
> OP_CHECKDATASIG
> ===============
>
> OP_CHECKDATASIG and OP_CHECKDATASIGVERIFY check whether a signature is valid with respect to a message and a public key.
>
> OP_CHECKDATASIG permits data to be imported into a script, and have its validity checked against some signing authority such as an "Oracle".
>
> OP_CHECKDATASIG and OP_CHECKDATASIGVERIFY are designed to be implemented similarly to OP_CHECKSIG [1]. Conceptually, one could imagine OP_CHECKSIG functionality being replaced by OP_CHECKDATASIG, along with a separate Op Code to create a hash from the transaction based on the SigHash algorithm.
>
> OP_CHECKDATASIG Specification
> -----------------------------
>
> ### Semantics
>
> OP_CHECKDATASIG fails immediately if the stack is not well formed. To be well formed, the stack must contain at least three elements [`<sig>`, `<msg>`, `<pubKey>`] in this order where `<pubKey>` is the top element and
>   * `<pubKey>` must be a validly encoded public key
>   * `<msg>` can be any string
>   * `<sig>` must follow the strict DER encoding as described in [2] and the S-value of `<sig>` must be at most the curve order divided by 2 as described in [3]
>
> If the stack is well formed, then OP_CHECKDATASIG pops the top three elements [`<sig>`, `<msg>`, `<pubKey>`] from the stack and pushes true onto the stack if `<sig>` is valid with respect to the raw single-SHA256 hash of `<msg>` and `<pubKey>` using the secp256k1 elliptic curve. Otherwise, it pops three elements and pushes false onto the stack in the case that `<sig>` is the empty string and fails in all other cases.
>
> Nullfail is enforced the same as for OP_CHECKSIG [3]. If the signature does not match the supplied public key and message hash, and the signature is not an empty byte array, the entire script fails.
>
> ### Opcode Number
>
> OP_CHECKDATASIG uses the previously unused opcode number 186 (0xba in hex encoding)
>
> ### SigOps
>
> Signature operations accounting for OP_CHECKDATASIG shall be calculated the same as OP_CHECKSIG. This means that each OP_CHECKDATASIG shall be counted as one (1) SigOp.
>
> ### Activation
>
> Use of OP_CHECKDATASIG, unless occuring in an unexecuted OP_IF branch, will make the transaction invalid if it is included in a block where the median timestamp of the prior 11 blocks is less than 1542300000.
>
> ### Unit Tests
>
>  - `<sig> <msg> <pubKey> OP_CHECKDATASIG` fails if 15 November 2018 protocol upgrade is not yet activated.
>  - `<sig> <msg> OP_CHECKDATASIG` fails if there are fewer than 3 items on stack.
>  - `<sig> <msg> <pubKey> OP_CHECKDATASIG` fails if `<pubKey>` is not a validly encoded public key.
>  - `<sig> <msg> <pubKey> OP_CHECKDATASIG` fails if `<sig>` is not a validly encoded signature with strict DER encoding.
>  - `<sig> <msg> <pubKey> OP_CHECKDATASIG` fails if signature `<sig>` is not empty and does not pass the Low S check.
>  - `<sig> <msg> <pubKey> OP_CHECKDATASIG` fails if signature `<sig>` is not empty and does not pass signature validation of `<msg>` and `<pubKey>`.
>  - `<sig> <msg> <pubKey> OP_CHECKDATASIG` pops three elements and pushes false onto the stack if `<sig>` is an empty byte array.
>  - `<sig> <msg> <pubKey> OP_CHECKDATASIG` pops three elements and pushes true onto the stack if `<sig>` is a valid signature of `<msg>` with respect to `<pubKey>`.
>
> OP_CHECKDATASIGVERIFY Specification
> -----------------------------------
>
> ### Semantics
>
> OP_CHECKDATASIGVERIFY is equivalent to OP_CHECKDATASIG followed by OP_VERIFY. It leaves nothing on the stack, and will cause the script to fail immediately if the signature check does not pass.
>
> ### Opcode Number
>
> OP_CHECKDATASIGVERIFY uses the previously unused opcode number 187 (0xbb in hex encoding)
>
> ### SigOps
>
> Signature operations accounting for OP_CHECKDATASIGVERIFY shall be calculated the same as OP_CHECKSIGVERIFY. This means that each OP_CHECKDATASIGVERIFY shall be counted as one (1) SigOp.
>
> ### Activation
>
> Use of OP_CHECKDATASIGVERIFY, unless occuring in an unexecuted OP_IF branch, will make the transaction invalid if it is included in a block where the median timestamp of the prior 11 blocks is less than 1542300000.
>
> ### Unit Tests
>
>  - `<sig> <msg> <pubKey> OP_CHECKDATASIGVERIFY` fails if 15 November 2018 protocol upgrade is not yet activated.
>  - `<sig> <msg> OP_CHECKDATASIGVERIFY` fails if there are fewer than 3 item on stack.
>  - `<sig> <msg> <pubKey> OP_CHECKDATASIGVERIFY`fails if `<pubKey>` is not a validly encoded public key.
>  - `<sig> <msg> <pubKey> OP_CHECKDATASIGVERIFY` fails if `<sig>` is not a validly encoded signature with strict DER encoding.
>  - `<sig> <msg> <pubKey> OP_CHECKDATASIGVERIFY` fails if signature `<sig>` is not empty and does not pass the Low S check.
>  - `<sig> <msg> <pubKey> OP_CHECKDATASIGVERIFY` fails if `<sig>` is not a valid signature of `<msg>` with respect to `<pubKey>`.
>  - `<sig> <msg> <pubKey> OP_CHECKDATASIGVERIFY` pops the top three stack elements if `<sig>` is a valid signature of `<msg>` with respect to `<pubKey>`.
>
> Sample Implementation [4, 5]
> ----------------------------
>
> ```c++
>                     case OP_CHECKDATASIG:
>                     case OP_CHECKDATASIGVERIFY: {
>                         // Make sure this remains an error before activation.
>                         if ((flags & SCRIPT_ENABLE_CHECKDATASIG) == 0) {
>                             return set_error(serror, SCRIPT_ERR_BAD_OPCODE);
>                         }
>
>                         // (sig message pubkey -- bool)
>                         if (stack.size() < 3) {
>                             return set_error(
>                                 serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
>                         }
>
>                         valtype &vchSig = stacktop(-3);
>                         valtype &vchMessage = stacktop(-2);
>                         valtype &vchPubKey = stacktop(-1);
>
>                         if (!CheckDataSignatureEncoding(vchSig, flags,
>                                                         serror) ||
>                             !CheckPubKeyEncoding(vchPubKey, flags, serror)) {
>                             // serror is set
>                             return false;
>                         }
>
>                         bool fSuccess = false;
>                         if (vchSig.size()) {
>                             valtype vchHash(32);
>                             CSHA256()
>                                 .Write(vchMessage.data(), vchMessage.size())
>                                 .Finalize(vchHash.data());
>                             uint256 message(vchHash);
>                             CPubKey pubkey(vchPubKey);
>                             fSuccess = pubkey.Verify(message, vchSig);
>                         }
>
>                         if (!fSuccess && (flags & SCRIPT_VERIFY_NULLFAIL) &&
>                             vchSig.size()) {
>                             return set_error(serror, SCRIPT_ERR_SIG_NULLFAIL);
>                         }
>
>                         popstack(stack);
>                         popstack(stack);
>                         popstack(stack);
>                         stack.push_back(fSuccess ? vchTrue : vchFalse);
>                         if (opcode == OP_CHECKDATASIGVERIFY) {
>                             if (fSuccess) {
>                                 popstack(stack);
>                             } else {
>                                 return set_error(serror,
>                                                  SCRIPT_ERR_CHECKDATASIGVERIFY);
>                             }
>                         }
>                     } break;
> ```
>
> Sample Usage
> ------------
>
> The following example shows a spend and redeem script for a basic use of CHECKDATASIG.  This example validates the signature of some data, provides a placeholder where you would then process that data, and finally allows one of 2 signatures to spend based on the outcome of the data processing.
>
> ### spend script:
> ```
> push txsignature
> push txpubkey
> push msg
> push sig
> ```
> ### redeem script:
> ```
>                                 (txsig, txpubkey msg, sig)
> OP_OVER                         (txsig, txpubkey, msg, sig, msg)
> push data pubkey                (txsig, txpubkey, msg, sig, msg, pubkey)
> OP_CHECKDATASIGVERIFY           (txsig, txpubkey, msg)
> ```
> Now that msg is on the stack top, the script can write predicates on it,
> resulting in the message being consumed and a true/false condition left on the stack: (txpubkey, txsig, boolean)
> ```
> OP_IF                           (txsig, txpubkey)
>   OP_DUP                        (txsig, txpubkey, txpubkey)
>   OP_HASH160                    (txsig, txpubkey, address)
>   push <p2pkh spend address>    (txsig, txpubkey, address, p2pkh spend address)
>   OP_EQUALVERIFY                (txsig, txpubkey)
>   OP_CHECKSIG
> OP_ELSE
>   (same as if clause but a different <p2pkh spend address>)
> OP_ENDIF
> ```
>
> History
> -------
>
> This specification is based on Andrew Stone’s OP_DATASIGVERIFY proposal [6, 7]. It is modified from Stone's original proposal based on a synthesis of all the peer-review and feedback received [8].
>
> References
> ----------
>
> [1] [OP_CHECKSIG](https://en.bitcoin.it/wiki/OP_CHECKSIG)
>
> [2] [Strict DER Encoding](https://github.com/bitcoin/bips/blob/master/bip-0066.mediawiki)
>
> [3] [Low-S and Nullfail Specification](https://github.com/bitcoin/bips/blob/master/bip-0146.mediawiki)
>
> [4] [Bitcoin ABC implementation](https://reviews.bitcoinabc.org/D1621)
>
> [5] [Bitcoin ABC implementation update](https://reviews.bitcoinabc.org/D1646)
>
> [6] [Andrew Stone’s OP_DATASIGVERIFY](https://github.com/BitcoinUnlimited/BitcoinUnlimited/blob/bucash1.3.0.0/doc/opdatasigverify.md)
>
> [7] [Andrew Stone's article on Scripting](https://medium.com/@g.andrew.stone/bitcoin-scripting-applications-decision-based-spending-8e7b93d7bdb9)
>
> [8] [Peer Review of Andrew Stone's Proposal](https://github.com/bitcoincashorg/bitcoincash.org/pull/10)
>
>
> --
> @JeremyRubin <https://twitter.com/JeremyRubin>
> <https://twitter.com/JeremyRubin>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 16457 bytes --]