iop

Documentation

Overview

Package iop provides an API to computations common to iop backends (permutation, quotient).

Index

• Variables
• type Basis
• type Expression
• type Form
• type Layout
• type Polynomial
  • func BuildRatioCopyConstraint(entries []*Polynomial, permutation []int64, beta, gamma fr.Element, ...) (*Polynomial, error)
  • func BuildRatioShuffledVectors(numerator, denominator []*Polynomial, beta fr.Element, expectedForm Form, ...) (*Polynomial, error)
  • func DivideByXMinusOne(a *Polynomial, domains [2]*fft.Domain) (*Polynomial, error)
  • func Evaluate(f Expression, r []fr.Element, form Form, x ...*Polynomial) (*Polynomial, error)
  • func NewPolynomial(coeffs *[]fr.Element, form Form) *Polynomial
  • func (p *Polynomial) Blind(blindingOrder int) *Polynomial
  • func (p *Polynomial) BlindedSize() int
  • func (p *Polynomial) Clone(capacity ...int) *Polynomial
  • func (p Polynomial) Coefficients() []fr.Element
  • func (p *Polynomial) Evaluate(x fr.Element) fr.Element
  • func (p *Polynomial) GetCoeff(i int) fr.Element
  • func (p *Polynomial) ReadFrom(r io.Reader) (int64, error)
  • func (p *Polynomial) SetBlindedSize(size int)
  • func (p *Polynomial) SetSize(size int)
  • func (p *Polynomial) ShallowClone() *Polynomial
  • func (p *Polynomial) Shift(shift int) *Polynomial
  • func (p *Polynomial) Size() int
  • func (p *Polynomial) ToBitReverse() *Polynomial
  • func (p *Polynomial) ToCanonical(d *fft.Domain, nbTasks ...int) *Polynomial
  • func (p *Polynomial) ToLagrange(d *fft.Domain, nbTasks ...int) *Polynomial
  • func (p *Polynomial) ToLagrangeCoset(d *fft.Domain) *Polynomial
  • func (p *Polynomial) ToRegular() *Polynomial
  • func (p *Polynomial) WriteTo(w io.Writer) (int64, error)

Variables

var (
	ErrMustBeRegular              = errors.New("the layout must be Regular")
	ErrMustBeCanonical            = errors.New("the basis must be Canonical")
	ErrMustBeLagrangeCoset        = errors.New("the basis must be LagrangeCoset")
	ErrInconsistentFormat         = errors.New("the format of the polynomials must be the same")
	ErrInconsistentSize           = errors.New("the sizes of the polynomial must be the same as the size of the domain")
	ErrNumberPolynomials          = errors.New("the number of polynomials in the denominator and the numerator must be the same")
	ErrSizeNotPowerOfTwo          = errors.New("the size of the polynomials must be a power of two")
	ErrInconsistentSizeDomain     = errors.New("the size of the domain must be consistent with the size of the polynomials")
	ErrIncorrectNumberOfVariables = errors.New("the number of variables is incorrect")
)

errors related to the computation of the quotient and the ratios.

Types

type Basis

type Basis uint32

Basis indicates the basis in which a polynomial is represented.

const (
	Canonical Basis = 1 << iota
	Lagrange
	LagrangeCoset
)

type Expression

type Expression func(i int, x ...fr.Element) fr.Element

Expression represents a multivariate polynomial.

type Form

type Form struct {
	Basis  Basis
	Layout Layout
}

Form describes the form of a polynomial. TODO should be a regular enum?

type Layout

type Layout uint32

Layout indicates if a polynomial has a BitReverse or a Regular layout

const (
	Regular Layout = 8 << iota
	BitReverse
)

type Polynomial

type Polynomial struct {
	// contains filtered or unexported fields
}

Polynomial wraps a polynomial so that it is interpreted as P'(X)=P(\omega^{s}X). Size is the real size of the polynomial (seen as a vector). For instance if len(P)=32 but P.Size=8, it means that P has been extended (e.g. it is evaluated on a larger set) but P is a polynomial of degree 7. blindedSize is the size of the polynomial when it is blinded. By default blindedSize=Size, until the polynomial is blinded.

func BuildRatioCopyConstraint

func BuildRatioCopyConstraint(
	entries []*Polynomial,
	permutation []int64,
	beta, gamma fr.Element,
	expectedForm Form,
	domain *fft.Domain) (*Polynomial, error)

BuildRatioCopyConstraint builds the accumulating ratio polynomial to prove that [P₁ ∥ .. ∥ P_{n—1}] is invariant by the permutation \sigma. Namely it returns the polynomial Z whose evaluation on the j-th root of unity is Z(ω^j) = Π_{i<j}(Π_{k<n}(P_k(ω^i)+β*u^k+γ))/(P_k(ω^i)+σ(kn+i)+γ))) * entries list of polynomials whose evaluation are invariant under \sigma * beta, gamma challenges * expectedForm expected form of the resulting polynomial

func BuildRatioShuffledVectors

func BuildRatioShuffledVectors(numerator, denominator []*Polynomial, beta fr.Element, expectedForm Form, domain *fft.Domain) (*Polynomial, error)

Build an 'accumulating ratio' polynomial. * numerator list of polynomials that will form the numerator of the ratio * denominator list of polynomials that will form the denominator of the ratio The polynomials in the denominator and the numerator are expected to be of the same size and the size must be a power of 2. The polynomials are given as pointers in case the caller wants to FFTInv the polynomials during the process. * beta variable at which the numerator and denominators are evaluated * expectedForm expected form of the resulting polynomial * Return: say beta=β, numerator = [P₁,...,P_m], denominator = [Q₁,..,Q_m]. The function returns a polynomial whose evaluation on the j-th root of unity is (Π_{k<j}Π_{i<m}(β-Pᵢ(ωᵏ)))/(β-Qᵢ(ωᵏ))

