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

[Keagan McClelland]

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/1fe82678/attachment.htm>