package octez-libs

  1. Overview
  2. Docs
package octez-libs
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.

See 2019/953 Section 4.1 for more details.

Functor building an implementation of a polynomial protocol given a polynomial commitment scheme PC.

module type S = sig ... end

Output signature of the functor Polynomial_protocol.Make.

module Make (PC : Kzg.Interfaces.Polynomial_commitment) : S with module PC = PC
include sig ... end
module PC : sig ... end
type prover_public_parameters = PC.Public_parameters.prover

The type of prover public parameters.

val prover_public_parameters_t : prover_public_parameters Repr.t
type verifier_public_parameters = PC.Public_parameters.verifier

The type of verifier public parameters.

val verifier_public_parameters_t : verifier_public_parameters Repr.t
type proof = Make(Kzg.Polynomial_commitment).proof = {
  1. cm_t : PC.Commitment.t;
  2. pc_proof : PC.proof;
  3. pc_answers : PC.answer list;
}

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.

val proof_t : proof Repr.t

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.

val verify : verifier_public_parameters -> Kzg.Utils.Transcript.t -> n:int -> generator:Kzg.Bls.Scalar.t -> commitments:PC.Commitment.t list -> eval_points:Identities.eval_point list list -> identities:Identities.verifier_identities -> proof -> bool * Kzg.Utils.Transcript.t

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.

OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct