goldilocks

package
v0.0.3 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jan 14, 2025 License: MIT Imports: 13 Imported by: 0

Documentation

Overview

This package implements efficient Golidlocks arithmetic operations within Gnark. We do not use the emulated field arithmetic API, because it is too slow for our purposes. Instead, we use an efficient reduction method that leverages the fact that the modulus is a simple linear combination of powers of two.

Index

Constants

View Source 
const D = 2
View Source 
const DTH_ROOT uint64 = 18446744069414584320
View Source 
const W uint64 = 7

Variables

View Source 
var EXPECTED_OPTIMAL_BASEWIDTH int = 16

The bit width size that the gnark commit based range checker should use.

View Source 
var MODULUS *big.Int = emulated.Goldilocks{}.Modulus()

The modulus of the field.

View Source 
var MODULUS_UINT64 uint64 = 18446744069414584321
View Source 
var MULTIPLICATIVE_GROUP_GENERATOR goldilocks.Element = goldilocks.NewElement(14293326489335486720)

The multiplicative group generator of the field.

View Source 
var POWER_OF_TWO_GENERATOR goldilocks.Element = goldilocks.NewElement(7277203076849721926)

The power of two generator of the field.

View Source 
var RANGE_CHECK_NB_BITS int = 144

The number of bits to use for range checks on inner products of field elements. This MUST be a multiple of EXPECTED_OPTIMAL_BASEWIDTH if the commit based range checker is used. There is a bug in the pre 0.9.2 gnark range checker where it wouldn't appropriately range check a bitwidth that is misaligned from EXPECTED_OPTIMAL_BASEWIDTH: https://github.com/Consensys/gnark/security/advisories/GHSA-rjjm-x32p-m3f7

View Source 
var TWO_ADICITY uint64 = 32

The two adicity of the field.

Functions

func InverseHint 

func InverseHint(_ *big.Int, inputs []*big.Int, results []*big.Int) error

The hint used to compute Inverse.

func MulAddHint 

func MulAddHint(_ *big.Int, inputs []*big.Int, results []*big.Int) error

The hint used to compute MulAdd.

func PrimitiveRootOfUnity 

func PrimitiveRootOfUnity(nLog uint64) goldilocks.Element

Computes the n'th primitive root of unity for the Goldilocks field.

func ReduceHint 

func ReduceHint(_ *big.Int, inputs []*big.Int, results []*big.Int) error

The hint used to compute Reduce.

func SplitLimbsHint 

func SplitLimbsHint(_ *big.Int, inputs []*big.Int, results []*big.Int) error

The hint used to split a GoldilocksVariable into 2 32 bit limbs.

func StrArrayToBigIntArray 

func StrArrayToBigIntArray(input []string) []big.Int

func StrArrayToFrontendVariableArray 

func StrArrayToFrontendVariableArray(input []string) []frontend.Variable

func TwoAdicSubgroup 

func TwoAdicSubgroup(nLog uint64) []goldilocks.Element

Types

type Chip 

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

The chip used for Goldilocks field operations.

func New 

func New(api frontend.API) *Chip

Creates a new Goldilocks Chip.

func (*Chip) Add 

func (p *Chip) Add(a Variable, b Variable) Variable

Adds two goldilocks field elements and returns a value within the goldilocks field.

func (*Chip) AddExtension 

func (p *Chip) AddExtension(a, b QuadraticExtensionVariable) QuadraticExtensionVariable

Adds two quadratic extension variables in the Goldilocks field.

func (*Chip) AddExtensionAlgebra 

func (p *Chip) AddExtensionAlgebra(
	a QuadraticExtensionAlgebraVariable,
	b QuadraticExtensionAlgebraVariable,
) QuadraticExtensionAlgebraVariable

func (*Chip) AddExtensionNoReduce 

func (p *Chip) AddExtensionNoReduce(a, b QuadraticExtensionVariable) QuadraticExtensionVariable

