Date: Tue, 8 Mar 2022 11:27:19 +1000
From: Anthony Towns <aj@erisian.com.au>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Message-ID: <20220308012719.GA6992@erisian.com.au>
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <uOr9bwW2C0lwMSiUOEie2rzyrA7uE4Rm7kVnU2FnF9jyMGjYDvN0WhDM6QbZ_XxNlu44WqE7meXBZAeHAd94DAWnYcSBOPuo4nb4UQp2Wmk=@protonmail.com>
 <CAHUJnBCrw0n_9=2gugMhTW6QCjStBFxEsGrF=BY9JX806OurXQ@mail.gmail.com>
User-Agent: Mutt/1.10.1 (2018-07-13)
Cc: Bram Cohen <bram@chia.net>
Subject: Re: [bitcoin-dev] bitcoin scripting and lisp
Precedence: list

On Sun, Mar 06, 2022 at 10:26:47PM -0800, Bram Cohen via bitcoin-dev wrote:
> > After looking into it, I actually think chia lisp [1] gets pretty much all
> > the major design decisions pretty much right. There are obviously a few
> > changes needed given the differences in design between chia and bitcoin:
> Bitcoin uses the UTXO model as opposed to Chia's Coin Set model. While
> these are close enough that it's often explained as Chia uses the UTXO
> model but that isn't technically true. Relevant to the above comment is
> that in the UTXO model transactions get passed to a scriptpubkey and it
> either assert fails or it doesn't, while in the coin set model each puzzle
> (scriptpubkey) gets run and either assert fails or returns a list of extra
> conditions it has, possibly including timelocks and creating new coins,
> paying fees, and other things.

One way to match the way bitcoin do things, you could have the "list of
extra conditions" encoded explicitly in the transaction via the annex,
and then check the extra conditions when the script is executed.

> If you're doing everything from scratch it's cleaner to go with the coin
> set model, but retrofitting onto existing Bitcoin it may be best to leave
> the UTXO model intact and compensate by adding a bunch more opcodes which
> are special to parsing Bitcoin transactions. The transaction format itself
> can be mostly left alone but to enable some of the extra tricks (mostly
> implementing capabilities) it's probably a good idea to make new
> conventions for how a transaction can have advisory information which
> specifies which of the inputs to a transaction is the parent of a specific
> output and also info which is used for communication between the UTXOs in a
> transaction.

I think the parent/child coin relationship is only interesting when
"unrelated" spends can assert that the child coin is being created -- ie
things along the lines of the "transaction sponsorship" proposal. My
feeling is that complicates the mempool a bit much, so is best left for
later, if done at all.

(I think the hard part of managing the extra conditions is mostly
in keeping it efficient to manage the mempool and construct the most
profitable blocks/bundles, rather than where the data goes)

> But one could also make lisp-generated UTXOs be based off transactions
> which look completely trivial and have all their important information be
> stored separately in a new vbytes area. That works but results in a bit of
> a dual identity where some coins have both an old style id and a new style
> id which gunks up what

We've already got a txid and a wtxid, adding more ids seems best avoided
if possible...

> > Pretty much all the opcodes in the first section are directly from chia
> > lisp, while all the rest are to complete the "bitcoin" functionality.
> > The last two are extensions that are more food for thought than a real
> > proposal.
> Are you thinking of this as a completely alternative script format or an
> extension to bitcoin script?

As an alternative to tapscript, so when constructing the merkle tree of
scripts for a taproot address, you could have some of those scripts be
in tapscript as it exists today with OP_CHECKSIG etc, and others could
be in lisp. (You could then have an entirely lisp-based sub-merkle-tree
of lisp fragments via sha256tree or similar of course)

> They're radically different approaches and
> it's hard to see how they mix. Everything in lisp is completely sandboxed,
> and that functionality is important to a lot of things, and it's really
> normal to be given a reveal of a scriptpubkey and be able to rely on your
> parsing of it.

The above prevents combining puzzles/solutions from multiple coin spends,
but I don't think that's very attractive in bitcoin's context, the way
it is for chia. I don't think it loses much else?

