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

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

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

Awesome to hear that!

Actually I don't think I did know (or I forgot/didn't catch it) that there
was an updated spec for elements, I searched around for what I could find
and came up empty handed. Do you have any links for that? That sounds
perfect to me.

On Sat, Jul 3, 2021, 10:50 AM Russell O'Connor <roconnor@blockstream•com>
wrote:

> 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: 17452 bytes --]