barretenberg icon indicating copy to clipboard operation
barretenberg copied to clipboard

Make `offset_generator_element` a free witness in biggroup batch_mul

Open suyash67 opened this issue 2 months ago • 0 comments

To ensure we don't hit a point at infinity while constructing ROM tables in biggroup batch_mul, we "mask" the input points with (multiples of) an offset generator of the form:

$$H = \delta \cdot G_{\textsf{offset}}$$

where $\delta$ is a Fiat-Shamir challenge (a circuit witness) and $G_{\textsf{offset}}$ is a deterministic generator (free witness in the circuit). The purpose of masking is to never let an honest prover reach a point where an entry in the ROM tables (simple linear combination of the points) is a point at infinity. If we didn't have masking, and say we are performing an MSM of the form:

$$P + 3P + 4P$$

we would have an entry in the ROM table of the form: $((P) + (3P) - (4P)) = \mathcal{O}$. We mask it using a challenge $\delta$ so that a prover would not know this masking generator $H$ beforehand. Ariel thinks we don't need to multiply with $\delta$, and that just a free-witness should be good enough (if the prover really wants to generate a valid proof, he must select a valid, random point $G_{\textsf{offset}}$). We need to decide if this is fine and then implement this change.

suyash67 avatar Nov 18 '25 12:11 suyash67