AztecProtocol / barretenberg

Apache License 2.0
129 stars 78 forks source link

valid `batch_mul` in a vanilla ultra circuit will fail when the group elements are equal #971

Open maramihali opened 2 months ago

maramihali commented 2 months ago

In the folding recursive verifier we might hit the scenerio where we do a batch_mul(commitments, lagranges) where the commitments are equal. That is because when we add gates to ensure no zero commitments these will be the same for all circuits. This hits an edge case in the biggroup's batch_mul implementation. The function computes linear combinations of the points, specifically for points [A], [B] we compute [A] + [B] and [A] - [B] and so if the points are equal [A] - [B] would be zero. This edge case is handled in cycle_group using offset_generators so we can follow that pattern to fix for biggroup. This problem persists even after having a zero commitment in biggroup because using zero's representation would be too expensive.

At the moment, for the folding recursive verifier instantiated as a vanilla ultra circuit we hack around and avoid batch_mul's altogether.