> > There's two ways to think about upgradability here; if someday we want
> > to add new opcodes to the language -- perhaps something to validate zero
> > knowledge proofs or calculate sha3 or use a different ECC curve, or some
> > way to support cross-input signature aggregation, or perhaps it's just
> > that some snippets are very widely used and we'd like to code them in
> > C++ directly so they validate quicker and don't use up as much block
> > weight. One approach is to just define a new version of the language
> > via the tapleaf version, defining new opcodes however we like.
> A nice side benefit of sticking with the UTXO model is that the soft fork
> hook can be that all unknown opcodes make the entire thing automatically
> pass.

I don't think that works well if you want to allow the spender (the
puzzle solution) to be able to use opcodes introduced in a soft-fork
(eg, for graftroot-like behaviour)?

> Chia's approach to transaction fees is essentially identical to Bitcoin's
> although a lot fewer things in the ecosystem support fees due to a lack of
> having needed it yet. I don't think mempool issues have much to do with
> choice of scriptpubkey language. which is mostly about adding in covenants
> and capabilities.

Having third parties be able to link their spends to yours complicates
mempool behaviour a fair bit (see the discussions on pinning wrt
lightning txs -- and that's only with direct participants being able to
link transactions). But it's very much a second-order effect compared
to having fees being a meaningful thing at all. It took, what, six or
seven years for people to start actually using dynamic fees in bitcoin?

> I previously posted some thoughts about this here:
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-December/019722.html

I'm pretty skeptical about having a database of large script snippets
that will hopefully be reused in the future.

On Mon, Mar 07, 2022 at 10:56:38PM +0000, ZmnSCPxj via bitcoin-dev wrote:
> > while in the coin set model each puzzle (scriptpubkey) gets run and either assert fails or returns a list of extra conditions it has, possibly including timelocks and creating new coins, paying fees, and other things.
> Does this mean it basically gets recursive covenants?

In chia the "scriptPubKey" is the hash of a lisp program, and when you
create a new coin, the "scriptPubKey" of the newly generated coin is
also the output of a lisp program. So writing a quine gets you general
recursive covenants in a pretty straight forward way, as I understand it.

> > >  - serialization seems to be a bit verbose -- 100kB of serialized clvm
> > >    code from a random block gzips to 60kB; optimising the serialization
> > >    for small lists, and perhaps also for small literal numbers might be
> > >    a feasible improvement; though it's not clear to me how frequently
> > >    serialization size would be the limiting factor for cost versus
> > >    execution time or memory usage.
> > A lot of this is because there's a hook for doing compression at the consensus layer which isn't being used aggressively yet. That one has the downside that the combined cost of transactions can add up very nonlinearly, but when you have constantly repeated bits of large boilerplate it gets close and there isn't much of an alternative. That said even with that form of compression maxxed out it's likely that gzip could still do some compression but that would be better done in the database and in wire protocol formats rather than changing the format which is hashed at the consensus layer.
> How different is this from "jets" as proposed in Simplicity?

Rather than a "transaction" containing "inputs/outputs", chia has spend
bundles that spend and create coins; and spend bundles can be merged
together, so that a block only has a single spend bundle. That spend
bundle joins all the puzzles (the programs that, when hashed match
the scriptPubKey) and solutions (scriptSigs) for the coins being spent
together.

I /think/ the compression hook would be to allow you to have the puzzles
be (re)generated via another lisp program if that was more efficient
than just listing them out. But I assume it would be turtles, err,
lisp all the way down, no special C functions like with jets.

> > > Pretty much all the opcodes in the first section are directly from chia
> > > lisp, while all the rest are to complete the "bitcoin" functionality.
> > > The last two are extensions that are more food for thought than a real
> > > proposal.
> >
> > Are you thinking of this as a completely alternative script format or an extension to bitcoin script? They're radically different approaches and it's hard to see how they mix. Everything in lisp is completely sandboxed, and that functionality is important to a lot of things, and it's really normal to be given a reveal of a scriptpubkey and be able to rely on your parsing of it.
> 
> I believe AJ is proposing a completely alternative format to OG Bitcoin SCRIPT.
> Basically, as I understand it, nothing in the design of Tapscript versions prevents us from completely changing the interpretation of Tapscript bytes, and use a completely different language.
> That is, we could designate a new Tapscript version as completely different from OG Bitcoin SCRIPT.

BIP342 defines tapscript, and it's selected by the taproot leaf version
0xc0; this hypothetical lispy "btcscript" might be selected via taproot
leaf version 0xc2 or similar (elements' tapscript variant is selected
via version 0xc4).

Cheers,
aj