Batch operations for witness generation

[imeckler]

We could defer computing inverses in the witness (for computing EC ops) and batch compute them at the end.

[mimoo]

An explanation from @kevaundray that I found really useful:

So if you imagine that you need to compute the following circuit:

x = 1/y t + x = 0

I could generate the witness values as:

y = 2 x= 1/2 t = -1/2

So at the end we have three field elements [2, 1/2, -1/2] and I had to do 2 inversions to compute these witness values.

The alternative way is to have the following values at the end [2, (1,2), (-1,2)]

So no inversions are done yet, I can then do a batch inversion of the tuples/rationals. In that example ‘t’ relied on ‘x’ but we were still able to represent it without using inversions.

After doing a batch inversion and multiple of [2, (1,2), (-1,2)] i should end up with [2, 1/2, -1/2] which is what I would have gotten if I just did the inversions directly. I guess the trick is to allow witness values to be temporarily stored as fractions, which then allows you to defer inversions.

https://github.com/zcash/halo2/blob/d111807798d4719df36dc2b05b0104b69efdceb3/halo2_proofs/src/plonk/prover.rs#L286

[github-actions[bot]]

Stale issue message

[mimoo]

to add more colors, this would be for the circuit-writer

[github-actions[bot]]

Stale issue message

[github-actions[bot]]

Stale issue message