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

From: ZmnSCPxj <ZmnSCPxj@protonmail•com>
To: "Jorge Timón" <jtimon@jtimon•cc>
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Speedy covenants (OP_CAT2)
Date: Sat, 07 May 2022 14:08:27 +0000	[thread overview]
Message-ID: <CiNPwh37hW6iDk3mMg6G2QWMPS5ADUvSdySnNp6esOaloiVyoPwHGxOMLyG6mMGQnyf4iGcch12XfmOB2WnFcETwFwvRTSNSeBu27G9Cju8=@protonmail.com> (raw)
In-Reply-To: <CABm2gDrdwMjLu=i0p2m4SZ_91xpr-RvwSSWOnS9jhaQ3uaCxPA@mail.gmail.com>

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