Date: Sat, 07 May 2022 14:08:27 +0000
To: =?utf-8?Q?Jorge_Tim=C3=B3n?= <jtimon@jtimon.cc>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <CiNPwh37hW6iDk3mMg6G2QWMPS5ADUvSdySnNp6esOaloiVyoPwHGxOMLyG6mMGQnyf4iGcch12XfmOB2WnFcETwFwvRTSNSeBu27G9Cju8=@protonmail.com>
In-Reply-To: <CABm2gDrdwMjLu=i0p2m4SZ_91xpr-RvwSSWOnS9jhaQ3uaCxPA@mail.gmail.com>
References: <CABm2gDoivzQKFr6KqeqW6+Lx7xFVprRCUAn1k3X6P29NPzw+yQ@mail.gmail.com>
 <1JO1xrnJ9GwGM4TgLH_rL_LpnZgSb1SyeEOJ9Gzc1VMbKUrmxSh-zUXKwFNvp_5wyiDtRviOf-gRJbrfbhOJl-qym1eEHXpoDAgjE9juucw=@protonmail.com>
 <CABm2gDrdwMjLu=i0p2m4SZ_91xpr-RvwSSWOnS9jhaQ3uaCxPA@mail.gmail.com>
Feedback-ID: 2872618:user:proton
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Speedy covenants (OP_CAT2)
Precedence: list

Good morning Jorge,

> Thanks a lot for the many clarifications.
> Yeah, I forgot it wasn't OP_CAT alone, but in combination with other thin=
gs.
> 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 intr=
ospection 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 c=
ovenants.

* Even ***with*** `OP_CAT`, the following will enable non-recursive covenan=
ts 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 sup=
ports recursive covenants than to design one which avoids recursive covenan=
ts.

Recursive covenants are very near to true Turing-completeness.
We want to avoid Turing-completeness due to the halting problem being unsol=
vable for Turing-complete languages.
That is, given just a program, we cannot determine for sure if for all poss=
ible 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 functi=
onal programming with codata.

As a very rough bastardization, a program written in a total functional pro=
gramming language with codata will always assuredly terminate.
However, the return value of a total functional programming language with c=
odata 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 indefi=
nitely.

Translated to Bitcoin transactions, a recursive covenant system can force a=
n 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 ou=
tput.

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

--

Common reactions:

* We can just limit the number of opcodes we can process and then fail it i=
f 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 o=
nes (i.e. equivalent to total without codata), may I suggest you instead lo=
ok 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 p=
roof 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