Feat/plonk prover #64
Conversation
|
|
||
| // WriteTo mock impementation | ||
| func (md *MockDigest) WriteTo(w io.Writer) (n int64, err error) { | ||
| return 0, nil |
There was a problem hiding this comment.
return errNotImplemented or panic
|
|
||
| // ReadFrom mock impementation | ||
| func (md *MockDigest) ReadFrom(r io.Reader) (n int64, err error) { | ||
| return 0, nil |
There was a problem hiding this comment.
return errNotImplemented or panic
|
|
||
| // WriteTo panics | ||
| func (s *Scheme) WriteTo(w io.Writer) (n int64, err error) { | ||
| return 0, nil |
There was a problem hiding this comment.
return errNotImplemented or panic
|
|
||
| // Degree returns the degree of the polynomial, which is the length of Data. | ||
| func (p Poly) Degree() uint64 { | ||
| res := uint64(len(p) - 1) |
There was a problem hiding this comment.
if we have a unitialized Polynomial, (ie len(p) == 0) this return a large degree. Maybe return 0 if len(p) == 0? or panic, if we never hit that.
| // Eval evaluates p at v | ||
| func (p Poly) Eval(v interface{}) interface{} { | ||
| var res, _v fr.Element | ||
| _v.Set(v.(*fr.Element)) |
There was a problem hiding this comment.
since you don't modify v, you may try to keep it as an address, to avoid unneeded copies
| var res, _v fr.Element | ||
| _v.Set(v.(*fr.Element)) | ||
| s := len(p) | ||
| res.Set(&p[s-1]) |
There was a problem hiding this comment.
same as above, this panics if len(p) == 0.
| } | ||
| return lro | ||
| // TODO panic if wire is already instantiated |
There was a problem hiding this comment.
check if O was already instantiated
| if coset != 0 { | ||
| if decimation == DIF { |
There was a problem hiding this comment.
as discussed, this significantly slows down groth16.Prove
This PR contains a first version of the plonk prover, instantiated with a dummy polynomial commitment scheme. There are no custom gates.
The exposed API for using PLONK is the same as Groth16:
plonk.Setup(...),plonk.Prove(...),plonk.Verify(...).Note 1: currently the verifier is not succint. Indeed the public polynomials corresponding to a circuit are not committed, and the verifier has to evaluate them at a random point, and this operation is not succint.
Note 2: Fiat Shamir is not implemented, so the numerous challenges are hard coded at the moment. It's the next step to add Fiat Shamir.
API
The workflow for writing a circuit is the same as Groth16. Things starts to differ at the circuit compilation stage.
Compilation
sparseR1cs, err := frontend.Compile(curve.ID, backend.PLONK, circuit.Circuit)->sparseR1csis now a list of constraints of the formql*l+qr*r+qm*l*r+qo*o+qk=0, whereql,qr,qm,qo,qkare coefficients corresponding to the circuit, andl,r,oare the wires.Setup
Once a circuit is compiled, the list of coefficients
(ql,qr,qm,qo,qk)needs to be converted to polynomials, and the permutation leavingl || r || oinvariant (corresponding to the gates wiring) needs to be computed. Domains for FFTs and associated precomputed values are computed (there are 2 domains). Finally a polynomial commitment scheme is chosen.Those information are public (since they correspond to a circuit that a prover and a verifier share) and are stored in a struct called
PublicRaw(the raw means that the polynomials are not committed).Generation of public data:
publicData, err := Setup(sparseR1cs, polynomialCommitmentScheme, witness)Currently only a dummy polynomial commitment scheme is implemented in
crypto/(it is not necessary for validating the plonk prover and plonk verifier).The witness is necessary in the setup to add special constraints encoding the public input, namely the constraints
l-witness[i]=0are prepend to the constraint system. The permutation takes in account those constraints (which are not encoded in the circuit after compilation), so they cannot be tampered. This operation is described in the comments of theSetupfunction which refer to "placeholders".Prove
proof, err := Prove(sparseR1cs, publicData, witness)--> it returns aproofobject, containing commitments to the solutionl,r,o, as well as the permutation accumulating polynomial Z, and the quotient polynomial H.The order of operations is such that the number of FFT calls is minimized.
Verify
err = Verify(proof, publicData, witness)--> verifies the openings ofl,r,o,h,zat a challenge (on which the prover has no control), and verifies the final polynomial equality evaluated at the challenge.Note: the opening of
lfrom the prover is incomplete, and the verifier needs to complete it by adding the public witness, just as in Groth16. This mecanism ensures that the verifies is convinced that the proof is associated to the right public inputs, exactly like in Groth16.Status