polynomial

Documentation

Overview

Package polynomial provides polynomial methods and commitment schemes.

Index

• func EvalEq(q, h []fr.Element) 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, p *Pool) fr.Element
  • func (m *MultiLin) Fold(r fr.Element)
  • func (m *MultiLin) FoldParallel(r fr.Element) utils.Task
  • func (m MultiLin) NumVars() int
  • func (m MultiLin) Sum() 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) SetZero()
  • func (p *Polynomial) Sub(p1, p2 Polynomial) *Polynomial
  • func (p *Polynomial) SubConstantInPlace(c *fr.Element)
  • func (p Polynomial) Text(base int) string
• type Pool
  • func NewPool(maxN ...int) (pool Pool)
  • func (p *Pool) Clone(slice []fr.Element) []fr.Element
  • func (p *Pool) Dump(slices ...[]fr.Element)
  • func (p *Pool) Make(n int) []fr.Element
  • func (p *Pool) PrintPoolStats()

Functions

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

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 bookkeeping 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 bookkeeping 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, p *Pool) 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

func (*MultiLin) FoldParallel

func (m *MultiLin) FoldParallel(r fr.Element) utils.Task

func (MultiLin) NumVars

func (m MultiLin) NumVars() int

func (MultiLin) Sum

func (m MultiLin) Sum() fr.Element

type Polynomial

type Polynomial []fr.Element

Polynomial represented by coefficients in the 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]

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) SetZero

func (p Polynomial) SetZero()

func (*Polynomial) Sub

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

Sub subtracts p2 from p1 TODO make interface more consistent with Add

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

type Pool

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

func NewPool

func NewPool(maxN ...int) (pool Pool)

func (*Pool) Clone

func (p *Pool) Clone(slice []fr.Element) []fr.Element

func (*Pool) Dump

func (p *Pool) Dump(slices ...[]fr.Element)

Dump dumps a set of polynomials into the pool

func (*Pool) Make

func (p *Pool) Make(n int) []fr.Element

func (*Pool) PrintPoolStats

func (p *Pool) PrintPoolStats()