constraint

package
v0.0.0-...-ae8e47d Latest Latest
Warning

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

 Go to latest Published: Mar 25, 2023 License: Apache-2.0 Imports: 17 Imported by: 0

Documentation

Overview

Package constraint provides constructs needed to build and use a constraint system.

A constraint system is a list of mathematical constraints;

  • Each constraint is composed of LinearExpression of Term
  • A Term is an association between a coefficient and a Variable

Index

Constants

View Source 
const (
	CoeffIdZero     = 0
	CoeffIdOne      = 1
	CoeffIdTwo      = 2
	CoeffIdMinusOne = 3
	CoeffIdMinusTwo = 4
)

ids of the coefficients with simple values in any cs.coeffs slice. TODO @gbotrel let's keep that here for the refactoring -- and move it to concrete cs package after

View Source 
const CommitmentDst = "bsb22-commitment"

Variables

This section is empty.

Functions

This section is empty.

Types

type Coeff 

type Coeff [6]uint64

Coeff represents a term coefficient data. It is instantiated by the concrete constraint system implementation. Most of the scalar field used in gnark are on 4 uint64, so we have a clear memory overhead here.

func (*Coeff) IsZero 

func (z *Coeff) IsZero() bool

IsZero returns true if coefficient == 0

type CoeffEngine 

type CoeffEngine interface {
	FromInterface(interface{}) Coeff
	ToBigInt(*Coeff) *big.Int
	Mul(a, b *Coeff)
	Add(a, b *Coeff)
	Sub(a, b *Coeff)
	Neg(a *Coeff)
	Inverse(a *Coeff)
	One() Coeff
	IsOne(*Coeff) bool
	String(*Coeff) string
}

CoeffEngine capability to perform arithmetic on Coeff

type Commitment 

type Commitment struct {
	Committed              []int // sorted list of id's of committed variables
	NbPrivateCommitted     int
	HintID                 hint.ID // TODO @gbotrel we probably don't need that here
	CommitmentIndex        int
	CommittedAndCommitment []int // sorted list of id's of committed variables AND the commitment itself
}

func NewCommitment 

func NewCommitment(committed []int, nbPublicCommitted int) Commitment

NewCommitment initialize a Commitment object

  • committed are the sorted wireID to commit to (without duplicate)
  • nbPublicCommited is the number of public inputs among the commited wireIDs

func (*Commitment) Is 

func (i *Commitment) Is() bool

func (*Commitment) NbCommitted 

func (i *Commitment) NbCommitted() int

func (*Commitment) NbPublicCommitted 

func (i *Commitment) NbPublicCommitted() int

func (*Commitment) PrivateCommitted 

func (i *Commitment) PrivateCommitted() []int

func (*Commitment) PrivateToPublic 

func (i *Commitment) PrivateToPublic() []int

PrivateToPublic returns indexes of variables which are private to the constraint system, but public to Groth16. That is, private committed variables and the commitment itself

func (*Commitment) SerializeCommitment 

func (i *Commitment) SerializeCommitment(privateCommitment []byte, publicCommitted []*big.Int, fieldByteLen int) []byte

type ConstraintSystem 

type ConstraintSystem interface {
	io.WriterTo
	io.ReaderFrom
	CoeffEngine

	// IsSolved returns nil if given witness solves the constraint system and error otherwise
	IsSolved(witness witness.Witness, opts ...backend.ProverOption) error

	// GetNbVariables return number of internal, secret and public Variables
	// Deprecated: use GetNbSecretVariables() instead
	GetNbVariables() (internal, secret, public int)

	GetNbInternalVariables() int
	GetNbSecretVariables() int
	GetNbPublicVariables() int

	GetNbConstraints() int
	GetNbCoefficients() int

	Field() *big.Int
	FieldBitLen() int

	AddPublicVariable(name string) int
	AddSecretVariable(name string) int
	AddInternalVariable() int

	// AddSolverHint adds a hint to the solver such that the output variables will be computed
	// using a call to output := f(input...) at solve time.
	AddSolverHint(f hint.Function, input []LinearExpression, nbOutput int) (internalVariables []int, err error)

	AddCommitment(c Commitment) error

	AddLog(l LogEntry)

	// MakeTerm returns a new Term. The constraint system may store coefficients in a map, so
	// calls to this function will grow the memory usage of the constraint system.
	MakeTerm(coeff *Coeff, variableID int) Term

	NewDebugInfo(errName string, i ...interface{}) DebugInfo

	// AttachDebugInfo enables attaching debug information to multiple constraints.
	// This is more efficient than using the AddConstraint(.., debugInfo) since it will store the
	// debug information only once.
	AttachDebugInfo(debugInfo DebugInfo, constraintID []int)

	// CheckUnconstrainedWires returns and error if the constraint system has wires that are not uniquely constrained.
	// This is experimental.
	CheckUnconstrainedWires() error
}

