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

Last edited
Mar 7, 2022 8:37 PM
Project

Authors: @nikkolasg g @Kubuxu

In Groth16 system

image

is evaluated twice, once within and once within due to being used both for and . Evaluation of is a significantly expensive multiexp operation.

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

Removal of the computation within 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 and are used to randomize the proof.

If is set to zero, we might as well set to zero as well, which doesn’t result in as big of benefit ( is computed in as is ).

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.