Can Bitcoin Script be expressed in Simplicity?

[seedhammer]

I believe the most significant cost of adding Simplicity to Bitcoin is the eternal carrying cost of an additional language in consensus code. How close to 1 language can we get with Simplicity? Obviously, Script can't be removed, but to what extent can Script be implemented in Simplicity?

If so, it seems to me Bitcoin Core consensus code would become strictly cheaper to reason about than today, and alternate implementations would become more feasible: given Simplicity in Bitcoin, and Script implemented in Simplicity it should be much safer to use a node in language X given a provably correct Simplicity implementation in X.

[uncomputable]

Simplicity can express the semantics of any Bitcoin script, i.e., the Simplicity program will accept exactly the same witness data + transaction introspection as the Bitcoin script. Writing a Bitcoin Script interpreter in Simplicity is more difficult, because Bitcoin Script has weird quirks around the interpretation of bytes as integers, lock times, etc., to name one of many challenges.

[apoelstra]

How close to 1 language can we get with Simplicity?

Unfortunately I think it's impossible to reimplement Script in any other language. Simplicity is expressive enough to do it, but it's the rules of C++ which are fractal and unknowable, so any attempt to do this would inevitably entail an unintentional hardforking change.

So the answer to "how close to" is "not close enough" :).

If we were to start with a clean slate, say, if we were implementing Liquid today, we'd probably start out trying to implement as much of our consensus logic directly in Simplicity, which would give us a formal specification (and reimplementability) for free. We might even attempt to reimplement Script, so that users from Bitcoin could port their code without too much pain. But the result would certainly not be bug-for-bug compatible with Script.

[seedhammer]

Unfortunately I think it's impossible to reimplement Script in any other language. Simplicity is expressive enough to do it, but it's the rules of C++ which are fractal and unknowable, so any attempt to do this would inevitably entail an unintentional hardforking change.

I'm surprised you say "impossible" and not merely "very difficult and tedious". It seems to me that either the relevant parts of some C++ standard can be ported to Simplicity, or that even small differences such as switching between clang, gcc or a hypothetical future C++ compiler may also introduce unintentional hard forks.

We might even attempt to reimplement Script, so that users from Bitcoin could port their code without too much pain. But the result would certainly not be bug-for-bug compatible with Script.

This is great, but would that mean the use of Script will decay to approximately zero in the coming years?

I suppose a follow-up question is: if an unrelated change in compilers or runtime may introduce subtle hard forks, and those hard forks are getting subtler over time as Script use decreases, that's a reason to (carefully) port Script to Simplicity. It seems better to have a one-time controlled (x% risk of) hard fork than forever lurking hard forks.

So the answer to "how close to" is "not close enough" :).

A follow-up to this would be: can Script be piecewise ported (and proved equivalent) to Simplicity scripts, decreasing maintenance burden over time? Say, the most common and simple Script opcodes (or even entire script patterns).

[apoelstra]

A standard is not a specification; there is no specification of C++ or of any C++ compiler.

Given that we are de-facto assuming that the output of clang/gcc/mingw/etc are consistent with each other and across versions (though as you say, this is a dangerous assumption!), I suppose one approach could be to compile the script interpreter to RISC-V with gcc and then implement a RISC-V interpreter in Simplicity. This seems to me like it's in the "difficult and very tedious" category. But I maintain that directly attempting to specify C++ code is literally impossible.

This is great, but would that mean the use of Script will decay to approximately zero in the coming years?

No, there's lots of stuff that Script makes very simple and efficient to implement. Though it's probably true that complicated uses of Script (of which there are basically none, except for BitVM) would probably be replaced by a pure Simplicity implementation.

It seems better to have a one-time controlled (x% risk of) hard fork than forever lurking hard forks.

Hmm, yeah, I could be convinced of this. Though it would be a lot of work. I don't know if you'd be able to get community buy-in for such a thing.