Adds two quadratic extension variables in the Goldilocks field without reducing.

func (*Chip) AddNoReduce 

func (p *Chip) AddNoReduce(a Variable, b Variable) Variable

Adds two goldilocks field elements and returns a value that may not be within the goldilocks field (e.g. the sum is not reduced).

func (*Chip) AssertIsEqual 

func (p *Chip) AssertIsEqual(x, y Variable)

func (*Chip) AssertIsEqualExtension 

func (p *Chip) AssertIsEqualExtension(
	a QuadraticExtensionVariable,
	b QuadraticExtensionVariable,
)

Asserts that two quadratic extension variables are equal.

func (*Chip) DivExtension 

func (p *Chip) DivExtension(a, b QuadraticExtensionVariable) (QuadraticExtensionVariable, frontend.Variable)

Divides two quadratic extension variables in the Goldilocks field.

func (*Chip) ExpExtension 

func (p *Chip) ExpExtension(
	a QuadraticExtensionVariable,
	exponent uint64,
) QuadraticExtensionVariable

Exponentiates a quadratic extension variable to some exponent in the Golidlocks field.

func (*Chip) InnerProductExtension 

func (p *Chip) InnerProductExtension(
	constant Variable,
	startingAcc QuadraticExtensionVariable,
	pairs [][2]QuadraticExtensionVariable,
) QuadraticExtensionVariable

Computes an inner product over quadratic extension variable vectors in the Goldilocks field.

func (*Chip) Inverse 

func (p *Chip) Inverse(x Variable) (Variable, frontend.Variable)

Computes the inverse of a field element x such that x * x^-1 = 1.

func (*Chip) InverseExtension 

func (p *Chip) InverseExtension(a QuadraticExtensionVariable) (QuadraticExtensionVariable, frontend.Variable)

Computes the inverse of a quadratic extension variable in the Goldilocks field.

func (*Chip) IsZero 

func (p *Chip) IsZero(x QuadraticExtensionVariable) frontend.Variable

Outputs whether the quadratic extension variable is zero.

func (*Chip) Lookup 

func (p *Chip) Lookup(
	b frontend.Variable,
	x, y QuadraticExtensionVariable,
) QuadraticExtensionVariable

Lookup is similar to select, but returns the first variable if the bit is zero and vice-versa.

func (*Chip) Lookup2 

func (p *Chip) Lookup2(
	b0 frontend.Variable,
	b1 frontend.Variable,
	qe0, qe1, qe2, qe3 QuadraticExtensionVariable,
) QuadraticExtensionVariable

Lookup2 is similar to Lookup2. It returns the ith qe value (0 indexed) where i is bit decomposed to b0,b1 (little endian).

func (*Chip) Mul 

func (p *Chip) Mul(a Variable, b Variable) Variable

Multiplies two goldilocks field elements and returns a value within the goldilocks field.

func (*Chip) MulAdd 

func (p *Chip) MulAdd(a Variable, b Variable, c Variable) Variable

Multiplies two field elements and adds a field element (e.g. computes a * b + c). The returned value will be within the goldilocks field.

func (*Chip) MulAddExtension 

func (p *Chip) MulAddExtension(a, b, c QuadraticExtensionVariable) QuadraticExtensionVariable

Multiplies two operands a and b and adds to c in the Goldilocks extension field. a * b + c must be less than RANGE_CHECK_NB_BITS bits.

func (*Chip) MulAddExtensionNoReduce 

func (p *Chip) MulAddExtensionNoReduce(a, b, c QuadraticExtensionVariable) QuadraticExtensionVariable

func (*Chip) MulAddNoReduce 

func (p *Chip) MulAddNoReduce(a Variable, b Variable, c Variable) Variable

Multiplies two field elements and adds a field element (e.g. computes a * b + c). The returned value may no be within the goldilocks field (e.g. the result is not reduced).

func (*Chip) MulExtension 

