Optimization of proving a [non-zk]SNARK (Groth16)

Creator

Kubuxu

Created

Mar 7, 2022 5:43 PM

Stage

Graduated from Notebook

Authors: @Deleted User @Kubuxu

In Groth16 system

$B$ is evaluated twice, once within $G_1$ and once within $G_2$ due to $B$ being used both for $[C]_1$ and $[B]_2$. Evaluation of $B$ is a significantly expensive multiexp operation.

If $r$ is picked to be to zero by the prover (a completely valid value for $r$), as well as s, then evaluation of $B$ within $G_1$ can be omitted as latter it would be multiplied by zero.

Removal of the $B$ computation within $G_1$ results in 10% proving performance improvement (ProveCommit2, ReplicaUpdate, WindowPoSt).

This removes the protection of the prover against curious verifier (the proof cannot be called zero-knowledge anymore), as $r$ and $s$ are used to randomize the proof.

If $r$ is set to zero, we might as well set $s$ to zero as well, which doesn’t result in as big of benefit ($A$ is computed in $G_1$ as is $C$).

The verification routine is unchanged, the soundness of the system is unaffected.

This was previously discovered by Ariel Gabizon and Keyvan Kambakhsh but latter forgotten.

Closed