Improve G2 deserialization performance in arkworks

[simonmasson]

The deserialization in arkworks is currently very slow because of the subgroup check:

test bls12_381::g1::deser           ... bench:     190,636 ns/iter (+/- 3,634)
test bls12_381::g2::deser           ... bench:     630,359 ns/iter (+/- 4,483)

Using the technique of eprint 2019/814 would lead to a more efficient subgroup check and hence a more efficient deserialization. Roughly, G2 subgroup check can be ~3.5-4 times faster, and G1 subgroup check can be ~1.5-2 times faster. I am currently working on this.

[simonmasson]

I implemented the fast subgroup for both G1 and G2, and here are the results:

• With the naive subgroup check:

  test bls12_381::g1::deser           ... bench:     222,111 ns/iter (+/- 57,015)
  test bls12_381::g2::deser           ... bench:     646,068 ns/iter (+/- 71,398)

• With the fast subgroup check:

  test bls12_381::g1::deser           ... bench:     129,490 ns/iter (+/- 4,764)
  test bls12_381::g2::deser           ... bench:     192,589 ns/iter (+/- 55,601)

[simonmasson]

Benchmarks can be reproducible in the heliaxdev/curves repository, branch simon/fast-subgroup-checks.

cd /tmp
git clone git@github.com:heliaxdev/curves.git
cd curves/curve-benches/
git checkout simon/fast-subgroup-checks
cargo bench -- bls12_381 --exact

Next step is to benchmark the functions of Ferveo. It will be done in the branch simon/fast-subgroup-checks of Ferveo.

[simonmasson]

The subgroup check has been added to arkworks-rs/{algebra, curves}. Maybe the square root algorithm can be computed faster (?).