Skip to content
This repository was archived by the owner on Feb 17, 2025. It is now read-only.
This repository was archived by the owner on Feb 17, 2025. It is now read-only.

Implement composition polynomials #9

@nemothenoone

Description

@nemothenoone

Composition polynomial represents a polynomial of the form:

F(x, y_1, y_2, ... , y_k) = \sum_i (c_{2i} + c_{2i+1} * x^{n_i}) * f_i(x, y_0, y_1, ... , y_k, p_0, ... , p_m) * P_i(x)/Q_i(x).

Where:

  • The term (c_{2i} + c_{2i+1} * x^{n_i}) is used for both logical 'AND' over all the constraints, and degree adjustment of each constraint.
  • The sequence (p_0, ... , p_m) consists of the evaluations of the periodic public columns.
  • The term f_i(y_0, y_1, ... , y_k, p_0, ... , p_m) represents a constraint.
  • The term P_i(x)/Q_i(x) is a rational function such that Q_i(x)/P(i) is a polynomial with only simple roots, and its roots are exactly the locations in which the constraint f_i has to be satisfied.

Parameters deduction:

  • (c_0, c_1, ...) are the random coefficients chosen by the verifier.
  • The values of (n_0, n_1,...) are computed so that the degree bound of the resulting polynomial will be air->GetCompositionPolynomialDegreeBound().
  • The functions (f_0, f_1,...) are induced by air.ConstraintsEval().
  • The mask (for evaluations on entire cosets) is obtained from air.GetMask().

Composition polynomials are supposed to be used both to evaluate F(x, y_0, y_1, ...) on a single point, and on entire cosets using optimizations improving the (amortized) computation time for each point in the coset.

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or request

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions