[bitcoin-dev] Speedy covenants (OP_CAT2)

[bitcoin-dev] Speedy covenants (OP_CAT2)

[Jorge Timón]

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

OP_CAT was removed. If I remember correctly, some speculated that perhaps
it was removed because it could allow covenants.
I don't remember any technical concern about the OP besides enabling
covenants.
Before it was a common opinion that covenants shouldn't be enabled in
bitcoin because, despite having good use case, there are some nasty attacks
that are enabled with them too. These days it seems the opinion of the
benefits being worth the dangers is quite generalized. Which is quite
understandable given that more use cases have been thought since then.

Re-enabling OP_CAT with the exact same OP would be a hardfork, but creating
a new OP_CAT2 that does the same would be a softfork.
As far a I know, this is the covenants proposal that has been implemented
for the longest time, if that's to be used as a selection criteria.
And as always, this is not incompatible with deploying other convenant
proposals later.
Personally I find the simplicity proposal the best one among all the
covenant proposals by far, including this one.
But I understand that despite the name, the proposal is harder to review
and test than other proposals, for it wouldn't simply add covenants, but a
complete new scripting language that is better in many senses.
Speedy covenants, on the other hand, is much simpler and has been
implemented for longer, so in principle, it should be easier to deploy in a
speedy manner.

What are the main arguments against speedy covenants (aka op_cat2) and
against deploying simplicity in bitcoin respectively?

Sorry if this was discussed before.

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

Re: [bitcoin-dev] Speedy covenants (OP_CAT2)

[ZmnSCPxj]

Good morning Jorge,

> OP_CAT was removed. If I remember correctly, some speculated that perhaps it was removed because it could allow covenants.I don't remember any technical concern about the OP besides enabling covenants.Before it was a common opinion that covenants shouldn't be enabled in bitcoin because, despite having good use case, there are some nasty attacks that are enabled with them too. These days it seems the opinion of the benefits being worth the dangers is quite generalized. Which is quite understandable given that more use cases have been thought since then.

I think the more accurate reason for why it was removed is because the following SCRIPT of N size would lead to 2^N memory usage:

    OP_1 OP_DUP OP_CAT OP_DUP OP_CAT OP_DUP OP_CAT OP_DUP OP_CAT OP_DUP OP_CAT OP_DUP OP_CAT ...

In particular it was removed at about the same time as `OP_MUL`, which has similar behavior (consider that multiplying two 32-bit numbers results in a 64-bit number, similar to `OP_CAT`ting a vector to itself).

`OP_CAT` was removed long before covenants were even expressed as a possibility.

Covenants were first expressed as a possibility, I believe, during discussions around P2SH.
Basically, at the time, the problem was this:

* Some receivers wanted to use k-of-n multisignature for improved security.
* The only way to implement this, pre-P2SH, was by putting in the `scriptPubKey` all the public keys.
* The sender is the one paying for the size of the `scriptPubKey`.
* It was considered unfair that the sender is paying for the security of the receiver.

Thus, `OP_EVAL` and the P2SH concept was conceived.
Instead of the `scriptPubKey` containing the k-of-n multisignature, you create a separate script containing the public keys, then hash it, and the `scriptPubKey` would contain the hash of the script.
By symmetry with the P2PKH template:

    OP_DUP OP_HASH160 <hash160(pubkey)> OP_EQUALVERIFY OP_CHECKSIG

The P2SH template would be:

    OP_DUP OP_HASH160 <hash160(redeemScript)> OP_EQUALVERIFY OP_EVAL

`OP_EVAL` would take the stack top vector and treat it as a Bitcoin SCRIPT.

It was then pointed out that `OP_EVAL` could be used to create recursive SCRIPTs by quining using `OP_CAT`.
`OP_CAT` was already disabled by then, but people were talking about re-enabling it somehow by restricting the output size of `OP_CAT` to limit the O(2^N) behavior.

Thus, since then, `OP_CAT` has been associated with ***recursive*** covenants (and people are now reluctant to re-enable it even with a limit on its output size, because recursive covenants).
In particular, `OP_CAT` in combination with `OP_CHECKSIGFROMSTACK` and `OP_CHECKSIG`, you could get a deferred `OP_EVAL` and then use `OP_CAT` too to quine.

Because of those concerns, the modern P2SH is now "just a template" with an implicit `OP_EVAL` of the `redeemScript`, but without any `OP_EVAL` being actually enabled.

(`OP_EVAL` cannot replace an `OP_NOP` in a softfork, but it is helpful to remember that P2SH was pretty much what codified the difference between softfork and hardfork, and the community at the time was small enough (or so it seemed) that a hardfork might not have been disruptive.)

> Re-enabling OP_CAT with the exact same OP would be a hardfork, but creating a new OP_CAT2 that does the same would be a softfork.

If you are willing to work in Taproot the same OP-code can be enabled in a softfork by using a new Tapscript version.

If you worry about quantum-computing-break, a new SegWit version (which is more limited than Tapscript versions, unfortunately) can also be used, creating a new P2WSHv2 (or whatever version) that enables these opcodes.

> As far a I know, this is the covenants proposal that has been implemented for the longest time, if that's to be used as a selection criteria.And as always, this is not incompatible with deploying other convenant proposals later.

No, it was `OP_EVAL`, not `OP_CAT`.
In particular if `OP_EVAL` was allowed in the `redeemScript` then it would enable covenants as well.
It was just pointed out that `OP_CAT` enables recursive covenenats in combination with `OP_EVAL`-in-`redeemScript`.

In particular, in combination with `OP_CAT`, `OP_EVAL` not only allows recursive covenants, but also recursion *within* a SCRIPT i.e. unbounded SCRIPT execution.
Thus, `OP_EVAL` is simply not going to fly, at all.

> Personally I find the simplicity proposal the best one among all the covenant proposals by far, including this one.But I understand that despite the name, the proposal is harder to review and test than other proposals, for it wouldn't simply add covenants, but a complete new scripting language that is better in many senses.Speedy covenants, on the other hand, is much simpler and has been implemented for longer, so in principle, it should be easier to deploy in a speedy manner.
>
> What are the main arguments against speedy covenants (aka op_cat2) and against deploying simplicity in bitcoin respectively?
> Sorry if this was discussed before.

`OP_CAT`, by itself, does not implement any covenants --- instead, it creates recursive covenants when combined with almost all covenant opcodes.

Regards,
ZmnSCPxj

Re: [bitcoin-dev] Speedy covenants (OP_CAT2)

[vjudeu]

> Re-enabling OP_CAT with the exact same OP would be a hardfork, but creating a new OP_CAT2 that does the same would be a softfork.

We have TapScript for that. OP_CAT is defined as OP_SUCCESS, it can be re-enabled in a soft-fork way. For now, OP_CAT in TapScript simply means "anyone can move those coins", so adding some restrictions is all we need to re-enable this opcode. Introducing OP_CAT2 is not needed at all, unless it will be totally different, but then it should not be named as OP_CAT2, but rather as OP_SOMETHING_ELSE, it depends how different it will be from OP_CAT.

> OP_1 OP_DUP OP_CAT OP_DUP OP_CAT OP_DUP OP_CAT OP_DUP OP_CAT OP_DUP OP_CAT OP_DUP OP_CAT ...

So we can use OP_SUBSTR instead. Maybe even OP_SPLIT will be enough, if data expansion is the only problem, then we can focus on getting it smaller. Or better, we could use OP_FIND that would return true/false answer if element A is a part of element B, when we do byte-to-byte comparison. In general, we can use many different string-based functions to do the same things, we can choose something that will not exponentially explode as OP_CAT.

> It was considered unfair that the sender is paying for the security of the receiver.

It can be changed by using different sighashes, for example, it is possible to create a "negative fee transaction", where all transaction costs are paid by receiver. Using SIGHASH_SINGLE | SIGHASH_ANYONECANPAY with a higher amount in outputs than inputs is enough to do that, see testnet3 transaction 495d2007ae8b741c70c3d278c02ce03702223b9675e954ecabbb634c6cd5bf40.

