Bench marking Chaum-Pedersen Signature in the G1 vs in another sister group

[drskalman]

This is to see if we get a significant speed up using another (smaller) curve to compute Chaum-Pedersen Signatures instead of doing it in G1.

[drskalman]

I'm getting this result from benchmarking, these are for 100 operation in each benchmark:

test bench::test_add_in_signature_group_no_glv_no_mul_by_a        ... bench:      52,390.58 ns/iter (+/- 7,576.31)
test bench::test_add_in_weirestarss_sister_group                  ... bench:      31,420.78 ns/iter (+/- 1,886.16)
test bench::test_base_field_mul_in_signature_group                ... bench:       3,314.71 ns/iter (+/- 189.57)
test bench::test_base_field_mul_in_weirestarss_sister_group       ... bench:       1,756.46 ns/iter (+/- 152.71)
test bench::test_double_in_signature_group_no_glv_no_mul_by_a     ... bench:      41,997.51 ns/iter (+/- 4,560.46)
test bench::test_double_in_weirestarss_sister_group               ... bench:      31,403.28 ns/iter (+/- 4,360.36)
test bench::test_scalar_mul_in_signature_group                    ... bench:   9,855,113.30 ns/iter (+/- 1,388,543.03)
test bench::test_scalar_mul_in_signature_group_no_glv_no_mul_by_a ... bench:  15,120,891.70 ns/iter (+/- 2,198,052.41)
test bench::test_scalar_mul_in_weirestarss_sister_group           ... bench:   9,961,467.90 ns/iter (+/- 1,480,594.64)

while field multiplication is (/ 3314.71 1756.46) 88% faster, Curve addition and doubling are only (/ 52390.58 31420.78) = 66% (/ 41997.51 31403.28) = 33% faster respectively. So I don't find it a surprise that scalar multiplication is only (/ 15120891.70 9961467.90) = 51% faster. And that advantage is erased by use of GLV which is (/ 15120891.70 9855113.30) = 53% faster than naive scalar multiplication.

[drskalman]

I implemented Straus + GLV. Here are the results:

SW Sister:

[Shamir] scalar_to_bigint: 55ns
[Shamir] skip_leading_zeros: 39ns
[Shamir] precompute_sum: 23ns
[Shamir] main_loop (256 bits): 228.885µs
[Shamir] TOTAL: 249.512µs
[CP] A_check_point (dual_scalar_mul): 250.293µs
[GLV] scalar_decomposition: 2.934µs
[GLV] computing 16-element table at runtime
[GLV] table_setup: 46.357µs
[GLV] scalar_to_bigint: 79ns
[GLV] skip_leading_zeros: 188ns
[GLV] main_loop (125 bits): 212.758µs
[GLV] TOTAL: 266.41µs
[CP] B_check_point (dual_scalar_mul): 721.309µs
[CP] TOTAL: 1.528533ms
[SW Test] verify_cp_signature (Strauss-Shamir): 1.531311ms


G1 as its own Sister:

[GLV] scalar_decomposition: 2.427µs
[GLV] using precomputed 256-element table
[GLV] table_setup: 459ns
[GLV] scalar_to_bigint: 78ns
[GLV] skip_leading_zeros: 180ns
[GLV] main_loop (126 bits): 212.311µs
[GLV] TOTAL: 219.348µs
[CP] A_check_point (dual_scalar_mul): 219.938µs
[GLV] scalar_decomposition: 2.357µs
[GLV] computing 16-element table at runtime
[GLV] table_setup: 43.885µs
[GLV] scalar_to_bigint: 79ns
[GLV] skip_leading_zeros: 165ns
[GLV] main_loop (126 bits): 212.799µs
[GLV] TOTAL: 263.802µs
[CP] B_check_point (dual_scalar_mul): 714.984µs
[CP] TOTAL: 1.499989ms
[G1 Test] verify_cp_signature (Straus+GLV G1 as Sister): 1.501483ms

Precomputation of generator and public key table gives me (264/219 ~ 1.2) about 20% speed up.

[drskalman]

Benchmarks for verifying 100 signatures:

test bench::test_bls_verify_many_signatures_chaum_pedersen_in_weierstrass_sister_group_naive  ... bench:  71,707,910.90 ns/iter (+/- 15,981,093.43)
test bench::test_bls_verify_many_signatures_chaum_pedersen_in_weierstrass_sister_group_straus ... bench:  56,673,368.50 ns/iter (+/- 7,464,420.98)
test bench::test_verify_cp_signature_ark_msm                                                  ... bench:  83,484,527.70 ns/iter (+/- 10,148,656.06)
test bench::test_verify_cp_signature_naive                                                    ... bench:  69,121,854.70 ns/iter (+/- 11,885,304.97)
test bench::test_verify_cp_signature_strauss_shamir_with_glv                                  ... bench:  54,598,180.90 ns/iter (+/- 3,157,865.26)
test bench::test_verify_cp_signature_strauss_shamir_without_glv                               ... bench:  56,008,530.30 ns/iter (+/- 8,041,054.80)

[drskalman]

test bench::test_bls_verify_many_signatures_chaum_pedersen_in_weierstrass_sister_group_naive  ... bench:  74,191,843.10 ns/iter (+/- 4,907,156.95)
test bench::test_bls_verify_many_signatures_chaum_pedersen_in_weierstrass_sister_group_straus ... bench:  59,035,318.10 ns/iter (+/- 3,677,845.55)
test bench::test_verify_cp_signature_ark_msm                                                  ... bench:  88,462,893.80 ns/iter (+/- 2,077,186.53)
test bench::test_verify_cp_signature_naive                                                    ... bench:  72,392,576.90 ns/iter (+/- 2,087,447.51)
test bench::test_verify_cp_signature_strauss_shamir_with_glv                                  ... bench:  56,549,039.40 ns/iter (+/- 2,530,194.70)
test bench::test_verify_cp_signature_strauss_shamir_without_glv                               ... bench:  58,125,801.60 ns/iter (+/- 3,283,162.73)
test bench::test_verify_signature_with_pairing                                                ... bench: 147,369,407.60 ns/iter (+/- 8,744,499.37)

comparing to normal bls signature verification cp, is 2.5 times faster i.e. we get 150% speed up.

[drskalman]

I still had redundant hash to curve calls :-/, this ithe result after removing those:

  ┌─────────────────────────────┬───────────┬──────────────┐
  │          Benchmark          │ Time (ms) │  vs Pairing  │
  ├─────────────────────────────┼───────────┼──────────────┤
  │ Strauss-Shamir + GLV        │ 38.2      │ 3.85x faster │
  ├─────────────────────────────┼───────────┼──────────────┤
  │ Strauss-Shamir (no GLV)     │ 39.7      │ 3.71x faster │
  ├─────────────────────────────┼───────────┼──────────────┤
  │ Weierstrass sister (Straus) │ 42.2      │ 3.49x faster │
  ├─────────────────────────────┼───────────┼──────────────┤
  │ Naive CP                    │ 52.6      │ 2.80x faster │
  ├─────────────────────────────┼───────────┼──────────────┤
  │ Weierstrass sister (naive)  │ 59.0      │ 2.50x faster │
  ├─────────────────────────────┼───────────┼──────────────┤
  │ Ark MSM                     │ 66.7      │ 2.21x faster │
  ├─────────────────────────────┼───────────┼──────────────┤
  │ Pairing verification        │ 147.3     │ baseline     │
  └─────────────────────────────┴───────────┴──────────────┘
  Verifying 100 Signatures.

CP is about 4 times faster than BLS that is about 300% speed up.