Merging schnorrsig module from Elements.

[DavidBurkett]

Pulling this in so we can use secp256k1_schnorrsig_verify_batch. We can probably just switch to the schnorrsig module entirely, and remove our custom aggsig module, but I haven't tested that yet.

[garyyu]

Thanks @DavidBurkett for this merging 👍

Remind to enable the test for new schnorrsig module, in .travis.yml, add a --enable-module-schnorrsig=xx in configure or sth.

An interesting bench test result on my laptop:

$ ./bench_schnorrsig 

schnorrsig_sign: min 63.0us / avg 64.0us / max 65.3us
schnorrsig_verify: min 77.3us / avg 78.5us / max 80.6us
schnorrsig_batch_verify_1: min 86.7us / avg 87.9us / max 88.9us
schnorrsig_batch_verify_2: min 69.2us / avg 70.2us / max 71.9us
schnorrsig_batch_verify_4: min 59.5us / avg 60.1us / max 60.9us
schnorrsig_batch_verify_8: min 55.8us / avg 56.9us / max 58.7us
schnorrsig_batch_verify_16: min 54.0us / avg 55.7us / max 58.3us
schnorrsig_batch_verify_32: min 53.6us / avg 54.1us / max 55.1us
schnorrsig_batch_verify_64: min 53.8us / avg 56.6us / max 61.3us
schnorrsig_batch_verify_128: min 50.3us / avg 50.8us / max 51.8us
schnorrsig_batch_verify_256: min 46.3us / avg 50.2us / max 57.5us
schnorrsig_batch_verify_512: min 44.8us / avg 48.7us / max 54.3us
schnorrsig_batch_verify_1024: min 40.4us / avg 40.5us / max 40.6us
schnorrsig_batch_verify_2048: min 37.7us / avg 38.3us / max 39.5us
schnorrsig_batch_verify_4096: min 35.2us / avg 35.8us / max 36.3us
schnorrsig_batch_verify_8192: min 34.0us / avg 34.5us / max 35.1us
schnorrsig_batch_verify_16384: min 34.5us / avg 35.4us / max 36.6us
schnorrsig_batch_verify_32768: min 34.1us / avg 34.6us / max 34.9us

That means if we batch with 1000 signatures, the average time is 40.5/78.5 = 51.6% compared to no batching. It's about 2 times fast, not much as I was expecting :-)

[DavidBurkett]

Good catch. I will enable those.

The batch verify reduces it from 2n point multiplications down to n+1. So ~50% is expected. Should be able to get similar gains with smaller batch sizes (eg 100)

[garyyu]

Hi @DavidBurkett , Could you finish this? just need very small modification on .travis.yml. And then next step is to integrate it in https://github.com/mimblewimble/rust-secp256k1-zkp, and then the Grin repo batch optimization.

Please let me know if any help is needed.

[DavidBurkett]

Yep, sorry for the delay @garyyu. It's fixed now. Once this is merged, I'll get started on rust-secp256k1-zkp.