On 2022-05-07 05:06:46 user ZmnSCPxj via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> Good morning Jorge,

> OP_CAT was removed. If I remember correctly, some speculated that perhaps it was removed because it could allow covenants.I don't remember any technical concern about the OP besides enabling covenants.Before it was a common opinion that covenants shouldn't be enabled in bitcoin because, despite having good use case, there are some nasty attacks that are enabled with them too. These days it seems the opinion of the benefits being worth the dangers is quite generalized. Which is quite understandable given that more use cases have been thought since then.

I think the more accurate reason for why it was removed is because the following SCRIPT of N size would lead to 2^N memory usage:

    OP_1 OP_DUP OP_CAT OP_DUP OP_CAT OP_DUP OP_CAT OP_DUP OP_CAT OP_DUP OP_CAT OP_DUP OP_CAT ...

In particular it was removed at about the same time as `OP_MUL`, which has similar behavior (consider that multiplying two 32-bit numbers results in a 64-bit number, similar to `OP_CAT`ting a vector to itself).

`OP_CAT` was removed long before covenants were even expressed as a possibility.

Covenants were first expressed as a possibility, I believe, during discussions around P2SH.
Basically, at the time, the problem was this:

* Some receivers wanted to use k-of-n multisignature for improved security.
* The only way to implement this, pre-P2SH, was by putting in the `scriptPubKey` all the public keys.
* The sender is the one paying for the size of the `scriptPubKey`.
* It was considered unfair that the sender is paying for the security of the receiver.

Thus, `OP_EVAL` and the P2SH concept was conceived.
Instead of the `scriptPubKey` containing the k-of-n multisignature, you create a separate script containing the public keys, then hash it, and the `scriptPubKey` would contain the hash of the script.
By symmetry with the P2PKH template:

    OP_DUP OP_HASH160 <hash160(pubkey)> OP_EQUALVERIFY OP_CHECKSIG

The P2SH template would be:

    OP_DUP OP_HASH160 <hash160(redeemScript)> OP_EQUALVERIFY OP_EVAL

`OP_EVAL` would take the stack top vector and treat it as a Bitcoin SCRIPT.

It was then pointed out that `OP_EVAL` could be used to create recursive SCRIPTs by quining using `OP_CAT`.
`OP_CAT` was already disabled by then, but people were talking about re-enabling it somehow by restricting the output size of `OP_CAT` to limit the O(2^N) behavior.

Thus, since then, `OP_CAT` has been associated with ***recursive*** covenants (and people are now reluctant to re-enable it even with a limit on its output size, because recursive covenants).
In particular, `OP_CAT` in combination with `OP_CHECKSIGFROMSTACK` and `OP_CHECKSIG`, you could get a deferred `OP_EVAL` and then use `OP_CAT` too to quine.

Because of those concerns, the modern P2SH is now "just a template" with an implicit `OP_EVAL` of the `redeemScript`, but without any `OP_EVAL` being actually enabled.

(`OP_EVAL` cannot replace an `OP_NOP` in a softfork, but it is helpful to remember that P2SH was pretty much what codified the difference between softfork and hardfork, and the community at the time was small enough (or so it seemed) that a hardfork might not have been disruptive.)

> Re-enabling OP_CAT with the exact same OP would be a hardfork, but creating a new OP_CAT2 that does the same would be a softfork.

If you are willing to work in Taproot the same OP-code can be enabled in a softfork by using a new Tapscript version.

If you worry about quantum-computing-break, a new SegWit version (which is more limited than Tapscript versions, unfortunately) can also be used, creating a new P2WSHv2 (or whatever version) that enables these opcodes.

> As far a I know, this is the covenants proposal that has been implemented for the longest time, if that's to be used as a selection criteria.And as always, this is not incompatible with deploying other convenant proposals later.

No, it was `OP_EVAL`, not `OP_CAT`.
In particular if `OP_EVAL` was allowed in the `redeemScript` then it would enable covenants as well.
It was just pointed out that `OP_CAT` enables recursive covenenats in combination with `OP_EVAL`-in-`redeemScript`.

In particular, in combination with `OP_CAT`, `OP_EVAL` not only allows recursive covenants, but also recursion *within* a SCRIPT i.e. unbounded SCRIPT execution.
Thus, `OP_EVAL` is simply not going to fly, at all.

> Personally I find the simplicity proposal the best one among all the covenant proposals by far, including this one.But I understand that despite the name, the proposal is harder to review and test than other proposals, for it wouldn't simply add covenants, but a complete new scripting language that is better in many senses.Speedy covenants, on the other hand, is much simpler and has been implemented for longer, so in principle, it should be easier to deploy in a speedy manner.
>
> What are the main arguments against speedy covenants (aka op_cat2) and against deploying simplicity in bitcoin respectively?
> Sorry if this was discussed before.

`OP_CAT`, by itself, does not implement any covenants --- instead, it creates recursive covenants when combined with almost all covenant opcodes.

Regards,
ZmnSCPxj
_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Speedy covenants (OP_CAT2)

[Jorge Timón]

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

Thanks a lot for the many clarifications.
Yeah, I forgot it wasn't OP_CAT alone, but in combination with other things.
I guess this wouldn't be a covenants proposal then.
But simplicity would enable covenants too indeed, no?
Or did I get that wrong too?

On Sat, May 7, 2022 at 5:06 AM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:

> Good morning Jorge,
>
> > OP_CAT was removed. If I remember correctly, some speculated that
> perhaps it was removed because it could allow covenants.I don't remember
> any technical concern about the OP besides enabling covenants.Before it was
> a common opinion that covenants shouldn't be enabled in bitcoin because,
> despite having good use case, there are some nasty attacks that are enabled
> with them too. These days it seems the opinion of the benefits being worth
> the dangers is quite generalized. Which is quite understandable given that
> more use cases have been thought since then.
>
> I think the more accurate reason for why it was removed is because the
> following SCRIPT of N size would lead to 2^N memory usage:
>
>     OP_1 OP_DUP OP_CAT OP_DUP OP_CAT OP_DUP OP_CAT OP_DUP OP_CAT OP_DUP
> OP_CAT OP_DUP OP_CAT ...
>
> In particular it was removed at about the same time as `OP_MUL`, which has
> similar behavior (consider that multiplying two 32-bit numbers results in a
> 64-bit number, similar to `OP_CAT`ting a vector to itself).
>
> `OP_CAT` was removed long before covenants were even expressed as a
> possibility.
>
> Covenants were first expressed as a possibility, I believe, during
> discussions around P2SH.
> Basically, at the time, the problem was this:
>
> * Some receivers wanted to use k-of-n multisignature for improved security.
> * The only way to implement this, pre-P2SH, was by putting in the
> `scriptPubKey` all the public keys.
> * The sender is the one paying for the size of the `scriptPubKey`.
> * It was considered unfair that the sender is paying for the security of
> the receiver.
>
> Thus, `OP_EVAL` and the P2SH concept was conceived.
> Instead of the `scriptPubKey` containing the k-of-n multisignature, you
> create a separate script containing the public keys, then hash it, and the
> `scriptPubKey` would contain the hash of the script.
> By symmetry with the P2PKH template:
>
>     OP_DUP OP_HASH160 <hash160(pubkey)> OP_EQUALVERIFY OP_CHECKSIG
>
> The P2SH template would be:
>
>     OP_DUP OP_HASH160 <hash160(redeemScript)> OP_EQUALVERIFY OP_EVAL
>
> `OP_EVAL` would take the stack top vector and treat it as a Bitcoin SCRIPT.
>
> It was then pointed out that `OP_EVAL` could be used to create recursive
> SCRIPTs by quining using `OP_CAT`.
> `OP_CAT` was already disabled by then, but people were talking about
> re-enabling it somehow by restricting the output size of `OP_CAT` to limit
> the O(2^N) behavior.
>
> Thus, since then, `OP_CAT` has been associated with ***recursive***
> covenants (and people are now reluctant to re-enable it even with a limit
> on its output size, because recursive covenants).
> In particular, `OP_CAT` in combination with `OP_CHECKSIGFROMSTACK` and
> `OP_CHECKSIG`, you could get a deferred `OP_EVAL` and then use `OP_CAT` too
> to quine.
>
> Because of those concerns, the modern P2SH is now "just a template" with
> an implicit `OP_EVAL` of the `redeemScript`, but without any `OP_EVAL`
> being actually enabled.
>
> (`OP_EVAL` cannot replace an `OP_NOP` in a softfork, but it is helpful to
> remember that P2SH was pretty much what codified the difference between
> softfork and hardfork, and the community at the time was small enough (or
> so it seemed) that a hardfork might not have been disruptive.)
>
> > Re-enabling OP_CAT with the exact same OP would be a hardfork, but
> creating a new OP_CAT2 that does the same would be a softfork.
>
> If you are willing to work in Taproot the same OP-code can be enabled in a
> softfork by using a new Tapscript version.
>
> If you worry about quantum-computing-break, a new SegWit version (which is
> more limited than Tapscript versions, unfortunately) can also be used,
> creating a new P2WSHv2 (or whatever version) that enables these opcodes.
>
> > As far a I know, this is the covenants proposal that has been
> implemented for the longest time, if that's to be used as a selection
> criteria.And as always, this is not incompatible with deploying other
> convenant proposals later.
>
> No, it was `OP_EVAL`, not `OP_CAT`.
> In particular if `OP_EVAL` was allowed in the `redeemScript` then it would
> enable covenants as well.
> It was just pointed out that `OP_CAT` enables recursive covenenats in
> combination with `OP_EVAL`-in-`redeemScript`.
>
> In particular, in combination with `OP_CAT`, `OP_EVAL` not only allows
> recursive covenants, but also recursion *within* a SCRIPT i.e. unbounded
> SCRIPT execution.
> Thus, `OP_EVAL` is simply not going to fly, at all.
>
> > Personally I find the simplicity proposal the best one among all the
> covenant proposals by far, including this one.But I understand that despite
> the name, the proposal is harder to review and test than other proposals,
> for it wouldn't simply add covenants, but a complete new scripting language
> that is better in many senses.Speedy covenants, on the other hand, is much
> simpler and has been implemented for longer, so in principle, it should be
> easier to deploy in a speedy manner.
> >
> > What are the main arguments against speedy covenants (aka op_cat2) and
> against deploying simplicity in bitcoin respectively?
> > Sorry if this was discussed before.
>
> `OP_CAT`, by itself, does not implement any covenants --- instead, it
> creates recursive covenants when combined with almost all covenant opcodes.
>
> Regards,
> ZmnSCPxj
>

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

