Date: Fri, 04 Mar 2022 23:10:48 +0000
To: Anthony Towns <aj@erisian.com.au>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <0yCTRKhBa9IPPg5J4HfKxraWJ4w6gUS5LRAoCPk01NpbYk-9R5zxAOmJO1Z8voUiatUJugYB6Oa9t1wFLbhQSgDie8hBzr0Z1EJVm6XGvMI=@protonmail.com>
In-Reply-To: <20220304010442.GC3869@erisian.com.au>
References: <20220304010442.GC3869@erisian.com.au>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Subject: Re: [bitcoin-dev] bitcoin scripting and lisp
Precedence: list


Good morning aj,

> On Sun, Feb 27, 2022 at 04:34:31PM +0000, ZmnSCPxj via bitcoin-dev wrote:
>
> > In reaction to this, AJ Towns mailed me privately about some of his
> > thoughts on this insane `OP_EVICT` proposal.
> > He observed that we could generalize the `OP_EVICT` opcode by
> > decomposing it into smaller parts, including an operation congruent
> > to the Scheme/Haskell/Scala `map` operation.
>
> At much the same time Zman was thinking about OP_FOLD and in exactly the
> same context, I was wondering what the simplest possible language that
> had some sort of map construction was -- I mean simplest in a "practical
> engineering" sense; I think Simplicity already has the Euclidean/Peano
> "least axioms" sense covered.
>
> The thing that's most appealing to me about bitcoin script as it stands
> (beyond "it works") is that it's really pretty simple in an engineering
> sense: it's just a "forth" like system, where you put byte strings on a
> stack and have a few operators to manipulate them. The alt-stack, and
> supporting "IF" and "CODESEPARATOR" add a little additional complexity,
> but really not very much.
>
> To level-up from that, instead of putting byte strings on a stack, you
> could have some other data structure than a stack -- eg one that allows
> nesting. Simple ones that come to mind are lists of (lists of) byte
> strings, or a binary tree of byte strings [0]. Both those essentially
> give you a lisp-like language -- lisp is obviously all about lists,
> and a binary tree is just made of things or pairs of things, and pairs
> of things are just another way of saying "car" and "cdr".
>
> A particular advantage of lisp-like approaches is that they treat code
> and data exactly the same -- so if we're trying to leave the option open
> for a transaction to supply some unexpected code on the witness stack,
> then lisp handles that really naturally: you were going to include data
> on the stack anyway, and code and data are the same, so you don't have
> to do anything special at all. And while I've never really coded in
> lisp at all, my understanding is that its biggest problems are all about
> doing things efficiently at large scales -- but script's problem space
> is for very small scale things, so there's at least reason to hope that
> any problems lisp might have won't actually show up for this use case.

I heartily endorse LISP --- it has a trivial implementation of `eval` that =
is easily implementable once you have defined a proper data type in preferr=
ed-language-here to represent LISP datums.
Combine it with your idea of committing to a max-number-of-operations (whic=
h increases the weight of the transaction) and you may very well have somet=
hing viable.
(In particular, even though `eval` is traditionally (re-)implemented in LIS=
P itself, the limit on max-number-of-operations means any `eval` implementa=
tion within the same language is also forcibly made total.)

Of note is that the supposed "problem at scale" of LISP is, as I understand=
 it, due precisely to its code and data being homoiconic to each other.
This homoiconicity greatly tempts LISP programmers to use macros, i.e. prog=
rams that generate other programs from some input syntax.
Homoiconicity means that one can manipulate code just as easily as the data=
, and thus LISP macros are a trivial extension on the language.
This allows each LISP programmer to just code up a macro to expand common p=
atterns.
However, each LISP programmer then ends up implementing *different*, but *s=
imilar* macros from each other.
Unfortunately, programming at scale requires multiple programmers speaking =
the same language.
Then programming at scale is hampered because each LISP programmer has thei=
r own private dialect of LISP (formed from the common LISP language and fro=
m their own extensive set of private macros) and intercommunication between=
 them is hindered by the fact that each one speaks their own private dialec=