func (p *Chip) MulExtension(a, b QuadraticExtensionVariable) QuadraticExtensionVariable

Multiplies quadratic extension variable in the Goldilocks field.

func (*Chip) MulExtensionAlgebra 

func (p *Chip) MulExtensionAlgebra(
	a QuadraticExtensionAlgebraVariable,
	b QuadraticExtensionAlgebraVariable,
) QuadraticExtensionAlgebraVariable

func (*Chip) MulExtensionNoReduce 

func (p *Chip) MulExtensionNoReduce(a, b QuadraticExtensionVariable) QuadraticExtensionVariable

Multiplies quadratic extension variable in the Goldilocks field without reducing.

func (*Chip) MulNoReduce 

func (p *Chip) MulNoReduce(a Variable, b Variable) Variable

Multiplies two goldilocks field elements and returns a value that may not be within the goldilocks field (e.g. the product is not reduced).

func (*Chip) PartialInterpolateExtAlgebra 

func (p *Chip) PartialInterpolateExtAlgebra(
	domain []goldilocks.Element,
	values []QuadraticExtensionAlgebraVariable,
	barycentricWeights []goldilocks.Element,
	point QuadraticExtensionAlgebraVariable,
	initialEval QuadraticExtensionAlgebraVariable,
	initialPartialProd QuadraticExtensionAlgebraVariable,
) (QuadraticExtensionAlgebraVariable, QuadraticExtensionAlgebraVariable)

func (*Chip) RangeCheck 

func (p *Chip) RangeCheck(x Variable)

Range checks a field element x to be less than the Golidlocks modulus 2 ^ 64 - 2 ^ 32 + 1.

func (*Chip) RangeCheckQE 

func (p *Chip) RangeCheckQE(a QuadraticExtensionVariable)

func (*Chip) RangeCheckWithMaxBits 

func (p *Chip) RangeCheckWithMaxBits(x Variable, maxNbBits uint64)

This function will assert that the field element x is less than 2^maxNbBits.

func (*Chip) Reduce 

func (p *Chip) Reduce(x Variable) Variable

Reduces a field element x such that x % MODULUS = y.

func (*Chip) ReduceExtension 

func (p *Chip) ReduceExtension(x QuadraticExtensionVariable) QuadraticExtensionVariable

func (*Chip) ReduceWithMaxBits 

func (p *Chip) ReduceWithMaxBits(x Variable, maxNbBits uint64) Variable

Reduces a field element x such that x % MODULUS = y.

func (*Chip) ReduceWithPowers 

func (p *Chip) ReduceWithPowers(
	terms []QuadraticExtensionVariable,
	scalar QuadraticExtensionVariable,
) QuadraticExtensionVariable

Reduces a list of extension field terms with a scalar power in the Goldilocks field.

func (*Chip) ScalarMulExtension 

func (p *Chip) ScalarMulExtension(
	a QuadraticExtensionVariable,
	b Variable,
) QuadraticExtensionVariable

Multiplies quadratic extension variable in the Goldilocks field by a scalar.

func (*Chip) ScalarMulExtensionAlgebra 

func (p *Chip) ScalarMulExtensionAlgebra(
	a QuadraticExtensionVariable,
	b QuadraticExtensionAlgebraVariable,
) QuadraticExtensionAlgebraVariable

func (*Chip) Sub 

func (p *Chip) Sub(a Variable, b Variable) Variable

Subracts two goldilocks field elements and returns a value within the goldilocks field.

func (*Chip) SubExtension 

func (p *Chip) SubExtension(a, b QuadraticExtensionVariable) QuadraticExtensionVariable

Subtracts two quadratic extension variables in the Goldilocks field.

func (*Chip) SubExtensionAlgebra 

func (p *Chip) SubExtensionAlgebra(
	a QuadraticExtensionAlgebraVariable,
	b QuadraticExtensionAlgebraVariable,
) QuadraticExtensionAlgebraVariable

