backend

Documentation

Index

• func BitReverse(a []fr.Element)
• func FFT(a []fr.Element, domain *Domain, fType FFTType, inverse bool)
• type Domain
  • func NewDomain(m int) *Domain
• type FFTType
• type R1CS
  • func (r1cs *R1CS) AddTerm(res *fr.Element, t r1c.Term, value fr.Element) *fr.Element
  • func (r1cs *R1CS) GetCurveID() gurvy.ID
  • func (r1cs *R1CS) GetNbCoefficients() int
  • func (r1cs *R1CS) GetNbConstraints() int
  • func (r1cs *R1CS) GetNbWires() int
  • func (r1cs *R1CS) IsSolved(assignment map[string]interface{}) error
  • func (r1cs *R1CS) Solve(assignment map[string]interface{}, a, b, c, wireValues []fr.Element) error

Functions

func BitReverse

func BitReverse(a []fr.Element)

BitReverse applies the bit-reversal permutation to a. len(a) must be a power of 2 (as in every single function in this file)

func FFT

func FFT(a []fr.Element, domain *Domain, fType FFTType, inverse bool)

FFT computes (recursively) the discrete Fourier transform of a and stores the result in a. if fType == DIT (decimation in time), the input must be in bit-reversed order if fType == DIF (decimation in frequency), the output will be in bit-reversed order len(a) must be a power of 2, and w must be a len(a)th root of unity in field F.

Types

type Domain

type Domain struct {
	Generator        fr.Element
	GeneratorInv     fr.Element
	GeneratorSqRt    fr.Element // generator of 2 adic subgroup of order 2*nb_constraints
	GeneratorSqRtInv fr.Element
	Cardinality      int
	CardinalityInv   fr.Element

	// Twiddles factor for the FFT using Generator for each stage of the recursive FFT
	Twiddles [][]fr.Element

	// Twiddles factor for the FFT using GeneratorInv for each stage of the recursive FFT
	TwiddlesInv [][]fr.Element

	// ExpTable1 = scale by inverse of n + coset
	// ifft(a) would normaly do FFT(a, wInv) then scale by CardinalityInv
	// fft_coset(a) would normaly mutliply a with expTable of fftDomain.GeneratorSqRt
	// this pre-computed ExpTable1 do both in one pass --> it contains
	// ExpTable1[0] = fftDomain.CardinalityInv
	// ExpTable1[1] = fftDomain.GeneratorSqrt^1 * fftDomain.CardinalityInv
	// ExpTable1[2] = fftDomain.GeneratorSqrt^2 * fftDomain.CardinalityInv
	// ...
	// note that the ExpTable1 is in bitReversed order
	ExpTable1 []fr.Element

	// similar reasoning as in ExpTable1 pass -->
	// ExpTable2[0] = fftDomain.CardinalityInv
	// ExpTable2[1] = fftDomain.GeneratorSqRtInv^1 * fftDomain.CardinalityInv
	// ExpTable2[2] = fftDomain.GeneratorSqRtInv^2 * fftDomain.CardinalityInv
	// note that the ExpTable2 is in bitReversed order
	ExpTable2 []fr.Element
}

Domain with a power of 2 cardinality compute a field element of order 2x and store it in GeneratorSqRt all other values can be derived from x, GeneratorSqrt

func NewDomain

func NewDomain(m int) *Domain

NewDomain returns a subgroup with a power of 2 cardinality cardinality >= m compute a field element of order 2x and store it in GeneratorSqRt all other values can be derived from x, GeneratorSqrt

type FFTType

type FFTType uint8

FFTType is used in the FFT call to select decimation in time or in frequency

const (
	DIT FFTType = iota
	DIF
)

See FFTType and FFT documentation

type R1CS

type R1CS struct {
	// Wires
	NbWires       int
	NbPublicWires int // includes ONE wire
	NbSecretWires int
	SecretWires   []string // private wire names, correctly ordered (the i-th entry is the name of the (offset+)i-th wire)
	PublicWires   []string // public wire names, correctly ordered (the i-th entry is the name of the (offset+)i-th wire)
	Logs          []backend.LogEntry
	DebugInfo     []backend.LogEntry

	// Constraints
	NbConstraints   int // total number of constraints
	NbCOConstraints int // number of constraints that need to be solved, the first of the Constraints slice
	Constraints     []r1c.R1C
	Coefficients    []fr.Element // R1C coefficients indexes point here
}

R1CS decsribes a set of R1CS constraint

func (*R1CS) AddTerm

func (r1cs *R1CS) AddTerm(res *fr.Element, t r1c.Term, value fr.Element) *fr.Element

AddTerm returns res += (value * term.Coefficient)

func (*R1CS) GetCurveID

func (r1cs *R1CS) GetCurveID() gurvy.ID

GetCurveID returns the curveID of this R1CS

func (*R1CS) GetNbCoefficients

func (r1cs *R1CS) GetNbCoefficients() int

GetNbCoefficients return the number of unique coefficients needed in the R1CS

func (*R1CS) GetNbConstraints

func (r1cs *R1CS) GetNbConstraints() int

GetNbConstraints returns the number of constraints

func (*R1CS) GetNbWires

func (r1cs *R1CS) GetNbWires() int

GetNbWires returns the number of wires

func (*R1CS) IsSolved

func (r1cs *R1CS) IsSolved(assignment map[string]interface{}) error

IsSolved returns nil if given assignment solves the R1CS and error otherwise this method wraps r1cs.Solve() and allocates r1cs.Solve() inputs

func (*R1CS) Solve

func (r1cs *R1CS) Solve(assignment map[string]interface{}, a, b, c, wireValues []fr.Element) error

Solve sets all the wires and returns the a, b, c vectors. the r1cs system should have been compiled before. The entries in a, b, c are in Montgomery form. assignment: map[string]value: contains the input variables a, b, c vectors: ab-c = hz wireValues = [intermediateVariables | privateInputs | publicInputs]