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

[Keagan McClelland]

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/962ae56e/attachment.htm>