ConstraintSystem interface that all constraint systems implement.

type DebugInfo 

type DebugInfo LogEntry

type Hint 

type Hint struct {
	ID     hint.ID            // hint function id
	Inputs []LinearExpression // terms to inject in the hint function
	Wires  []int              // IDs of wires the hint outputs map to
}

Hint represents a solver hint it enables the solver to compute a Wire with a function provided at solving time using pre-defined inputs

type Iterable 

type Iterable interface {
	// WireIterator returns a new iterator to iterate over the wires of the implementer (usually, a constraint)
	// Call to next() returns the next wireID of the Iterable object and -1 when iteration is over.
	//
	// For example a R1C constraint with L, R, O linear expressions, each of size 2, calling several times
	// 		next := r1c.WireIterator();
	// 		for wID := next(); wID != -1; wID = next() {}
	//		// will return in order L[0],L[1],R[0],R[1],O[0],O[1],-1
	WireIterator() (next func() int)
}

type LinearExpression 

type LinearExpression []Term

A LinearExpression is a linear combination of Term

func (LinearExpression) Clone 

func (l LinearExpression) Clone() LinearExpression

Clone returns a copy of the underlying slice

func (LinearExpression) String 

func (l LinearExpression) String(r Resolver) string

type LogEntry 

type LogEntry struct {
	Caller    string
	Format    string
	ToResolve []LinearExpression // TODO @gbotrel we could store here a struct with a flag that says if we expand or evaluate the expression
	Stack     []int
}

LogEntry is used as a shared data structure between the frontend and the backend to represent string values (in logs or debug info) where a value is not known at compile time (which is the case for variables that need to be resolved in the R1CS)

func (*LogEntry) WriteVariable 

func (l *LogEntry) WriteVariable(le LinearExpression, sbb *strings.Builder)

type R1C 

type R1C struct {
	L, R, O LinearExpression
}

R1C used to compute the wires

func (*R1C) String 

func (r1c *R1C) String(r Resolver) string

String formats a R1C as L⋅R == O

func (*R1C) WireIterator 

func (r1c *R1C) WireIterator() func() int

WireIterator implements constraint.Iterable

type R1CS 

type R1CS interface {
	ConstraintSystem

	// AddConstraint adds a constraint to the system and returns its id
	// This does not check for validity of the constraint.
	// If a debugInfo parameter is provided, it will be appended to the debug info structure
	// and will grow the memory usage of the constraint system.
	AddConstraint(r1c R1C, debugInfo ...DebugInfo) int

	// GetConstraints return the list of R1C and a helper for pretty printing.
	// See StringBuilder for more info.
	// ! this is an experimental API.
	GetConstraints() ([]R1C, Resolver)
}

type R1CSCore 

type R1CSCore struct {
	System
	Constraints []R1C
}

R1CS describes a set of R1C constraint

func (*R1CSCore) CheckUnconstrainedWires 

func (r1cs *R1CSCore) CheckUnconstrainedWires() error

IsValid perform post compilation checks on the Variables

1. checks that all user inputs are referenced in at least one constraint 2. checks that all hints are constrained

func (*R1CSCore) GetNbConstraints 

func (r1cs *R1CSCore) GetNbConstraints() int

GetNbConstraints returns the number of constraints

func (*R1CSCore) UpdateLevel 

func (r1cs *R1CSCore) UpdateLevel(cID int, c Iterable)

type Resolver 

type Resolver interface {
	CoeffToString(coeffID int) string
	VariableToString(variableID int) string
}

Resolver allows pretty printing of constraints.

type SparseR1C 

type SparseR1C struct {
	L, R, O Term
	M       [2]Term
	K       int // stores only the ID of the constant term that is used
}

SparseR1C used to compute the wires L+R+M[0]M[1]+O+k=0 if a Term is zero, it means the field doesn't exist (ex M=[0,0] means there is no multiplicative term)

func (*SparseR1C) String 

func (c *SparseR1C) String(r Resolver) string

String formats the constraint as qL⋅xa + qR⋅xb + qO⋅xc + qM⋅(xaxb) + qC == 0

func (*SparseR1C) WireIterator 

func (c *SparseR1C) WireIterator() func() int

WireIterator implements constraint.Iterable

type SparseR1CS 

type SparseR1CS interface {
	ConstraintSystem

	// AddConstraint adds a constraint to the sytem and returns its id
	// This does not check for validity of the constraint.
	// If a debugInfo parameter is provided, it will be appended to the debug info structure
	// and will grow the memory usage of the constraint system.
	AddConstraint(c SparseR1C, debugInfo ...DebugInfo) int

	// GetConstraints return the list of SparseR1C and a helper for pretty printing.
	// See StringBuilder for more info.
	// ! this is an experimental API.
	GetConstraints() ([]SparseR1C, Resolver)
}

type SparseR1CSCore 

type SparseR1CSCore struct {
	System
	Constraints []SparseR1C
}

