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

[ZmnSCPxj]

Good morning Russell,

Thank you very much your information!
I understood it better now.

> I've taken the liberty of replying on the mailing list to your question (we went off list only because of my failure to reply-all before).
>
> The way I imagine working with Simplicity is as follows.
>
> Someone develops a Simplicity program that they want to commit funds to (let's use Bitcoin as our example Blockchain here, but it could be Elements, or Liquid, etc.).
> This Simplicity program can be represented compactly as a DAG, where identical subexpressions are shared.  This sharing is unrelated to purity of Simplicity (in fact, outside of core Simplicity there are many impure Simplicity combinators), rather sharing is possible simply by virtue of the fact that identical subexpressions are identical.  All this development work happens off-chain.
>
> Once the agent is satisfied with their Simplicity program, they fill the witness values with dummy data and compute the program's "Commitment Merkle Root".   (The Commitment Merkle Root excludes witness values from its computation.) This is a recursive computation over the abstract syntax tree. However because identical subexpressions have identical commitment merkle roots (because the merkle root of a subexpression is only a function of the subexpression, and not of its overall position in the syntax tree), the results of these intermediate merkle roots can be shared during comptuation.  This means that the time it takes to compute the program's Commitment Merkle Root is proportional to the size of the program as a DAG (as opposed to the size of the program as a tree).
>
> The agent constructs a Bitcoin transaction that sends funds to the Commitment Merkle Root, which is embedded in the output's scriptPubKey via a new Segwit version, or indirectly via a Taproot version.
>
> Later, when the agent wishes to redeem these funds, they must create a transaction, and take their Simplicity program and
>
> 1) fill in suitable witness data in the program's witness nodes,
> 2) give the program a test run to make sure it passes successfully when given their prospective transaction,
> 3) prune any unused branches from their program that was not used in the above test execution (by converting case expressions into either assertl or assertr expressions).  Note: due to sharing it is possible that both branches of a case expression are executed, each one during different passes.  Such case expressions are not pruned.
>
> Once this is done they take that pruned "witness program" and compute its Witness Merkle Root and run the static analysis to determine the programs cost (in terms of program size, and bounds on the time and memory use).  This data is added as the witness data to the transaction.  Unlike the Commitment Merkle Root, the Witness Merkle root includes the witness values.
>
> The agent broadcasts this transaction to their peers.  Before accepting this data, their peers need the "witness program" to validate it.  The agent serialize the witness program as a DAG and transmits it to their peers, possibly abbreviating common sub-expressions that they have negotiated with their peers as ones they are both familiar with.  The agent's peers receive the witness program and computes its Commitment Merkle Root, Witness Merkle Root, and the static analysis of the execution costs and validates that the Witness Merkle Root and static analysis results match the transaction's witness data, and the Commitment Merkle root matches the value in the UTXO.  (The peers also make sure that the static analysis results are within acceptable/consensus required bounds and other anti-DoS checks).
>
> Lastly the peers execute the witness program to make sure it completes with success.  This execution can be done by traversing the DAG representing the witness program, and the presence of shared sub-expressions doesn't pose a problem, since this "program code" is read-only data.
>
> There are many variations of the above protocol that we could do instead, and the protocol I describe above is among the more aggressive variants I am considering.

Some minor comments:

1.  You mentioned some impure operations outside of core Simplicity.  Possibly `witness`, and maybe the equivalent of `OP_CHECKLOCKTIMEVERIFY` and `OP_CHECKSEQUENCEVERIFY`?  Are there others?  For my mind, it seems the "impurity" here would become pure once a specific transaction is committed to; my understanding is that Bitcoin SCRIPT itself is "pure" in that sense. (of course, if your input is the entire universe, every program is pure, since it simply outputs a different configuration of the entire universe)
2.  It seems to me that most of the savings with common sub-expressions is with transporting the program. Which is important because block size limit.
3.  From what I understand, effectively each fullnode still executes the program to confirm it completes without violating any assertions.

Regards,
ZmnSCPxj
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.ozlabs.org/pipermail/simplicity/attachments/20181206/a04ef318/attachment.html>