Single-threaded generation of random poly is slow

[jonathanpwang]

halo2/halo2_proofs/src/plonk/vanishing/prover.rs

Line 51 in 9e6d1b7

for coeff in random_poly.iter_mut() {

When k > 20 or so, this single-threaded generation of a random polynomial is actually quite slow and can even dominate the proving cost(!). If zero-knowledge is not necessary, then you can simply set the polynomial to 1, 0, 0, ... (note 0, 0, ... makes the commitment the identity point, which sometimes causes trouble).

When zero-knowledge is needed, you can still parallelize this generation using parallelize and par_iter_mut but I think it might require some care around what properties you want the random number generator to have. You can't pass &mut between threads. I previously just added Send + Clone to the R trait, but I think rng.clone() is not good practice between threads? If you use a specific rng such as StdRng then you can either seed it using thread_rng per thread or use set_stream.

I did not have strong opinions about how to proceed, so just leaving this here as a PSA for now.

[CPerezz]

I remember we had an implementation that speeded this up so that it wasn't an issue at all.

Thet's weird.. Will investigate on that and follow up!

[CPerezz]

Hey @jonathanpwang I've not been able to find any popular rust libs that allow for fast random vec instanciation.

What about this:
we evaluate num_cpus and we query the rng num_cpus times.
Then, we wake one thread that computes 2^k / num_cpus items where each one is the original random value (safe seed) multiplied by itself.

On that way the seeds of each thread are crypto secure. And so, the derived computations.

[jonathanpwang]

Then, we wake one thread that computes 2^k / num_cpus items where each one is the original random value (safe seed) multiplied by itself.

I wasn't sure what trait R needed in order to do this. If you try to use &mut rng within a thread it will complain since &mut is not copyable. Are you suggesting to use rng.clone() but then multiply it by the safe seed random value? That sounds pretty good to me (R would need to implement Sync + Clone I think).

[CPerezz]

@jonathanpwang Sorry I not explained correctly.
I hope this pseudocode demonstrates a bit more the idea.

I'm assuming that even inside the pieces, scalars have a known relation between them, you can't do anything with it as when the next piece comes the relation is broken + the initial scalar was random.
I'm not sure how much you can break going this way (I'm not sure at all is safe xD).

let num_cpus = GET_NUM_CPUS;

let rand_scalars_needed_per_thread = (2<<DOMAIN.degree()) / num_cpus;
// This is still single threaded. We compute N random scalars.
let scalars = (0..num_cpus).iter().map(|| Scalar::random(&mut rng)).collect();

let handler = thread::spawn(|| {
    let starting_rand_scalar = scalars[i].clone();
    let mut piece = vec![starting_random_scalar];
    for _ in 0..rand_scalars_needed_per_thread {
          piece.push(piece.last().unwrap() * starting_rand_scalar);
    }
   piece
});

handler.join().unwrap();

// Then we join all the pieces and we have the random vec computed in parallel.

[jonathanpwang]

Ah I see. This is a nice solution. I'm also not totally sure how safe it is to use the powers for randomness, but it is done in many other places in the prover, so it's probably ok? :)

[CPerezz]

@jonathanpwang I hope the solution purposed in #152 works well enough.
In my 8cpu machine gets decently better results.

[lispc]

Btw in scroll fork，we set the random poly full of 1s so the commitment is (1,2) point.. Since we don't need blinding as a rollup

[CPerezz]

@lispc makes complete sense. But we want to allow for other usages. And, so, we leave correct settings for blinders in case you want to use them :)