bip-340: recreate batch verify speedup graph w/ latest libsecp256k1 #1096

jonasnick commented at 9:19 PM on April 1, 2021: contributor

Since creating that graph there have been significant improvements in libsecp256k1 to the speed of certain operations, such as making use of the endomorphism by default and the safegcd algorithm. This new graph shows the batch verification speedup in light of these improvements.

There are also some minor improvements to the graph itself. In particular, the (1,1) datapoint was removed because it is not part of the estimation for the fitted line.

This commit also contains the Makefile, shell script and gnuplot file that were used to create the graph.

CC @sipa @real-or-random

sipa commented at 3:55 AM on April 2, 2021: member

Trying to run your benchmark code I get:

$ make
cat raw_output.txt | grep -v "schnorrsig_batch_verify_1" | awk 'match($0,                         /schnorrsig_batch_verify_(.*):.*avg (.*)us /, a) {print a[1] " " a[2]}' >                         batch.dat                                                                         awk: line 1: syntax error at or near ,

bip-340: recreate batch verify speedup graph w/ latest libsecp256k1

Since creating that graph there have been significant improvements in
libsecp256k1 to the speed of certain operations, such as making use of the
endomorphism by default and the safegcd algorithm. This new graph shows the
batch verification speedup in light of these improvements.

There are also some minor improvements to the graph itself. In particular,
the (1,1) datapoint was removed because it is not part of the estimation for the
fitted line.

This commit also contains the Makefile, shell script and gnuplot file that were
used to create the graph.

4ce1ff8b63

jonasnick commented at 8:24 AM on April 2, 2021: contributor

@sipa Hm, I can't reproduce this. awk --version is GNU Awk 5.1.0 on my end.

sipa commented at 4:37 PM on April 2, 2021: member

@jonasnick Ok, apparently I was using "mawk" instead of "gawk".

I redid the benchmarks myself (Intel i7-7820HQ, clock fixed at 2.6 Ghz) with higher granularity and higher iteration count, and got this graph:

speedup-batch

I'm not sure a logarithmic interpolation is what we need...

in bip-0340/speedup-batch/Makefile:5 in 4ce1ff8b63 outdated

   0 | @@ -0,0 +1,11 @@
   1 | +bench_output.txt: bench.sh
   2 | +	SECP256K1_BENCH_ITERS=100000 ./bench.sh bench_output.txt
   3 | +
   4 | +batch.dat: bench_output.txt
   5 | +	cat bench_output.txt | grep -v "schnorrsig_batch_verify_1" | awk 'match($$0, /schnorrsig_batch_verify_(.*):.*avg (.*)us /, a) {print a[1] " " a[2]}' > batch.dat

sipa commented at 4:38 PM on April 2, 2021:

This is ignoring all numbers where the batch size starts with decimal digit "1". By using grep -v "schnorrsig_batch_verify_1:" that is avoided.

jonasnick commented at 5:03 PM on April 2, 2021:

good catch, fixed

fixup! use gawk instead of awk, fix excluding n=1 batch_verify 820bcf8936

jonasnick marked this as a draft on Apr 2, 2021

jonasnick commented at 5:07 PM on April 2, 2021: contributor

I'll rerun the experiment with similar granularity. That many data points makes the fitted line useless anyway.

sipa commented at 11:18 PM on April 2, 2021: member

New graph with much higher scratch space:

speedup-batch

0racl3z approved

jonasnick commented at 2:34 PM on April 13, 2021: contributor

Before creating a new graph, we should take into account 1) https://github.com/sipa/bips/issues/219 and 2) new estimated optimal pippenger threshold/windows.

sipa commented at 4:48 PM on April 13, 2021: member

@jonasnick Also, the optimal pippenger thresholds/windows may be affected by the use of 128-bit randomizers?

0racl3z commented at 7:49 PM on April 13, 2021: none

Im supposed to be using tails aren't i..😔

On Tue, Apr 13, 2021, 11:49 AM Pieter Wuille @.***> wrote:

