package tezos-plonk

  1. Overview
  2. Docs
package tezos-plonk
Legend:
Library
Module
Module type
Parameter
Class
Class type

Module to operate with polynomials in FFT evaluations form.

type polynomial = PC.Polynomial.Polynomial.t
val t : t Repr.t
val of_array : (int * PC.Scalar.t array) -> t

of_array (d, e) creates a value of type t from the evaluation representation of a polynomial e of degree d, i.e, it converts an OCaml array to a C array

val to_array : t -> PC.Scalar.t array

to_array converts a C array to an OCaml array

val string_of_eval : t -> string

string_of_eval e returns the string representation of evaluation e

val of_domain : domain -> t

of_domain d converts d from type domain to type t.

Note: of_domain d doesn't create a copy of d

val to_domain : t -> domain

to_domain d converts d from type t to type domain.

Note: to_domain d doesn't create a copy of d

val zero : t

zero returns the evaluation representation of the zero polynomial

val is_zero : t -> bool

is_zero p checks whether a polynomial p is the zero polynomial

val degree : t -> int

degree returns the degree of a polynomial. Returns -1 for the zero polynomial

val length : t -> int

length e returns the size of domain where a polynomial is evaluated, or equally, the size of a C array where evaluation e is stored

val create : int -> t

create len returns the evaluation representation of a zero polynomial of size len

val copy : ?res:t -> t -> t

copy ?res a returns a copy of evaluation a. The function writes the result in res if res has the correct size and allocates a new array for the result otherwise

val get : t -> int -> PC.Scalar.t

get p i returns the i-th element of a given array p

val mul_by_scalar : PC.Scalar.t -> t -> t

mul_by_scalar computes muliplication of a polynomial by a blst_fr element

val mul_c : ?res:t -> evaluations:t list -> ?composition_gx:(int list * int) -> ?powers:int list -> unit -> t

mul_c computes p₁(gᶜ₁·x)ᵐ₁·p₂(gᶜ₂·x)ᵐ₂·…·pₖ(gᶜₖ·x)ᵐₖ, where

  • pᵢ = List.nth evaluations i
  • mᵢ = List.nth powers i
  • cᵢ = List.nth (fst composition_gx) i
  • n = snd composition_gx is the order of generator, i.e., gⁿ = 1

The function writes the result in res if res has the correct size (= min (size pᵢ)) and allocates a new array for the result otherwise

Note: res and pᵢ are disjoint

val linear_c : ?res:t -> evaluations:t list -> ?linear_coeffs:PC.Scalar.t list -> ?composition_gx:(int list * int) -> ?add_constant:PC.Scalar.t -> unit -> t

linear_c computes λ₁·p₁(gᶜ₁·x) + λ₂·p₂(gᶜ₂·x) + … + λₖ·pₖ(gᶜₖ·x) + add_constant, where

  • pᵢ = List.nth evaluations i
  • λᵢ = List.nth linear_coeffs i
  • cᵢ = List.nth (fst composition_gx) i
  • n = snd composition_gx is the order of generator, i.e., gⁿ = 1

The function writes the result in res if res has the correct size (= min (size pᵢ)) and allocates a new array for the result otherwise

Note: res and pᵢ are disjoint

val linear_with_powers : t list -> PC.Scalar.t -> t

linear_with_powers p s computes ∑ᵢ sⁱ·p.(i). This function is more efficient than linear + powers for evaluations of the same size

val add : ?res:t -> t -> t -> t

add ?res a b computes polynomial addition of a and b. The function writes the result in res if res has the correct size (= min (size (a, b))) and allocates a new array for the result otherwise

Note: res can be equal to either a or b

val equal : t -> t -> bool

equal a b checks whether a polynomial a is equal to a polynomial b

Note: equal is defined as restrictive equality, i.e., the same polynomial evaluated on different domains are said to be different

val evaluation_fft : domain -> polynomial -> t

evaluation_fft domain p converts the coefficient representation of a polynomial p to the evaluation representation. domain can be obtained using Domain.build

