Legend:
Library
Module
Module type
Parameter
Class
Class type
A polynomial protocol allows a prover to convince a verifier of the fact that certain algebraic identites between polynomials (polynomials that have been previously committed) hold when evaluated over a set of points. (In our implementation such set of points must be a subgroup of roots of unity.)
For example, let K be a field and let H be a subset of K. Let f1(X), f2(X) and f3(X) be univariate polynomials over K and let C1, C2 and C3 be polynomial commitments to f1, f2 and f3, respectively. A polynomial protocol allows a prover to argue knowledge of:
PoK{ (f1, f2, f3) : Ci = Com(fi) ∀ i /\ f1(x) * f2(x) = f3(x) ∀ x ∈ H }
This can be accomplished by evaluating polynomial commitments at a single point ξ (uniformly sampled from K). For that, note that the above polynomial identity holds for every x ∈ H iff polynomial (f1 * f2 - f3) is divisible by Zh, the minimal (monic) polynomial that vanishes over set H. Thus, the prover can commit to polynomial T := (f1 * f2 - f3) / Zh and evaluate polynomial commitments C1, C2, C3, T at ξ (chosen after T). Let c1, c2, c3, t be such evaluations. The verifier can then check that t * Zh(ξ) = c1 * c2 - c3.
A general polynomial protocol should allow for multiple identities involving addition, multiplication and composition of polynomials.
The type for prover identities: functions from a (string) map of polynomials in FFT evaluations form to a (string) map of evaluated identities (also polynomials in FFT evaluations form).
A type to involve in the identities computations corresponding to (public) polynomials that have not been committed by the prover. It maps an evaluation point ξ and a PC.answer into a (string) map of evaluated (non-committed) polynomials.
The type for proofs, containing a commitment to the polynomial T that asserts the satisfiability of the identities over the subset of interest, as well as a PC proof and a list of PC answers.
The type for evaluation points. Either X, GX, or a custom point, which must be specified by an evaluation point name paired with a function that computes it from ξ. For example:
X could be implemented as Custom ("x", Fun.id)
GX could be implemented as Custom ("gx", fun x -> Scalar.mul generator x).
convert_eval_points gen x points maps the polynomial protocol points : eval_point list into scalars, by evaluating the underlying "composition" polynomial at x. The generator gen is used in case the eval_point equals GX, in which case the resulting scalar is x * gen.
compute_t ~n ~alpha evaluations returns a polynomial T splitted in chunks, where T(X) = (sum_i alpha^i evaluations[i]) / (X^n - 1) and the returned chunks { 'T_0' -> T0; 'T_1' -> T1; 'T_2' -> T2 } are such that T = T0 + X^n T1 + X^{2n} T2.
The polynomial commitment setup function, requires a labeled argument of setup parameters for the underlying PC and a labeled argument containing the path location of a set of SRS files.
The prover function. Takes as input the prover_public_parameters, an initial transcript (possibly including a context if this prove is used as a building block of a bigger protocol), the size n of subgroup H, the canonical generator of subgroup H, a list of secrets including polynomials that have supposedly been committed (and a verifier received such commitments) as well as prover auxiliary information generated during the committing process, a list of evaluation point lists specifying the evaluation points where each secret needs to be evaluated at, a map of the above-mentioned polynomials this time in FFT evaluations form, for efficient polynomial multiplication, and some prover_identities that are supposedly satisfied by the secret polynomials. Outputs a proof and an updated transcript.
The verifier function. Takes as input the verifier_public_parameters, an initial transcript (that should coincide with the initial transcript used by prove), the size n of subgroup H, the canonical generator of subgroup H, a list of commitments to the secret polynomials by the prover, a list of evaluation points as in prove, some verifier_identities, and a proof. Outputs a bool value representing acceptance or rejection.