search

w3f / fflonk

Apache License 2.0
25 stars 6 forks source link

Small multiexp #18

Closed swasilyev closed 2 years ago

swasilyev commented 2 years ago

Stolen from https://github.com/zcash/halo2/pull/20

burdges commented 2 years ago

Interesting, should this be supported separately in arkworks?

swasilyev commented 2 years ago

Not sure. I guess Pippenger (or whatever var-base msm is in arkworks) becomes effective for just a couple (5-10) of bases.

swasilyev commented 2 years ago

https://github.com/w3f/fflonk/commit/6297e858feb01ba3d5d12948db574fc7d2e1e0cf

small-multiexp-vs-msm/small-multiexp-full/10
                        time:   [4.9025 ms 4.9884 ms 5.0778 ms]
small-multiexp-vs-msm/var-base-msm-full/10
                        time:   [6.1368 ms 6.2176 ms 6.3038 ms]
small-multiexp-vs-msm/small-multiexp-full/20
                        time:   [9.3413 ms 9.4883 ms 9.6417 ms]
small-multiexp-vs-msm/var-base-msm-full/20
                        time:   [8.7169 ms 8.8329 ms 8.9625 ms]

More like 15-20

burdges commented 2 years ago

In other words, they could dynamically tune it, so the interface need not be any more complicated.