[Simplicity] Translating a Simplicity Dialect to MAST-enabled Bitcoin SCRIPT

[Russell O'Connor]

I agree that there are fungibility issues when it comes to the idea of
using Simplicity on Bitcoin.  Unfortunately, it seems likely to be
unavoidable.  Features like P2WSH/Taproot will likely mean that you cannot
tell a UTXO uses Simplicity until the UTXO is redeemed.  At redemption
time, it might be pretty clear if a program was derived from Simplicity
anyways, even if Simplicity were translated to Bitcoin Script.

A big problem is that translating Simplicity to Bitcoin Script would miss
out on a whole host of Simplicity features.  In particular, we wouldn't
have sub-expression sharing, which is likely going to be quite important
for many sophisticated programs.  Sub-expression sharing lets you "unroll"
bounded loops without multiplying the size of your program.

While I won't be pursuing this angle, that doesn't mean someone else cannot
explore doing this.  Actually, have some relevant work related to this
concept that I'm aiming to present in January/February, so stay tuned for
that.

On Sun, Dec 2, 2018 at 11:14 PM ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:

> Good morning Russell,
>
> Thank you very much your explanation of this plan.
>
> However, I wonder if it would generally be wiser, if we consider to use
> Bitcoin SCRIPT as execution target for a Simplicity dialect, to improve
> privacy and fungibility by not immediately advertising that a UTXO uses
> Simplicity.
> A separate SegWit version would immediately evidence use of Simplicity,
> with high probability.
>
> Of course, it is likely that even Simplicity-derived SCRIPT will look very
> different from what a human-level sentience might create.
> We could hope for the invention of a mythical "sufficiently smart
> compiler" that will optimize the generated SCRIPT to nearer to what a
> human-level sentinece might create by hand, but that is unlikely.
>
> Finally, we also need to re-enable OP_CAT, OP_AND, and O_RSHIFT.
>
> Which leads to another topic.
> Current Bitcoin SCRIPT disables many operations, like OP_CAT, OP_AND,
> OP_RSHIFT.
> These operations are needed in Bitcoin SCRIPT in order to emulate many of
> the basic operations of the Bit Machine currently targeted by the
> Simplicity.
> Even if these operations are re-enabled, it is likely that they will be
> imposed some limits to prevent the issues that caused them to be disabled
> in the first place.
> Thus it seems to me that a Bit Machine implementation would also require
> similar limits to the size of types, as it seems likely to me that a
> human-level sentience can manually write Bit Machine code that would
> massively increase memory consumption.
>
> Regards,
> ZmnSCPxj
>
>
>
> Sent with ProtonMail <https://protonmail.com> Secure Email.
>
> ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
> On Friday, November 30, 2018 6:19 AM, Russell O'Connor <
> roconnor at blockstream.io> wrote:
>
> Hi ZmnSCPxj,
>
> (It seems I wasn't subscribed to my own list, so I've manually quoted your
> post below)
>
> Should the Bitcoin community be interested in incorporating Simplicity, it
> would be done by utilizing the Segwit version scheme, and/or any upcoming
> Taproot version scheme.
>
> Segwit leaves completely open the interpretation of witness data for
> future versions, and does not require that the data be in some form of
> Bitcoin Script.  So it is possible, for example, to pass serialized
> Simplicity programs through Segwit's data blob, have it interpreted by a
> Simplicity interpreter, and not deal with Bitcoin Script at all (beyond the
> specific form of the scriptPubKey that BIP141
> <https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki#Witness_program>
> mandates).
>
> I do want to emphasize that we are a long way from even considering
> Simplicity for Bitcoin.  Such a radical update would need a huge amount of
> vetting before it would be acceptable for Bitcoin, if ever.  The best way
> to do that vetting is by running Simplicity in a sidechain, which is why
> I'm aiming to put Simplicity into the Elements platform first, then into
> Blockstream's Liquid network.  Even so, there still remains a lot of work
> to do before Simplicity can be incorporated into Elements.
>
> --
> Russell
>
>
>> Good morning list,
>>
>> From my understanding, Simplicity describes a family of languages which are effectively total (provably terminating) and not partial (may crash).
>> This prevents arbitrary looping, requiring bounds on recursion.
>>
>> Now, due to the fact that total languages assuredly terminate, it is possible to completely analyze a program written in a total language.
>> In particular, it is possible to speculatively execute every possible branch of a total program.
>>
>> If we import certain Bitcoin SCRIPT operations (signature checks and such) as primitives (jets?) of a Simplicity dialect, it seems to me possible to translate each possible execution of a total program written in this Simplicity dialect to a simple branchless Bitcoin SCRIPT.
>> Scripts would verify that the correct branch is being executed with given inputs, by use of `OP_VERIFY` on operations on those inputs.
>> (although we probably need to reenable some of the bit-manipulation operations in Bitcoin SCRIPT)
>> We can then commit all such SCRIPTs in a single MAST, or possibly just store each SCRIPT and a Graftroot signature (Graftroot has the tremendous advantage of low overhead, requiring O(1) information to select a branch, compared to O(log N) for MAST).
>>
>> Then a Simplicity interpreter can simply execute using given inputs, and determine which of the branches will run, and provide the SegWit `witness` stack to claim a TXO.
>>
>> Am I right in thinking that this is the eventual way that Simplicity will reach the Bitcoin blockchain?
>>
>> Finally: first post.
>>
>> Regards,
>> ZmnSCPxj
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.ozlabs.org/pipermail/simplicity/attachments/20181203/6c5477f1/attachment-0001.html>