[Simplicity] Experimental Branch: haskell-ffi-jets-secp256k1

[Russell O'Connor]

Indeed, this 13s is more or less the same pre-processing that is used when
serializing a Simplicity program developed in Haskell so that it can later
be read and evaluated by the C implementation.  I expect the C evaluation
is even faster than 0.02 seconds (and I'll probably add an FFI interface to
the whole C Simplicity evaluator eventually so you can run it from Haskell).

Though this is effectively a "compile time" cost, due to lazy evaluation in
Haskell, this compilation cost ends up deferred until the first time it is
needed. This is why my first execution incurs this cost, but subsequent
executions do not.

On Fri, Mar 20, 2020 at 2:05 PM Keagan McClelland <
keagan.mcclelland at gmail.com> wrote:

> Ah, I think I misunderstood something about your original post. Am I
> correct in saying that the 13s is a strict *compile time* cost and that
> conversion to maximal sharing is done before committing to some expression?
>
> If so I am much less worried. I think devs will more than tolerate a 13s
> compile time. What I am nervous about is a 13s evaluation time during
> consensus validation as I'm concerned 13s would make the system unusable.
>
> On Fri, Mar 20, 2020 at 12:00 PM Russell O'Connor <
> roconnor at blockstream.com> wrote:
>
>> The current Haskell implementation of Simplicity uses implicit sharing of
>> subexpressions.  There is a process for converting to an explicitly shared
>> structure, and I suspect it is this conversion process that is the main
>> expense.  It involves repeatedly taking unions of maps of merkle roots that
>> may have obvious large overlapping subsets.  It is necessary to convert to
>> explicit sharing because, while a Simplicity expression is logically a
>> tree, if you traverse it as a tree in order to find all jets, it would take
>> an exponential amount of time.
>>
>> One solution might be to take a more sophisticated approach to computing
>> the "unions" of these maps (which are representing DAGs).   After all, if
>> the merkle root of one subexpression occurs in both maps, then all of those
>> sub-subexpressions must also be in both maps, and can therefore be skipped.
>>
>> It might also be reasonable to develop Simplicity programs through a
>> different type of Simplicity expressions with explicit sharing of
>> subexpressions. Converting such a program to the implicit representation
>> would be trivial, and you could therefore use all the existing tools
>> (evaluation, serialization, etc.) at their existing costs.  However you
>> could also do evaluation directly on this alternative representation with
>> explicit sharing.  This would let you bypass the conversion of implicit
>> sharing to explicit sharing.  This comes at the cost of not maximizing the
>> sharing, but for evaluation purposes, maximizing sharing doesn't really
>> matter (during evaluation shared subexpressions are necessarily repeatedly
>> evaluated anyways).  I haven't done this up to now because I've been trying
>> my best to stay close to the semantics of Simplicity which has no notion of
>> sharing.  Obviously this purity has come at some cost, so this alternative
>> approach is probably worth investigating.
>>
>> Another option might be to make the use of jets in Simplicity programming
>> explicit and include an optional optimized implementation as part of the
>> explicit jet.  This has the minor disadvantage that jets might appear
>> incidentally when programs are composed out of subexpressions.  Searching
>> for jets will always find jets if they exist, but if the programmer is
>> marking jets explicitly, they might miss some.
>>
>> Some of the above imperfect solutions might be very handy during
>> development, leaving the current AST search that maximizes sharing and jets
>> for a final pass once development is complete.  Ultimately we will need one
>> or more higher level languages that get compiled to Simplicity.  When that
>> exists we will probably mostly do development through a direct
>> interpretation of that higher-level language, and compile to a fully shared
>> and optimized Simplicity program for final testing with the C
>> implementation.  For this reason, it might not be worth expending too much
>> effort on making writing raw Simplicity more comfortable.  What I've
>> implemented in the haskell-ffi-jets-secp256k1 branch was easy to build on
>> the existing, necessary code for searching for jets for serialization
>> purposes.  However, since such a higher-level language doesn't yet exist,
>> expending a little bit more effort to making writing raw Simplicity is
>> perhaps reasonable.
>>
>> On Fri, Mar 20, 2020 at 12:54 PM Keagan McClelland <
>> keagan.mcclelland at gmail.com> wrote:
>>
>>> Thanks Russell!
>>>
>>> Is the 13 seconds expression search time a fundamental limitation
>>> related to the AST search, or is it more a result of the implementation
>>> currently? I ask because it seems like jets could be marked by their merkle
>>> roots and stored in a hash table. If this is the case, it's not immediately
>>> obvious why the search would be any different during the first time than
>>> the others.
>>>
>>> On Fri, Mar 20, 2020 at 10:16 AM Russell O'Connor <
>>> roconnor at blockstream.com> wrote:
>>>
>>>> Dear all,
>>>>
>>>> I know of a couple of people who are getting into the nitty-gritty of
>>>> developing Simplicity programs despite the lack of tooling support.  I
>>>> appreciate the efforts of these bold persons, so I'll be trying to give
>>>> more updates on this mailing list.
>>>>
>>>> While the main focus of my efforts are still on the consensus critical
>>>> components of the C library, I want to put some effort into helping
>>>> Simplicity developers.  Right now, Simplicity programs are best developed
>>>> in using the Simplicity Haskell library.  However, testing of Simplicity
>>>> programs by directly interpreting the Simplicity expressions is very slow
>>>> for all but the simplest programs.
>>>>
>>>> Recently I've pushed an experimental branch, <
>>>> https://github.com/ElementsProject/simplicity/tree/haskell-ffi-jets-secp256k1>.
>>>> This branch adds 'Simplicity.Elements.Jets.fastEval' and
>>>> 'Simplicity.Bitcoin.Jets.fastEval' functions that searches for
>>>> subexpressions with known jets, and evaluates these subexpressions using
>>>> jets, making FFI calls to a C implementation in some cases.  At the moment,
>>>> the set of known jets includes 32-bit arithmetic, sha-256 compression, and
>>>> (old-style) schnorr signature assertion. More jets will be developed.
>>>>
>>>> While the overhead of searching for jets is quite high, once completed
>>>> an expression can be repeatedly evaluated, making this process quite
>>>> suitable for randomized testing.  Observe below that by sharing
>>>> fastSchnorrAssert the first evaluation takes 13 seconds, but
>>>> subsequent evaluations take 0.02 seconds.  Without using jets, the direct
>>>> interpretation of schnorrAssert using Simplicity.Elements.Semantics.sem
>>>> could take hours.
>>>>
>>>>     Prelude Simplicity.Ty.Word> let fastSchnorrAssert =
>>>> Simplicity.Elements.Jets.fastEval
>>>> Simplicity.Programs.LibSecp256k1.Lib.schnorrAssert
>>>>     (0.02 secs, 102,456 bytes)
>>>>     Prelude Simplicity.Ty.Word> let {pk = toWord256
>>>> 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798; m =
>>>> toWord256 0; sig = toWord512
>>>> 0x528F745793E8472C0329742A463F59E58F3A3F1A4AC09C28F6F8514D4D0322A258BD08398F82CF67B812AB2C7717CE566F877C2F8795C846146978E8F04782AE}
>>>> in fastSchnorrAssert undefined ((pk,m),sig)
>>>>     Just ()
>>>>     (12.71 secs, 17,984,271,240 bytes)
>>>>     Prelude Simplicity.Ty.Word> let {pk = toWord256
>>>> 0xEEFDEA4CDB677750A420FEE807EACF21EB9898AE79B9768766E4FAA04A2D4A34; m =
>>>> toWord256
>>>> 0x243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89; sig =
>>>> toWord512
>>>> 0x667C2F778E0616E611BD0C14B8A600C5884551701A949EF0EBFD72D452D64E844160BCFC3F466ECB8FACD19ADE57D8699D74E7207D78C6AEDC3799B52A8E0598}
>>>> in fastSchnorrAssert undefined ((pk,m),sig)
>>>>     Nothing
>>>>     (0.02 secs, 555,224 bytes)
>>>>     Prelude Simplicity.Ty.Word> let {pk = toWord256
>>>> 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798; m =
>>>> toWord256 0; sig = toWord512
>>>> 0x528F745793E8472C0329742A463F59E58F3A3F1A4AC09C28F6F8514D4D0322A258BD08398F82CF67B812AB2C7717CE566F877C2F8795C846146978E8F04782AE}
>>>> in fastSchnorrAssert undefined ((pk,m),sig)
>>>>     Just ()
>>>>     (0.02 secs, 526,288 bytes)
>>>>
>>>> This feature is still under development; however, I want to make it
>>>> available as early as possible, because I think it will be especially
>>>> helpful for some folks, even at this early stage.
>>>> --
>>>> Simplicity mailing list
>>>> Simplicity at lists.ozlabs.org
>>>> https://lists.ozlabs.org/listinfo/simplicity
>>>>
>>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.ozlabs.org/pipermail/simplicity/attachments/20200320/43a26204/attachment-0001.htm>