polynomial

Documentation

Overview

Package polynomial provides polynomial methods and commitment schemes.

Index

• func ClearPool() int
• func CountPool() int
• func Dump(arrs ...[]fr.Element) int
• func EvalEq(q, h []fr.Element) fr.Element
• func Make(n int) []fr.Element
• type MultiLin
  • func (m *MultiLin) Add(left, right MultiLin)
  • func (m MultiLin) Clone() MultiLin
  • func (m *MultiLin) Eq(q []fr.Element)
  • func (m MultiLin) Evaluate(coordinates []fr.Element) fr.Element
  • func (m *MultiLin) Fold(r fr.Element)
• type Polynomial
  • func InterpolateOnRange(values []fr.Element) Polynomial
  • func (p *Polynomial) Add(p1, p2 Polynomial) *Polynomial
  • func (p *Polynomial) AddConstantInPlace(c *fr.Element)
  • func (p *Polynomial) Clone() Polynomial
  • func (p *Polynomial) Degree() uint64
  • func (p *Polynomial) Equal(p1 Polynomial) bool
  • func (p *Polynomial) Eval(v *fr.Element) fr.Element
  • func (p *Polynomial) Scale(c *fr.Element, p0 Polynomial)
  • func (p *Polynomial) ScaleInPlace(c *fr.Element)
  • func (p *Polynomial) Set(p1 Polynomial)
  • func (p *Polynomial) SubConstantInPlace(c *fr.Element)
  • func (p Polynomial) Text(base int) string

Functions

func ClearPool

func ClearPool() int

ClearPool Clears the pool completely, shields against memory leaks Eg: if we forgot to dump a polynomial at some point, this will ensure the value get dumped eventually Returns how many polynomials were cleared that way

func CountPool

func CountPool() int

CountPool Returns the number of elements in the pool without mutating it

func Dump

func Dump(arrs ...[]fr.Element) int

Dump dumps a set of polynomials into the pool Returns the number of deallocated polys

func EvalEq

func EvalEq(q, h []fr.Element) fr.Element

EvalEq computes Eq(q₁, ... , qₙ, h₁, ... , hₙ) = Π₁ⁿ Eq(qᵢ, hᵢ) where Eq(x,y) = xy + (1-x)(1-y) = 1 - x - y + xy + xy interpolates

    _________________
    |       |       |
    |   0   |   1   |
    |_______|_______|
y   |       |       |
    |   1   |   0   |
    |_______|_______|

            x

In other words the polynomial evaluated here is the multilinear extrapolation of one that evaluates to q' == h' for vectors q', h' of binary values

func Make

func Make(n int) []fr.Element

Make tries to find a reusable polynomial or allocates a new one

Types

type MultiLin

type MultiLin []fr.Element

MultiLin tracks the values of a (dense i.e. not sparse) multilinear polynomial The variables are X₁ through Xₙ where n = log(len(.)) .[∑ᵢ 2ⁱ⁻¹ bₙ₋ᵢ] = the polynomial evaluated at (b₁, b₂, ..., bₙ) It is understood that any hypercube evaluation can be extrapolated to a multilinear polynomial

func (*MultiLin) Add

func (m *MultiLin) Add(left, right MultiLin)

Add two bookKeepingTables

func (MultiLin) Clone

func (m MultiLin) Clone() MultiLin

Clone creates a deep copy of a book-keeping table. Both multilinear interpolation and sumcheck require folding an underlying array, but folding changes the array. To do both one requires a deep copy of the book-keeping table.

func (*MultiLin) Eq

func (m *MultiLin) Eq(q []fr.Element)

Eq sets m to the representation of the polynomial Eq(q₁, ..., qₙ, *, ..., *) × m[0]

func (MultiLin) Evaluate

func (m MultiLin) Evaluate(coordinates []fr.Element) fr.Element

Evaluate extrapolate the value of the multilinear polynomial corresponding to m on the given coordinates

func (*MultiLin) Fold

func (m *MultiLin) Fold(r fr.Element)

Fold is partial evaluation function k[X₁, X₂, ..., Xₙ] → k[X₂, ..., Xₙ] by setting X₁=r

type Polynomial

type Polynomial []fr.Element

Polynomial represented by coefficients bn254 fr field.

func InterpolateOnRange

func InterpolateOnRange(values []fr.Element) Polynomial

InterpolateOnRange performs the interpolation of the given list of elements On the range [0, 1,..., len(values) - 1] TODO: Am I crazy or is this EXTRApolation and not INTERpolation

func (*Polynomial) Add

func (p *Polynomial) Add(p1, p2 Polynomial) *Polynomial

Add adds p1 to p2 This function allocates a new slice unless p == p1 or p == p2

func (*Polynomial) AddConstantInPlace

func (p *Polynomial) AddConstantInPlace(c *fr.Element)

AddConstantInPlace adds a constant to the polynomial, modifying p

func (*Polynomial) Clone

func (p *Polynomial) Clone() Polynomial

Clone returns a copy of the polynomial

func (*Polynomial) Degree

func (p *Polynomial) Degree() uint64

Degree returns the degree of the polynomial, which is the length of Data.

func (*Polynomial) Equal

func (p *Polynomial) Equal(p1 Polynomial) bool

Equal checks equality between two polynomials

func (*Polynomial) Eval

func (p *Polynomial) Eval(v *fr.Element) fr.Element

Eval evaluates p at v returns a fr.Element

func (*Polynomial) Scale

func (p *Polynomial) Scale(c *fr.Element, p0 Polynomial)

Scale multiplies p0 by v, storing the result in p

func (*Polynomial) ScaleInPlace

func (p *Polynomial) ScaleInPlace(c *fr.Element)

ScaleInPlace multiplies p by v, modifying p

func (*Polynomial) Set

func (p *Polynomial) Set(p1 Polynomial)

Set to another polynomial

func (*Polynomial) SubConstantInPlace

func (p *Polynomial) SubConstantInPlace(c *fr.Element)

SubConstantInPlace subs a constant to the polynomial, modifying p

func (Polynomial) Text

func (p Polynomial) Text(base int) string