[bitcoin-dev] CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin
Russell O'Connor
roconnor at blockstream.com
Sat Jul 3 17:50:21 UTC 2021
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 at 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 at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20210703/ce1d831d/attachment-0001.html>
More information about the bitcoin-dev
mailing list