Re: [bitcoin-dev] Speedy covenants (OP_CAT2)

[Jorge Timón]

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

On Sat, May 7, 2022 at 5:52 AM <vjudeu@gazeta.pl> wrote:

> > Re-enabling OP_CAT with the exact same OP would be a hardfork, but
> creating a new OP_CAT2 that does the same would be a softfork.
>
> We have TapScript for that. OP_CAT is defined as OP_SUCCESS, it can be
> re-enabled in a soft-fork way. For now, OP_CAT in TapScript simply means
> "anyone can move those coins", so adding some restrictions is all we need
> to re-enable this opcode. Introducing OP_CAT2 is not needed at all, unless
> it will be totally different, but then it should not be named as OP_CAT2,
> but rather as OP_SOMETHING_ELSE, it depends how different it will be from
> OP_CAT.
>

Oh, well, I didn't know any of that. I guess it could be a modification of
OP_SUCCESS if it makes sense instead of a new opcode.

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

Re: [bitcoin-dev] Speedy covenants (OP_CAT2)

[ZmnSCPxj]

Good morning Jorge,

> Thanks a lot for the many clarifications.
> Yeah, I forgot it wasn't OP_CAT alone, but in combination with other things.
> I guess this wouldn't be a covenants proposal then.
> But simplicity would enable covenants too indeed, no?
> Or did I get that wrong too?

Yes, it would enable covenants.

