bitcoin scripting and lisp
6 messages, 4 to 6 Mar 2022. Started by Anthony Towns.
ZmnSCPxj (2), Russell O'Connor (2), Anthony Towns, Jeremy Rubin
On Sun, Feb 27, 2022 at 04:34:31PM +0000, ZmnSCPxj via bitcoin-dev wrote:
Quoted text (5 lines)
> 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
Quoted text (1 line)
> - + * / divmod - (signed, bignum) arithmetic
ashift - arithmetic shift (sign extended)
Quoted text (1 line)
>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 - same as bip340-verify, except for traditional ecdsa? secp256k1-muladd - given (a B C) where B,C are points, calculate a*B+C?
That compares to about 60 (non-disabled) opcodes in current script. 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.
Using a lisp-style approach seems an improvement in general to me. For example, rather than the streaming-sha256 approach in Elements, where you could write:
"a" SHA256INITIALIZE "b" SHA256UPDATE "c" SHA256UPDATE "d" SHA256FINALIZE
to get the sha256 of "abcd" without having to CAT them first (important if they'd potentially overflow the 520B stack item limit), in chia lisp you write:
(sha256 "a" "b" "c" "d")
which still has the benefit of streaming the inputs into the function, but only adds a single opcode, doesn't involve representing the internal sha256 midstate on the stack, and generally seems easier to understand, at least to me.
As another example, following the traditional functional "tail recursion instead of for-loops" approach, doing CHECKMULTISIG might become something like:
(defun checksig (sig key)
bip340-verify (f sig) (bip342-txmsg (r sig)) key)
(defun checkmultisig (sigs keys k)
if (= k 0)
1
(if (l sigs)
(if (checksig (f sigs) (f keys))
(checkmultisig (r sigs) (r keys) (- k 1))
(checkmultisig sigs (r keys) k)
)
0
)
)
Here each "sig" is a pair of a 64B bip340 signature and a 1B sighash; instead of a 65B string combining both, and sigs, keys are lists, and k is the number of successful signature checks you're requiring for success.
Of course, "defun" and "if" aren't listed as opcodes above; instead you have a compiler that gives you nice macros like defun and translates them into correct uses of the "a" opcode, etc. As I understand it, those sort of macros and translations are pretty well understood across lisp-like languages, and, of course, they're already implemented for chia lisp.
I think with the "tx" opcode defined similarly to how Rusty suggested it [2] you could implement OP_CTV-like behaviours in similar way, and also replace "bip342-txmsg" with your own code to generate SIGHASH_ANYPREVOUT or SIGHASH_GROUP style messages to sign. (This would mean also being able to pull information about the utxo being spent to obtain its amount and scriptpubkey, which are committed to wit ANYPREVOUT. If it was also able to obtain the "is_coinbase" flag, that might allow you a more accurate covenant-based implementation of drivechains...)
Likewise, with the "taproot" opcode defined in a way that lets you extract out the internal public key and merkle path, I think you could implement OP_TLUV and OP_EVICT with a similar recursive approach.
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.
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 is concerned, the expression will either fail entirely or evaluate as zero; so anyone who doesn't support the softfork can just replace it with zero 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 to have OP_SUCCESS-like behaviour if you're trying to allow accepting code from the witness data -- otherwise as soon as you reveal that your script does accept arbitrary code supplied by the spender, someone could stick in an OP_SUCCESS code, and remove all the restrictions on spending and steal your funds.
To me, it seems like chia lisp is a better answer to the problem here than the Simplicity language. Simplicity is complicated in a few ways:
- it defines over 100 jets (plus another 6 for sha3, and another 45 for individual libsecp256k1 functions) that need to be implemented natively to efficiently track consensus [3]
- as far as I know, how to soft-fork in new jets isn't yet well established. I think the ideal is that you just write everything in raw simplicity, and either the interpreter has a jet and does things quickly, or doesn't, and gets the same result much more slowly [4]. But that approach doesn't seem compatible with maintaining consensus, when "slowly" can be slower by more than 6 orders of magnitude [5].
- to understand what's going on with a smart contract, you need to understand both simplicity (to define the program) and the bit machine (to follow how it's computed), both of which are fairly novel -- and if nobody's directly coding in simplicity which seems likely, you're adding a third layer on top of that: you want to understand what the programmer asked for (the source), what is included in the transaction (the simplicity code) and how that's executed by consensus code (via the bit machine).
There's a branch for enabling simplicity on elements/liquid [6] to see what enabling simplicity might involve in concrete terms; it just... doesn't seem at all simple in practice to me. I can't see how you'd reasonably translate that simplicity code into a BIP series that anyone could understand, or how you'd do a thorough review of all the changes...
By contrast, chia lisp has fewer opcodes than Simplicity's jets, has feasible approaches to low-impact soft forks to increase functionality, can be used with only two levels of abstraction (lisp with macros and the opcodes-only vm level) that seem not too bad to understand, and (in my opinion) doesn't seem too hard to implement/maintain reasonably.
On the other hand, Simplicity's big advantage over *everything* else is in formal verification. But I'm not really seeing why you couldn't preserve that advantage by writing simplicity definitions for the "lisp" opcodes [7], so that you can "compile" the lisp programs to simplicity, and then verify them however you like.
One of the things people sometimes claim about bitcoin as an asset, is that it's got both the advantage of having been first to market, but also that if some altcoin comes along with great new ideas, then those ideas can just be incorporated into bitcoin too, so bitcoin can preserve it's lead even from innovators. Granted, I've only really been looking at chia lisp for a bit over a week, but it really seems to me like a case where it might be worth putting that philosophy into practice.
If we were to adopt this, obviously we shouldn't call it "chia lisp" anymore, since it wouldn't work the same in important ways. But since the program would be encoded as a binary-tree of car/cdr pairs, maybe we could call it "binary-tree coded script", or "btc-script" for short...
PS: related tweets: [8]
Cheers, aj
[0] You could also allow things to be pushed onto the stack that
(recursively) can push things onto the stack -- the language "Joy"
takes this approach. It seems to end up equivalent to doing things
in a list oriented way to me.
[1] https://chialisp.com/docs/ref/clvm
[2] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-February/019871.html
[3] https://raw.githubusercontent.com/ElementsProject/simplicity/pdf/Simplicity-TR.pdf
[4] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-November/015244.html https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-October/015227.html https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-October/015228.html
[5] https://medium.com/blockstream/simplicity-jets-release-803db10fd589
[6] https://github.com/ElementsProject/elements/compare/simplicity
[7] At least I think so? chia lisp does multibyte math, that is "+"
can accept "arbitrary" length bytestrings, which it interprets as
numbers and adds together; whereas Simplicity requires finite types.
I think you could decide "a program that only costs X can't have any
bytestrings greater than length k*X" and construct a finite type up to
that length, maybe? So long as you're only using it for verification,
maybe that stays feasible? Or perhaps you could arbitrarily limit
the strings to a max of 520 bytes at a consensus level, and the
corresponding Simplicity types to 4160 bits and go from there?
[8] https://twitter.com/brian_trollz/status/1499048316956549123 https://twitter.com/jb55/status/1499045998315724801
[9] Oops, out of order footnotes. Anyway...
[10] [9] The CREATE/ASSERT bundling stuff is interesting; and could be
used to achieve functionality like the "transaction sponsorship"
stuff. It doesn't magically solve the issues with maintaining the
mempool and using that to speed up block acceptance, though, and
the chia chain has apparently suffered from mempool-flooding attacks
recently [11] so I don't think they've solved the broader problem,
and thus I think it still makes more sense to stick with bitcoin's
current model here.
[11] https://thechiaplot.net/2021/11/03/interview-with-the-chia-dust-stormer/ https://github.com/Chia-Network/post-mortem/blob/main/post-mortem.md
Good morning aj,
Quoted text (39 lines)
> 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 preferred-language-here to represent LISP datums. Combine it with your idea of committing to a max-number-of-operations (which increases the weight of the transaction) and you may very well have something viable. (In particular, even though `eval` is traditionally (re-)implemented in LISP itself, the limit on max-number-of-operations means any `eval` implementation 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. programs 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 patterns. However, each LISP programmer then ends up implementing *different*, but *similar* 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 their own private dialect of LISP (formed from the common LISP language and from their own extensive set of private macros) and intercommunication between them is hindered by the fact that each one speaks their own private dialect. Some LISP-like languages (e.g. Scheme) have classically targeted a "small" subset of absolutely-necessary operations, and each implementation of the language immediately becomes a new dialect due to having slightly different forms for roughly the same convenience function or macro, and *then* individual 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 Scheme implementations have not always liked to implement *all* the "large" standard.
Otherwise, every big C program contains a half-assed implementation of half of Common LISP, so ----
Quoted text (9 lines)
> - 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 the 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 amount of work done in both cases would be the same, at least until the number of allocs exceeds the nursery size.
Alternately, the implementation may use immutable byte vectors, in which case `OP_DUP` is just a pointer copy. Or alternately the implementation may use copy-on-write byte vectors, in which case `OP_DUP` is just a pointer copy plus refcount increment, and `OP_DROP` is just a refcount decrement, and the amount of memory used remains small.
Quoted text (32 lines)
> 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. > > 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 is > concerned, the expression will either fail entirely or evaluate as zero; > so anyone who doesn't support the softfork can just replace it with zero > 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 to > have OP_SUCCESS-like behaviour if you're trying to allow accepting code > from the witness data -- otherwise as soon as you reveal that your script > does accept arbitrary code supplied by the spender, someone could stick > in an OP_SUCCESS code, and remove all the restrictions on spending and > steal your funds.
Oh no `1 RETURN`!
Well, the advantage of chialisp here is that it enables the opcode for a *block* of code, so the opcode *itself* could return arbitrary data, it is just the entire block of code that is restricted to returning `0`. So it would be something like an `OP_BEGINSOFTFORK .... OP_ENDSOFTFORK` where any reserved opcodes in the middle have arbitrary behavior, the entire block 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 procedure, as I think you want `cost` to be statically determined, and very likely also `version`.
Regards, ZmnSCPxj
It seems like a decent concept for exploration.
AJ, I'd be interested to know what you've been able to build with Chia Lisp and what your experience has been... e.g. what does the Lightning Network look like on Chia?
One question that I have had is that it seems like to me that neither simplicity nor chia lisp would be particularly suited to a ZK prover...
Were that the explicit goal, it would seem that we could pretty easily adapt something like Cairo for Bitcoin transactions, and then we'd get a big privacy benefit as well as enabling whatever programming paradigm you find convenient (as it is compiled to a circuit verifier of some kind)...
Quoted text (1 line)
>
On Sat, Mar 5, 2022 at 8:41 AM Jeremy Rubin via bitcoin-dev < bitcoin-dev@lists•linuxfoundation•org> wrote:
Quoted text (10 lines)
> It seems like a decent concept for exploration. > > AJ, I'd be interested to know what you've been able to build with Chia > Lisp and what your experience has been... e.g. what does the Lightning > Network look like on Chia? > > > One question that I have had is that it seems like to me that neither > simplicity nor chia lisp would be particularly suited to a ZK prover... >
Not that I necessarily disagree with this statement, but I can say that I have experimented with compiling Simplicity to Boolean circuits. It was a while ago, but I think the result of compiling my SHA256 program was within an order of magnitude of the hand made SHA256 circuit for bulletproofs.
Good morning Russell,
Quoted text (9 lines)
> On Sat, Mar 5, 2022 at 8:41 AM Jeremy Rubin via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote: > > > It seems like a decent concept for exploration. > > > > AJ, I'd be interested to know what you've been able to build with Chia Lisp and what your experience has been... e.g. what does the Lightning Network look like on Chia? > > > > One question that I have had is that it seems like to me that neither simplicity nor chia lisp would be particularly suited to a ZK prover... > > Not that I necessarily disagree with this statement, but I can say that I have experimented with compiling Simplicity to Boolean circuits. It was a while ago, but I think the result of compiling my SHA256 program was within an order of magnitude of the hand made SHA256 circuit for bulletproofs.
"Within" can mean "larger" or "smaller" in this context, which was it? From what I understand, compilers for ZK-provable circuits are still not as effective as humans, so I would assume "larger", but I would be much interested if it is "smaller"!
Regards, ZmnSCPxj
The circuit generated from Simplicity was larger than the hand made one.
On Sat, Mar 5, 2022 at 6:20 PM ZmnSCPxj <ZmnSCPxj@protonmail•com> wrote:
Quoted text (28 lines)
> Good morning Russell, > > > On Sat, Mar 5, 2022 at 8:41 AM Jeremy Rubin via bitcoin-dev < > bitcoin-dev@lists•linuxfoundation•org> wrote: > > > > > It seems like a decent concept for exploration. > > > > > > AJ, I'd be interested to know what you've been able to build with Chia > Lisp and what your experience has been... e.g. what does the Lightning > Network look like on Chia? > > > > > > One question that I have had is that it seems like to me that neither > simplicity nor chia lisp would be particularly suited to a ZK prover... > > > > Not that I necessarily disagree with this statement, but I can say that > I have experimented with compiling Simplicity to Boolean circuits. It was > a while ago, but I think the result of compiling my SHA256 program was > within an order of magnitude of the hand made SHA256 circuit for > bulletproofs. > > "Within" can mean "larger" or "smaller" in this context, which was it? > From what I understand, compilers for ZK-provable circuits are still not > as effective as humans, so I would assume "larger", but I would be much > interested if it is "smaller"! > > Regards, > ZmnSCPxj >