On Sun, Feb 27, 2022 at 04:34:31PM +, 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.
So, to me, that seemed like something worth looking into...
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:
- having secp256k1 signatures (and curve operations), instead of
BLS12-381 ones
- adding tx introspection instead of having bundle-oriented CREATE_COIN,
and CREATE/ASSERT results [10]
and there are a couple of other things that could maybe be improved
upon:
- 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.
- 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.
But otherwise, it seems a pretty good match.
I think you'd need about 40 opcodes to match bitcoin script and (roughly)
chia lisp, something like:
q- quote
a- apply
x- exception / immediately fail (OP_RETURN style)
i- if/then/else
softfork - upgradability
not, all, any- boolean logic
bitand, bitor, bitxor, bitnot, shift - bitwise logic
=- bitwise equality
> - + * / divmod - (signed, bignum) arithmetic
ashift - arithmetic shift (sign extended)
>s - string comparison
strlen, substr, concat - string ops
f, r, c, l - list ops (head, tail, make a list, is this a list?)
sha256 - hashing
numequal - arithmetic equal, equivalent to (= (+ a 0) (+ b 0))
ripemd160, hash160, hash256 - more hashing
bip342-txmsg - given a sighash byte, construct the bip342 message
bip340-verify- given a pubkey, message, and signature bip340 verify it
tx - get various information about the tx
taproot - get merkle path/internalpubkey/program/annex information
ecdsa-
