Batch verify

[iquerejeta]

Content

This PR implements batch-verification for STM certificates, and benchmarks the results. In the final verify of the aggregated multisignatures, we check a pairing equality, meaning that for a chain of n STM certificates, we compute 2n pairings. By using a batching technique, we can reduce this number to n + 1 pairings.

Comments

Benchmarks show that if we only look at the final check of STM signatures (verifying that the aggregate signature is correct with respect to the aggregate public key), the gains are considerable. A x2 improvement for batches of 100 signatures:

MultiSig/Batch Verification/Batch size: 1
                        time:   [586.49 µs 588.12 µs 590.48 µs]

MultiSig/Batch Verification/Batch size: 100
                        time:   [5.4062 ms 5.4660 ms 5.5350 ms]

However, STM signature verification, at least in the current state, requires also to compute the aggregate of the signatures and public keys. This requires two multiscalar multiplications of at least k (for k the security parameter) elements. The overhead caused by the pairing evaluation is minimised, and the gains of batch-verification are less significant:

STM/Blake2b/Batch Verification/k: 25, m: 150, nr_parties: 300/batch size: 1
                        time:   [2.2606 ms 2.2674 ms 2.2747 ms]

STM/Blake2b/Batch Verification/k: 25, m: 150, nr_parties: 300/batch size: 10
                        time:   [18.056 ms 18.089 ms 18.127 ms]

STM/Blake2b/Batch Verification/k: 25, m: 150, nr_parties: 300/batch size: 20
                        time:   [34.939 ms 34.981 ms 35.029 ms]

STM/Blake2b/Batch Verification/k: 25, m: 150, nr_parties: 300/batch size: 100
                        time:   [175.11 ms 175.22 ms 175.34 ms]

STM/Blake2b/Batch Verification/k: 250, m: 1523, nr_parties: 2000/batch size: 1
                        time:   [3.9876 ms 4.0245 ms 4.0574 ms]

STM/Blake2b/Batch Verification/k: 250, m: 1523, nr_parties: 2000/batch size: 10
                        time:   [35.719 ms 35.956 ms 36.202 ms]

STM/Blake2b/Batch Verification/k: 250, m: 1523, nr_parties: 2000/batch size: 20
                        time:   [76.466 ms 78.880 ms 81.210 ms]

STM/Blake2b/Batch Verification/k: 250, m: 1523, nr_parties: 2000/batch size: 100
                        time:   [318.40 ms 319.29 ms 320.23 ms]

We can see that for parameters with k = 25, we have that the improvements are 23%, while with k = 250, the improvements are of 20%. However, and observation can be made that, for k=25, batching 10 STM signatures gives a 19% speedup, while going up to batches of size 100 only gives a ~3% improvement (wrt batches of size 10). For k = 250, the pattern is less significant, with ~10% and ~10% respectively.

Issue(s)

Closes #530

[github-actions[bot]]

Unit Test Results

    6 files   -   1    21 suites   - 3   21s :stopwatch: - 1m 53s 308 tests  - 29  308 :heavy_check_mark:  - 29  0 :zzz: ±0  0 :x: ±0  309 runs   - 29  309 :heavy_check_mark:  - 29  0 :zzz: ±0  0 :x: ±0 

Results for commit eb4ca900. ± Comparison against base commit 18360730.

This pull request removes 29 tests.

dense_mapping::tests ‑ test_precision_approximation
key_reg::tests ‑ test_keyreg
merkle_tree::tests ‑ test_bytes_path
merkle_tree::tests ‑ test_bytes_tree
merkle_tree::tests ‑ test_bytes_tree_commitment
merkle_tree::tests ‑ test_create_invalid_proof
merkle_tree::tests ‑ test_create_proof
multi_sig::tests ‑ serialize_deserialize_pk
multi_sig::tests ‑ serialize_deserialize_sk
multi_sig::tests ‑ test_aggregate_sig
…

:recycle: This comment has been updated with latest results.

[github-actions[bot]]

Test Results

    3 files  ±0    28 suites  ±0   5m 17s :stopwatch: + 2m 43s 383 tests +2  383 :heavy_check_mark: +2  0 :zzz: ±0  0 :x: ±0  444 runs  +2  444 :heavy_check_mark: +2  0 :zzz: ±0  0 :x: ±0 

Results for commit 2ff20390. ± Comparison against base commit a43b1b8b.

This pull request removes 1 and adds 3 tests. Note that renamed tests count towards both.

multi_sig::tests ‑ serialize_deserialize_pk

multi_sig::tests ‑ batch_verify
multi_sig::tests ‑ serialize_deserialize_vk
stm::tests ‑ batch_verify

:recycle: This comment has been updated with latest results.