However, it could also enable *recursive* covenants, depending on what introspection operations are actually implemented (though maybe not? Russell O'Connor should be the one that answers this).

It is helpful to delineate between non-recursive covenants from recursive covenants.

* Even ***with*** `OP_CAT`, the following will enable non-recursive covenants without enabling recursive covenants:
  * `OP_CTV`
  * `SIGHASH_ANYPREVOUT`
* With `OP_CAT`, the following would enable recursive covenants:
  * `OP_EVAL`
  * `OP_CHECKSIGFROMSTACK`
  * `OP_TX`/`OP_TXHASH`
  * ...possibly more.
    * It is actually *easier* to *design* an opcode which inadvertently supports recursive covenants than to design one which avoids recursive covenants.

Recursive covenants are very near to true Turing-completeness.
We want to avoid Turing-completeness due to the halting problem being unsolvable for Turing-complete languages.
That is, given just a program, we cannot determine for sure if for all possible inputs, it will terminate.
It is important in our context (Bitcoin) that any SCRIPT programs we write *must* terminate, or else we run the risk of a DoS on the network.

A fair amount of this is theoretical crap, but if you want to split hairs, recursive covenants are *not* Turing-complete, but are instead total functional programming with codata.

As a very rough bastardization, a program written in a total functional programming language with codata will always assuredly terminate.
However, the return value of a total functional programming language with codata can be another program.
An external program (written in a Turing-complete language) could then just keep invoking the interpreter of the total functional programming language with codata (taking the output program and running it, taking *its* output program and running it, ad infinitum, thus effectively able to loop indefinitely.

Translated to Bitcoin transactions, a recursive covenant system can force an output to be spent only if the output is spent on a transaction where one of the outputs is the same covenant (possibly with tweaks).
Then an external program can keep passing the output program to the Bitcoin SCRIPT interpreter --- by building transactions that spend the previous output.

This behavior is still of concern.
It may be possible to attack the network by eroding its supply, by such a recursive covenant.

--

Common reactions:

* We can just limit the number of opcodes we can process and then fail it if it takes too many operations!
  That way we can avoid DoS!
  * Yes, this indeed drops it from Turing-complete to total, possibly total functional programming **without** codata.
    But if it is possible to treat data as code, it may drop it "total but with codata" instead (i.e. recursive covenants).
    But if you want to avoid recursive covenants while allowing recursive ones (i.e. equivalent to total without codata), may I suggest you instead look at `OP_CTV` and `SIGHASH_ANYPREVOUT`?

* What is so wrong with total-with-codata anyway??
  So what if the recursive covenant could potentially consume all Bitcoins, nobody will pay to it except as a novelty!!
  If you want to burn your funds, 1BitcoinEater willingly accepts it!
  * The burden of proof-of-safety is on the proposer, so if you have some proof that total-with-codata is safe, by construction, then sure, we can add opcodes that may enable recursive covenants, and add `OP_CAT` back in too.

Regards,
ZmnSCPxj

Re: [bitcoin-dev] Speedy covenants (OP_CAT2)

[ZmnSCPxj]

Good morning Jorge,

> Thanks again.
> I won't ask anything else about bitcoin, I guess, since it seems my questions are too "misinforming" for the list.
> I also agreed with vjudeu, also too much misinformation on my part to agree with him, it seems.
> I mean, I say that because it doesn't look like my emails are appearing on the mailing list:
>
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-May/thread.html#start
>
> Do any of you now who moderates the mailing list? I would like to ask him what was wrong with my latest messages.

Cannot remember.

> Can the censored messages me seen somewhere perhaps?

https://lists.ozlabs.org/pipermail/bitcoin-dev-moderation/

E.g.: https://lists.ozlabs.org/pipermail/bitcoin-dev-moderation/2022-May/000325.html

> That way the moderation could be audited.
>
> This is quite worrying in my opinion.
> But I'm biased, perhaps I deserve to be censored. It would still be nice to understand why, if you can help me.
> Now I wonder if this is the first time I was censored or I was censored in bip8 discussions too, and who else was censored, when, why and by whom.
> Perhaps I'm missing something about how the mailing list works and/or are giving this more importance than it has.

Sometimes the moderator is just busy living his or her life to moderate messages within 24 hours.

Regards,
ZmnSCPxj

Re: [bitcoin-dev] Speedy covenants (OP_CAT2)

[Nadav Ivgi]

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

On Sat, May 7, 2022 at 5:08 PM ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:
> * Even ***with*** `OP_CAT`, the following will enable non-recursive
covenants without enabling recursive covenants:
>  * `OP_CTV`, ...
> * With `OP_CAT`, the following would enable recursive covenants:
>  * `OP_CHECKSIGFROMSTACK`, ...

Why does CTV+CAT not enable recursive covenants while CSFS+CAT does?

CTV+CAT lets you similarly assert against the outputs and verify that they
match some dynamically constructed script.

Is it because CTV does not let you have a verified copy of the input's
prevout scriptPubKey on the stack [0], while with OP_CSFS you can because
the signature hash covers it?

But you don't actually need this for recursion. Instead of having the user
supply the script in the witness stack and verifying it against the input
to obtain the quine, the script can simply contain a copy of itself as an
initial push (minus this push). You can then reconstruct the full script
quine using OP_CAT, as a PUSH(<script>) followed by the literal <script>.

When I started experimenting with recursive covenants on liquid, I started
with the approach of verifying user-supplied witness data against the
input. It ended up being quite complex and verbose with taproot, because
you have to compute the tagged taptree hash from the tapscript and
TWEAKVERIFY it against the prevout's taproot output key (which also
requires the internal key and parity flag, provided as two extra witness
elements by the user).

I then realized that it is much simpler to have the tapscript hold a copy
of itself, that it's as safe and that it reduces the witness size cost
(because you don't need to do the entire taproot dance to verify the
tapscript), and switched to this approach.

Here are two examples of recursive covenants using this approach that I
played with (for liquid, rough sketches, very lightly tested and has some
known issues. the $label thing is a scriptwiz notation and can be ignored):

https://gist.github.com/shesek/be910619b247ce5e1aedd84e9ba9db42 (auction)
https://gist.github.com/shesek/ede9ca921a394580b23d301b8d84deea (listed
price sale with royalty)
(And here's the second example written in Minsc:
https://min.sc/next/#gist=e1c9914b4cb940137122d6d30972c25c)

shesek

[0] It does not cover it, and it cannot be done even by providing the full
prev tx because the prevout txid is not covered either.


On Sat, May 7, 2022 at 5:08 PM ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Good morning Jorge,
>
> > Thanks a lot for the many clarifications.
> > Yeah, I forgot it wasn't OP_CAT alone, but in combination with other
> things.
> > I guess this wouldn't be a covenants proposal then.
> > But simplicity would enable covenants too indeed, no?
> > Or did I get that wrong too?
>
> Yes, it would enable covenants.
>
> However, it could also enable *recursive* covenants, depending on what
> introspection operations are actually implemented (though maybe not?
> Russell O'Connor should be the one that answers this).
>
> It is helpful to delineate between non-recursive covenants from recursive
> covenants.
>
> * Even ***with*** `OP_CAT`, the following will enable non-recursive
> covenants without enabling recursive covenants:
>   * `OP_CTV`
>   * `SIGHASH_ANYPREVOUT`
> * With `OP_CAT`, the following would enable recursive covenants:
>   * `OP_EVAL`
>   * `OP_CHECKSIGFROMSTACK`
>   * `OP_TX`/`OP_TXHASH`
>   * ...possibly more.
>     * It is actually *easier* to *design* an opcode which inadvertently
> supports recursive covenants than to design one which avoids recursive
> covenants.
>
> Recursive covenants are very near to true Turing-completeness.
> We want to avoid Turing-completeness due to the halting problem being
> unsolvable for Turing-complete languages.
> That is, given just a program, we cannot determine for sure if for all
> possible inputs, it will terminate.
> It is important in our context (Bitcoin) that any SCRIPT programs we write
> *must* terminate, or else we run the risk of a DoS on the network.
>
> A fair amount of this is theoretical crap, but if you want to split hairs,
> recursive covenants are *not* Turing-complete, but are instead total
> functional programming with codata.
>
> As a very rough bastardization, a program written in a total functional
> programming language with codata will always assuredly terminate.
> However, the return value of a total functional programming language with
> codata can be another program.
> An external program (written in a Turing-complete language) could then
> just keep invoking the interpreter of the total functional programming
> language with codata (taking the output program and running it, taking
> *its* output program and running it, ad infinitum, thus effectively able to
> loop indefinitely.
>
> Translated to Bitcoin transactions, a recursive covenant system can force
> an output to be spent only if the output is spent on a transaction where
> one of the outputs is the same covenant (possibly with tweaks).
> Then an external program can keep passing the output program to the
> Bitcoin SCRIPT interpreter --- by building transactions that spend the
> previous output.
>
> This behavior is still of concern.
> It may be possible to attack the network by eroding its supply, by such a
> recursive covenant.
>
> --
>
> Common reactions:
>
> * We can just limit the number of opcodes we can process and then fail it
> if it takes too many operations!
>   That way we can avoid DoS!
>   * Yes, this indeed drops it from Turing-complete to total, possibly
> total functional programming **without** codata.
>     But if it is possible to treat data as code, it may drop it "total but
> with codata" instead (i.e. recursive covenants).
>     But if you want to avoid recursive covenants while allowing recursive
> ones (i.e. equivalent to total without codata), may I suggest you instead
> look at `OP_CTV` and `SIGHASH_ANYPREVOUT`?
>
> * What is so wrong with total-with-codata anyway??
>   So what if the recursive covenant could potentially consume all
> Bitcoins, nobody will pay to it except as a novelty!!
>   If you want to burn your funds, 1BitcoinEater willingly accepts it!
>   * The burden of proof-of-safety is on the proposer, so if you have some
> proof that total-with-codata is safe, by construction, then sure, we can
> add opcodes that may enable recursive covenants, and add `OP_CAT` back in
> too.
>
> 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: 8119 bytes --]

Re: [bitcoin-dev] Speedy covenants (OP_CAT2)

[ZmnSCPxj]

Good morning shesek,

> On Sat, May 7, 2022 at 5:08 PM ZmnSCPxj via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> > * Even ***with*** `OP_CAT`, the following will enable non-recursive covenants without enabling recursive covenants:
> >  * `OP_CTV`, ...
> > * With `OP_CAT`, the following would enable recursive covenants:
> >  * `OP_CHECKSIGFROMSTACK`, ...
>
> Why does CTV+CAT not enable recursive covenants while CSFS+CAT does?
>
> CTV+CAT lets you similarly assert against the outputs and verify that they match some dynamically constructed script.
>
> Is it because CTV does not let you have a verified copy of the input's prevout scriptPubKey on the stack [0], while with OP_CSFS you can because the signature hash covers it?
>
> But you don't actually need this for recursion. Instead of having the user supply the script in the witness stack and verifying it against the input to obtain the quine, the script can simply contain a copy of itself as an initial push (minus this push). You can then reconstruct the full script quine using OP_CAT, as a PUSH(<script>) followed by the literal <script>.

    <OP_PUSH_length-of-script> OP_SWAP OP_DUP OP_CAT OP_CAT <rest of script...>

Ha, yes, looks like you are correct here.

`OP_CAT` makes *all* covenant opcodes recursive, because you can always quine using `OP_CAT`.

By itself it does not make recursive covenants, but with probably any opcode it would.

Looks like `OP_CAT` is not getting enabled until after we are reasonably sure that recursive covenants are not really unsafe.

Regards,
ZmnSCPxj

Re: [bitcoin-dev] Speedy covenants (OP_CAT2)

[vjudeu]

> Looks like `OP_CAT` is not getting enabled until after we are reasonably sure that recursive covenants are not really unsafe.

Maybe we should use OP_SUBSTR instead of OP_CAT. Or even better: OP_SPLIT. Then, we could have OP_SPLIT <n> <pos1> <pos2> ... <posN> that would split a string N times (so there will be N+1 pieces). Or we could have just OP_SPLIT <pos> to split one string into two. Or maybe OP_2SPLIT and OP_3SPLIT, just to split into two or three pieces (as we have OP_2DUP and OP_3DUP). I think OP_SUBSTR or OP_SPLIT is better than OP_CAT, because then things always get smaller and we can be always sure that we will have one byte as the smallest unit in our Script.

On 2022-05-08 04:20:19 user ZmnSCPxj via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> Good morning shesek,

> On Sat, May 7, 2022 at 5:08 PM ZmnSCPxj via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> > * Even ***with*** `OP_CAT`, the following will enable non-recursive covenants without enabling recursive covenants:
> >  * `OP_CTV`, ...
> > * With `OP_CAT`, the following would enable recursive covenants:
> >  * `OP_CHECKSIGFROMSTACK`, ...
>
> Why does CTV+CAT not enable recursive covenants while CSFS+CAT does?
>
> CTV+CAT lets you similarly assert against the outputs and verify that they match some dynamically constructed script.
>
> Is it because CTV does not let you have a verified copy of the input's prevout scriptPubKey on the stack [0], while with OP_CSFS you can because the signature hash covers it?
>
> But you don't actually need this for recursion. Instead of having the user supply the script in the witness stack and verifying it against the input to obtain the quine, the script can simply contain a copy of itself as an initial push (minus this push). You can then reconstruct the full script quine using OP_CAT, as a PUSH(<script>) followed by the literal <script>.

    <OP_PUSH_length-of-script> OP_SWAP OP_DUP OP_CAT OP_CAT <rest of script...>

Ha, yes, looks like you are correct here.

`OP_CAT` makes *all* covenant opcodes recursive, because you can always quine using `OP_CAT`.

By itself it does not make recursive covenants, but with probably any opcode it would.

Looks like `OP_CAT` is not getting enabled until after we are reasonably sure that recursive covenants are not really unsafe.

Regards,
ZmnSCPxj
_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] Speedy covenants (OP_CAT2)

[ZmnSCPxj]

Good morning vjudeu,


> > Looks like `OP_CAT` is not getting enabled until after we are reasonably sure that recursive covenants are not really unsafe.
>
> Maybe we should use OP_SUBSTR instead of OP_CAT. Or even better: OP_SPLIT. Then, we could have OP_SPLIT <n> <pos1> <pos2> ... <posN> that would split a string N times (so there will be N+1 pieces). Or we could have just OP_SPLIT <pos> to split one string into two. Or maybe OP_2SPLIT and OP_3SPLIT, just to split into two or three pieces (as we have OP_2DUP and OP_3DUP). I think OP_SUBSTR or OP_SPLIT is better than OP_CAT, because then things always get smaller and we can be always sure that we will have one byte as the smallest unit in our Script.

Unfortunately `OP_SUBSTR` can be used to synthesize an effective `OP_CAT`.

Instead of passing in two items on the witness stack to be `OP_CAT`ted together, you instead pass in the two items to concatenate, and *then* the concatenation.
Then you can synthesize a SCRIPT which checks that the supposed concatenation is indeed the two items to be concatenated.

Recursive covenants DO NOT arise from the increasing amounts of memory the trivial `OP_DUP OP_CAT OP_DUP OP_CAT` repetition allocates.

REMEMBER: `OP_CAT` BY ITSELF DOES NOT ENABLE COVENANTS, WHETHER RECURSIVE OR NOT.

Instead, `OP_CAT` enable recursive covenants (which we are not certain are safe) because `OP_CAT` allows quining to be done.
Quining is a technique to pass a SCRIPT with a copy of its code, so that it can then enforce that the output is passed to the exact same input SCRIPT.

`OP_SUBSTR` allows a SCRIPT to validate that it is being passed a copy of itself and that the complete SCRIPT contains its copy as an `OP_PUSH` and the rest of the SCRIPT as actual code.
This is done by `OP_SUBSTR` the appropriate parts of the supposed complete SCRIPT and comparing them to a reference value we have access to (because our own SCRIPT was passed to us inside an `OP_PUSH`).

   # Assume that the witness stack top is the concatenation of
   #   `OP_PUSH`, the SCRIPT below, then the`SCRIPT below.
   # Assume this SCRIPT is prepended with an OP_PUSH of our own code.
   OP_TOALTSTACK # save our reference
   OP_DUP 1 <scriptlength> OP_SUBSTR # Get the OP_PUSH argument
   OP_FROMALTSTACK OP_DUP OP_TOALTSTACK # Get our reference
   OP_EQUALVERIFY # check they are the same
   OP_DUP <1 + scriptlength> <scriptlength> OP_SUBSTR # Get the SCRIPT body
   OP_FROMALTSTACK # Get our reference
   OP_EQUALVERIFY # check they are the same
   # At this point, we have validated that the top of the witness stack
   # is the quine of this SCRIPT.
   # TODO: validate the `OP_PUSH` instruction, left as an exercise for the
   # reader.

Thus, `OP_SUBSTR` is enough to enable quining and is enough to implement recursive covenants.

We cannot enable `OP_SUBSTR` either, unless we are reasonably sure that recursive covenants are safe.

(FWIW recursive covenants are probably safe, as they are not in fact Turing-complete, they are a hair less powerful, equivalent to the total functional programming with codata.)

Regards,
ZmnSCPxj

Re: [bitcoin-dev] Speedy covenants (OP_CAT2)

[alicexbt]

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

Hi vjudeu,

> It can be changed by using different sighashes, for example, it is possible to create a "negative fee transaction", where all transaction costs are paid by receiver. Using SIGHASH_SINGLE | SIGHASH_ANYONECANPAY with a higher amount in outputs than inputs is enough to do that, see testnet3 transaction 495d2007ae8b741c70c3d278c02ce03702223b9675e954ecabbb634c6cd5bf40.

This transaction has 2 inputs: 0.00074 tBTC and 0.00073 tBTC (0.00074 + 0.00073 = 0.00147) which is more than output amount 0.001 tBTC

/dev/fd0

Sent with [ProtonMail](https://protonmail.com/) secure email.
------- Original Message -------
On Saturday, May 7th, 2022 at 9:22 AM, vjudeu via bitcoin-dev bitcoin-dev@lists.linuxfoundation.org wrote:

>> Re-enabling OP_CAT with the exact same OP would be a hardfork, but creating a new OP_CAT2 that does the same would be a softfork.
>
> We have TapScript for that. OP_CAT is defined as OP_SUCCESS, it can be re-enabled in a soft-fork way. For now, OP_CAT in TapScript simply means "anyone can move those coins", so adding some restrictions is all we need to re-enable this opcode. Introducing OP_CAT2 is not needed at all, unless it will be totally different, but then it should not be named as OP_CAT2, but rather as OP_SOMETHING_ELSE, it depends how different it will be from OP_CAT.
>
>> OP_1 OP_DUP OP_CAT OP_DUP OP_CAT OP_DUP OP_CAT OP_DUP OP_CAT OP_DUP OP_CAT OP_DUP OP_CAT ...
>
> So we can use OP_SUBSTR instead. Maybe even OP_SPLIT will be enough, if data expansion is the only problem, then we can focus on getting it smaller. Or better, we could use OP_FIND that would return true/false answer if element A is a part of element B, when we do byte-to-byte comparison. In general, we can use many different string-based functions to do the same things, we can choose something that will not exponentially explode as OP_CAT.
>
>> It was considered unfair that the sender is paying for the security of the receiver.
>
> It can be changed by using different sighashes, for example, it is possible to create a "negative fee transaction", where all transaction costs are paid by receiver. Using SIGHASH_SINGLE | SIGHASH_ANYONECANPAY with a higher amount in outputs than inputs is enough to do that, see testnet3 transaction 495d2007ae8b741c70c3d278c02ce03702223b9675e954ecabbb634c6cd5bf40.
>
> On 2022-05-07 05:06:46 user ZmnSCPxj via bitcoin-dev bitcoin-dev@lists.linuxfoundation.org wrote:
>
>> Good morning Jorge,
>
>> OP_CAT was removed. If I remember correctly, some speculated that perhaps it was removed because it could allow covenants.I don't remember any technical concern about the OP besides enabling covenants.Before it was a common opinion that covenants shouldn't be enabled in bitcoin because, despite having good use case, there are some nasty attacks that are enabled with them too. These days it seems the opinion of the benefits being worth the dangers is quite generalized. Which is quite understandable given that more use cases have been thought since then.
>
> I think the more accurate reason for why it was removed is because the following SCRIPT of N size would lead to 2^N memory usage:
>
> OP_1 OP_DUP OP_CAT OP_DUP OP_CAT OP_DUP OP_CAT OP_DUP OP_CAT OP_DUP OP_CAT OP_DUP OP_CAT ...
>
> In particular it was removed at about the same time as OP_MUL, which has similar behavior (consider that multiplying two 32-bit numbers results in a 64-bit number, similar to OP_CATting a vector to itself).
>
> OP_CAT was removed long before covenants were even expressed as a possibility.
>
> Covenants were first expressed as a possibility, I believe, during discussions around P2SH.
> Basically, at the time, the problem was this:
>
> * Some receivers wanted to use k-of-n multisignature for improved security.
> * The only way to implement this, pre-P2SH, was by putting in the scriptPubKey all the public keys.
> * The sender is the one paying for the size of the scriptPubKey.
> * It was considered unfair that the sender is paying for the security of the receiver.
>
> Thus, OP_EVAL and the P2SH concept was conceived.
> Instead of the scriptPubKey containing the k-of-n multisignature, you create a separate script containing the public keys, then hash it, and the scriptPubKey would contain the hash of the script.
> By symmetry with the P2PKH template:
>
> OP_DUP OP_HASH160 <hash160(pubkey)> OP_EQUALVERIFY OP_CHECKSIG
>
> The P2SH template would be:
>
> OP_DUP OP_HASH160 <hash160(redeemScript)> OP_EQUALVERIFY OP_EVAL
>
> OP_EVAL would take the stack top vector and treat it as a Bitcoin SCRIPT.
>
> It was then pointed out that OP_EVAL could be used to create recursive SCRIPTs by quining using OP_CAT.
> OP_CAT was already disabled by then, but people were talking about re-enabling it somehow by restricting the output size of OP_CAT to limit the O(2^N) behavior.
>
> Thus, since then, OP_CAT has been associated with recursive covenants (and people are now reluctant to re-enable it even with a limit on its output size, because recursive covenants).
> In particular, OP_CAT in combination with OP_CHECKSIGFROMSTACK and OP_CHECKSIG, you could get a deferred OP_EVAL and then use OP_CAT too to quine.
>
> Because of those concerns, the modern P2SH is now "just a template" with an implicit OP_EVAL of the redeemScript, but without any OP_EVAL being actually enabled.
>
> (OP_EVAL cannot replace an OP_NOP in a softfork, but it is helpful to remember that P2SH was pretty much what codified the difference between softfork and hardfork, and the community at the time was small enough (or so it seemed) that a hardfork might not have been disruptive.)
>
>> Re-enabling OP_CAT with the exact same OP would be a hardfork, but creating a new OP_CAT2 that does the same would be a softfork.
>
> If you are willing to work in Taproot the same OP-code can be enabled in a softfork by using a new Tapscript version.
>
> If you worry about quantum-computing-break, a new SegWit version (which is more limited than Tapscript versions, unfortunately) can also be used, creating a new P2WSHv2 (or whatever version) that enables these opcodes.
>
>> As far a I know, this is the covenants proposal that has been implemented for the longest time, if that's to be used as a selection criteria.And as always, this is not incompatible with deploying other convenant proposals later.
>
> No, it was OP_EVAL, not OP_CAT.
> In particular if OP_EVAL was allowed in the redeemScript then it would enable covenants as well.
> It was just pointed out that OP_CAT enables recursive covenenats in combination with OP_EVAL-in-redeemScript.
>
> In particular, in combination with OP_CAT, OP_EVAL not only allows recursive covenants, but also recursion within a SCRIPT i.e. unbounded SCRIPT execution.
> Thus, OP_EVAL is simply not going to fly, at all.
>
>> Personally I find the simplicity proposal the best one among all the covenant proposals by far, including this one.But I understand that despite the name, the proposal is harder to review and test than other proposals, for it wouldn't simply add covenants, but a complete new scripting language that is better in many senses.Speedy covenants, on the other hand, is much simpler and has been implemented for longer, so in principle, it should be easier to deploy in a speedy manner.
>>
>> What are the main arguments against speedy covenants (aka op_cat2) and against deploying simplicity in bitcoin respectively?
>> Sorry if this was discussed before.
>
> OP_CAT, by itself, does not implement any covenants --- instead, it creates recursive covenants when combined with almost all covenant opcodes.
>
> 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: 9980 bytes --]

Re: [bitcoin-dev] Speedy covenants (OP_CAT2)

[vjudeu]

> This transaction has 2 inputs: 0.00074 tBTC and 0.00073 tBTC (0.00074 + 0.00073 = 0.00147) which is more than output amount 0.001 tBTC

It was created without the second input, see: https://bitcointalk.org/index.php?topic=5390103.msg59616324#msg59616324
I didn't touch that later, the signatures are the same. Some user named coinlatte just completed it: https://bitcointalk.org/index.php?topic=5390103.msg60029953#msg60029953


On 2022-05-11 17:25:41 user alicexbt <alicexbt@protonmail.com> wrote:

Hi vjudeu,

It can be changed by using different sighashes, for example, it is possible to create a "negative fee transaction", where all transaction costs are paid by receiver. Using SIGHASH_SINGLE | SIGHASH_ANYONECANPAY with a higher amount in outputs than inputs is enough to do that, see testnet3 transaction 495d2007ae8b741c70c3d278c02ce03702223b9675e954ecabbb634c6cd5bf40.


This transaction has 2 inputs: 0.00074 tBTC and 0.00073 tBTC (0.00074 + 0.00073 = 0.00147) which is more than output amount 0.001 tBTC


/dev/fd0





Sent with ProtonMail secure email.

------- Original Message -------
On Saturday, May 7th, 2022 at 9:22 AM, vjudeu via bitcoin-dev bitcoin-dev@lists.linuxfoundation.org wrote:







Re-enabling OP_CAT with the exact same OP would be a hardfork, but creating a new OP_CAT2 that does the same would be a softfork.

We have TapScript for that. OP_CAT is defined as OP_SUCCESS, it can be re-enabled in a soft-fork way. For now, OP_CAT in TapScript simply means "anyone can move those coins", so adding some restrictions is all we need to re-enable this opcode. Introducing OP_CAT2 is not needed at all, unless it will be totally different, but then it should not be named as OP_CAT2, but rather as OP_SOMETHING_ELSE, it depends how different it will be from OP_CAT.

OP_1 OP_DUP OP_CAT OP_DUP OP_CAT OP_DUP OP_CAT OP_DUP OP_CAT OP_DUP OP_CAT OP_DUP OP_CAT ...

So we can use OP_SUBSTR instead. Maybe even OP_SPLIT will be enough, if data expansion is the only problem, then we can focus on getting it smaller. Or better, we could use OP_FIND that would return true/false answer if element A is a part of element B, when we do byte-to-byte comparison. In general, we can use many different string-based functions to do the same things, we can choose something that will not exponentially explode as OP_CAT.

It was considered unfair that the sender is paying for the security of the receiver.

It can be changed by using different sighashes, for example, it is possible to create a "negative fee transaction", where all transaction costs are paid by receiver. Using SIGHASH_SINGLE | SIGHASH_ANYONECANPAY with a higher amount in outputs than inputs is enough to do that, see testnet3 transaction 495d2007ae8b741c70c3d278c02ce03702223b9675e954ecabbb634c6cd5bf40.

On 2022-05-07 05:06:46 user ZmnSCPxj via bitcoin-dev bitcoin-dev@lists.linuxfoundation.org wrote:

Good morning Jorge,

OP_CAT was removed. If I remember correctly, some speculated that perhaps it was removed because it could allow covenants.I don't remember any technical concern about the OP besides enabling covenants.Before it was a common opinion that covenants shouldn't be enabled in bitcoin because, despite having good use case, there are some nasty attacks that are enabled with them too. These days it seems the opinion of the benefits being worth the dangers is quite generalized. Which is quite understandable given that more use cases have been thought since then.

I think the more accurate reason for why it was removed is because the following SCRIPT of N size would lead to 2^N memory usage:

OP_1 OP_DUP OP_CAT OP_DUP OP_CAT OP_DUP OP_CAT OP_DUP OP_CAT OP_DUP OP_CAT OP_DUP OP_CAT ...

In particular it was removed at about the same time as OP_MUL, which has similar behavior (consider that multiplying two 32-bit numbers results in a 64-bit number, similar to OP_CATting a vector to itself).

OP_CAT was removed long before covenants were even expressed as a possibility.

Covenants were first expressed as a possibility, I believe, during discussions around P2SH.
Basically, at the time, the problem was this:

* Some receivers wanted to use k-of-n multisignature for improved security.
* The only way to implement this, pre-P2SH, was by putting in the scriptPubKey all the public keys.
* The sender is the one paying for the size of the scriptPubKey.
* It was considered unfair that the sender is paying for the security of the receiver.

Thus, OP_EVAL and the P2SH concept was conceived.
Instead of the scriptPubKey containing the k-of-n multisignature, you create a separate script containing the public keys, then hash it, and the scriptPubKey would contain the hash of the script.
By symmetry with the P2PKH template:

OP_DUP OP_HASH160 <hash160(pubkey)> OP_EQUALVERIFY OP_CHECKSIG

The P2SH template would be:

OP_DUP OP_HASH160 <hash160(redeemScript)> OP_EQUALVERIFY OP_EVAL

OP_EVAL would take the stack top vector and treat it as a Bitcoin SCRIPT.

It was then pointed out that OP_EVAL could be used to create recursive SCRIPTs by quining using OP_CAT.
OP_CAT was already disabled by then, but people were talking about re-enabling it somehow by restricting the output size of OP_CAT to limit the O(2^N) behavior.

Thus, since then, OP_CAT has been associated with recursive covenants (and people are now reluctant to re-enable it even with a limit on its output size, because recursive covenants).
In particular, OP_CAT in combination with OP_CHECKSIGFROMSTACK and OP_CHECKSIG, you could get a deferred OP_EVAL and then use OP_CAT too to quine.

Because of those concerns, the modern P2SH is now "just a template" with an implicit OP_EVAL of the redeemScript, but without any OP_EVAL being actually enabled.

(OP_EVAL cannot replace an OP_NOP in a softfork, but it is helpful to remember that P2SH was pretty much what codified the difference between softfork and hardfork, and the community at the time was small enough (or so it seemed) that a hardfork might not have been disruptive.)

Re-enabling OP_CAT with the exact same OP would be a hardfork, but creating a new OP_CAT2 that does the same would be a softfork.

If you are willing to work in Taproot the same OP-code can be enabled in a softfork by using a new Tapscript version.

If you worry about quantum-computing-break, a new SegWit version (which is more limited than Tapscript versions, unfortunately) can also be used, creating a new P2WSHv2 (or whatever version) that enables these opcodes.

As far a I know, this is the covenants proposal that has been implemented for the longest time, if that's to be used as a selection criteria.And as always, this is not incompatible with deploying other convenant proposals later.

No, it was OP_EVAL, not OP_CAT.
In particular if OP_EVAL was allowed in the redeemScript then it would enable covenants as well.
It was just pointed out that OP_CAT enables recursive covenenats in combination with OP_EVAL-in-redeemScript.

In particular, in combination with OP_CAT, OP_EVAL not only allows recursive covenants, but also recursion within a SCRIPT i.e. unbounded SCRIPT execution.
Thus, OP_EVAL is simply not going to fly, at all.

Personally I find the simplicity proposal the best one among all the covenant proposals by far, including this one.But I understand that despite the name, the proposal is harder to review and test than other proposals, for it wouldn't simply add covenants, but a complete new scripting language that is better in many senses.Speedy covenants, on the other hand, is much simpler and has been implemented for longer, so in principle, it should be easier to deploy in a speedy manner.

What are the main arguments against speedy covenants (aka op_cat2) and against deploying simplicity in bitcoin respectively?
Sorry if this was discussed before.

OP_CAT, by itself, does not implement any covenants --- instead, it creates recursive covenants when combined with almost all covenant opcodes.

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

Re: [bitcoin-dev] Speedy covenants (OP_CAT2)

[Russell O'Connor]

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

On Wed, May 11, 2022 at 7:42 AM ZmnSCPxj via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> REMEMBER: `OP_CAT` BY ITSELF DOES NOT ENABLE COVENANTS, WHETHER RECURSIVE
> OR NOT.
>

I think the state of the art has advanced to the point where we can say
"OP_CAT in tapscript enables non recursive covenants and it is unknown
whether OP_CAT can enable recursive covenants or not".

A. Poelstra in
https://www.wpsoftware.net/andrew/blog/cat-and-schnorr-tricks-i.html show
how to use CAT to use the schnorr verification opcode to get the sighash
value + 1 onto the stack, and then through some grinding and some more CAT,
get the actual sighash value on the stack.  From there we can use SHA256 to
get the signed transaction data onto the stack and apply introspect (using
CAT) to build functionality similar to OP_CTV.

The missing bits for enabling recursive covenants comes down to needing to
transform a scriptpubkey into an taproot address, which involves some
tweaking.  Poelstra has suggested that it might be possible to hijack the
ECDSA checksig operation from a parallel, legacy input, in order to perform
the calculations for this tweaking.  But as far as I know no one has yet
been able to achieve this feat.

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

Re: [bitcoin-dev] Speedy covenants (OP_CAT2)

[ZmnSCPxj]

Good morning Russell,

> On Wed, May 11, 2022 at 7:42 AM ZmnSCPxj via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> > REMEMBER: `OP_CAT` BY ITSELF DOES NOT ENABLE COVENANTS, WHETHER RECURSIVE OR NOT.
>
>
> I think the state of the art has advanced to the point where we can say "OP_CAT in tapscript enables non recursive covenants and it is unknown whether OP_CAT can enable recursive covenants or not".
>
> A. Poelstra in https://www.wpsoftware.net/andrew/blog/cat-and-schnorr-tricks-i.html show how to use CAT to use the schnorr verification opcode to get the sighash value + 1 onto the stack, and then through some grinding and some more CAT, get the actual sighash value on the stack. From there we can use SHA256 to get the signed transaction data onto the stack and apply introspect (using CAT) to build functionality similar to OP_CTV.
>
> The missing bits for enabling recursive covenants comes down to needing to transform a scriptpubkey into an taproot address, which involves some tweaking. Poelstra has suggested that it might be possible to hijack the ECDSA checksig operation from a parallel, legacy input, in order to perform the calculations for this tweaking. But as far as I know no one has yet been able to achieve this feat.

Hmm, I do not suppose it would have worked in ECDSA?
Seems like this exploits linearity in the Schnorr.
For the ECDSA case it seems that the trick in that link leads to `s = e + G[x]` where `G[x]` is the x-coordinate of `G`.
(I am not a mathist, so I probably am not making sense; in particular, there may be an operation to add two SECP256K1 scalars that I am not aware of)

In that case, since Schnorr was added later, I get away by a technicality, since it is not *just* `OP_CAT` which enabled this style of covenant, it was `OP_CAT` + BIP340 v(^^);;;;;

Also holy shit math is scary.

Seems this also works with `OP_SUBSTR`, simply by inverting it into "validate that the concatenation is correct" rather than "concatenate it ourselves".




So really: are recursive covenants good or...?
Because if recursive covenants are good, what we should really work on is making them cheap (in CPU load/bandwidth load terms) and private, to avoid centralization and censoring.

Regards,
ZmnSCPxj

Re: [bitcoin-dev] Speedy covenants (OP_CAT2)

[Russell O'Connor]

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

On Wed, May 11, 2022 at 11:07 PM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:

> Good morning Russell,
>
> > On Wed, May 11, 2022 at 7:42 AM ZmnSCPxj via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
> >
> > > REMEMBER: `OP_CAT` BY ITSELF DOES NOT ENABLE COVENANTS, WHETHER
> RECURSIVE OR NOT.
> >
> >
> > I think the state of the art has advanced to the point where we can say
> "OP_CAT in tapscript enables non recursive covenants and it is unknown
> whether OP_CAT can enable recursive covenants or not".
> >
> > A. Poelstra in
> https://www.wpsoftware.net/andrew/blog/cat-and-schnorr-tricks-i.html show
> how to use CAT to use the schnorr verification opcode to get the sighash
> value + 1 onto the stack, and then through some grinding and some more CAT,
> get the actual sighash value on the stack. From there we can use SHA256 to
> get the signed transaction data onto the stack and apply introspect (using
> CAT) to build functionality similar to OP_CTV.
> >
> > The missing bits for enabling recursive covenants comes down to needing
> to transform a scriptpubkey into an taproot address, which involves some
> tweaking. Poelstra has suggested that it might be possible to hijack the
> ECDSA checksig operation from a parallel, legacy input, in order to perform
> the calculations for this tweaking. But as far as I know no one has yet
> been able to achieve this feat.
>
> Hmm, I do not suppose it would have worked in ECDSA?
> Seems like this exploits linearity in the Schnorr.
> For the ECDSA case it seems that the trick in that link leads to `s = e +
> G[x]` where `G[x]` is the x-coordinate of `G`.
> (I am not a mathist, so I probably am not making sense; in particular,
> there may be an operation to add two SECP256K1 scalars that I am not aware
> of)
>
> In that case, since Schnorr was added later, I get away by a technicality,
> since it is not *just* `OP_CAT` which enabled this style of covenant, it
> was `OP_CAT` + BIP340 v(^^);;;;;
>

Correct.


> Also holy shit math is scary.
>
> Seems this also works with `OP_SUBSTR`, simply by inverting it into
> "validate that the concatenation is correct" rather than "concatenate it
> ourselves".
>
>
>
>
> So really: are recursive covenants good or...?
> Because if recursive covenants are good, what we should really work on is
> making them cheap (in CPU load/bandwidth load terms) and private, to avoid
> centralization and censoring.
>

My view is that recursive covenants are inevitable.  It is nearly
impossible to have programmable money without it because it is so difficult
to avoid.

Given that we cannot have programmable money without recursive covenants
and given all the considerations already discussed regarding them, i.e. no
worse than being compelled to co-sign transactions, and that user generated
addresses won't be encumbered by a covenant unless they specifically
generate it to be, I do think it makes sense to embrace them.


> Regards,
> ZmnSCPxj
>

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

Re: [bitcoin-dev] Speedy covenants (OP_CAT2)

[Anthony Towns]

On Thu, May 12, 2022 at 06:48:44AM -0400, Russell O'Connor via bitcoin-dev wrote:
> On Wed, May 11, 2022 at 11:07 PM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:
> > So really: are recursive covenants good or...?
> My view is that recursive covenants are inevitable.  It is nearly
> impossible to have programmable money without it because it is so difficult
> to avoid.

I think my answer is that yes they are good: they enable much more
powerful contracting.

Of course, like any cryptographic tool they can also be harmful to you if
you misuse them, and so before you use them yourself you should put in the
time to understand them well enough that you *don't* misuse them. Same as
using a kitchen knife, or riding a bicycle, or swimming. Can be natural
to be scared at first, too.

> Given that we cannot have programmable money without recursive covenants
> and given all the considerations already discussed regarding them, i.e. no
> worse than being compelled to co-sign transactions, and that user generated
> addresses won't be encumbered by a covenant unless they specifically
> generate it to be, I do think it makes sense to embrace them.

I think that's really the easy way to be sure *you* aren't at risk
from covenants: just follow the usual "not your keys, not your coins"
philosophy.

The way you currently generate an address from a private key already
guarantees that *your* funds won't be encumbered by any covenants; all
you need to do is to keep doing that. And generating the full address
yourself is already necessary with taproot: if you don't understand
all the tapscript MAST paths, then even though you can spend the coin,
one of those paths you don't know about might already allow someone to
steal your funds. But if you generated the address, you (or at least your
software) will understand everything and not include anything dangerous,
so your funds really are safu.

It may be that some people will refuse to send money to your address
because they have some rule that says "I'll only send money to people who
encumber all their funds with covenant X" and you didn't encumber your
address in that way -- but that just means they're refusing to pay you,
just as people who say "I'll only pay you off-chain via coinbase" or
"I'll only pay you via SWIFT" won't send funds to your bitcoin address.

Other examples might include "we only support segwit-v0 addresses not
taproot ones", or "you're on an OFAC sanctions list so I can't send
to you or the government will put me in prison" or "my funds are in a
multisig with the government who won't pay to anyone who isn't also in
a multisig with them".

It does mean you still need people with the moral fortitude to say "no,
if you can't pay me properly, we can't do business" though.

Even better: in so far as wallet software will just ignore any funds
sent to addresses that they didn't generate themselves according to the
rules you selected, you can already kind of outsource that policy to
your wallet. And covenants, recursive or otherwise, don't change that.


For any specific opcode proposal, I think you still want to consider

 1) how much you can do with it
 2) how efficient it is to validate (and thus how cheap it is to use)
 3) how easy it is to make it do what you want
 4) how helpful it is at preventing bugs
 5) how clean and maintainable the validation code is

