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

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

[Jeremy]

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

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>

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

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

[Russell O'Connor]

[-- 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 --]

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

[Jeremy]

[-- 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 --]

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

[Russell O'Connor]

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

There is one line written at
https://github.com/ElementsProject/elements/pull/949/files#r660130155. I
suppose we need to decide on which variants of *VERIFY and *ADD we want to
include (presumably all of them) and choose which opcodes they will be
assigned to.  And I guess for CHECKSIGFROMSTACKADD will want to place the n
value between the signature and the message on the stack.  ... So I suppose
we will need more than one sentence.

The semantics would be basically to call secp256k1_schnorrsig_verify <
https://github.com/bitcoin-core/secp256k1/blob/0440945fb5ce69d335fed32827b5166e84b02e05/include/secp256k1_schnorrsig.h#L158>,
treating pubkeys and signatures the same way the other CHECKSIG operations
do, and in passing the (variable length) message from the stack.
CHECKSIGFROMSTACK would also be subject to the same sigops budget that
CHECKSIG has in tapscript.

On Sat, Jul 3, 2021 at 2:30 PM Jeremy <jlrubin@mit.edu> wrote:

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

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

[Jeremy]

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

I don't really see the point of CHECKSIGFROMSTACKADD since it's not bound
to the txdata? When might you use this?

And yes -- "Add OP_CHECKSIGFROMSTACK and OP_CHECKSIGFROMSTACKVERIFY to
follow the semantics from bip340-342 when witness program is v1." is a bit
light on detail for what the BIP would end up looking like. If you're able
to open up the design process a bit more on that it would be good as I
think there are some topics worth discussing at large before things proceed
with Elements (assuming feature compatibility remains a goal).

The non-prehashed argument seems OK (at the cost of an extra byte...) but
are there specific applications for !=32 arguments? I can't think of a
particular one beyond perhaps efficiency. Can we safely use 0-520 byte
arguments?

Also do you have thoughts on the other questions i posed above? E.g.
splitting R/S could be helpful w/o CAT.

--
@JeremyRubin <https://twitter.com/JeremyRubin>
<https://twitter.com/JeremyRubin>


On Sat, Jul 3, 2021 at 1:13 PM Russell O'Connor <roconnor@blockstream.com>
wrote:

> There is one line written at
> https://github.com/ElementsProject/elements/pull/949/files#r660130155.
>

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

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

[Russell O'Connor]

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

On Sun, Jul 4, 2021 at 1:30 PM Jeremy <jlrubin@mit.edu> wrote:

> I don't really see the point of CHECKSIGFROMSTACKADD since it's not bound
> to the txdata? When might you use this?
>

I don't feel strongly about *ADD.  I just figured it might be useful to do
a 2-of-3 between Alice, Bob and an Oracle signed value.  But I don't have
any particular use case in mind.  Either way the *ADD functionality can be
replicated by various SWAPs and ADDs etc, so we could just leave it out
until it is wanted.


> And yes -- "Add OP_CHECKSIGFROMSTACK and OP_CHECKSIGFROMSTACKVERIFY to
> follow the semantics from bip340-342 when witness program is v1." is a bit
> light on detail for what the BIP would end up looking like. If you're able
> to open up the design process a bit more on that it would be good as I
> think there are some topics worth discussing at large before things proceed
> with Elements (assuming feature compatibility remains a goal).
>

I'm certainly open to a wider design process.  We can open a specific issue
on the Elements repo.  That said, I don't see a particularly wide design
space on this front.


> The non-prehashed argument seems OK (at the cost of an extra byte...) but
> are there specific applications for !=32 arguments? I can't think of a
> particular one beyond perhaps efficiency. Can we safely use 0-520 byte
> arguments?
>

One of the reasons given in the issue (yes, the thread there is very long)
was that hashing the message requires the hash to be collision resistant
while if you give the message directly it only requires the hash to be
"random-prefix" collision / preimage resistant.  For example SHA-1 is
clearly not collision resistant but it appears to still be random-prefix
collision resistant AFAIU.  Another reason is that it allows for extremely
fast signing oracles because and R value and the midstate of the hash can
be precomputed all the way upto the application prefix, and if the message
being signed is less than 55 bytes or so, the signing cost can be as low as
one compression function and a little bit of non-EC modular arithmetic to
compute S.  If the message were required to be prehashed, then it would
take a minimum of 2 compression function calls to sign, nearly doubling the
signing time needed for the fast oracle.

Even if BIP-0340 kept its requirements that the message be exactly 32
bytes, I would still be inclined to design CHECKSIGFROMSTACK for tapscript
to take the 32-byte message from the stack instead of hashing a message
itself (BIP-0340 does it's own hashing, so prehashing the message isn't a
security concern in the same way it is for ECDSA.)  This would keep the
message off the blockchain, saving space and adding some amount of privacy
and making the operation compatible with rolling SHA256 opcodes.  But given
that BIP-0340 is going to be extended to support non-32 byte messages, then
there is no reason to impose a message length restriction on
CHECKSIGFROMSTACK.  Yes the operation will still be subject to stack item
length restrictions.  This is something script writers will have to be
aware of, but I see little reason to support messages split across multiple
stack items when we expect, by far, most messages to be 32-bytes, and I
expect those rare non-32 byte messages are expected to be reasonably short.


> Also do you have thoughts on the other questions i posed above? E.g.
> splitting R/S could be helpful w/o CAT.
>

Regarding  internal pubkeys and invalid pubkeys, I see no reason to deviate
from whatever tapscript CHECKSIG* do.

Regarding splitting R/S, This is harder because Elements does have CAT and
I think we should add CAT to Bitcoin too.  This game of trying to prevent
covenants by restricting script to the point where we are not even allowed
to have a CAT operation is a losing game.  It's just a matter of time
before we accidently introduce some way to enable covenants anyways, and it
is not worth cutting off vast amounts of functionality in pursuit of this
questionable goal.  And I say this as someone who was originally of the
opinion that we should be very very cautious before enabling new
expressivity such as covenants.  All the scary scenarios of covenants that
I am aware of can be more easily, cheaply, and flexibility implemented by
just having a counterparty in a multi-party signature that enforces their
own policy that they only sign transactions that pay to outputs that they
remain a party to.  And even if scary covenants were scarier than what can
already be done by multisig and policy, I still don't think they are scary
enough to warrant keeping CAT disabled.

So I don't think we should get fancy with CHECKSIGFROMSTACK.  Just take a
normal 64-byte signature value as a stack item.  But I don't feel strongly
about this, and I wouldn't oppose splitting R and S in Bitcoin if that is
where consensus lies.

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

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

[Jeremy]

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

Re-threading Sanket's comment on split R value:

I also am in general support of the `OP_CHECKSIGFROMSTACK` opcode. We would
> need to update the suggestion to BIP340, and add it to sigops budget. I
> have no strong preference for splitting R and s values or variable-length
> messages.
>

Back to my comment:


I see a few options:

1) Making a new 64 byte PK standard which is (R, PK)
2) Splitting (R,S)
3) Different opcodes
4) CAT

The drawback of option 1 is that it's designed to support only very
specific use cases. The main drawback of splitting via option 2 is that you
entail an extra push byte for every use. Option 3 wastes opcodes. CAT has
the general drawbacks of CAT, but worth noting that CAT will likely
eventually land making the splitting feature redundant.


Before getting too in the weeds, it might be worth listing out interesting
script fragments that people are aware of with split R/S so we can see how
useful it might be?

Use a specific R Value
- <S> <M> || <R> SWAP <PK> CSFS

Reuse arbitrary R for a specific M (pay to leak key)
-  <R> <S1> <S2>  ||  DUP2 EQUAL NOT VERIFY 2 PICK SWAP <M> DUP TOALTSTACK
CSFSV FROMALTSTACK CSFS

Verify 2 different messages reuse the same R.
- <S1> <R> <M1> <S2> <M2> ||  2 PICK EQUAL NOT VERIFY 3 PICK <PK> DUP
TOALTSTACK CSFSV FROMALTSTACK CSFS

Use a R Value signed by an oracle:
- <S> <M> <S_oracle> <R_oracle> <R> || DUP TOALTSTACK <PK_oracle> CSFSV
FROMALTSTACK SWAP <PK> CSFS

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

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

[Russell O'Connor]

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

If the main outstanding issue is whether to split R or S, I think as far as
Elements goes, I am inclined to go with the CAT option regardless of
whether Bitcoin chooses to split R/S or not (not that I'm necessarily a
decision maker here).

The issue here is that (a) Elements already has CAT, and (b) updating
CHECKSIGFROMSTACK is effectively a blocking issue for deploying Taproot on
Elements.  I don't think we will be holding up CHECKSIGFROMSTACK for this
issue even if it risks being incompatible with an eventual Bitcoin
CHECKSIGFROMSTACK.

To be clear, I don't mean to prejudice this discussion by this statement.
This just happens to be what makes sense for the Elements project at this
time, and what makes sense for Elements may not necessarily make sense for
Bitcoin.

Of course, I think we should just go for CAT compatibility.  Otherwise we
are just going to have a proliferation of trusted CAT oracles paid for with
lightning by people wanting to perform CAT operations.

On Tue, Jul 6, 2021 at 1:55 PM Jeremy via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Re-threading Sanket's comment on split R value:
>
> I also am in general support of the `OP_CHECKSIGFROMSTACK` opcode. We
>> would need to update the suggestion to BIP340, and add it to sigops budget.
>> I have no strong preference for splitting R and s values or variable-length
>> messages.
>>
>
> Back to my comment:
>
>
> I see a few options:
>
> 1) Making a new 64 byte PK standard which is (R, PK)
> 2) Splitting (R,S)
> 3) Different opcodes
> 4) CAT
>
> The drawback of option 1 is that it's designed to support only very
> specific use cases. The main drawback of splitting via option 2 is that you
> entail an extra push byte for every use. Option 3 wastes opcodes. CAT has
> the general drawbacks of CAT, but worth noting that CAT will likely
> eventually land making the splitting feature redundant.
>
>
> Before getting too in the weeds, it might be worth listing out interesting
> script fragments that people are aware of with split R/S so we can see how
> useful it might be?
>
> Use a specific R Value
> - <S> <M> || <R> SWAP <PK> CSFS
>
> Reuse arbitrary R for a specific M (pay to leak key)
> -  <R> <S1> <S2>  ||  DUP2 EQUAL NOT VERIFY 2 PICK SWAP <M> DUP TOALTSTACK
> CSFSV FROMALTSTACK CSFS
>
> Verify 2 different messages reuse the same R.
> - <S1> <R> <M1> <S2> <M2> ||  2 PICK EQUAL NOT VERIFY 3 PICK <PK> DUP
> TOALTSTACK CSFSV FROMALTSTACK CSFS
>
> Use a R Value signed by an oracle:
> - <S> <M> <S_oracle> <R_oracle> <R> || DUP TOALTSTACK <PK_oracle> CSFSV
> FROMALTSTACK SWAP <PK> CSFS
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

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

[Jeremy]

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

I don't think Elements engineering decisions or management timelines should
have any bearing on what Bitcoin adopts, beyond learning what
works/doesn't. Same as litecoin, dogecoin, or bitcoin cash :)