R1CS describes a set of SparseR1C constraint TODO @gbotrel maybe SparseR1CSCore and R1CSCore should go in code generation directly to avoid confusing this package.

func (*SparseR1CSCore) CheckUnconstrainedWires 

func (system *SparseR1CSCore) CheckUnconstrainedWires() error

func (*SparseR1CSCore) GetNbConstraints 

func (cs *SparseR1CSCore) GetNbConstraints() int

GetNbConstraints returns the number of constraints

func (*SparseR1CSCore) UpdateLevel 

func (cs *SparseR1CSCore) UpdateLevel(cID int, c Iterable)

type StringBuilder 

type StringBuilder struct {
	strings.Builder
	Resolver
}

StringBuilder is a helper to build string from constraints, linear expressions or terms. It embeds a strings.Builder object for convenience.

func NewStringBuilder 

func NewStringBuilder(r Resolver) *StringBuilder

NewStringBuilder returns a new StringBuilder.

func (*StringBuilder) WriteLinearExpression 

func (sbb *StringBuilder) WriteLinearExpression(l LinearExpression)

WriteLinearExpression appends the linear expression to the current buffer

func (*StringBuilder) WriteTerm 

func (sbb *StringBuilder) WriteTerm(t Term)

WriteLinearExpression appends the term to the current buffer

type System 

type System struct {
	// serialization header
	GnarkVersion string
	ScalarField  string

	// number of internal wires
	NbInternalVariables int

	// input wires names
	Public, Secret []string

	// logs (added with system.Println, resolved when solver sets a value to a wire)
	Logs []LogEntry

	// debug info contains stack trace (including line number) of a call to a system.API that
	// results in an unsolved constraint
	DebugInfo   []LogEntry
	SymbolTable debug.SymbolTable
	// maps constraint id to debugInfo id
	// several constraints may point to the same debug info
	MDebug map[int]int

	MHints             map[int]*Hint      // maps wireID to hint
	MHintsDependencies map[hint.ID]string // maps hintID to hint string identifier

	// each level contains independent constraints and can be parallelized
	// it is guaranteed that all dependencies for constraints in a level l are solved
	// in previous levels
	// TODO @gbotrel these are currently updated after we add a constraint.
	// but in case the object is built from a serialized representation
	// we need to init the level builder lbWireLevel from the existing constraints.
	Levels [][]int

	CommitmentInfo Commitment
	// contains filtered or unexported fields
}

System contains core elements for a constraint System

func NewSystem 

func NewSystem(scalarField *big.Int) System

NewSystem initialize the common structure among constraint system

func (*System) AddCommitment 

func (system *System) AddCommitment(c Commitment) error

func (*System) AddInternalVariable 

func (system *System) AddInternalVariable() (idx int)

func (*System) AddLog 

func (system *System) AddLog(l LogEntry)

func (*System) AddPublicVariable 

func (system *System) AddPublicVariable(name string) (idx int)

func (*System) AddSecretVariable 

func (system *System) AddSecretVariable(name string) (idx int)

func (*System) AddSolverHint 

func (system *System) AddSolverHint(f hint.Function, input []LinearExpression, nbOutput int) (internalVariables []int, err error)

func (*System) AttachDebugInfo 

func (system *System) AttachDebugInfo(debugInfo DebugInfo, constraintID []int)

func (*System) CheckSerializationHeader 

func (system *System) CheckSerializationHeader() error

CheckSerializationHeader parses the scalar field and gnark version headers

This is meant to be use at the deserialization step, and will error for illegal values

func (*System) Field 

func (system *System) Field() *big.Int

func (*System) FieldBitLen 

func (system *System) FieldBitLen() int

bitLen returns the number of bits needed to represent a fr.Element

func (*System) GetNbInternalVariables 

func (system *System) GetNbInternalVariables() int

func (*System) GetNbPublicVariables 

func (system *System) GetNbPublicVariables() int

func (*System) GetNbSecretVariables 

func (system *System) GetNbSecretVariables() int

func (*System) GetNbVariables 

func (system *System) GetNbVariables() (internal, secret, public int)

GetNbVariables return number of internal, secret and public variables

func (*System) NewDebugInfo 

func (system *System) NewDebugInfo(errName string, i ...interface{}) DebugInfo

func (*System) VariableToString 

func (system *System) VariableToString(vID int) string

VariableToString implements Resolver

type Term 

type Term struct {
	CID, VID uint32
}

Term represents a coeff * variable in a constraint system

func (*Term) CoeffID 

func (t *Term) CoeffID() int

func (*Term) IsConstant 

func (t *Term) IsConstant() bool

func (*Term) MarkConstant 

func (t *Term) MarkConstant()

func (Term) String 

func (t Term) String(r Resolver) string

func (*Term) WireID 

func (t *Term) WireID() int

Source Files

View all Source files

Directories

Path Synopsis

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.