func DivideByXMinusOne

func DivideByXMinusOne(a *Polynomial, domains [2]*fft.Domain) (*Polynomial, error)

DivideByXMinusOne The input must be in LagrangeCoset. The result is in Canonical Regular.

func Evaluate

func Evaluate(f Expression, r []fr.Element, form Form, x ...*Polynomial) (*Polynomial, error)

Evaluate evaluates f on each entry of x. The returned value is the vector of evaluations of e on x. The form of the result is form. if r is provided (not nil), it is used as the result vector, that is the memory space for the coefficients of the resulting polynomial. The Size field of the result is the same as the one of x[0]. The blindedSize field of the result is the same as Size. The Shift field of the result is 0.

func NewPolynomial

func NewPolynomial(coeffs *[]fr.Element, form Form) *Polynomial

NewPolynomial returned a Polynomial from the provided coefficients in the given form. A Polynomial can be seen as a "shared pointer" on a list of coefficients. It is the responsibility of the user to call the Clone method if the coefficients shouldn't be mutated.

func (*Polynomial) Blind

func (p *Polynomial) Blind(blindingOrder int) *Polynomial

Blind blinds a polynomial q by adding Q(X)*(X^{n}-1), where deg Q = blindingOrder and Q is random, and n is the size of q. Sets the result to p and returns it.

blindingOrder is the degree of Q, where the blinding is Q(X)*(X^{n}-1) where n is the size of p. The size of p is modified since the underlying polynomial is of bigger degree now. The new size is p.Size+1+blindingOrder.

/!\ The code panics if wq is not in canonical, regular layout

func (*Polynomial) BlindedSize

func (p *Polynomial) BlindedSize() int

BlindedSize returns the the size of the polynomial when it is blinded. By default blindedSize=Size, until the polynomial is blinded.

func (*Polynomial) Clone

func (p *Polynomial) Clone(capacity ...int) *Polynomial

Clone returns a deep copy of p. The underlying polynomial is cloned; see also ShallowClone to perform a ShallowClone on the underlying polynomial. If capacity is provided, the new coefficient slice capacity will be set accordingly.

func (Polynomial) Coefficients

func (p Polynomial) Coefficients() []fr.Element

Coefficients returns a slice on the underlying data structure.

func (*Polynomial) Evaluate

func (p *Polynomial) Evaluate(x fr.Element) fr.Element

Evaluate evaluates p at x. The code panics if the function is not in canonical form.

func (*Polynomial) GetCoeff

func (p *Polynomial) GetCoeff(i int) fr.Element

GetCoeff returns the i-th entry of p, taking the layout in account.

func (*Polynomial) ReadFrom

func (p *Polynomial) ReadFrom(r io.Reader) (int64, error)

ReadFrom implements io.ReaderFrom

func (*Polynomial) SetBlindedSize

func (p *Polynomial) SetBlindedSize(size int)

SetBlindedSize sets the blinded size of the polynomial.

func (*Polynomial) SetSize

func (p *Polynomial) SetSize(size int)

SetSize sets the size of the polynomial. size is the real size of the polynomial (seen as a vector). For instance if len(P)=32 but P.size=8, it means that P has been extended (e.g. it is evaluated on a larger set) but P is a polynomial of degree 7.

func (*Polynomial) ShallowClone

func (p *Polynomial) ShallowClone() *Polynomial

ShallowClone returns a shallow copy of p. The underlying polynomial coefficient is NOT cloned and both objects will point to the same coefficient vector.

func (*Polynomial) Shift

func (p *Polynomial) Shift(shift int) *Polynomial

Shift the wrapped polynomial; it doesn't modify the underlying data structure, but flag the Polynomial such that it will be interpreted as p(\omega^shift X)

func (*Polynomial) Size

func (p *Polynomial) Size() int

Size returns the real size of the polynomial (seen as a vector). For instance if len(P)=32 but P.Size=8, it means that P has been extended (e.g. it is evaluated on a larger set) but P is a polynomial of degree 7.

func (*Polynomial) ToBitReverse

func (p *Polynomial) ToBitReverse() *Polynomial

ToBitReverse changes the layout of p to BitReverse. Leaves p unchanged if p's layout was already BitReverse.

func (*Polynomial) ToCanonical

func (p *Polynomial) ToCanonical(d *fft.Domain, nbTasks ...int) *Polynomial

ToCanonical converts p to canonical form. Leaves p unchanged if p was already in Canonical form.

func (*Polynomial) ToLagrange

func (p *Polynomial) ToLagrange(d *fft.Domain, nbTasks ...int) *Polynomial

ToLagrange converts p to Lagrange form. Leaves p unchanged if p was already in Lagrange form.

func (*Polynomial) ToLagrangeCoset

func (p *Polynomial) ToLagrangeCoset(d *fft.Domain) *Polynomial

ToLagrangeCoset Sets p to q, in LagrangeCoset form and returns it.

func (*Polynomial) ToRegular

func (p *Polynomial) ToRegular() *Polynomial

ToRegular changes the layout of p to Regular. Leaves p unchanged if p's layout was already Regular.

func (*Polynomial) WriteTo

func (p *Polynomial) WriteTo(w io.Writer) (int64, error)

WriteTo implements io.WriterTo