domain

Documentation

Index

• Variables
• func BitReverse[K interface{}](list []K)
• func BitReverseInt(k, bitsize uint64) uint64
• type CosetDomain
  • func NewCosetDomain(domain *Domain, fft_coset FFTCoset) *CosetDomain
  • func (d *CosetDomain) CosetFFtFr(values []fr.Element) []fr.Element
  • func (d *CosetDomain) CosetIFFtFr(values []fr.Element) []fr.Element
• type Domain
  • func NewDomain(x uint64) *Domain
  • func (domain *Domain) EvaluateLagrangePolynomial(poly []fr.Element, evalPoint fr.Element) (*fr.Element, error)
  • func (domain *Domain) EvaluateLagrangePolynomialWithIndex(poly []fr.Element, evalPoint fr.Element) (*fr.Element, int64, error)
  • func (d *Domain) FftFr(values []fr.Element) []fr.Element
  • func (domain *Domain) FftG1(values []bls12381.G1Affine) []bls12381.G1Affine
  • func (domain *Domain) FindRootIndex(point fr.Element) int64
  • func (d *Domain) IfftFr(values []fr.Element) []fr.Element
  • func (domain *Domain) IfftG1(values []bls12381.G1Affine) []bls12381.G1Affine
  • func (domain *Domain) ReverseRoots()
• type FFTCoset

Variables

var ErrPolynomialMismatchedSizeDomain = errors.New("domain size does not equal the number of evaluations in the polynomial")

Functions

func BitReverse

func BitReverse[K interface{}](list []K)

BitReverse applies the bit-reversal permutation to `list`. `len(list)` must be a power of 2

This means that for post-state list output and pre-state list input, we have output[i] == input[bitreverse(i)], where bitreverse reverses the bit-pattern of i, interpreted as a log2(len(list))-bit integer.

This is in no way needed for basic KZG and is included in this library as a stepping-stone to full Dank-sharding.

Modified from gnark-crypto.

func BitReverseInt

func BitReverseInt(k, bitsize uint64) uint64

Types

type CosetDomain

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

CosetDomain represents a domain for performing FFT operations over a coset. It combines a standard FFT domain with coset information for efficient coset FFT computations.

func NewCosetDomain

func NewCosetDomain(domain *Domain, fft_coset FFTCoset) *CosetDomain

NewCosetDomain creates a new CosetDomain with the given Domain and FFTCoset.

func (*CosetDomain) CosetFFtFr

func (d *CosetDomain) CosetFFtFr(values []fr.Element) []fr.Element

CosetFFtFr performs a forward coset FFT on the input values.

It first scales the input values by powers of the coset generator, then performs a standard FFT on the scaled values.

func (*CosetDomain) CosetIFFtFr

func (d *CosetDomain) CosetIFFtFr(values []fr.Element) []fr.Element

CosetIFFtFr performs an inverse coset FFT on the input values.

It first performs a standard inverse FFT, then scales the results by powers of the inverse coset generator to shift back to the original domain.

type Domain

type Domain struct {
	// Size of the domain as a uint64. This must be a power of 2.
	// Since the base field has 2^i'th roots of unity for i<=32, Cardinality is <= 2^32)
	Cardinality uint64
	// Inverse of the size of the domain as
	// a field element. This is useful for
	// inverse FFTs.
	CardinalityInv fr.Element
	// Generator for the multiplicative subgroup
	// Not a primitive element (i.e. generator) for the *whole* field.
	//
	// This generator will have order equal to the
	// cardinality of the domain.
	Generator fr.Element
	// Inverse of the Generator. This is precomputed
	// and useful for inverse FFTs.
	GeneratorInv fr.Element

	// Roots of unity for the multiplicative subgroup
	// Note that these may or may not be in bit-reversed order.
	Roots []fr.Element

	// Precomputed inverses of the domain which
	// we will use to speed up the computation of
	// f(x)/g(x) where g(x) is a linear polynomial
	// which vanishes on a point on the domain
	PreComputedInverses []fr.Element
}

Domain is a struct defining the set of points that polynomials are evaluated over. To enable efficient FFT-based algorithms, these points are chosen as 2^i'th roots of unity and we precompute and store certain values related to that inside the struct.

func NewDomain

func NewDomain(x uint64) *Domain

NewDomain returns a new domain with the desired number of points x.

We only support powers of 2 for x.

Modified from gnark-crypto.

func (*Domain) EvaluateLagrangePolynomial

func (domain *Domain) EvaluateLagrangePolynomial(poly []fr.Element, evalPoint fr.Element) (*fr.Element, error)

EvaluateLagrangePolynomial evaluates a Lagrange polynomial at the given point of evaluation.

The input polynomial is given in evaluation form, meaning a list of evaluations at the points in the domain. If len(poly) != domain.Cardinality, returns an error.

func (*Domain) EvaluateLagrangePolynomialWithIndex

func (domain *Domain) EvaluateLagrangePolynomialWithIndex(poly []fr.Element, evalPoint fr.Element) (*fr.Element, int64, error)

EvaluateLagrangePolynomialWithIndex is the implementation for [EvaluateLagrangePolynomial].

It evaluates a Lagrange polynomial at the given point of evaluation and reports whether the given point was among the points of the domain:

• The input polynomial is given in evaluation form, that is, a list of evaluations at the points in the domain.
• The evaluationResult is the result of evaluation at evalPoint.
• indexInDomain is the index inside domain.Roots, if evalPoint is among them, -1 otherwise

This semantics was copied from the go library, see: https://cs.opensource.google/go/x/exp/+/522b1b58:slices/slices.go;l=117

func (*Domain) FftFr

func (d *Domain) FftFr(values []fr.Element) []fr.Element

func (*Domain) FftG1

func (domain *Domain) FftG1(values []bls12381.G1Affine) []bls12381.G1Affine

Computes an FFT (Fast Fourier Transform) of the G1 elements.

The elements are returned in order as opposed to being returned in bit-reversed order.

func (*Domain) FindRootIndex

func (domain *Domain) FindRootIndex(point fr.Element) int64

FindRootIndex returns the index of the element in the domain or -1 if not found.

• If point is in the domain (meaning that point is a domain.Cardinality'th root of unity), returns the index of the point in the domain.
• If point is not in the domain, returns -1.

func (*Domain) IfftFr

func (d *Domain) IfftFr(values []fr.Element) []fr.Element

func (*Domain) IfftG1

func (domain *Domain) IfftG1(values []bls12381.G1Affine) []bls12381.G1Affine

Computes an IFFT(Inverse Fast Fourier Transform) of the G1 elements.

The elements are returned in order as opposed to being returned in bit-reversed order.

func (*Domain) ReverseRoots

func (domain *Domain) ReverseRoots()

ReverseRoots applies the bit-reversal permutation to the list of precomputed roots of unity and their inverses in the domain.

type FFTCoset

type FFTCoset struct {
	// CosetGen is the generator element of the coset.
	// It's used to shift the domain for coset FFT operations.
	CosetGen fr.Element

	// InvCosetGen is the inverse of the coset generator.
	// It's used in inverse coset FFT operations to shift back to the original domain.
	InvCosetGen fr.Element
}

FFTCoset represents a coset for Fast Fourier Transform operations. It contains the generator of the coset and its inverse.