Compute Decider's CM challenges in Groth16 circuit, link G16 & KZG proofs in Onchain Decider, refactor CommitmentScheme trait

[arnaucube]

• Refactor commitment package
  • Refactor Commitment trait and the kzg, ipa, pedersen impls
  • Add methods to prove & verify given challenges (not computing them in-method)
• Add KZG challenges computation in decider_eth_circuit
• Add cmE & cmW KZG proving & verification in DeciderEth
• Link Decider's Groth16 proof & KZG proofs data
• Fix point to bytes arkworks inconsistency
• Patch ark_curves to use a cherry-picked version with bn254::constraints & grumpkin for v0.4.0 (once arkworks v0.5.0 is released this will no longer be needed)

[arnaucube]

Thanks a lot for the review! ^^

Regarding

could be nice to avoid computing them multiple times across the circuit

they (the kzg challenges) are not computed multiple times across the circuit, only once (in-circuit). Outside the circuit I agree that there is no need for the verifier to compute them, updated to have only the prover computing them (appart from in-circuit) and providing them to the verifier.

[arnaucube]

The circuit is in fact checking that they are correctly computed, and the prover computes them in order to pass them as public inputs, but in-circuit they are not computed more than once. But you are right in that the prover outside the circuit is computing them twice, one in the decider_eth::prove and another time also inside the same method but in the other submethod from_nova. Good catch! Updated it here

[dmpierre]

The circuit is in fact checking that they are correctly computed, and the prover computes them in order to pass them as public inputs, but in-circuit they are not computed more than once. But you are right in that the prover outside the circuit is computing them twice, one in the decider_eth::prove and another time also inside the same method but in the other submethod from_nova. Good catch! Updated it here

Sorry I think my comment might have been unclear and made you confused, I indeed meant that the challenges were computed three different times within the circuit, the prover and the verifier.

LGTM!

[arnaucube]

(for the record, updated the PR moving the computation of the challenge r of the final NIFS.V into the circuit, to avoid needing to compute it by the verifier, and thus avoiding computing Poseidon in the smart contract)

[arnaucube]

Oh right! Absolutely! My bad, thanks for pointing it out!

Currently the code is checking: (only listing for $W{i+1}.W,~ U{i+1}.\overline{W}$ but same applies for $E, \overline{E}$)

• [out-circuit] the instance witness $W_{i+1}$ and the challenge $c_W$ are used to generate the KZG proofs at decider_eth.rs#L147
  • $(\pi_{KZG, W},~eval_W) \leftarrow KZG.P(cW, W{i+1}.W)$
    • where $eval_W=p_W(c_W)$, with $pW(X)\in \mathbb{F}[X]$ being the interpolated polynomial from the vector $W{i+1}.W$
• [in-circuit] it is checked the relaxed r1cs relation using $W{i+1}$ & $U{i+1}$, at decider_eth_circuit.rs#L377
  • $check~RelaxedR1CS(W{i+1}, U{i+1}) ==true$
• [in-circuit] the $U_{i+1}$ is used also to compute the KZG challenges (it checks their correct computation), at decider_eth_circuit.rs#L464
  • $cW \leftarrow H(U{i+1}.\overline{W})$
• [out-circuit] verifier checks the KZG proofs, using the $U_{i+1}$ and the challenges, at decider_eth.rs#L216
  • $KZG.V(U_{i+1}.\overline{W}, cW, (\pi{KZG,W},~eval_W))==true$

and so, as you pointed out, it's missing to check:

• $eval_W == p_W(c_W)$ (and same for $eval_E, c_E$)

Will add it! Again, thanks a lot for pointing this!

[arnaucube]

Update on this. Added the code to check in-circuit the $eval_W==p_W(c_W),~ eval_E==p_E(c_E)$: commit 9fb09628 But, currently facing an issue when interpolating (in-circuit) the polynomials to be evaluated, which seems to come from having a domain bigger than 2^11. Just opened the issue #80 to keep track of it, and also sent a message to arkworks's discord server hoping to find a solution. I'm thinking that if in a couple of days we don't find a solution we can merge the current PR as it is, and we can work on #80 in parallel to other stuff that depends on the current PR (ie. the Solidity verifier).

[arnaucube]

(commented it over chat, we're merging this to unblock other tasks, and in parallel we will work on #80 )