Subject: Re: [bitcoin-dev] bitcoin scripting and lisp

From: ZmnSCPxj <[email-masked]>
Date: Wed, 16 Mar 2022 14:54:05 +0000

Good morning aj et al.,

> On Tue, Mar 08, 2022 at 03:06:43AM +0000, ZmnSCPxj via bitcoin-dev wrote:
>
> > > > 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?
> > > > But cross-input signature aggregation is a nice-to-have we want for Bitcoin, and, to me, cross-input sigagg is not much different from cross-input puzzle/solution compression.
>
> Signature aggregation has a lot more maths and crypto involved than
> reversible compression of puzzles/solutions. I was more meaning
> cross-transaction relationships rather than cross-input ones though.

My point is that in the past we were willing to discuss the complicated crypto math around cross-input sigagg in order to save bytes, so it seems to me that cross-input compression of puzzles/solutions at least merits a discussion, since it would require a lot less heavy crypto math, and *also* save bytes.

> > > 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.
> > > Eh, you could use Common LISP or a recent-enough RnRS Scheme to write a cryptocurrency node software, so "special C function" seems to overprivilege C...
>
> Jets are "special" in so far as they are costed differently at the
> consensus level than the equivalent pure/jetless simplicity code that
> they replace. Whether they're written in C or something else isn't the
> important part.
>
> By comparison, generating lisp code with lisp code in chia doesn't get
> special treatment.

Hmm, what exactly do you mean here?

If I have a shorter piece of code that expands to a larger piece of code because metaprogramming, is it considered the same cost as the larger piece of code (even if not all parts of the larger piece of code are executed, e.g. branches)?

Or is the cost simply proportional to the number of operations actually executed?

I think there are two costs here:

* Cost of bytes to transmit over the network.
* Cost of CPU load.

Over here in Bitcoin we have been mostly conflating the two, to the point that Taproot even eliminates unexecuted branches from being transmitted over the network so that bytes transmitted is approximately equal to opcodes executed.

It seems to me that lisp-generating-lisp compression would reduce the cost of bytes transmitted, but increase the CPU load (first the metaprogram runs, and *then* the produced program runs).

> (You could also use jets in a way that doesn't impact consensus just
> to make your node software more efficient in the normal case -- perhaps
> via a JIT compiler that sees common expressions in the blockchain and
> optimises them eg)

I believe that is relevant in the other thread about Jets that I and Billy forked off from `OP_FOLD`?

Over in that thread, we seem to have largely split jets into two types:

* Consensus-critical jets which need a softfork but reduce the weight of the jetted code (and which are invisible to pre-softfork nodes).
* Non-consensus-critical jets which only need relay change and reduces bytes sent, but keeps the weight of the jetted code.

It seems to me that lisp-generating-lisp compression would roughly fall into the "non-consensus-critical jets", roughly.

> On Wed, Mar 09, 2022 at 02:30:34PM +0000, ZmnSCPxj via bitcoin-dev wrote:
>
> > Do note that PTLCs remain more space-efficient though, so forget about HTLCs and just use PTLCs.
>
> Note that PTLCs aren't really Chia-friendly, both because chia doesn't
> have secp256k1 operations in the first place, but also because you can't
> do a scriptless-script because the information you need to extract
> is lost when signatures are non-interactively aggregated via BLS --
> so that adds an expensive extra ECC operation rather than reusing an
> op you're already paying for (scriptless script PTLCs) or just adding
> a cheap hash operation (HTLCs).
>
> (Pretty sure Chia could do (= PTLC (pubkey_for_exp PREIMAGE)) for
> preimage reveal of BLS PTLCs, but that wouldn't be compatible with
> bitcoin secp256k1 PTLCs. You could sha256 the PTLC to save a few bytes,
> but I think given how much a sha256 opcode costs in Chia, that that
> would actually be more expensive?)
>
> None of that applies to a bitcoin implementation that doesn't switch to
> BLS signatures though.

Not being a mathist, I have absolutely no idea, but: at least as I understood from the original mimblewimble.txt from Voldemort, BLS signatures had an additional assumption, which I *think* means "theoretically less secure than SECP256K1 Schnorr / ECDSA".
Is my understanding correct?
And if so, how theoretical would that be?

PTLC signatures have the very nice property of being indistinguishable from non-PTLC signatures to anyone without the adaptor, and I think privacy-by-default should be what we encourage.

> > > But if they're fully baked into the scriptpubkey then they're opted into by the recipient and there aren't any weird surprises.
> > > This is really what I kinda object to.
> > > Yes, "buyer beware", but consider that as the covenant complexity increases, the probability of bugs, intentional or not, sneaking in, increases as well.
> > > And a bug is really "a weird surprise" --- xref TheDAO incident.
>
> Which is better: a bug in the complicated script code specified for
> implementing eltoo in a BOLT; or a bug in the BIP/implementation of a
> new sighash feature designed to make it easy to implement eltoo, that's
> been soft-forked into consensus?
>
> Seems to me, that it's always better to have the bug be at the wallet
> level, since that can be fixed by upgrading individual wallet software.

Good point.

Though I should note that BIP-118 was originally proposed with a 5-line patch, so ---

> I'm not sure that a "covenant language implementation" would necessarily
> be "that" complicated. And if so, having a DSL for covenants could,
> at least in theory, make for a much simpler implementation of
> ANYPREVOUT/CTV/TLUV/EVICT/etc than doing it directly in C++, which
> might mean those things are less likely to have "weird surprises" rather
> than more.

<rant>
DSLs?
Domain-specific languages?

Do you know how many people hate autoconf?
That is because autoconf is secretly an embedded DSL in a really obscure language called `m4`.
Some of the `autoconf` weirdnesses are due precisely to having to hack `m4` to make it look nicer, like that weird rule to use double `[[` and `]]` quotes around sections of program source code.
Yes, it means we can have a nice `autoconf-archive`, but the actual code inside that archive?
People *making*`autoconf` macros have to learn both `m4` and the existing `autoconf` macro ecosystem.

Then there is BluespecSV.
Bluespec used to be an embedded DSL inside Haskell.
Nobody wanted it because they had to learn *two* languages, Haskell, and Bluespec.
Eventually they created BluespecSV, which was a language with completely separate grammar and tokens from Haskell, instead of embedded in it, and Bluespec was finally *actually* used in production.
But the damage was done: people who do digital hardware design tend to *bristle* when they hear the word "Haskell", because of all the horrible embedded DSLs in Haskell (Bluespec was just one, but I have heard of a few others which never managed to jump from being more than a lab toy, including a cute one where the on-FPGA layout of the circuit was part of the construction of the circuit description).

Embedded DSLs are cute, but they require learning two languages, not a single new one.
Just say no to embedded DSLs!
</rant>

Ah, much better.

This seems to me to be not much different from adding a separate compiler, which translates from the surface language to the underlying opcode/lisp language, with similar risks: now you have *another* bit of indirection to audit.
It feels like building a perpetual-motion machine, where we keep adding more stuff in the hope of reducing the complexity.

Regards,
ZmnSCPxj