Note:

  • size of domain must be a power of two
  • degree of polynomial must be strictly less than the size of domain
val interpolation_fft : domain -> t -> polynomial

interpolation_fft domain p converts the evaluation representation of a polynomial p to the coefficient representation. domain can be obtained using Domain.build

Note:

  • size of domain must be a power of two
  • size of a polynomial must be equal to size of domain
val interpolation_fft2 : domain -> PC.Scalar.t array -> polynomial
val dft : domain -> polynomial -> t

dft domain polynomial converts the coefficient representation of a polynomial p to the evaluation representation. domain can be obtained using Domain.build

requires:

  • size domain to divide Bls12_381.Fr.order - 1
  • size domain != 2^k
  • degree polynomial < size domain
val idft_inplace : domain -> t -> polynomial

idft_inplace domain t converts the evaluation representation of a polynomial p to the coefficient representation. domain can be obtained using Domain.build

requires:

  • size domain to divide Bls12_381.Fr.order - 1
  • size domain != 2^k
  • size domain = size t
val evaluation_fft_prime_factor_algorithm : domain1:domain -> domain2:domain -> polynomial -> t

evaluation_fft_prime_factor_algorithm domain1 domain2 p converts the coefficient representation of a polynomial p to the evaluation representation. domain can be obtained using Domain.build. See the Prime-factor FFT algorithm.

requires:

  • size domain1 * size domain2 to divide Bls12_381.Fr.order - 1
  • size domain1 and size domain2 to be coprime
  • if for some k size domain1 != 2^k then size domain1 <= 2^10
  • if for some k size domain2 != 2^k then size domain2 <= 2^10
  • degree polynomial < size domain1 * size domain2
val interpolation_fft_prime_factor_algorithm_inplace : domain1:domain -> domain2:domain -> t -> polynomial

interpolation_fft_prime_factor_algorithm domain1 domain2 t converts the evaluation representation of a polynomial p to the coefficient representation. domain can be obtained using Domain.build. See the Prime-factor FFT algorithm.

requires:

  • size domain1 * size domain2 to divide Bls12_381.Fr.order - 1
  • size domain1 and size domain2 to be coprime
  • if for some k size domain1 != 2^k then size domain1 <= 2^10
  • if for some k size domain2 != 2^k then size domain2 <= 2^10
  • size t = size domain1 * size domain2
val size_evaluations : t Plonk.SMap.t -> int

size_evaluations returns the maximum size of elements in evaluations

val find_evaluation : t Plonk.SMap.t -> string -> t

find_evaluation m name returns the evaluation for a given name name

val print_evaluations_name : t Plonk.SMap.t -> unit

print_evaluations_name prints (name, degree, length) for each evaluation

val get_domain : t Plonk.SMap.t -> domain

get_domain returns the evaluation for "X"

val compute_evaluations : domain:domain -> polynomial Plonk.SMap.t -> t Plonk.SMap.t

compute_evaluations converts the coefficient representation of each polynomial pᵢ to the evaluation representation.

Note:

  • size of domain must be a power of two
  • size of a polynomial pᵢ must be less than or equal to size of domain
val compute_evaluations_update_map : ?domain:domain -> evaluations:t Plonk.SMap.t -> polynomial Plonk.SMap.t -> t Plonk.SMap.t

compute_evaluations_update_map writes the result of compute_evaluations in evaluations. If domain is not provided, get_domain is called

val mul : ?res:t -> evaluations:t Plonk.SMap.t -> poly_names:string list -> ?composition_gx:(int list * int) -> ?powers:int list -> unit -> t

mul invokes mul_c with the evaluations for given names poly_names

val linear : ?res:t -> evaluations:t Plonk.SMap.t -> poly_names:Plonk.SMap.key list -> ?linear_coeffs:PC.Scalar.t list -> ?composition_gx:(int list * int) -> ?add_constant:PC.Scalar.t -> unit -> t

linear invokes linear_c with the evaluations for given names poly_names