TODO
Compute wire polynomials , , with randomnesses
Output , ,
Compute permutation polynomial with randomnesses and challenge
Output
Compute quotient polynomial with challenge
Output , ,
Compute linearisation polynomial with challenge
Output , , , , , , ,
Compute opening proof polynomial with challenge
Output ,
When we want to access adjacent gate, for example , we only need to add extra evaluations and aggregate them in commit .
For Dusk Network's implementation as example, they access next gate's , , , so they have to aggregate them into .
Submit proof
TODO
Why is (Why is )
liangcc
Why we use randomnesses in , and but in ?
Cited Ariel Gabizon from <a href="https://www.plonk.cafe/t/noob-questions-plonk-paper/73">plonk.cafe #73</a> The rule is that if the poly is opened at points you need blinding factors; to hide both the commitment (which is an evaluation at a secret point in the exponent, but still to prove zk holds you’ll need this to be totally random, this proof that zk holds is quite similar to existing proofs - e.g. in Marlin, but is a missing hole in the paper right now) and the evaluation points.
So is opened at points and hence needs blinding factors.
Why bother including and in proof and check them in pairing if verifier can calculate himself.
han Guessing it's the reason that verification complexity is polylogarithmic , because evaluation is linear time.
Why is lack of and
han Guessing it's because we need to ensure prover is using the , and as we expected, so we let verifier compute these part.
How to constraint prover to use right and in and as verifier expected
han Guessing it's constrainted by the lack part of . If prover uses different and , then reconstructed by verifier will not equal to prover's .
Take Dusk Network implementation as an example
They split wire value into base-4, which makes , in range widget and logic widget to reduce gate number. For the reason that using base-4 is to make use of the max available degree of the permutation grand product in , which (4 wires).
TODO
TODO
TODO
AND
and XOR
at the same time)TODO