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

[Russell O'Connor]

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/20181129/ad63fbfd/attachment.html>