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

From: Nadav Ivgi <nadav@shesek•info>
To: ZmnSCPxj <ZmnSCPxj@protonmail•com>,
	 Bitcoin Protocol Discussion
	<bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Speedy covenants (OP_CAT2)
Date: Sun, 8 May 2022 05:03:25 +0300	[thread overview]
Message-ID: <CAGXD5f2vLaZgEUG7eu6S9YQSSLeJ0LAM+i2o1ngVb=VmxS3Rrg@mail.gmail.com> (raw)
In-Reply-To: <CiNPwh37hW6iDk3mMg6G2QWMPS5ADUvSdySnNp6esOaloiVyoPwHGxOMLyG6mMGQnyf4iGcch12XfmOB2WnFcETwFwvRTSNSeBu27G9Cju8=@protonmail.com>

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