func (*Chip) SubExtensionNoReduce 

func (p *Chip) SubExtensionNoReduce(a, b QuadraticExtensionVariable) QuadraticExtensionVariable

Subtracts two quadratic extension variables in the Goldilocks field without reducing.

func (*Chip) SubMulExtension 

func (p *Chip) SubMulExtension(a, b, c QuadraticExtensionVariable) QuadraticExtensionVariable

Subtracts two operands a and b and multiplies the diff by c in the Goldilocks extension field. (a - b) * c must be less than RANGE_CHECK_NB_BITS bits.

func (*Chip) SubNoReduce 

func (p *Chip) SubNoReduce(a Variable, b Variable) Variable

Subracts two goldilocks field elements and returns a value that may not be within the goldilocks field (e.g. the difference is not reduced).

type FrontendTyper 

type FrontendTyper interface {
	FrontendType() Type
}

type QuadraticExtensionAlgebraVariable 

type QuadraticExtensionAlgebraVariable = [D]QuadraticExtensionVariable

func NewQuadraticExtensionAlgebraVariable 

func NewQuadraticExtensionAlgebraVariable(
	a QuadraticExtensionVariable,
	b QuadraticExtensionVariable,
) QuadraticExtensionAlgebraVariable

func OneExtensionAlgebra 

func OneExtensionAlgebra() QuadraticExtensionAlgebraVariable

func ZeroExtensionAlgebra 

func ZeroExtensionAlgebra() QuadraticExtensionAlgebraVariable

type QuadraticExtensionVariable 

type QuadraticExtensionVariable [2]Variable

func NewQuadraticExtensionVariable 

func NewQuadraticExtensionVariable(x Variable, y Variable) QuadraticExtensionVariable

func OneExtension 

func OneExtension() QuadraticExtensionVariable

func Uint64ArrayToQuadraticExtension 

func Uint64ArrayToQuadraticExtension(input []uint64) QuadraticExtensionVariable

func Uint64ArrayToQuadraticExtensionArray 

func Uint64ArrayToQuadraticExtensionArray(input [][]uint64) []QuadraticExtensionVariable

func ZeroExtension 

func ZeroExtension() QuadraticExtensionVariable

func (QuadraticExtensionVariable) ToQuadraticExtensionAlgebra 

func (p QuadraticExtensionVariable) ToQuadraticExtensionAlgebra() QuadraticExtensionAlgebraVariable

type RangeCheckerType 

type RangeCheckerType int
const (
	NATIVE_RANGE_CHECKER RangeCheckerType = iota
	COMMIT_RANGE_CHECKER
	BIT_DECOMP_RANGE_CHECKER
)

type Type 

type Type int

The types, structs, and functions in this file were ported over from the gnark library https://github.com/Consensys/gnark/blob/3421eaa7d544286abf3de8c46282b8d4da6d5da0/std/rangecheck/rangecheck_commit.go 

const (
	R1CS Type = iota
	SCS
)

type Variable 

type Variable struct {
	Limb frontend.Variable
}

A type alias used to represent Goldilocks field elements.

func NegOne 

func NegOne() Variable

The negative one element in the Goldilocks field.

func NewVariable 

func NewVariable(x frontend.Variable) Variable

Creates a new Goldilocks field element from an existing variable. Assumes that the element is already reduced.

func NewVariableUint64 added in v0.0.2 

func NewVariableUint64(x uint64) Variable

Creates a new Goldilocks field element from an existing uint64. It reduces the element.

func One 

func One() Variable

The one element in the Goldilocks field.

func Uint64ArrayToVariableArray 

func Uint64ArrayToVariableArray(input []uint64) []Variable

func Zero 

func Zero() Variable

The zero element in the Golidlocks field.

func (Variable) ToQuadraticExtension 

func (p Variable) ToQuadraticExtension() QuadraticExtensionVariable

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.