t.
Some LISP-like languages (e.g. Scheme) have classically targeted a "small" =
subset of absolutely-necessary operations, and each implementation of the l=
anguage immediately becomes a new dialect due to having slightly different =
forms for roughly the same convenience function or macro, and *then* indivi=
dual programmers build their own private dialect on top.
For Scheme specifically, R7RS has targeted providing a "large" standard as =
well, as did R6RS (which only *had* a "large" standard), but individual Sch=
eme implementations have not always liked to implement *all* the "large" st=
andard.

Otherwise, every big C program contains a half-assed implementation of half=
 of Common LISP, so ----


> -   I don't think execution costing takes into account how much memory
>     is used at any one time, just how much was allocated in total; so
>     the equivalent of (OP_DUP OP_DROP OP_DUP OP_DROP ..) only has the
>     allocations accounted for, with no discount given for the immediate
>     freeing, so it gets treated as having the same cost as (OP_DUP
>     OP_DUP .. OP_DROP OP_DROP ..). Doing it that way would be a worse
>     than how bitcoin script is currently costed, but doing better might
>     mean locking in an evaluation method at the consensus level. Seems
>     worth looking into, at least.

This may depend on the language that the interpreter is written in.

For example, on a typical GC language, both the N * `OP_DUP OP_DROP` and th=
e N * `OP_DUP` + N * `OP_DROP` will have similar behavior when allocated at=
 the nursery.
Since the GC nursery acts as a large buffer of potential allocations, the a=
mount of work done in both cases would be the same, at least until the numb=
er of allocs exceeds the nursery size.

Alternately, the implementation may use immutable byte vectors, in which ca=
se `OP_DUP` is just a pointer copy.
Or alternately the implementation may use copy-on-write byte vectors, in wh=
ich case `OP_DUP` is just a pointer copy plus refcount increment, and `OP_D=
ROP` is just a refcount decrement, and the amount of memory used remains sm=
all.


>     There's two ways to think about upgradability here; if someday we wan=
t
>     to add new opcodes to the language -- perhaps something to validate z=
ero
>     knowledge proofs or calculate sha3 or use a different ECC curve, or s=
ome
>     way to support cross-input signature aggregation, or perhaps it's jus=
t
>     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.
>
>     The other is to use the "softfork" opcode -- chia defines it as:
>
>     (softfork cost code)
>
>     though I think it would probably be better if it were
>
>     (softfork cost version code)
>
>     where the idea is that "code" will use the "x" opcode if there's a
>     problem, and anyone supporting the "version" softfork can verify that
>     there aren't any problems at a cost of "cost". However, whether you
>     do or don't support that softfork, as far as the rest of the script i=
s
>     concerned, the expression will either fail entirely or evaluate as ze=
ro;
>     so anyone who doesn't support the softfork can just replace it with z=
ero
>     and continue on, treating it as if it had costed "cost" units.
>
>     One thing worth noting: "softfork" behaves more like OP_NOP than
>     tapscript's OP_SUCCESS -- I think it's just not possible in general t=
o
>     have OP_SUCCESS-like behaviour if you're trying to allow accepting co=
de
>     from the witness data -- otherwise as soon as you reveal that your sc=
ript
>     does accept arbitrary code supplied by the spender, someone could sti=
ck
>     in an OP_SUCCESS code, and remove all the restrictions on spending an=
d
>     steal your funds.

Oh no `1 RETURN`!

Well, the advantage of chialisp here is that it enables the opcode for a *b=
lock* of code, so the opcode *itself* could return arbitrary data, it is ju=
st the entire block of code that is restricted to returning `0`.
So it would be something like an `OP_BEGINSOFTFORK .... OP_ENDSOFTFORK` whe=
re any reserved opcodes in the middle have arbitrary behavior, the entire b=
lock gets a *copy* of the current stack and alt stack, with any changes to =
the stack / alt stack disappear after the `OP_ENDSOFTFORK`.
Thus, the entire block as a whole would act as an `OP_NOP`.
(OG Bitcoin SCRIPT FTW!)

I think the `softfork` form would have to be a syntax though and not a proc=
edure, as I think you want `cost` to be statically determined, and very lik=
ely also `version`.

Regards,
ZmnSCPxj