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

[Russell O'Connor]

Oops, I forgot to reply-all on this thread.

On Tue, Dec 4, 2018 at 4:50 PM Russell O'Connor <roconnor at blockstream.io>
wrote:

> In more complex Simplicity programs, even one specific code path used
> during redemption might traverse identical subexpressions multiple times.
> With Simplicity's sharing, the you pay the program size cost (which will
> likely be the dominant cost) for identical subexpressions only once (you
> will also pay the time cost for those multiple traversals, multiple times,
> but the time cost will probably be less steep than the program size costs,
> meaning you would need to traverse the same expensive expression many many
> times before it starts becoming a significant factor).  If this path were
> instead compiled to Bitcoin Script, it would mean duplicating the
> expression as many times as it is traversed unless you augment Bitcoin
> Script even further by adding some operations to allow for subroutines.
>
> I'm sorry that I haven't yet written up details about how I imagine the
> weight cost of Simplicity to be determined, but roughly speaking there are
> 3 types of costs:
>
> * Program size cost: the size of the Simplicity's expressions DAG (with
> sharing).
> * Program time cost: roughly the number of Simplicity combinators
> encountered during evaluation, counting the same node visited with
> multiplicity.
> * Program memory cost: the maximum resident memory required during
> evaluation.
>
> These factors would be combined to assigned an overall "weight" cost of a
> Simplicity expression, in some sort of arbitrary way.  The idea is that we
> want to exclude abusive programs, while permitting useful programs.
> Hopefully there is a wide enough gap between these two classes of programs
> that we can create an arbitrary division between the two, whose exact
> details, while being consensus critical, isn't all that important.  Also,
> rather than instrumenting the interpreter to count these costs, I'm
> inclined to just use the bounds determined by static analysis for the cost,
> but this is design choice is debatable.
>
> On Mon, Dec 3, 2018 at 11:01 PM ZmnSCPxj <ZmnSCPxj at protonmail.com> wrote:
>
>> Good morning Russell,
>>
>> > 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.
>>
>> My understanding is the value of sub-expression sharing is visible in
>> storing the Simplicity contract offchain --- onchain, only the specific
>> path that the contract took is visible, and sub-expression sharing is not
>> in effect.
>> Is my understanding wrong?
>>
>> Regards,
>> ZmnSCPxj
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.ozlabs.org/pipermail/simplicity/attachments/20181205/e226f843/attachment.html>