Investigate whether the overhead of generating random polys for zk can be reduced

[daira]

According to the thread starting here, this overhead is significant for large k.

We could either:

• try to reduce the degree of the polynomials r(X) generated in step 3 and s(X) in step 20 of the protocol (this would obviously require a proof that the protocol is still zk); or
• improve the concrete cost of C::Scalar::random(rng) (by choosing a different RNG to OsRng, sampling less randomness, better parallelization, and/or finding a different method than Montgomery reduction to ensure a uniform output).

[daira]

Here are the benchmark results for cargo bench -- plonk-prover in halo2_proofs after applying the attached norandom.diff (inspired by https://github.com/privacy-scaling-explorations/halo2/pull/73), which uses Scalar::zero() in various places instead of Scalar::random(&mut rng):

Benchmarking plonk-prover/8: Warming up for 3.0000 s
Warning: Unable to complete 10 samples in 5.0s. You may wish to increase target time to 5.6s or enable flat sampling.
plonk-prover/8          time:   [101.42 ms 106.77 ms 119.50 ms]                         
                        change: [-8.1800% -2.8545% +6.1356%] (p = 0.51 > 0.05)
                        No change in performance detected.
Found 1 outliers among 10 measurements (10.00%)
  1 (10.00%) high severe
Benchmarking plonk-prover/9: Warming up for 3.0000 s
Warning: Unable to complete 10 samples in 5.0s. You may wish to increase target time to 7.1s or enable flat sampling.
plonk-prover/9          time:   [126.73 ms 127.77 ms 128.42 ms]                         
                        change: [-21.724% -16.713% -12.366%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 1 outliers among 10 measurements (10.00%)
  1 (10.00%) low mild
Benchmarking plonk-prover/10: Warming up for 3.0000 s
Warning: Unable to complete 10 samples in 5.0s. You may wish to increase target time to 9.8s or enable flat sampling.
plonk-prover/10         time:   [171.82 ms 174.95 ms 179.21 ms]                          
                        change: [-37.766% -36.156% -34.569%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 3 outliers among 10 measurements (30.00%)
  1 (10.00%) low severe
  2 (20.00%) high severe
plonk-prover/11         time:   [247.87 ms 252.69 ms 259.70 ms]                          
                        change: [-33.523% -31.753% -29.447%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 1 outliers among 10 measurements (10.00%)
  1 (10.00%) high severe
plonk-prover/12         time:   [394.67 ms 396.62 ms 398.68 ms]                          
                        change: [-36.885% -35.351% -34.182%] (p = 0.00 < 0.05)
                        Performance has improved.
Benchmarking plonk-prover/13: Warming up for 3.0000 s
Warning: Unable to complete 10 samples in 5.0s. You may wish to increase target time to 7.1s.
plonk-prover/13         time:   [670.41 ms 681.91 ms 697.02 ms]                          
                        change: [-40.810% -37.210% -34.106%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 2 outliers among 10 measurements (20.00%)
  1 (10.00%) high mild
  1 (10.00%) high severe
Benchmarking plonk-prover/14: Warming up for 3.0000 s
Warning: Unable to complete 10 samples in 5.0s. You may wish to increase target time to 11.8s.
plonk-prover/14         time:   [1.2011 s 1.2406 s 1.2831 s]                             
                        change: [-35.935% -33.544% -30.763%] (p = 0.00 < 0.05)
                        Performance has improved.
Benchmarking plonk-prover/15: Warming up for 3.0000 s
Warning: Unable to complete 10 samples in 5.0s. You may wish to increase target time to 21.7s.
plonk-prover/15         time:   [2.1763 s 2.2137 s 2.2547 s]                             
                        change: [-18.982% -17.556% -16.104%] (p = 0.00 < 0.05)
                        Performance has improved.
Benchmarking plonk-prover/16: Warming up for 3.0000 s
Warning: Unable to complete 10 samples in 5.0s. You may wish to increase target time to 40.1s.
plonk-prover/16         time:   [4.0621 s 4.1581 s 4.2753 s]                             
                        change: [-18.459% -16.712% -14.398%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 2 outliers among 10 measurements (20.00%)
  2 (20.00%) high severe

[daira]

Most of the performance gap persists with this minimal diff, which only changes the sampling of r(X) and s(X) polynomials (as @sean and I suspected):

commit 0569143ac8cc0cbfdf81ba6a0c6ecae7a233b2ea (HEAD -> daira-insecure-nozk-do-not-merge)
Author: Daira Hopwood <daira@jacaranda.org>
Date:   Wed Jul 13 17:57:34 2022 +0100

    DO NOT MERGE. Minimal change to show performance gap due to random sampling of r(X) and s(X) polynomials.

diff --git a/halo2_proofs/src/plonk/vanishing/prover.rs b/halo2_proofs/src/plonk/vanishing/prover.rs
index c794070b..f2d24d65 100644
--- a/halo2_proofs/src/plonk/vanishing/prover.rs
+++ b/halo2_proofs/src/plonk/vanishing/prover.rs
@@ -44,7 +44,7 @@ impl<C: CurveAffine> Argument<C> {
         // Sample a random polynomial of degree n - 1
         let mut random_poly = domain.empty_coeff();
         for coeff in random_poly.iter_mut() {
-            *coeff = C::Scalar::random(&mut rng);
+            *coeff = C::Scalar::from(42);
         }
         // Sample a random blinding factor
         let random_blind = Blind(C::Scalar::random(rng));
diff --git a/halo2_proofs/src/poly/commitment/prover.rs b/halo2_proofs/src/poly/commitment/prover.rs
index f58973c1..27557453 100644
--- a/halo2_proofs/src/poly/commitment/prover.rs
+++ b/halo2_proofs/src/poly/commitment/prover.rs
@@ -44,7 +44,7 @@ pub fn create_proof<
     // by setting all coefficients to random values.
     let mut s_poly = (*p_poly).clone();
     for coeff in s_poly.iter_mut() {
-        *coeff = C::Scalar::random(&mut rng);
+        *coeff = C::Scalar::from(42);
     }
     // Evaluate the random polynomial at x_3
     let s_at_x3 = eval_polynomial(&s_poly[..], x_3);

Benchmarking plonk-prover/8: Warming up for 3.0000 s
Warning: Unable to complete 10 samples in 5.0s. You may wish to increase target time to 5.7s or enable flat sampling.
plonk-prover/8          time:   [102.84 ms 104.57 ms 106.73 ms]                         
                        change: [-17.736% -11.689% -6.5011%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 2 outliers among 10 measurements (20.00%)
  1 (10.00%) low mild
  1 (10.00%) high mild
Benchmarking plonk-prover/9: Warming up for 3.0000 s
Warning: Unable to complete 10 samples in 5.0s. You may wish to increase target time to 7.2s or enable flat sampling.
plonk-prover/9          time:   [129.15 ms 131.66 ms 134.78 ms]                         
                        change: [-11.672% -9.4764% -7.4507%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 2 outliers among 10 measurements (20.00%)
  1 (10.00%) high mild
  1 (10.00%) high severe
Benchmarking plonk-prover/10: Warming up for 3.0000 s
Warning: Unable to complete 10 samples in 5.0s. You may wish to increase target time to 9.7s or enable flat sampling.
plonk-prover/10         time:   [172.40 ms 173.47 ms 174.65 ms]                          
                        change: [-11.512% -10.880% -10.187%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 1 outliers among 10 measurements (10.00%)
  1 (10.00%) high mild
plonk-prover/11         time:   [253.59 ms 257.30 ms 263.95 ms]                          
                        change: [-17.277% -14.579% -11.760%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 1 outliers among 10 measurements (10.00%)
  1 (10.00%) high severe
plonk-prover/12         time:   [401.22 ms 414.84 ms 432.29 ms]                          
                        change: [-17.789% -14.585% -10.926%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 1 outliers among 10 measurements (10.00%)
  1 (10.00%) high severe
Benchmarking plonk-prover/13: Warming up for 3.0000 s
Warning: Unable to complete 10 samples in 5.0s. You may wish to increase target time to 6.8s.
plonk-prover/13         time:   [682.97 ms 707.57 ms 736.11 ms]                          
                        change: [-18.801% -15.369% -11.047%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 1 outliers among 10 measurements (10.00%)
  1 (10.00%) high mild
Benchmarking plonk-prover/14: Warming up for 3.0000 s
Warning: Unable to complete 10 samples in 5.0s. You may wish to increase target time to 11.9s.
plonk-prover/14         time:   [1.1858 s 1.2098 s 1.2469 s]                             
                        change: [-20.346% -17.718% -14.714%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 2 outliers among 10 measurements (20.00%)
  2 (20.00%) high severe
Benchmarking plonk-prover/15: Warming up for 3.0000 s
Warning: Unable to complete 10 samples in 5.0s. You may wish to increase target time to 21.7s.
plonk-prover/15         time:   [2.1700 s 2.1906 s 2.2142 s]                             
                        change: [-19.819% -17.997% -16.397%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 1 outliers among 10 measurements (10.00%)
  1 (10.00%) high mild
Benchmarking plonk-prover/16: Warming up for 3.0000 s
Warning: Unable to complete 10 samples in 5.0s. You may wish to increase target time to 41.8s.
plonk-prover/16         time:   [4.0862 s 4.1948 s 4.3730 s]                             
                        change: [-18.672% -16.080% -12.298%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 1 outliers among 10 measurements (10.00%)
  1 (10.00%) high severe

(These benchmark results may be more reliable since they were run when my machine was quieter.)