With my understanding of elements it makes sense that you wouldn't want to
break compatibility script version to script version, although that seems
inevitable that you will need to either hard fork or break compatibility if
you want to fix the CHECKSIGFROMSTACK has verify semantics bug. But perhaps
that's a smaller change than the # of stack elements popped? It makes sense
having CAT that adding a split CSFS wouldn't be a priority. However, I'd
suggest that as far as elements is concerned, if the bitcoin community
decides on something that is incompatible, elements can use up some
addition opcodes or a keytype to add CSFS_BITCOIN_COMPAT ops.

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

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

[David A. Harding]

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

On Sat, Jul 03, 2021 at 09:31:57AM -0700, Jeremy via bitcoin-dev wrote:
> Note that with *just* CheckSigFromStack, while you can do some very
> valuable use cases, but without OP_CAT it does not enable sophisticated
> covenants

Do you have concerns about sophisticated covenants, and if so, would you
mind describing them?  Your BIP119 CTV also mentions[1] being designed
to avoid sophisticated covenants.  If this is some sort of design
principle, I'd like to understand the logic behind it.

I'm a fan of CSFS, even mentioning it on zndtoshi's recent survey[2],
but it seems artificially limited without OP_CAT.  (I also stand by my
answer on that survey of believing there's a deep lack of developer
interest in CSFS at the moment.  But, if you'd like to tilt at that
windmill, I won't stop you.)

-Dave

[1] https://github.com/bitcoin/bips/blob/master/bip-0119.mediawiki#design-tradeoffs-and-risks

[2] https://twitter.com/zndtoshi/status/1405235814712422402


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

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

[Jeremy]

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

>
> Do you have concerns about sophisticated covenants, and if so, would you
> mind describing them?


Personally, not in particular worried about arbitrary covenants as I think
that: 1 validation costs can be kept in check; 2 you're free to burn your
coins it you want to.

I *do* care that when we enable covenants we don't make people jump through
too many hoops, but I also respect Russel's points that we can enable
functionality and then later figure out how to make it more efficient or
useful guided by use cases.


However, I think the broader community is unconvinced by the cost benefit
of arbitrary covenants. See
https://medium.com/block-digest-mempool/my-worries-about-too-generalized-covenants-5eff33affbb6
as a recent example. Therefore as a critical part of building consensus on
various techniques I've worked to emphasize that specific additions do not
entail risk of accidentally introducing more than was bargained for to
respect the concerns of others.


>
> I'm a fan of CSFS, even mentioning it on zndtoshi's recent survey[2],
> but it seems artificially limited without OP_CAT.  (I also stand by my
> answer on that survey of believing there's a deep lack of developer
> interest in CSFS at the moment.  But, if you'd like to tilt at that
> windmill, I won't stop you.)


Well if you're a fan of it, I'm a fan of it, Russel's a fan of it, and
Sanket's a fan of it that sounds like a good amount of dev interest :) I
know Olaoluwa is also a fan of it too and has some cool L2 protocols using
it.

I think it might not be *hype* because it's been around a while and has
always been bundled with cat so been a non starter for the reasons above. I
think as an independent non-bundle it's exciting and acceptable to a number
of devs. I also believe upgrades can be developed and tracked in parallel
so I'm taking on the windmill tilting personally to spearhead that -- on
the shoulders of Giants who have been creating specs for this already of
course.

Best,

Jeremy

P.s. icymi https://rubin.io/blog/2021/07/02/covenants/ covers my current
thinking about how to proceed w.r.t. deploying and developing covenant
systems for bitcoin

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

[bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[David A. Harding]

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

On Sun, Jul 04, 2021 at 11:39:44AM -0700, Jeremy wrote:
> However, I think the broader community is unconvinced by the cost benefit
> of arbitrary covenants. See
> https://medium.com/block-digest-mempool/my-worries-about-too-generalized-covenants-5eff33affbb6
> as a recent example. Therefore as a critical part of building consensus on
> various techniques I've worked to emphasize that specific additions do not
> entail risk of accidentally introducing more than was bargained for to
> respect the concerns of others.

Respecting the concerns of others doesn't require lobotomizing useful
tools.  Being respectful can also be accomplished by politely showing
that their concerns are unfounded (or at least less severe than they
thought).  This is almost always the better course IMO---it takes much
more effort to satisfy additional engineering constraints (and prove to
reviewers that you've done so!) than it does to simply discuss those
concerns with reasonable stakeholders.  As a demonstration, let's look
at the concerns from Shinobi's post linked above:

They seem to be worried that some Bitcoin users will choose to accept
coins that can't subsequently be fungibily mixed with other bitcoins.
But that's already been the case for a decade: users can accept altcoins
that are non-fungible with bitcoins.

They talk about covenants where spending is controlled by governments,
but that seems to me exactly like China's CBDC trial.

They talk about exchanges depositing users' BTC into a covenant, but 
that's just a variation on the classic not-your-keys-not-your-bitcoins
problem.  For all you know, your local exchange is keeping most of its
BTC balance commitments in ETH or USDT.

To me, it seems like the worst-case problems Shinobi describes with
covenants are some of the same problems that already exist with
altcoins.  I don't see how recursive covenants could make any of those
problems worse, and so I don't see any point in limiting Bitcoin's
flexibility to avoid those problems when there are so many interesting
and useful things that unlimited covenants could do.

-Dave

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[Billy Tetrud]

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

I agree with you David. I think rather unconstrained covenants are
incredibly useful and important. Yes you can burn coins with them, you can
also permanently limit the usability of certain coins (which is less
destructive than burning them). But as Jeremy said, people are free to burn
their coins. People would also be free (in general) to reject coins
encumbered by weird government provisions or unknown provisions in hidden
scripts. A person/wallet shouldn't accept coins encumbered by scripts it
doesn't recognize.

Even if 99% of bitcoins became permanently encumbered by weird covenants,
the other 1% could still be plenty of bitcoins to run the economy, because
of its potentially infinite divisibility. Losing these coins, or someone
basically turning them into altcoin-like bitcoins shouldn't be a concern
really. What's the risk exactly? That people will be forced to take these
encumbered coins? A government can already force people to take whatever
altcoin they want to force on people - covenants don't make this worse.

Shinobi asks: "What if you extorted users with your 51% attack to move into
those?"

Well, you could do this anyway even without covenants existing already. The
51% attack could simply extort people to use whatever rules they want just
as easily (which isn't to say that easily - most users would probably
refuse to be extorted in either case). So I don't really think this is very
valid.

On Sun, Jul 4, 2021 at 1:33 PM David A. Harding via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> On Sun, Jul 04, 2021 at 11:39:44AM -0700, Jeremy wrote:
> > However, I think the broader community is unconvinced by the cost benefit
> > of arbitrary covenants. See
> >
> https://medium.com/block-digest-mempool/my-worries-about-too-generalized-covenants-5eff33affbb6
> > as a recent example. Therefore as a critical part of building consensus
> on
> > various techniques I've worked to emphasize that specific additions do
> not
> > entail risk of accidentally introducing more than was bargained for to
> > respect the concerns of others.
>
> Respecting the concerns of others doesn't require lobotomizing useful
> tools.  Being respectful can also be accomplished by politely showing
> that their concerns are unfounded (or at least less severe than they
> thought).  This is almost always the better course IMO---it takes much
> more effort to satisfy additional engineering constraints (and prove to
> reviewers that you've done so!) than it does to simply discuss those
> concerns with reasonable stakeholders.  As a demonstration, let's look
> at the concerns from Shinobi's post linked above:
>
> They seem to be worried that some Bitcoin users will choose to accept
> coins that can't subsequently be fungibily mixed with other bitcoins.
> But that's already been the case for a decade: users can accept altcoins
> that are non-fungible with bitcoins.
>
> They talk about covenants where spending is controlled by governments,
> but that seems to me exactly like China's CBDC trial.
>
> They talk about exchanges depositing users' BTC into a covenant, but
> that's just a variation on the classic not-your-keys-not-your-bitcoins
> problem.  For all you know, your local exchange is keeping most of its
> BTC balance commitments in ETH or USDT.
>
> To me, it seems like the worst-case problems Shinobi describes with
> covenants are some of the same problems that already exist with
> altcoins.  I don't see how recursive covenants could make any of those
> problems worse, and so I don't see any point in limiting Bitcoin's
> flexibility to avoid those problems when there are so many interesting
> and useful things that unlimited covenants could do.
>
> -Dave
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[ZmnSCPxj]

Good morning Dave,

> On Sun, Jul 04, 2021 at 11:39:44AM -0700, Jeremy wrote:
>
> > However, I think the broader community is unconvinced by the cost benefit
> > of arbitrary covenants. See
> > https://medium.com/block-digest-mempool/my-worries-about-too-generalized-covenants-5eff33affbb6
> > as a recent example. Therefore as a critical part of building consensus on
> > various techniques I've worked to emphasize that specific additions do not
> > entail risk of accidentally introducing more than was bargained for to
> > respect the concerns of others.
>
> Respecting the concerns of others doesn't require lobotomizing useful
> tools. Being respectful can also be accomplished by politely showing
> that their concerns are unfounded (or at least less severe than they
> thought). This is almost always the better course IMO---it takes much
> more effort to satisfy additional engineering constraints (and prove to
> reviewers that you've done so!) than it does to simply discuss those
> concerns with reasonable stakeholders. As a demonstration, let's look
> at the concerns from Shinobi's post linked above:
>
> They seem to be worried that some Bitcoin users will choose to accept
> coins that can't subsequently be fungibily mixed with other bitcoins.
> But that's already been the case for a decade: users can accept altcoins
> that are non-fungible with bitcoins.
>
> They talk about covenants where spending is controlled by governments,
> but that seems to me exactly like China's CBDC trial.
>
> They talk about exchanges depositing users' BTC into a covenant, but
> that's just a variation on the classic not-your-keys-not-your-bitcoins
> problem. For all you know, your local exchange is keeping most of its
> BTC balance commitments in ETH or USDT.
>
> To me, it seems like the worst-case problems Shinobi describes with
> covenants are some of the same problems that already exist with
> altcoins. I don't see how recursive covenants could make any of those
> problems worse, and so I don't see any point in limiting Bitcoin's
> flexibility to avoid those problems when there are so many interesting
> and useful things that unlimited covenants could do.

The "altcoins are even worse" argument does seem quite convincing, and if Bitcoin can survive altcoins, surely it can survive covenants too?

In before "turns out covenants are the next ICO".
i.e. ICOs are just colored coins, which are useful for keeping track of various stuff, but have then been used as a vehicle to scam people.
But I suppose that is a problem that humans will always have: limited cognition, so that *good* popular things that are outside your specific field of study are indistinguishable from *bad* popular things.
So perhaps it should not be a concern on a technical level.
Maybe we should instead make articles about covenants so boring nobody will hype about it (^^;)v.

Increased functionality implies increased processing, and hopefully computation devices are getting cheap enough that the increased processing implied by new features should not be too onerous.



To my mind, an "inescapable" covenant (i.e. one that requires the output to be paid to the same covenant) is basically a Turing machine, and equivalent to a `while (true);` loop.
In a `while (true);` loop, the state of the machine reverts back to the same state, and it repeats again.
In an inescpable covenant, the control of some amount of funds reverts back to the same controlling SCRIPT, and it repeats again.
Yes, you can certainly add more functionality on top of that loop, just think of program main loops for games or daemons, which are, in essence, "just" `while (true) ...`.
But basically, such unbounded infinite loops are possible only under Turing machines, thus I consider covenants to be Turing-complete.
Principle of Least Power should make us wonder if we need full Turing machines for the functionality.

On the other hand --- codata processing *does* allow for unbounded loops, without requiring full Turing-completeness; they just require total functionality, not partial (and Turing-completeness is partial, not total).
Basically, data structures are unbounded storage, while codata structures are unbounded processing.
Perhaps covenants can encode an upper bound on the number of recursions, which prevents full Turing-completeness while allowing for a large number of use-cases.

(if the above paragraph makes no sense to you, hopefully this Wikipedia article will help: https://en.wikipedia.org/wiki/Total_functional_programming )
(basically my argument here is based on academic programming stuff, and might not actually matter in real life)

Regards,
ZmnSCPxj

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[Russell O'Connor]

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

Bear in mind that when people are talking about enabling covenants, we are
talking about whether OP_CAT should be allowed or not.

That said, recursive covenants, the type that are most worrying, seems to
require some kind of OP_TWEAK operation, and I haven't yet seen any
evidence that this can be simulated with CHECKSIG(FROMSTACK).  So maybe we
should leave such worries for the OP_TWEAK operation.

On Sun, Jul 4, 2021 at 8:51 PM ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Good morning Dave,
>
> > On Sun, Jul 04, 2021 at 11:39:44AM -0700, Jeremy wrote:
> >
> > > However, I think the broader community is unconvinced by the cost
> benefit
> > > of arbitrary covenants. See
> > >
> https://medium.com/block-digest-mempool/my-worries-about-too-generalized-covenants-5eff33affbb6
> > > as a recent example. Therefore as a critical part of building
> consensus on
> > > various techniques I've worked to emphasize that specific additions do
> not
> > > entail risk of accidentally introducing more than was bargained for to
> > > respect the concerns of others.
> >
> > Respecting the concerns of others doesn't require lobotomizing useful
> > tools. Being respectful can also be accomplished by politely showing
> > that their concerns are unfounded (or at least less severe than they
> > thought). This is almost always the better course IMO---it takes much
> > more effort to satisfy additional engineering constraints (and prove to
> > reviewers that you've done so!) than it does to simply discuss those
> > concerns with reasonable stakeholders. As a demonstration, let's look
> > at the concerns from Shinobi's post linked above:
> >
> > They seem to be worried that some Bitcoin users will choose to accept
> > coins that can't subsequently be fungibily mixed with other bitcoins.
> > But that's already been the case for a decade: users can accept altcoins
> > that are non-fungible with bitcoins.
> >
> > They talk about covenants where spending is controlled by governments,
> > but that seems to me exactly like China's CBDC trial.
> >
> > They talk about exchanges depositing users' BTC into a covenant, but
> > that's just a variation on the classic not-your-keys-not-your-bitcoins
> > problem. For all you know, your local exchange is keeping most of its
> > BTC balance commitments in ETH or USDT.
> >
> > To me, it seems like the worst-case problems Shinobi describes with
> > covenants are some of the same problems that already exist with
> > altcoins. I don't see how recursive covenants could make any of those
> > problems worse, and so I don't see any point in limiting Bitcoin's
> > flexibility to avoid those problems when there are so many interesting
> > and useful things that unlimited covenants could do.
>
> The "altcoins are even worse" argument does seem quite convincing, and if
> Bitcoin can survive altcoins, surely it can survive covenants too?
>
> In before "turns out covenants are the next ICO".
> i.e. ICOs are just colored coins, which are useful for keeping track of
> various stuff, but have then been used as a vehicle to scam people.
> But I suppose that is a problem that humans will always have: limited
> cognition, so that *good* popular things that are outside your specific
> field of study are indistinguishable from *bad* popular things.
> So perhaps it should not be a concern on a technical level.
> Maybe we should instead make articles about covenants so boring nobody
> will hype about it (^^;)v.
>
> Increased functionality implies increased processing, and hopefully
> computation devices are getting cheap enough that the increased processing
> implied by new features should not be too onerous.
>
>
>
> To my mind, an "inescapable" covenant (i.e. one that requires the output
> to be paid to the same covenant) is basically a Turing machine, and
> equivalent to a `while (true);` loop.
> In a `while (true);` loop, the state of the machine reverts back to the
> same state, and it repeats again.
> In an inescpable covenant, the control of some amount of funds reverts
> back to the same controlling SCRIPT, and it repeats again.
> Yes, you can certainly add more functionality on top of that loop, just
> think of program main loops for games or daemons, which are, in essence,
> "just" `while (true) ...`.
> But basically, such unbounded infinite loops are possible only under
> Turing machines, thus I consider covenants to be Turing-complete.
> Principle of Least Power should make us wonder if we need full Turing
> machines for the functionality.
>
> On the other hand --- codata processing *does* allow for unbounded loops,
> without requiring full Turing-completeness; they just require total
> functionality, not partial (and Turing-completeness is partial, not total).
> Basically, data structures are unbounded storage, while codata structures
> are unbounded processing.
> Perhaps covenants can encode an upper bound on the number of recursions,
> which prevents full Turing-completeness while allowing for a large number
> of use-cases.
>
> (if the above paragraph makes no sense to you, hopefully this Wikipedia
> article will help:
> https://en.wikipedia.org/wiki/Total_functional_programming )
> (basically my argument here is based on academic programming stuff, and
> might not actually matter in real life)
>
> Regards,
> ZmnSCPxj
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[Russell O'Connor]

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

On Sun, Jul 4, 2021 at 9:02 PM Russell O'Connor <roconnor@blockstream.com>
wrote:

> Bear in mind that when people are talking about enabling covenants, we are
> talking about whether OP_CAT should be allowed or not.
>
> That said, recursive covenants, the type that are most worrying, seems to
> require some kind of OP_TWEAK operation, and I haven't yet seen any
> evidence that this can be simulated with CHECKSIG(FROMSTACK).  So maybe we
> should leave such worries for the OP_TWEAK operation.
>

Upon further thought, you can probably make recursive covenants even with a
fixed scritpubkey by sneaking the state into a few bits of the UTXO's
amount.  Or if you try really hard, you may be able to stash your state
into a sibling output that is accessed via the txid embedded in the
prevoutpoint.

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

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[ZmnSCPxj]

Good morning Russell,


> On Sun, Jul 4, 2021 at 9:02 PM Russell O'Connor <roconnor@blockstream.com> wrote:
>
> > Bear in mind that when people are talking about enabling covenants, we are talking about whether OP_CAT should be allowed or not.
> >
> > That said, recursive covenants, the type that are most worrying, seems to require some kind of OP_TWEAK operation, and I haven't yet seen any evidence that this can be simulated with CHECKSIG(FROMSTACK).  So maybe we should leave such worries for the OP_TWEAK operation.
>
> Upon further thought, you can probably make recursive covenants even with a fixed scritpubkey by sneaking the state into a few bits of the UTXO's amount.  Or if you try really hard, you may be able to stash your state into a sibling output that is accessed via the txid embedded in the prevoutpoint.

Which is kind of the point of avoiding giving too much power, because people can be very clever and start doing unexpected things from what you think is already a limited subset.
"Give an inch and they will take a mile".

Still, as pointed out, altcoins already exist and are substantially worse, and altcoin implementations are all going to run on Turing machines anyway (which are powerful enough to offer Turing-machine functionality), so maybe this is not really giving too much power, people can already fork Bitcoin and add full EVM support on it.

Regards,
ZmnSCPxj

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[Anthony Towns]

On Sun, Jul 04, 2021 at 09:02:25PM -0400, Russell O'Connor via bitcoin-dev wrote:
> Bear in mind that when people are talking about enabling covenants, we are
> talking about whether OP_CAT should be allowed or not.

In some sense multisig *alone* enables recursive covenants: a government
that wants to enforce KYC can require that funds be deposited into
a multisig of "2 <recipient> <gov_key> 2 CHECKMULTISIG", and that
"recipient" has gone through KYC. Once deposited to such an address,
the gov can refus to sign with gov_key unless the funds are being spent
to a new address that follows the same rules.

(That's also more efficient than an explicit covenant since it's all
off-chain -- recipient/gov_key can jointly sign via taproot/MuSig at
that point, so that full nodes are only validating a single pubkey and
signature per spend, rather than having to do analysis of whatever the
underlying covenant is supposed to be [0])

This is essentially what Liquid already does -- it locks bitcoins into
a multisig and enforces an "off-chain" covenant that those bitcoins can
only be redeemed after some valid set of signatures are entered into
the Liquid blockchain. Likewise for the various BTC-on-Ethereum tokens.
To some extent, likewise for coins held in exchanges/custodial wallets
where funds can be transferred between customers off-chain.

You can "escape" from that recursive covenant by having the government
(or Liquid functionaries, or exchange admins) change their signing
policy of course; but you could equally escape any consensus-enforced
covenant by having a hard fork to stop doing consensus-enforcement (cf
ETH Classic?). To me, that looks more like a difference of procedure
and difficulty, rather than a fundamental difference in kind.

Cheers,
aj

[0] https://twitter.com/pwuille/status/1411533549224693762

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[Matt Corallo]

I find this point to be incredibly important. Indeed I, like several others, have historically been concerned with 
covenants in the unbounded form. However, as more and more research has been done in what they can accomplish, the 
weighting of such arguments naturally has to be reduced. More importantly, AJ's point here neuters anti-covanent 
arguments rather strongly.

Matt

On 7/5/21 01:04, Anthony Towns via bitcoin-dev wrote:
> On Sun, Jul 04, 2021 at 09:02:25PM -0400, Russell O'Connor via bitcoin-dev wrote:
>> Bear in mind that when people are talking about enabling covenants, we are
>> talking about whether OP_CAT should be allowed or not.
> 
> In some sense multisig *alone* enables recursive covenants: a government
> that wants to enforce KYC can require that funds be deposited into
> a multisig of "2 <recipient> <gov_key> 2 CHECKMULTISIG", and that
> "recipient" has gone through KYC. Once deposited to such an address,
> the gov can refus to sign with gov_key unless the funds are being spent
> to a new address that follows the same rules.
> 
> (That's also more efficient than an explicit covenant since it's all
> off-chain -- recipient/gov_key can jointly sign via taproot/MuSig at
> that point, so that full nodes are only validating a single pubkey and
> signature per spend, rather than having to do analysis of whatever the
> underlying covenant is supposed to be [0])
> 
> This is essentially what Liquid already does -- it locks bitcoins into
> a multisig and enforces an "off-chain" covenant that those bitcoins can
> only be redeemed after some valid set of signatures are entered into
> the Liquid blockchain. Likewise for the various BTC-on-Ethereum tokens.
> To some extent, likewise for coins held in exchanges/custodial wallets
> where funds can be transferred between customers off-chain.
> 
> You can "escape" from that recursive covenant by having the government
> (or Liquid functionaries, or exchange admins) change their signing
> policy of course; but you could equally escape any consensus-enforced
> covenant by having a hard fork to stop doing consensus-enforcement (cf
> ETH Classic?). To me, that looks more like a difference of procedure
> and difficulty, rather than a fundamental difference in kind.
> 
> Cheers,
> aj
> 
> [0] https://twitter.com/pwuille/status/1411533549224693762
> 
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> 

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[Greg Sanders]

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

Funny AJ mentions the multisig idea, because I know for a fact it's being
used in certain permissioned systems in this exact way. Regulators will
dream up these ideas with or without more useful covenants!

On Mon, Jul 5, 2021 at 9:46 PM Matt Corallo via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> I find this point to be incredibly important. Indeed I, like several
> others, have historically been concerned with
> covenants in the unbounded form. However, as more and more research has
> been done in what they can accomplish, the
> weighting of such arguments naturally has to be reduced. More importantly,
> AJ's point here neuters anti-covanent
> arguments rather strongly.
>
> Matt
>
> On 7/5/21 01:04, Anthony Towns via bitcoin-dev wrote:
> > On Sun, Jul 04, 2021 at 09:02:25PM -0400, Russell O'Connor via
> bitcoin-dev wrote:
> >> Bear in mind that when people are talking about enabling covenants, we
> are
> >> talking about whether OP_CAT should be allowed or not.
> >
> > In some sense multisig *alone* enables recursive covenants: a government
> > that wants to enforce KYC can require that funds be deposited into
> > a multisig of "2 <recipient> <gov_key> 2 CHECKMULTISIG", and that
> > "recipient" has gone through KYC. Once deposited to such an address,
> > the gov can refus to sign with gov_key unless the funds are being spent
> > to a new address that follows the same rules.
> >
> > (That's also more efficient than an explicit covenant since it's all
> > off-chain -- recipient/gov_key can jointly sign via taproot/MuSig at
> > that point, so that full nodes are only validating a single pubkey and
> > signature per spend, rather than having to do analysis of whatever the
> > underlying covenant is supposed to be [0])
> >
> > This is essentially what Liquid already does -- it locks bitcoins into
> > a multisig and enforces an "off-chain" covenant that those bitcoins can
> > only be redeemed after some valid set of signatures are entered into
> > the Liquid blockchain. Likewise for the various BTC-on-Ethereum tokens.
> > To some extent, likewise for coins held in exchanges/custodial wallets
> > where funds can be transferred between customers off-chain.
> >
> > You can "escape" from that recursive covenant by having the government
> > (or Liquid functionaries, or exchange admins) change their signing
> > policy of course; but you could equally escape any consensus-enforced
> > covenant by having a hard fork to stop doing consensus-enforcement (cf
> > ETH Classic?). To me, that looks more like a difference of procedure
> > and difficulty, rather than a fundamental difference in kind.
> >
> > Cheers,
> > aj
> >
> > [0] https://twitter.com/pwuille/status/1411533549224693762
> >
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> >
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[Anthony Towns]

On Mon, Jul 05, 2021 at 09:46:21AM -0400, Matt Corallo via bitcoin-dev wrote:
> More importantly, AJ's point here neuters anti-covanent arguments rather
> strongly.
>
> On 7/5/21 01:04, Anthony Towns via bitcoin-dev wrote:
> > In some sense multisig *alone* enables recursive covenants: a government
> > that wants to enforce KYC can require that funds be deposited into
> > a multisig of "2 <recipient> <gov_key> 2 CHECKMULTISIG", and that
> > "recipient" has gone through KYC. Once deposited to such an address,
> > the gov can refus to sign with gov_key unless the funds are being spent
> > to a new address that follows the same rules.

I couldn't remember where I'd heard this, but it looks like I came
across it via Andrew Poelstra's "CAT and Schnorr Tricks II" post [0]
(Feb 2021), in which he credits Ethan Heilman for originally coming up
with the analogy (in 2019, cf [1]).

[0] https://medium.com/blockstream/cat-and-schnorr-tricks-ii-2f6ede3d7bb5
[1] https://twitter.com/Ethan_Heilman/status/1194624166093369345

Cheers,
aj

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[Russell O'Connor]

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

Hi ZmnSCPxj,

I don't believe we need to ban Turing completeness for the sake of banning
Turing completeness.  My concerns have always been around ensuring that
transaction and block validation is not unduly burdensome for nodes.  So
for Bitcoin Script, we want to bound the amount of resources needed to
execute it, preferably as a linear function of weight[1], and preferably
have it clear what the evaluation costs are going to be prior to
evaluation[2].  We also want to keep Script execution as a pure function of
the transaction data so that nodes do not need to reevaluate their mempool
on every new block.  For consensus purposes we prefer to have simple
primitive operations that have clear and precise semantics that are as
likely as possible to be reimplemented correctly if they are reimplemented
(or at least let us not make this problem worse than it already is).  In
particular, Script needs to be easy to parse to avoid weird parsing
machines that lead to security vulnerabilities within node software.

While the above design constraints imply a prohibition on Turing complete
computation within a single Script, they do not imply a prohibition on
arbitrary, covenant-enabled computations that spans across multiple
transactions.  Neither would these constraints prohibit some kind of STARK
or SNARK tapleaf version that was somehow capable of succinctly
representing arbitrary computations, so long as validation costs remain
bounded.

And while it is true that covenant-enabled computations could allow users
to put their funds at risk through weird machines that manipulate their
money on the blockchain, as longs as that weirdness stays at that level of
the abstract Bitcoin Script machine, then I suppose it is *caveat emptor*;
don't send your funds to random unverified Bitcoin Scripts, advice that is
already the case today.  We can keep that potential weirdness at bay by
keeping Script simple, and maintaining our understanding that the Script
programs (like the rest of the blockchain data) are untrusted inputs and
they need to be validated and scrutinized before interpretation.

[1] In tapscript I believe all operations are linear time with the
exception of OP_ROLL.  However OP_ROLL is still constrained by global
limits on stack size, etc.
[2] In Bitcoin Script, without loops of any kind, every opcode is evaluated
at most once, so counting opcodes is an easy way to put an upper bound on
your costs before evaluation.

On Sun, Jul 4, 2021 at 8:51 PM ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Good morning Dave,
>
> > On Sun, Jul 04, 2021 at 11:39:44AM -0700, Jeremy wrote:
> >
> > > However, I think the broader community is unconvinced by the cost
> benefit
> > > of arbitrary covenants. See
> > >
> https://medium.com/block-digest-mempool/my-worries-about-too-generalized-covenants-5eff33affbb6
> > > as a recent example. Therefore as a critical part of building
> consensus on
> > > various techniques I've worked to emphasize that specific additions do
> not
> > > entail risk of accidentally introducing more than was bargained for to
> > > respect the concerns of others.
> >
> > Respecting the concerns of others doesn't require lobotomizing useful
> > tools. Being respectful can also be accomplished by politely showing
> > that their concerns are unfounded (or at least less severe than they
> > thought). This is almost always the better course IMO---it takes much
> > more effort to satisfy additional engineering constraints (and prove to
> > reviewers that you've done so!) than it does to simply discuss those
> > concerns with reasonable stakeholders. As a demonstration, let's look
> > at the concerns from Shinobi's post linked above:
> >
> > They seem to be worried that some Bitcoin users will choose to accept
> > coins that can't subsequently be fungibily mixed with other bitcoins.
> > But that's already been the case for a decade: users can accept altcoins
> > that are non-fungible with bitcoins.
> >
> > They talk about covenants where spending is controlled by governments,
> > but that seems to me exactly like China's CBDC trial.
> >
> > They talk about exchanges depositing users' BTC into a covenant, but
> > that's just a variation on the classic not-your-keys-not-your-bitcoins
> > problem. For all you know, your local exchange is keeping most of its
> > BTC balance commitments in ETH or USDT.
> >
> > To me, it seems like the worst-case problems Shinobi describes with
> > covenants are some of the same problems that already exist with
> > altcoins. I don't see how recursive covenants could make any of those
> > problems worse, and so I don't see any point in limiting Bitcoin's
> > flexibility to avoid those problems when there are so many interesting
> > and useful things that unlimited covenants could do.
>
> The "altcoins are even worse" argument does seem quite convincing, and if
> Bitcoin can survive altcoins, surely it can survive covenants too?
>
> In before "turns out covenants are the next ICO".
> i.e. ICOs are just colored coins, which are useful for keeping track of
> various stuff, but have then been used as a vehicle to scam people.
> But I suppose that is a problem that humans will always have: limited
> cognition, so that *good* popular things that are outside your specific
> field of study are indistinguishable from *bad* popular things.
> So perhaps it should not be a concern on a technical level.
> Maybe we should instead make articles about covenants so boring nobody
> will hype about it (^^;)v.
>
> Increased functionality implies increased processing, and hopefully
> computation devices are getting cheap enough that the increased processing
> implied by new features should not be too onerous.
>
>
>
> To my mind, an "inescapable" covenant (i.e. one that requires the output
> to be paid to the same covenant) is basically a Turing machine, and
> equivalent to a `while (true);` loop.
> In a `while (true);` loop, the state of the machine reverts back to the
> same state, and it repeats again.
> In an inescpable covenant, the control of some amount of funds reverts
> back to the same controlling SCRIPT, and it repeats again.
> Yes, you can certainly add more functionality on top of that loop, just
> think of program main loops for games or daemons, which are, in essence,
> "just" `while (true) ...`.
> But basically, such unbounded infinite loops are possible only under
> Turing machines, thus I consider covenants to be Turing-complete.
> Principle of Least Power should make us wonder if we need full Turing
> machines for the functionality.
>
> On the other hand --- codata processing *does* allow for unbounded loops,
> without requiring full Turing-completeness; they just require total
> functionality, not partial (and Turing-completeness is partial, not total).
> Basically, data structures are unbounded storage, while codata structures
> are unbounded processing.
> Perhaps covenants can encode an upper bound on the number of recursions,
> which prevents full Turing-completeness while allowing for a large number
> of use-cases.
>
> (if the above paragraph makes no sense to you, hopefully this Wikipedia
> article will help:
> https://en.wikipedia.org/wiki/Total_functional_programming )
> (basically my argument here is based on academic programming stuff, and
> might not actually matter in real life)
>
> Regards,
> ZmnSCPxj
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[Billy Tetrud]

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

>  when people are talking about enabling covenants, we are talking about
whether OP_CAT should be allowed or not

Are they? Are you implying that anything that enables covenants is
equivalent to enabling OP_CAT? Generally when I think about enabling
covenants, I'm thinking more about OP_CTV (or some similarly specific opcode
<https://github.com/fresheneesz/bip-efficient-bitcoin-vaults/blob/main/bip-constraindestination.md>
).

> OP_TWEAK

I wasn't able to find anything about what that is. Would you mind
clarifying what that concept is?

On Mon, Jul 5, 2021 at 10:20 AM Russell O'Connor via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hi ZmnSCPxj,
>
> I don't believe we need to ban Turing completeness for the sake of banning
> Turing completeness.  My concerns have always been around ensuring that
> transaction and block validation is not unduly burdensome for nodes.  So
> for Bitcoin Script, we want to bound the amount of resources needed to
> execute it, preferably as a linear function of weight[1], and preferably
> have it clear what the evaluation costs are going to be prior to
> evaluation[2].  We also want to keep Script execution as a pure function of
> the transaction data so that nodes do not need to reevaluate their mempool
> on every new block.  For consensus purposes we prefer to have simple
> primitive operations that have clear and precise semantics that are as
> likely as possible to be reimplemented correctly if they are reimplemented
> (or at least let us not make this problem worse than it already is).  In
> particular, Script needs to be easy to parse to avoid weird parsing
> machines that lead to security vulnerabilities within node software.
>
> While the above design constraints imply a prohibition on Turing complete
> computation within a single Script, they do not imply a prohibition on
> arbitrary, covenant-enabled computations that spans across multiple
> transactions.  Neither would these constraints prohibit some kind of STARK
> or SNARK tapleaf version that was somehow capable of succinctly
> representing arbitrary computations, so long as validation costs remain
> bounded.
>
> And while it is true that covenant-enabled computations could allow users
> to put their funds at risk through weird machines that manipulate their
> money on the blockchain, as longs as that weirdness stays at that level of
> the abstract Bitcoin Script machine, then I suppose it is *caveat emptor*;
> don't send your funds to random unverified Bitcoin Scripts, advice that is
> already the case today.  We can keep that potential weirdness at bay by
> keeping Script simple, and maintaining our understanding that the Script
> programs (like the rest of the blockchain data) are untrusted inputs and
> they need to be validated and scrutinized before interpretation.
>
> [1] In tapscript I believe all operations are linear time with the
> exception of OP_ROLL.  However OP_ROLL is still constrained by global
> limits on stack size, etc.
> [2] In Bitcoin Script, without loops of any kind, every opcode is
> evaluated at most once, so counting opcodes is an easy way to put an upper
> bound on your costs before evaluation.
>
> On Sun, Jul 4, 2021 at 8:51 PM ZmnSCPxj via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> Good morning Dave,
>>
>> > On Sun, Jul 04, 2021 at 11:39:44AM -0700, Jeremy wrote:
>> >
>> > > However, I think the broader community is unconvinced by the cost
>> benefit
>> > > of arbitrary covenants. See
>> > >
>> https://medium.com/block-digest-mempool/my-worries-about-too-generalized-covenants-5eff33affbb6
>> > > as a recent example. Therefore as a critical part of building
>> consensus on
>> > > various techniques I've worked to emphasize that specific additions
>> do not
>> > > entail risk of accidentally introducing more than was bargained for to
>> > > respect the concerns of others.
>> >
>> > Respecting the concerns of others doesn't require lobotomizing useful
>> > tools. Being respectful can also be accomplished by politely showing
>> > that their concerns are unfounded (or at least less severe than they
>> > thought). This is almost always the better course IMO---it takes much
>> > more effort to satisfy additional engineering constraints (and prove to
>> > reviewers that you've done so!) than it does to simply discuss those
>> > concerns with reasonable stakeholders. As a demonstration, let's look
>> > at the concerns from Shinobi's post linked above:
>> >
>> > They seem to be worried that some Bitcoin users will choose to accept
>> > coins that can't subsequently be fungibily mixed with other bitcoins.
>> > But that's already been the case for a decade: users can accept altcoins
>> > that are non-fungible with bitcoins.
>> >
>> > They talk about covenants where spending is controlled by governments,
>> > but that seems to me exactly like China's CBDC trial.
>> >
>> > They talk about exchanges depositing users' BTC into a covenant, but
>> > that's just a variation on the classic not-your-keys-not-your-bitcoins
>> > problem. For all you know, your local exchange is keeping most of its
>> > BTC balance commitments in ETH or USDT.
>> >
>> > To me, it seems like the worst-case problems Shinobi describes with
>> > covenants are some of the same problems that already exist with
>> > altcoins. I don't see how recursive covenants could make any of those
>> > problems worse, and so I don't see any point in limiting Bitcoin's
>> > flexibility to avoid those problems when there are so many interesting
>> > and useful things that unlimited covenants could do.
>>
>> The "altcoins are even worse" argument does seem quite convincing, and if
>> Bitcoin can survive altcoins, surely it can survive covenants too?
>>
>> In before "turns out covenants are the next ICO".
>> i.e. ICOs are just colored coins, which are useful for keeping track of
>> various stuff, but have then been used as a vehicle to scam people.
>> But I suppose that is a problem that humans will always have: limited
>> cognition, so that *good* popular things that are outside your specific
>> field of study are indistinguishable from *bad* popular things.
>> So perhaps it should not be a concern on a technical level.
>> Maybe we should instead make articles about covenants so boring nobody
>> will hype about it (^^;)v.
>>
>> Increased functionality implies increased processing, and hopefully
>> computation devices are getting cheap enough that the increased processing
>> implied by new features should not be too onerous.
>>
>>
>>
>> To my mind, an "inescapable" covenant (i.e. one that requires the output
>> to be paid to the same covenant) is basically a Turing machine, and
>> equivalent to a `while (true);` loop.
>> In a `while (true);` loop, the state of the machine reverts back to the
>> same state, and it repeats again.
>> In an inescpable covenant, the control of some amount of funds reverts
>> back to the same controlling SCRIPT, and it repeats again.
>> Yes, you can certainly add more functionality on top of that loop, just
>> think of program main loops for games or daemons, which are, in essence,
>> "just" `while (true) ...`.
>> But basically, such unbounded infinite loops are possible only under
>> Turing machines, thus I consider covenants to be Turing-complete.
>> Principle of Least Power should make us wonder if we need full Turing
>> machines for the functionality.
>>
>> On the other hand --- codata processing *does* allow for unbounded loops,
>> without requiring full Turing-completeness; they just require total
>> functionality, not partial (and Turing-completeness is partial, not total).
>> Basically, data structures are unbounded storage, while codata structures
>> are unbounded processing.
>> Perhaps covenants can encode an upper bound on the number of recursions,
>> which prevents full Turing-completeness while allowing for a large number
>> of use-cases.
>>
>> (if the above paragraph makes no sense to you, hopefully this Wikipedia
>> article will help:
>> https://en.wikipedia.org/wiki/Total_functional_programming )
>> (basically my argument here is based on academic programming stuff, and
>> might not actually matter in real life)
>>
>> Regards,
>> ZmnSCPxj
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[Sanket Kanjalkar]

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

After some brainstorming about the possible drawbacks of enabling
covenants, I have also slowly become more comfortable with the idea of
"unlimited" covenants. AJs example clearly shows that _all_ possible
"misuses" of covenants are already possible by Multi-Sig today, so it's not
a new vector that we are adding today.

>  My concerns have always been around ensuring that transaction and block
validation is not unduly burdensome for nodes.  So for Bitcoin Script, we
want to bound the amount of resources needed to execute it, preferably as a
linear function of weight[1], and preferably have it clear what the
evaluation costs are going to be prior to evaluation[2].  We also want to
keep Script execution as a pure function of the transaction data so that
nodes do not need to reevaluate their mempool on every new block.

Many bitcoin upgrades, in particular, Segwit, and tapscript sigops budget
have been along with the same principle. And as mentioned before, none of
these go against enabling recursive covenants.

> Are they? Are you implying that anything that enables covenants is
equivalent to enabling OP_CAT?

No, it is not equivalent. Russell is referring to a way to do covenants by
only using `OP_CAT`(along with Schnorr sigs that we already have) as
mentioned by Andrew Poelstra here
<https://medium.com/blockstream/cat-and-schnorr-tricks-i-faf1b59bd298> .

I also am in general support of the `OP_CHECKSIGFROMSTACK` opcode. We would
need to update the suggestion to BIP340, and add it to sigops budget. I
have no strong preference for splitting R and s values or variable-length
messages.


On Tue, Jul 6, 2021 at 1:36 AM Billy Tetrud via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> >  when people are talking about enabling covenants, we are talking about
> whether OP_CAT should be allowed or not
>
> Are they? Are you implying that anything that enables covenants is
> equivalent to enabling OP_CAT? Generally when I think about enabling
> covenants, I'm thinking more about OP_CTV (or some similarly specific
> opcode
> <https://github.com/fresheneesz/bip-efficient-bitcoin-vaults/blob/main/bip-constraindestination.md>
> ).
>
> > OP_TWEAK
>
> I wasn't able to find anything about what that is. Would you mind
> clarifying what that concept is?
>
> On Mon, Jul 5, 2021 at 10:20 AM Russell O'Connor via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> Hi ZmnSCPxj,
>>
>> I don't believe we need to ban Turing completeness for the sake of
>> banning Turing completeness.  My concerns have always been around ensuring
>> that transaction and block validation is not unduly burdensome for nodes.
>> So for Bitcoin Script, we want to bound the amount of resources needed to
>> execute it, preferably as a linear function of weight[1], and preferably
>> have it clear what the evaluation costs are going to be prior to
>> evaluation[2].  We also want to keep Script execution as a pure function of
>> the transaction data so that nodes do not need to reevaluate their mempool
>> on every new block.  For consensus purposes we prefer to have simple
>> primitive operations that have clear and precise semantics that are as
>> likely as possible to be reimplemented correctly if they are reimplemented
>> (or at least let us not make this problem worse than it already is).  In
>> particular, Script needs to be easy to parse to avoid weird parsing
>> machines that lead to security vulnerabilities within node software.
>>
>> While the above design constraints imply a prohibition on Turing complete
>> computation within a single Script, they do not imply a prohibition on
>> arbitrary, covenant-enabled computations that spans across multiple
>> transactions.  Neither would these constraints prohibit some kind of STARK
>> or SNARK tapleaf version that was somehow capable of succinctly
>> representing arbitrary computations, so long as validation costs remain
>> bounded.
>>
>> And while it is true that covenant-enabled computations could allow users
>> to put their funds at risk through weird machines that manipulate their
>> money on the blockchain, as longs as that weirdness stays at that level of
>> the abstract Bitcoin Script machine, then I suppose it is *caveat emptor*;
>> don't send your funds to random unverified Bitcoin Scripts, advice that is
>> already the case today.  We can keep that potential weirdness at bay by
>> keeping Script simple, and maintaining our understanding that the Script
>> programs (like the rest of the blockchain data) are untrusted inputs and
>> they need to be validated and scrutinized before interpretation.
>>
>> [1] In tapscript I believe all operations are linear time with the
>> exception of OP_ROLL.  However OP_ROLL is still constrained by global
>> limits on stack size, etc.
>> [2] In Bitcoin Script, without loops of any kind, every opcode is
>> evaluated at most once, so counting opcodes is an easy way to put an upper
>> bound on your costs before evaluation.
>>
>> On Sun, Jul 4, 2021 at 8:51 PM ZmnSCPxj via bitcoin-dev <
>> bitcoin-dev@lists.linuxfoundation.org> wrote:
>>
>>> Good morning Dave,
>>>
>>> > On Sun, Jul 04, 2021 at 11:39:44AM -0700, Jeremy wrote:
>>> >
>>> > > However, I think the broader community is unconvinced by the cost
>>> benefit
>>> > > of arbitrary covenants. See
>>> > >
>>> https://medium.com/block-digest-mempool/my-worries-about-too-generalized-covenants-5eff33affbb6
>>> > > as a recent example. Therefore as a critical part of building
>>> consensus on
>>> > > various techniques I've worked to emphasize that specific additions
>>> do not
>>> > > entail risk of accidentally introducing more than was bargained for
>>> to
>>> > > respect the concerns of others.
>>> >
>>> > Respecting the concerns of others doesn't require lobotomizing useful
>>> > tools. Being respectful can also be accomplished by politely showing
>>> > that their concerns are unfounded (or at least less severe than they
>>> > thought). This is almost always the better course IMO---it takes much
>>> > more effort to satisfy additional engineering constraints (and prove to
>>> > reviewers that you've done so!) than it does to simply discuss those
>>> > concerns with reasonable stakeholders. As a demonstration, let's look
>>> > at the concerns from Shinobi's post linked above:
>>> >
>>> > They seem to be worried that some Bitcoin users will choose to accept
>>> > coins that can't subsequently be fungibily mixed with other bitcoins.
>>> > But that's already been the case for a decade: users can accept
>>> altcoins
>>> > that are non-fungible with bitcoins.
>>> >
>>> > They talk about covenants where spending is controlled by governments,
>>> > but that seems to me exactly like China's CBDC trial.
>>> >
>>> > They talk about exchanges depositing users' BTC into a covenant, but
>>> > that's just a variation on the classic not-your-keys-not-your-bitcoins
>>> > problem. For all you know, your local exchange is keeping most of its
>>> > BTC balance commitments in ETH or USDT.
>>> >
>>> > To me, it seems like the worst-case problems Shinobi describes with
>>> > covenants are some of the same problems that already exist with
>>> > altcoins. I don't see how recursive covenants could make any of those
>>> > problems worse, and so I don't see any point in limiting Bitcoin's
>>> > flexibility to avoid those problems when there are so many interesting
>>> > and useful things that unlimited covenants could do.
>>>
>>> The "altcoins are even worse" argument does seem quite convincing, and
>>> if Bitcoin can survive altcoins, surely it can survive covenants too?
>>>
>>> In before "turns out covenants are the next ICO".
>>> i.e. ICOs are just colored coins, which are useful for keeping track of
>>> various stuff, but have then been used as a vehicle to scam people.
>>> But I suppose that is a problem that humans will always have: limited
>>> cognition, so that *good* popular things that are outside your specific
>>> field of study are indistinguishable from *bad* popular things.
>>> So perhaps it should not be a concern on a technical level.
>>> Maybe we should instead make articles about covenants so boring nobody
>>> will hype about it (^^;)v.
>>>
>>> Increased functionality implies increased processing, and hopefully
>>> computation devices are getting cheap enough that the increased processing
>>> implied by new features should not be too onerous.
>>>
>>>
>>>
>>> To my mind, an "inescapable" covenant (i.e. one that requires the output
>>> to be paid to the same covenant) is basically a Turing machine, and
>>> equivalent to a `while (true);` loop.
>>> In a `while (true);` loop, the state of the machine reverts back to the
>>> same state, and it repeats again.
>>> In an inescpable covenant, the control of some amount of funds reverts
>>> back to the same controlling SCRIPT, and it repeats again.
>>> Yes, you can certainly add more functionality on top of that loop, just
>>> think of program main loops for games or daemons, which are, in essence,
>>> "just" `while (true) ...`.
>>> But basically, such unbounded infinite loops are possible only under
>>> Turing machines, thus I consider covenants to be Turing-complete.
>>> Principle of Least Power should make us wonder if we need full Turing
>>> machines for the functionality.
>>>
>>> On the other hand --- codata processing *does* allow for unbounded
>>> loops, without requiring full Turing-completeness; they just require total
>>> functionality, not partial (and Turing-completeness is partial, not total).
>>> Basically, data structures are unbounded storage, while codata
>>> structures are unbounded processing.
>>> Perhaps covenants can encode an upper bound on the number of recursions,
>>> which prevents full Turing-completeness while allowing for a large number
>>> of use-cases.
>>>
>>> (if the above paragraph makes no sense to you, hopefully this Wikipedia
>>> article will help:
>>> https://en.wikipedia.org/wiki/Total_functional_programming )
>>> (basically my argument here is based on academic programming stuff, and
>>> might not actually matter in real life)
>>>
>>> Regards,
>>> ZmnSCPxj
>>> _______________________________________________
>>> bitcoin-dev mailing list
>>> bitcoin-dev@lists.linuxfoundation.org
>>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>>
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>


-- 
Sanket Kanjalkar

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

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[Russell O'Connor]

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

On Tue, Jul 6, 2021 at 2:26 AM Billy Tetrud <billy.tetrud@gmail.com> wrote:

> >  when people are talking about enabling covenants, we are talking about
> whether OP_CAT should be allowed or not
>
> Are they? Are you implying that anything that enables covenants is
> equivalent to enabling OP_CAT? Generally when I think about enabling
> covenants, I'm thinking more about OP_CTV (or some similarly specific
> opcode
> <https://github.com/fresheneesz/bip-efficient-bitcoin-vaults/blob/main/bip-constraindestination.md>
> ).
>
> > OP_TWEAK
>
> I wasn't able to find anything about what that is. Would you mind
> clarifying what that concept is?
>

In tapscript one can generally recover the current input's scriptPubkey
through sighash introspection via the usual covenant tricks.  This allows
you to make a recursive covenant by spending funds back to the same
identical scriptPubkey.  However, in order for a recursive covenant to be
actually interesting, there needs to be some sort of state update in each
transition.  If there is no state update then sending funds back to itself
is of very limited value.  It will reset the timer on relative locks, but
that is about all.

The "normal" way of writing useful recursive covenants is to modify the
scriptPubkey by changing a fragment of it that contains some sort of
state.  However in order to update a tapscript pubkey one needs to apply
not only hashing, to create a Merkel root, but also to create a tweaked
taproot pubkey that commits to this root.  While script currently comes
with a SHA-256 hashing opcode, there is no opcode that will let you perform
the necessary tweaking to create a taproot scriptPubkey.

But as I mentioned afterwards, there are other places in the UTXO that you
could put data in order to perform a state update.

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

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[Jeremy]

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

heh -- I pointed out these evil multisig covenants in 2015 :)
https://medium.com/@jeremyrubin/regulating-bitcoin-by-mining-the-regulator-miner-attack-c8fd51185b78
I'm relatively unconcerned by it except to the extent that mining
centralizes to the point of censoring other traffic.

Overall, I think this is a great conversation to be having.

However, I want to push back on David's claim that  "Respecting the
concerns of others doesn't require lobotomizing useful tools.".

CHECKSIGFROMSTACK is a primitive and the opcode is not being nerfed in any
way shape or form. The argument here is that doing CSFS and not CAT is
nerfing CSFS... but CSFS is an independently useful and cool opcode that
has many of it's own merits.

Further, as described in my [blog post](
https://rubin.io/blog/2021/07/02/covenants/), CSFS has very high "design
specificity"... that is there's not *that* many design choices that could
possibly go into it. It's checking a signature. From the stack. That's all
folks! There are no design compromises in it. No lobotomy.

OP_CAT is more or less completely unrelated to CSFS. As Andrew has
[demonstrated](
https://www.wpsoftware.net/andrew/blog/cat-and-schnorr-tricks-i.html),
*just* OP_CAT alone (no CSFS) gives you covenants (albeit in a hacky way)
with Schnorr.

I think roconnor agrees that CAT(+CSFS?) are not really a "fantastic" way
to do covenants, that there are more direct approaches that will be better
or neccessary such as TWEAK or UPDATETAPLEAF. Let's work on those! But
let's also not hold up progress on other useful things while those are
brewing.

Non-Redundancy should be a non-goal for script -- although we strive to be
minimal, redundancy is inevitable. For example, OP_SWAP has identical
semantics to <1> ROLL, but SWAP is a common enough use that it is pragmatic
to assign it an opcode and OP_ROLL does something distinctly enhanced.
Similarly, even if we add CAT we will surely come up with saner ways to
implement covenant logic than Andrew's Schnorr tricks.

CTV in particular is designed to be a part of that story -- enough
functionality w/o OP_CAT to work *today* and serve a purpose long into the
future, but with OP_CAT (or shastream preferably) enhances it's
functionality in a useful way and with introspection opcodes (perhaps like
those being developed by elements) further gains functionality. Perhaps the
functionality available today will be redundant with a future way of doing
things, but we can only see so far into the future. However, we can see
that there are good things to build with it today.

It's the inverse of a lobotomy. Independent components that can come
together for a newer greater purpose rather than parts being torn apart
irreparably.

In the future when we have specific use cases in mind that *aren't* served
well (either efficiently or at all) by the existing primitives, it's
completely acceptable to add something new even if it makes an existing
feature redundant. APO, for example, will be redundant (afaict) will Glen
Willen's [Bitmask SigHash Flags](
https://bc-2.jp/archive/season2/materials/0203_NewElementsFeaturesEn.pdf)
should we ever get those.

--
@JeremyRubin <https://twitter.com/JeremyRubin>
<https://twitter.com/JeremyRubin>

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

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[ZmnSCPxj]

Good morning Russell,

> Hi ZmnSCPxj,
>
> I don't believe we need to ban Turing completeness for the sake of banning Turing completeness.

Well I believe we should ban partial Turing-completeness, but allow total Turing-completeness.

I just think that unlimited recursive covenants (with or without a convenient way to transform state at each iteration) are **not** partial Turing-complete, but *are* total Turing-complete. (^^)

(The rest of this writeup is mostly programming languages nerdery so anyone who is not interested in Haskell (or purely functional programming) and programming language nerdery can feel free to skip the rest of this post.
Basically, ZmnSCPxj thinks we should still ban Turing-completeness, but unbounded covenants get a pass because they are not, on a technicality, Turing-complete)

For now, let us first taboo the term "Turing-complete", and instead focus on what I think matters here, the distinction between partial and total,

In a total programming language we have a distinction between data and codata:

* Data is defined according to its constructors, i.e. an algebraic data type.
* Codata is defined according to its destructors, i.e. according to a "behavior" the codata has when a particular "action" is applied to it.

For example, a singly-linked list data type would be defined as follows:

    data List a where
        Cons :: a -> List a -> List a
        Nil :: List a

On the other hand, an infinite codata stream of objects would be defined as follows:

    codata Stream a where
        head :: Stream a -> a
        tail :: Stream a -> Stream a

For `data` types, the result type for each constructor listed in the definition *must* be the type being defined.
That is why `Cons` is declared as resulting in a `List a`.
We declare data according to its constructors.

For `codata` types, the *first argument* for each destructor listed in the definition *must* be the type being defined.
That is why `head` accepts as its first argument the `Stream a` type.

This is relevant because in a total function programming language, there exists some programming rule that restricts recursion.
The simplest such restriction is substructural recursion:

* If a function recurs:
  * Every self-call should pass in a substructure of an argument as that argument.

Every program that passes the above rule provably terminates.
Since every recursion passes in a smaller part of an argument, eventually we will reach an indivisible primitive object being passed in, and processing will stop recursing and can return some value.

Thus, a programing language that has substructural recursion rule check (and rejects programs that fail the substrucutral recursion check) are not "Turing-complete".
The reason is that Turing-complete languages cannot solve the Halting Problem.
But a language that includes the substructural recursion rule *does* have a Halting Problem solution: every program that passes the substructural recursion rule halts and the Halting Problem is decidable for all programs that pass the substructural recursion rule.
(i.e. we are deliberately restricting ourselves to a subset of programs that pass substructural recursion, and reject programs that do not pass this rule as "not really programs", so every program halts)

For example, the following definition of `mapList` is valid under substructural recursion:

    mapList :: (a -> b) -> (List a -> List b)
    mapList f Nil            = Nil
    mapList f (Cons a as)    = Cons (f a) (mapList f as)

The second sub-definition has a recursive call `mapList f as`.
The second argument to that call, however, is a substructure of the second argument `Cons a as` on the LHS of the definition, thus it is a substructural recursive call, and accepted in a total programming language.
*Every* recursion in `mapList` should then be a substructural call on the second argument of `mapList`.

Now let us consider the following definition of `fibonacci`:

    -- to use: fibonacci 1 1
    fibonacci :: Integer -> Integer -> List Integer
    fibonacci x y = Cons x (fibonacci y (x + y))

The above is not substructural recursive, neither argument in the recursive `fibonacci y (x + y)` call is a substructure of the arguments in the LHS of the `fibonacci` definition `fibonacci x y`.

Thus, we prevent certain unbounded computations like the above infinite sequence of fibonacci numbers.

Now, let us consider a definition of `mapStream`, the similar function on streams, using copattern matching rather than pattern matching:

    mapStream :: (a -> b) -> (Stream a -> Stream b)
    head (mapStream f as) = f (head as)
    tail (mapStream f as) = mapStream f (tail as)

Now the interesting thing here is that in the substructural recursion check, what is being defined in the above stanza is ***not*** `mapStream`, but `head` and `tail`!
Thus, it ignores the `mapStream f (tail as)`, because it is **not** recursion --- what is being defined here is `tail`.

Looking at the above stanza, we can see that the `head` definition recurses, in the call `head as`.
The first argument to `head as` is `as`, which is a substructure of the first argument of the LHS, `mapstream f as`.
Similarly for the `tail` definition, there is a recursive call `tail as` which is substructural recursive, since the LHS has the first argument as `mapStream f as` and `as` is a substructure of that call.

(Indeed, copatterns are an important advance in total programming languages, prior to copatterns people were bashing their heads trying to figure out a simple algorithm to ensure corecursion termination, and it turns out that copatterns make corecursion termination as trivial as substructural recursion on the destructurs)

Now let us consider the following alternate definition of `fibonacci` which returns a `Stream Integer` rather than a `List Integer`:

    fibonacci :: Integer -> Integer -> Stream Integer
    head (fibonacci x y) = x
    tail (fibonacci x y) = fibonacci y (x + y)

The first definition `head (fibonacci x y) = ...` is nonrecursive.
The sceon definition `tail (fibonacci x y) = ...` is ***also*** nonrecursive because what is being defined is `tail`, and `tail` does not even appear in the RHS of the definition!

With the syntax and its rules defined, let us now consider how to implement arbitrary-bound recursion in our total language.

Let us define the following types:

    data RecResult a where
        Complete ::     a -> RecResult a
        Continue :: Rec a -> RecResult a

    codata Rec a where
        step :: Rec a -> RecResult a

`Rec a` is a monad:

    instance Monad Rec where
        step (return a) = Complete a
        step (ma >>= f) = case (step ma) of
                            Complete a   -> Continue (f a)
                            Continue ma' -> Continue (ma' >>= f)
        -- pretend we do not have the Haskellian `fail` ^^

The definition of `step (ma >>= f)` is recursive, but it is a substructural recursion: we recurse on `(step ma)` but `ma` is a substructure of the first argument on the LHS, `ma >>= f`, thus the above still is provably corecursive terminating.

The above is sufficient to define an infinite loop:

    infiniteLoop :: Rec a
    step infiniteLoop = Continue infiniteLoop

The above is still accepted, since there is no recursion involved --- the RHS does not contain the function `step` being defined, thus no recursion.

Now the important thing to note here is that the above `Rec` type is a perfectly fine definition for the Haskellian `IO` type.

Then, the `main` program, of type `Rec ()`/`IO ()`, would then be passed to a driving function, written in C.
This C function would replace the C-level `main` function, and would just call `step` on the Haskell-level `main`.
If it results in `Complete ()`, the C function exits.
If it results in `Continue ma`, then it calls `step` again on the `ma` and checks the result again, in a loop.

    int main() {
        HaskellObject* ma = haskell_get_main_function();
        for (;;) {
            HaskellObject* result = haskell_step(ma);
            if (haskell_is_Complete(result))
                 break;
            ma = haskell_destructure_Continue(result);
        }
        return 0;
    }

The important point here is that *within* the total language, everything terminates.
We put all the dirty non-termination "outside", in the C function that drives the entire processing, and have a very simple infinite loop in it that is easy to audit for correctness.
Then, we can have significantly more confidence in the correctness of our program, since any infinite recursion would have to somehow resolve to some `IO` type, which explicitly allows for infinite recursion, and we can focus auditing on that part of the program alone.

Similarly, when we consider recursive covenants, we note always that there has to be some external driving program, written in something other than Bitcoin SCRIPT, which will continuously create transactions that will keep returning the funds to the same covenant (plus or minus some state update).
Otherwise, the funds will just sit there behind their protecting SCRIPT, just like every other UTXO owned by long-term HODLers.

Such a program that continually pays a fund to "the same" covenant is no different, in principle, from the above C driving function for our total-functional-programming dialect of Haskell.

Which is to say that I mostly agree with roconnor here (other than on exact definition of terms; I think my definition of "Turing-complete" is more restrictive than his, such that covenants are not in fact **technically** Turing-complete, but that is just semantics and I can live with that), I think that the recursive covenants in Bitcoin work equivalently to the `codata` types in total functional languages.
As long as Bitcoin SCRIPT itself is provably terminating, I have no objections to the fact that we get arbitrary-bound processing by use of covenants, as they are "outside" the SCRIPT and have to be operated separately by a separate program.

Indeed, we note as well that we can encode state in other parts of the TX anyway, so that we can write something more substantive than `while (true) { /* do nothing */ }`.
So we might as well make it easy on us and just add `OP_TWEAK` (and maybe convenience opcodes for building Taproot Merkle trees?) as well.


Regards,
ZmnSCPxj

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[Billy Tetrud]

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

Thanks for the clarifications Sanket and Russel!

> OP_TWEAK

Ah gotcha. I'm very much in support of recursive covenants. I was lead to
them as a way to create more efficient and flexible wallet vaults. I
actually wrote a proposal
<https://github.com/fresheneesz/bip-efficient-bitcoin-vaults/blob/main/bip-pushoutputstack.md>
for an opcode to add state to an output. Its pretty useless without an
accompanying covenant opcode, but it seems a bit more straightforward than
the tricks you mentioned (op_tweak and otherwise). I don't plan on starting
a discussion on it yet tho, more work to be done on it and other things
to open discussion on first.

In any case, its nice to see so much general agreement on a topic that
could easily be embroidered in contention.

On Tue, Jul 6, 2021 at 9:26 PM ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Good morning Russell,
>
> > Hi ZmnSCPxj,
> >
> > I don't believe we need to ban Turing completeness for the sake of
> banning Turing completeness.
>
> Well I believe we should ban partial Turing-completeness, but allow total
> Turing-completeness.
>
> I just think that unlimited recursive covenants (with or without a
> convenient way to transform state at each iteration) are **not** partial
> Turing-complete, but *are* total Turing-complete. (^^)
>
> (The rest of this writeup is mostly programming languages nerdery so
> anyone who is not interested in Haskell (or purely functional programming)
> and programming language nerdery can feel free to skip the rest of this
> post.
> Basically, ZmnSCPxj thinks we should still ban Turing-completeness, but
> unbounded covenants get a pass because they are not, on a technicality,
> Turing-complete)
>
> For now, let us first taboo the term "Turing-complete", and instead focus
> on what I think matters here, the distinction between partial and total,
>
> In a total programming language we have a distinction between data and
> codata:
>
> * Data is defined according to its constructors, i.e. an algebraic data
> type.
> * Codata is defined according to its destructors, i.e. according to a
> "behavior" the codata has when a particular "action" is applied to it.
>
> For example, a singly-linked list data type would be defined as follows:
>
>     data List a where
>         Cons :: a -> List a -> List a
>         Nil :: List a
>
> On the other hand, an infinite codata stream of objects would be defined
> as follows:
>
>     codata Stream a where
>         head :: Stream a -> a
>         tail :: Stream a -> Stream a
>
> For `data` types, the result type for each constructor listed in the
> definition *must* be the type being defined.
> That is why `Cons` is declared as resulting in a `List a`.
> We declare data according to its constructors.
>
> For `codata` types, the *first argument* for each destructor listed in the
> definition *must* be the type being defined.
> That is why `head` accepts as its first argument the `Stream a` type.
>
> This is relevant because in a total function programming language, there
> exists some programming rule that restricts recursion.
> The simplest such restriction is substructural recursion:
>
> * If a function recurs:
>   * Every self-call should pass in a substructure of an argument as that
> argument.
>
> Every program that passes the above rule provably terminates.
> Since every recursion passes in a smaller part of an argument, eventually
> we will reach an indivisible primitive object being passed in, and
> processing will stop recursing and can return some value.
>
> Thus, a programing language that has substructural recursion rule check
> (and rejects programs that fail the substrucutral recursion check) are not
> "Turing-complete".
> The reason is that Turing-complete languages cannot solve the Halting
> Problem.
> But a language that includes the substructural recursion rule *does* have
> a Halting Problem solution: every program that passes the substructural
> recursion rule halts and the Halting Problem is decidable for all programs
> that pass the substructural recursion rule.
> (i.e. we are deliberately restricting ourselves to a subset of programs
> that pass substructural recursion, and reject programs that do not pass
> this rule as "not really programs", so every program halts)
>
> For example, the following definition of `mapList` is valid under
> substructural recursion:
>
>     mapList :: (a -> b) -> (List a -> List b)
>     mapList f Nil            = Nil
>     mapList f (Cons a as)    = Cons (f a) (mapList f as)
>
> The second sub-definition has a recursive call `mapList f as`.
> The second argument to that call, however, is a substructure of the second
> argument `Cons a as` on the LHS of the definition, thus it is a
> substructural recursive call, and accepted in a total programming language.
> *Every* recursion in `mapList` should then be a substructural call on the
> second argument of `mapList`.
>
> Now let us consider the following definition of `fibonacci`:
>
>     -- to use: fibonacci 1 1
>     fibonacci :: Integer -> Integer -> List Integer
>     fibonacci x y = Cons x (fibonacci y (x + y))
>
> The above is not substructural recursive, neither argument in the
> recursive `fibonacci y (x + y)` call is a substructure of the arguments in
> the LHS of the `fibonacci` definition `fibonacci x y`.
>
> Thus, we prevent certain unbounded computations like the above infinite
> sequence of fibonacci numbers.
>
> Now, let us consider a definition of `mapStream`, the similar function on
> streams, using copattern matching rather than pattern matching:
>
>     mapStream :: (a -> b) -> (Stream a -> Stream b)
>     head (mapStream f as) = f (head as)
>     tail (mapStream f as) = mapStream f (tail as)
>
> Now the interesting thing here is that in the substructural recursion
> check, what is being defined in the above stanza is ***not*** `mapStream`,
> but `head` and `tail`!
> Thus, it ignores the `mapStream f (tail as)`, because it is **not**
> recursion --- what is being defined here is `tail`.
>
> Looking at the above stanza, we can see that the `head` definition
> recurses, in the call `head as`.
> The first argument to `head as` is `as`, which is a substructure of the
> first argument of the LHS, `mapstream f as`.
> Similarly for the `tail` definition, there is a recursive call `tail as`
> which is substructural recursive, since the LHS has the first argument as
> `mapStream f as` and `as` is a substructure of that call.
>
> (Indeed, copatterns are an important advance in total programming
> languages, prior to copatterns people were bashing their heads trying to
> figure out a simple algorithm to ensure corecursion termination, and it
> turns out that copatterns make corecursion termination as trivial as
> substructural recursion on the destructurs)
>
> Now let us consider the following alternate definition of `fibonacci`
> which returns a `Stream Integer` rather than a `List Integer`:
>
>     fibonacci :: Integer -> Integer -> Stream Integer
>     head (fibonacci x y) = x
>     tail (fibonacci x y) = fibonacci y (x + y)
>
> The first definition `head (fibonacci x y) = ...` is nonrecursive.
> The sceon definition `tail (fibonacci x y) = ...` is ***also***
> nonrecursive because what is being defined is `tail`, and `tail` does not
> even appear in the RHS of the definition!
>
> With the syntax and its rules defined, let us now consider how to
> implement arbitrary-bound recursion in our total language.
>
> Let us define the following types:
>
>     data RecResult a where
>         Complete ::     a -> RecResult a
>         Continue :: Rec a -> RecResult a
>
>     codata Rec a where
>         step :: Rec a -> RecResult a
>
> `Rec a` is a monad:
>
>     instance Monad Rec where
>         step (return a) = Complete a
>         step (ma >>= f) = case (step ma) of
>                             Complete a   -> Continue (f a)
>                             Continue ma' -> Continue (ma' >>= f)
>         -- pretend we do not have the Haskellian `fail` ^^
>
> The definition of `step (ma >>= f)` is recursive, but it is a
> substructural recursion: we recurse on `(step ma)` but `ma` is a
> substructure of the first argument on the LHS, `ma >>= f`, thus the above
> still is provably corecursive terminating.
>
> The above is sufficient to define an infinite loop:
>
>     infiniteLoop :: Rec a
>     step infiniteLoop = Continue infiniteLoop
>
> The above is still accepted, since there is no recursion involved --- the
> RHS does not contain the function `step` being defined, thus no recursion.
>
> Now the important thing to note here is that the above `Rec` type is a
> perfectly fine definition for the Haskellian `IO` type.
>
> Then, the `main` program, of type `Rec ()`/`IO ()`, would then be passed
> to a driving function, written in C.
> This C function would replace the C-level `main` function, and would just
> call `step` on the Haskell-level `main`.
> If it results in `Complete ()`, the C function exits.
> If it results in `Continue ma`, then it calls `step` again on the `ma` and
> checks the result again, in a loop.
>
>     int main() {
>         HaskellObject* ma = haskell_get_main_function();
>         for (;;) {
>             HaskellObject* result = haskell_step(ma);
>             if (haskell_is_Complete(result))
>                  break;
>             ma = haskell_destructure_Continue(result);
>         }
>         return 0;
>     }
>
> The important point here is that *within* the total language, everything
> terminates.
> We put all the dirty non-termination "outside", in the C function that
> drives the entire processing, and have a very simple infinite loop in it
> that is easy to audit for correctness.
> Then, we can have significantly more confidence in the correctness of our
> program, since any infinite recursion would have to somehow resolve to some
> `IO` type, which explicitly allows for infinite recursion, and we can focus
> auditing on that part of the program alone.
>
> Similarly, when we consider recursive covenants, we note always that there
> has to be some external driving program, written in something other than
> Bitcoin SCRIPT, which will continuously create transactions that will keep
> returning the funds to the same covenant (plus or minus some state update).
> Otherwise, the funds will just sit there behind their protecting SCRIPT,
> just like every other UTXO owned by long-term HODLers.
>
> Such a program that continually pays a fund to "the same" covenant is no
> different, in principle, from the above C driving function for our
> total-functional-programming dialect of Haskell.
>
> Which is to say that I mostly agree with roconnor here (other than on
> exact definition of terms; I think my definition of "Turing-complete" is
> more restrictive than his, such that covenants are not in fact
> **technically** Turing-complete, but that is just semantics and I can live
> with that), I think that the recursive covenants in Bitcoin work
> equivalently to the `codata` types in total functional languages.
> As long as Bitcoin SCRIPT itself is provably terminating, I have no
> objections to the fact that we get arbitrary-bound processing by use of
> covenants, as they are "outside" the SCRIPT and have to be operated
> separately by a separate program.
>
> Indeed, we note as well that we can encode state in other parts of the TX
> anyway, so that we can write something more substantive than `while (true)
> { /* do nothing */ }`.
> So we might as well make it easy on us and just add `OP_TWEAK` (and maybe
> convenience opcodes for building Taproot Merkle trees?) as well.
>
>
> Regards,
> ZmnSCPxj
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[Russell O'Connor]

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

On Wed, Jul 7, 2021 at 12:26 AM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:

> Good morning Russell,
>
> > Hi ZmnSCPxj,
> >
> > I don't believe we need to ban Turing completeness for the sake of
> banning Turing completeness.
>
> Well I believe we should ban partial Turing-completeness, but allow total
> Turing-completeness.
>

Unfortunately, when it comes to cross-transaction computations, it is
infeasible to ban non-terminating computation.

The nature of recursive covenants is that the program "writes" the *source
code* next step of the computation to the scriptPubKey to one of the
outputs of its transaction. Technically speaking it verifies that the
scriptPubKey is a commitment to the source code of the next step of the
program, but morally that is the same as writing the source code.  Then the
next step of the computation is invoked by someone "evaluating* that next
step's source code by creating a valid transaction that spends the
generated output.

The point is this ability to create new source code and then evaluate it
leads to the ability to write universal (i.e non-terminating)
computations.  The only way to prevent it is to ban source code
manipulation, but since Bitcoin Script source code is just a string of
bytes, it would mean banning the manipulation of strings of bytes.  But the
entire Bitcoin Script language works by manipulating strings of bytes
within a stack machine.  Indeed the most trivial of non-terminating
programs can be implemented by extracting the current input's scriptPubKey
from the sighash and "writing" the identical scriptPubKey to one of its
outputs.  That example hardly takes any manipulation at all to implement.

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

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[Russell O'Connor]

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

On Wed, Jul 7, 2021 at 9:12 AM Russell O'Connor <roconnor@blockstream.com>
wrote:

>
> On Wed, Jul 7, 2021 at 12:26 AM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:
>
>> Good morning Russell,
>>
>> > Hi ZmnSCPxj,
>> >
>> > I don't believe we need to ban Turing completeness for the sake of
>> banning Turing completeness.
>>
>> Well I believe we should ban partial Turing-completeness, but allow total
>> Turing-completeness.
>>
>
> Unfortunately, when it comes to cross-transaction computations, it is
> infeasible to ban non-terminating computation.
>
> The nature of recursive covenants is that the program "writes" the *source
> code* next step of the computation to the scriptPubKey to one of the
> outputs of its transaction. Technically speaking it verifies that the
> scriptPubKey is a commitment to the source code of the next step of the
> program, but morally that is the same as writing the source code.  Then the
> next step of the computation is invoked by someone "evaluating* that next
> step's source code by creating a valid transaction that spends the
> generated output.
>
> The point is this ability to create new source code and then evaluate it
> leads to the ability to write universal (i.e non-terminating)
> computations.  The only way to prevent it is to ban source code
> manipulation, but since Bitcoin Script source code is just a string of
> bytes, it would mean banning the manipulation of strings of bytes.  But the
> entire Bitcoin Script language works by manipulating strings of bytes
> within a stack machine.  Indeed the most trivial of non-terminating
> programs can be implemented by extracting the current input's scriptPubKey
> from the sighash and "writing" the identical scriptPubKey to one of its
> outputs.  That example hardly takes any manipulation at all to implement.
>

A follow up:  Because recursive covenants need to be sent to a new
transaction in order to recurse, you might choose to view this stepping
mechanism as productive by modeling each transaction step as the continue
constructor in your RecResult codata type.  Indeed after (drinking coffee
and) rereading your mailing list item, it seems that this is the point you
were making.

So sorry for my hasty response.  I believe we are largely in agreement here.

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

Re: [bitcoin-dev] Unlimited covenants, was Re: CHECKSIGFROMSTACK/{Verify} BIP for Bitcoin

[Jeremy]

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

Hah -- ZmnSCPxj that post's a doozy -- but it more or less makes sense the
argument you're making in favor of permitting recursion at the transaction
level.

One part that's less clear is if you can make a case against being
recursive in Script fragments themselves -- ignoring bitcoin script for the
moment, what would be wrong with a small VM that a spender is able to
"purchase" a number of cycles and available memory via the annex, and the
program must execute and halt within that time? Then, per block/txn, you
can enforce a total cycle and memory limit. This still isn't quite the EVM,
since there's no cross object calling convention and the output is still
UTXOs. What are the arguments against this model from a safety perspective?

<new topic>

One of my general concerns with recursive covenants is the ability to "go
wrong" in surprising ways. Consider the following program (Sapio
<http://learn.sapio-lang.org>-pseudocode), which is a non recursive
covenant (i.e., doable today with presigning oracles) that demonstrates the
issue.

struct Pool {
    members: Vec<(Amount, Key)>,
}
impl Pool {
    then!{
        fn withdraw(self, ctx) {
            let mut builder = ctx.template();
            for (a, k) in self.members.iter() {
                builder = builder.add_output(a, k.into(), None)?;
            }
            builder.into()
        }
    }
    guard! {
        fn all_signed(self, ctx) {
            Clause::And(self.members.iter().map(|(a,k)|
Clause::Key(k.clone())).into())
        }
    }
    finish! {
        guarded_by: [all_signed]
        fn add_member(self, ctx, o_member: Option<(Amount, Key)>) {
            let member = o_member.into()?;
            let mut new_members = self.members.clone();
            new_members.push(member.clone());
            ctx.template().add_output(ctx.funds() + member.0,
                  Pool {members: new_members}, None)?.into()
        }
    }
}

Essentially this is a recursive covenant that allows either Complete via
the withdraw call or Continue via add_member, while preserving the same
underlying code. In this case, all_signed must be signed by all current
participants to admit a new member.

This type of program is subtly "wrong" because the state transition of
add_member does not verify that the Pool's future withdraw call will be
valid. E.g., we could add more than a 1MB of outputs, and then our program
would be "stuck". So it's critical that in our "production grade" covenant
system we do some static analysis before proceeding to a next step to
ensure that all future txns are valid. This is a strength of the CTV/Sapio
model presently, you always output a list of future txns to aid static
analysis.

However, when we make the leap to "automatic" covenants, I posit that it
will be *incredibly* difficult to prove that recursive covenants don't have
a "premature termination" where a state transition that should be valid in
an idealized setting is accidentally invalid in the actual bitcoin
environment and the program reaches a untimely demise.

For instance, OP_CAT has this footgun -- by only permitting 520 bytes, you
hit covenant limits at around 13 outputs assuming you are length checking
each one and not permitting bare script. We can avoid this specific footgun
some of the time by using SHA256STREAM instead, of course.

However, it is generally very difficult to avoid all sorts of issues. E.g.,
with the ability to generate/update tapscript trees, what happens when
through updating a well formed tapscript tree 128 times you bump an
important clause past the 129 depth limit?

I don't think that these sorts of challenges mean that we shouldn't enable
covenants or avoid enabling them, but rather that as we explore we should
add primitives in a methodical way and give users/toolchain builders
primitives that enable and or encourage safety and good program design.

My personal view is that CTV/Sapio with it's AOT compilation of automated
state transitions and ability to statically analyze is a concept that can
mature and be used in production in the near term. But the tooling to
safely do recursive computations at the txn level will take quite a bit
longer to mature, and we should be investing effort in producing
compilers/frameworks for emitting well formed programs before we get too in
the weeds on things like OP_TWEAK. (side note -- there's an easy path for
adding this sort of experimental feature to Sapio if anyone is looking for
a place to start)

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