Batch Affine Ops, Batch Subgroup Verification, Batch MSM, w-NAF - Githubissues

arkworks-rs / snark

Interfaces for Relations and SNARKs for these relations

https://www.arkworks.rs

Apache License 2.0

770 stars 207 forks source link

Batch Affine Ops, Batch Subgroup Verification, Batch MSM, w-NAF #295

Closed jon-chuang closed 3 years ago

jon-chuang commented 3 years ago

With refactored tests and all features except GLV. Recommended to review only after merging tests + affine refactor.

2/3 of a series of PRs to scipr-lab/zexe.

Features:

Batch Affine ops
Batch and ordinary w-NAF
GLV framework, GLV precomputation script.
GLV impl for both batch affine and projective mul (only for BW6)
Batch bucket addition tree
Batched MSM (1.4-1.7x bump)
Batch subgroup verification based on addition to random buckets
2D test matrix feature-gating with axes (curve, test type)
Refactor tests to use common template
Code timing instrumentation with fine grained control of functions and callers

Combined speedup (with w-NAF) for

Batched mul (with GLV): 2.3-2.7x.
Non-batch projective mul (with GLV): 2.1x. Without GLV: 1.65-1.8x and 1.4x resp.

Speedup for subgroup verification

Over old impl 25-80x.
Over new batch mul: 10-30x.

Future PRs:

In the context of w-NAF/batch scalar mul, make window size (for batch and also individual mul) and prefetch (batch only) an SWParameter.

Pratyush commented 3 years ago

Hi @jon-chuang do you mind re-opening this PR against arkworks-rs/algebra and against arkworks-rs/curves?

(It'll probably be quite a rework, sorry for the inconvenience!)