package octez-libs

You can search for identifiers within the package.

in-package search v0.2.0

Package contains no libraries

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.

module Make_impl (PC : Kzg.Interfaces.Polynomial_commitment) : sig ... end

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 = {

cm_t : PC.Commitment.t;
pc_proof : PC.proof;
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

val setup : 
  setup_params:PC.Public_parameters.setup_params ->
  srs:(Kzg.Bls.Srs.t * Kzg.Bls.Srs.t) ->
  prover_public_parameters
  * verifier_public_parameters
  * Kzg.Utils.Transcript.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.

val prove : 
  prover_public_parameters ->
  Kzg.Utils.Transcript.t ->
  n:int ->
  generator:Kzg.Bls.Scalar.t ->
  secrets:
    (Kzg.Bls.Poly.t Plonk.Identities.SMap.t * PC.Commitment.prover_aux) list ->
  eval_points:Identities.eval_point list list ->
  evaluations:Identities.Evaluations.t Plonk.Identities.SMap.t ->
  identities:Identities.prover_identities ->
  nb_of_t_chunks:int ->
  proof * Kzg.Utils.Transcript.t

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.