I guess to me CTV and APO are weakest at (1); CAT/CSFS falls down on
(3) and (4); OP_TX is probably weakest at (5) and maybe not as good as
we'd like at (3) and (4)?

Cheers,
aj

Re: [bitcoin-dev] Speedy covenants (OP_CAT2)

[Russell O'Connor]

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

On Fri, May 13, 2022 at 5:43 PM Anthony Towns <aj@erisian.com.au> wrote:

> For any specific opcode proposal, I think you still want to consider
>
>  1) how much you can do with it
>  2) how efficient it is to validate (and thus how cheap it is to use)
>  3) how easy it is to make it do what you want
>  4) how helpful it is at preventing bugs
>  5) how clean and maintainable the validation code is
>
> I guess to me CTV and APO are weakest at (1); CAT/CSFS falls down on
> (3) and (4); OP_TX is probably weakest at (5) and maybe not as good as
> we'd like at (3) and (4)?
>

FWIW, I think the rmain reasons to do CAT+CSFS is to validate oracle
messages and pubkey delegation.  The ability to covenants would be
secondary and would mostly serve to get us some real user data about what
sort of covenants users find especially valuable.

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

Re: [bitcoin-dev] Speedy covenants (OP_CAT2)

[Erik Aronesty]

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

>
>
>
> FWIW, I think the rmain reasons to do CAT+CSFS is to validate oracle
> messages and pubkey delegation.  The ability to covenants would be
> secondary and would mostly serve to get us some real user data about what
> sort of covenants users find especially valuable.
>

I don't think this should be discounted.   I think it's worthwhile to
willingly include possibly less-than-awesome, but proven perfectly-safe
opcodes, knowing we will have to validate them forever, even if new, cooler
and more widely-used ones replace them years from now.

I honestly don't think the development of the latter will happen without
some version of the former.

Personally I am satisfied:

  - the safety of covenants, in general, is covered by how addresses are
generated
  - fears of forced forward-encumbrance are not any worse than can be
easily done today
  - ctv+apo, cat+csfs are fine, but we should pick ones that everyone
thinks are "good enough for everyone who cares about them"
  - they are not an undue burden on nodes in terms of
validate-cpu-cycles-per-byte (have we proven this?)
  - the complexity is low, code is easy to validate
  - won't introduce DDOS attack vectors (also needs to be proven i think?)
  - the game theory underpinning selfish miner support of the chain won't
be altered by causing a widespread use of on-chain leveraging instruments
(shorting bitcoin on-chain would be dangerous, for example)




>

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