@jonasnick https://github.com/jonasnick Also, the optimal pippenger thresholds/windows may be affected by the use of 128-bit randomizers?

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/bitcoin/bips/pull/1096#issuecomment-818886259, or unsubscribe https://github.com/notifications/unsubscribe-auth/ASNKRHBXMRNMVLLV2BJ7RVTTIRYYPANCNFSM42H2D2XQ .

luke-jr commented at 10:53 PM on April 22, 2021: member

What is the status here? It's marked as a Draft...

sipa commented at 11:03 PM on April 22, 2021: member

I think this is not ready for merge.

jonasnick commented at 7:08 AM on April 23, 2021: contributor

@luke-jr I changed this to draft after we realized that this PR isn't satisfactory, requires more work and has a dependency on another potential BIP-340 update. If you prefer, we can (temporarily) close this PR and move the discussion elsewhere.

0racl3z commented at 7:06 PM on April 23, 2021: none

Still aiming for a solution. I don't recall drafting it

On Thu, Apr 22, 2021, 5:53 PM Luke Dashjr @.***> wrote:

What is the status here? It's marked as a Draft...

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/bitcoin/bips/pull/1096#issuecomment-825232496, or unsubscribe https://github.com/notifications/unsubscribe-auth/ASNKRHEJS5E5VF2JJP7H74DTKCSHHANCNFSM42H2D2XQ .

gmaxwell commented at 9:22 PM on April 25, 2021: contributor

An alternative might just be removing the speedup details from the BIP entirely (or just for now).

0racl3z commented at 6:45 AM on April 27, 2021: none

Understood, i'm trying to restore old files in the hopes of any type of outcome.

On Sun, Apr 25, 2021, 4:22 PM Gregory Maxwell @.***> wrote:

An alternative might just be removing the speedup details from the BIP entirely (or just for now).

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/bitcoin/bips/pull/1096#issuecomment-826392009, or unsubscribe https://github.com/notifications/unsubscribe-auth/ASNKRHBW3GZM6A52MSGKGPLTKSBYNANCNFSM42H2D2XQ .

real-or-random commented at 10:58 AM on May 5, 2021: contributor

An alternative might just be removing the speedup details from the BIP entirely (or just for now).

I like that idea. This BIP a spec, which should be valid for years. So at some point the numbers will be outdated anyway... (Yeah, we have also other "motivational" sections which will be outdated at some point but I still don't think we need the speedup numbers.)

gmaxwell commented at 9:40 PM on May 5, 2021: contributor

Should be sufficient for the purpose of the BIP to just say that batch validation is a substantial speedup.

0racl3z approved

0racl3z commented at 6:12 PM on May 8, 2021: none

Thx!

jonasnick commented at 9:23 PM on May 13, 2021: contributor

Given that there are apparently many factors that significantly affect the speedup I agree that this plot is not very useful to a reader. We don't even mention that the graph only applies to a specific implementation. And for it's limited usefulness the graph draws too much attention in the BIP.

I'd suggest to add the graph to the libsecp doc/ dir and link to it from this BIP to prove that batching does in fact lead to a substantial speedup.

real-or-random commented at 7:51 AM on May 14, 2021: contributor

I'd suggest to add the graph to the libsecp doc/ dir and link to it from this BIP to prove that batching does in fact lead to a substantial speedup.

That's a good idea.

0racl3z commented at 7:30 PM on May 14, 2021: none

I'm in the process of a solution perhaps. I'll update when an outcome happens

On Fri, May 14, 2021, 2:51 AM Tim Ruffing @.***> wrote:

I'd suggest to add the graph to the libsecp doc/ dir and link to it from this BIP to prove that batching does in fact lead to a substantial speedup.

That's a good idea.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/bitcoin/bips/pull/1096#issuecomment-841079226, or unsubscribe https://github.com/notifications/unsubscribe-auth/ASNKRHB375KBB7ZMI7ED6DDTNTJBTANCNFSM42H2D2XQ .

jonasnick closed this on May 17, 2021

jonasnick cross-referenced this on May 17, 2021 from issue WIP: Add schnorrsig batch verification by jonasnick

jonasnick cross-referenced this on May 17, 2021 from issue BIP340: remove batch speedup graph and link to it instead by jonasnick