Date: Wed, 16 Mar 2022 14:54:05 +0000
To: Anthony Towns <aj@erisian.com.au>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <L7tNMIZp05o7FReQe8l-TjBDkuqbdby8Rk92X_BXEl7Hp5B7eAa-oyS0wMPDvLec03sJ7Q_yoW6ker0LS8k8VPXEHRhObF3EdB6zpLNZxRo=@protonmail.com>
In-Reply-To: <20220311044645.GB7597@erisian.com.au>
References: <20220311044645.GB7597@erisian.com.au>
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>,
 Bram Cohen <bram@chia.net>
Subject: Re: [bitcoin-dev] bitcoin scripting and lisp
Precedence: list

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 san=
dboxed,
> > > > and that functionality is important to a lot of things, and it's re=
ally
> > > > normal to be given a reveal of a scriptpubkey and be able to rely o=
n your
> > > > parsing of it.
> > > > The above prevents combining puzzles/solutions from multiple coin s=
pends,
> > > > 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-i=
nput 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 cry=
pto math around cross-input sigagg in order to save bytes, so it seems to m=
e that cross-input compression of puzzles/solutions at least merits a discu=
ssion, 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 puzz=
les
> > > 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 overprivi=
lege 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 be=
cause metaprogramming, is it considered the same cost as the larger piece o=
f 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 exe=
cuted?

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 t=
hat Taproot even eliminates unexecuted branches from being transmitted over=
 the network so that bytes transmitted is approximately equal to opcodes ex=
ecuted.

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 th=
e jetted code (and which are invisible to pre-softfork nodes).
* Non-consensus-critical jets which only need relay change and reduces byte=
s sent, but keeps the weight of the jetted code.

It seems to me that lisp-generating-lisp compression would roughly fall int=
o 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 (=3D 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 understo=
od from the original mimblewimble.txt from Voldemort, BLS signatures had an=
 additional assumption, which I *think* means "theoretically less secure th=
an 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 i=
nto 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 inc=
reases, 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 pat=
ch, 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 la=
nguage 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 `]]` qu=
otes around sections of program source code.
Yes, it means we can have a nice `autoconf-archive`, but the actual code in=
side 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 Bl=
uespec.
Eventually they created BluespecSV, which was a language with completely se=
parate grammar and tokens from Haskell, instead of embedded in it, and Blue=
spec was finally *actually* used in production.
But the damage was done: people who do digital hardware design tend to *bri=
stle* when they hear the word "Haskell", because of all the horrible embedd=
ed 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 cu=
te 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 sing=
le 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 la=
nguage, with similar risks: now you have *another* bit of indirection to au=
dit.
It feels like building a perpetual-motion machine, where we keep adding mor=
e stuff in the hope of reducing the complexity.


Regards,
ZmnSCPxj