constraint

package
v0.9.1 Latest Latest
Warning

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

 Go to latest Published: Oct 16, 2023 License: Apache-2.0 Imports: 22 Imported by: 84

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 = iota
	CoeffIdOne
	CoeffIdTwo
	CoeffIdMinusOne
	CoeffIdMinusTwo
)

ids of the coefficients with simple values in any cs.coeffs slice.

View Source 
const CommitmentDst = "bsb22-commitment"

Variables

This section is empty.

Functions

func SerializeCommitment added in v0.9.0 

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

Types

type Blueprint added in v0.9.0 

type Blueprint interface {
	// CalldataSize return the number of calldata input this blueprint expects.
	// If this is unknown at compile time, implementation must return -1 and store
	// the actual number of inputs in the first index of the calldata.
	CalldataSize() int

	// NbConstraints return the number of constraints this blueprint creates.
	NbConstraints() int

	// NbOutputs return the number of output wires this blueprint creates.
	NbOutputs(inst Instruction) int

	// WireWalker returns a function that walks the wires appearing in the blueprint.
	// This is used by the level builder to build a dependency graph between instructions.
	WireWalker(inst Instruction) func(cb func(wire uint32))
}

Blueprint enable representing heterogeneous constraints or instructions in a constraint system in a memory efficient way. Blueprints essentially help the frontend/ to "compress" constraints or instructions, and specify for the solving (or zksnark setup) part how to "decompress" and optionally "solve" the associated wires.

type BlueprintGenericHint added in v0.9.0 

type BlueprintGenericHint struct{}

func (*BlueprintGenericHint) CalldataSize added in v0.9.0 

func (b *BlueprintGenericHint) CalldataSize() int

func (*BlueprintGenericHint) CompressHint added in v0.9.0 

func (b *BlueprintGenericHint) CompressHint(h HintMapping, to *[]uint32)

func (*BlueprintGenericHint) DecompressHint added in v0.9.0 

func (b *BlueprintGenericHint) DecompressHint(h *HintMapping, inst Instruction)

func (*BlueprintGenericHint) NbConstraints added in v0.9.0 

func (b *BlueprintGenericHint) NbConstraints() int

func (*BlueprintGenericHint) NbOutputs added in v0.9.0 

func (b *BlueprintGenericHint) NbOutputs(inst Instruction) int

func (*BlueprintGenericHint) WireWalker added in v0.9.0 

func (b *BlueprintGenericHint) WireWalker(inst Instruction) func(cb func(wire uint32))

type BlueprintGenericR1C added in v0.9.0 

type BlueprintGenericR1C struct{}

BlueprintGenericR1C implements Blueprint and BlueprintR1C. Encodes 

L * R == 0

func (*BlueprintGenericR1C) CalldataSize added in v0.9.0 

func (b *BlueprintGenericR1C) CalldataSize() int

func (*BlueprintGenericR1C) CompressR1C added in v0.9.0 

func (b *BlueprintGenericR1C) CompressR1C(c *R1C, to *[]uint32)

func (*BlueprintGenericR1C) DecompressR1C added in v0.9.0 

func (b *BlueprintGenericR1C) DecompressR1C(c *R1C, inst Instruction)

func (*BlueprintGenericR1C) NbConstraints added in v0.9.0 

func (b *BlueprintGenericR1C) NbConstraints() int

func (*BlueprintGenericR1C) NbOutputs added in v0.9.0 

func (b *BlueprintGenericR1C) NbOutputs(inst Instruction) int

func (*BlueprintGenericR1C) WireWalker added in v0.9.0 

func (b *BlueprintGenericR1C) WireWalker(inst Instruction) func(cb func(wire uint32))

type BlueprintGenericSparseR1C added in v0.9.0 

type BlueprintGenericSparseR1C struct {
}

BlueprintGenericSparseR1C implements Blueprint and BlueprintSparseR1C. Encodes 

qL⋅xa + qR⋅xb + qO⋅xc + qM⋅(xaxb) + qC == 0

func (*BlueprintGenericSparseR1C) CalldataSize added in v0.9.0 

func (b *BlueprintGenericSparseR1C) CalldataSize() int

func (*BlueprintGenericSparseR1C) CompressSparseR1C added in v0.9.0 

func (b *BlueprintGenericSparseR1C) CompressSparseR1C(c *SparseR1C, to *[]uint32)

func (*BlueprintGenericSparseR1C) DecompressSparseR1C added in v0.9.0 

func (b *BlueprintGenericSparseR1C) DecompressSparseR1C(c *SparseR1C, inst Instruction)

func (*BlueprintGenericSparseR1C) NbConstraints added in v0.9.0 

func (b *BlueprintGenericSparseR1C) NbConstraints() int

func (*BlueprintGenericSparseR1C) NbOutputs added in v0.9.0 

func (b *BlueprintGenericSparseR1C) NbOutputs(inst Instruction) int

func (*BlueprintGenericSparseR1C) Solve added in v0.9.0 

func (b *BlueprintGenericSparseR1C) Solve(s Solver, inst Instruction) error

func (*BlueprintGenericSparseR1C) WireWalker added in v0.9.0 

func (b *BlueprintGenericSparseR1C) WireWalker(inst Instruction) func(cb func(wire uint32))

type BlueprintHint added in v0.9.0 

type BlueprintHint interface {
	Blueprint
	CompressHint(h HintMapping, to *[]uint32)
	DecompressHint(h *HintMapping, instruction Instruction)
}

BlueprintHint indicates that the blueprint and associated calldata encodes a hint.

type BlueprintID added in v0.9.0 

type BlueprintID uint32

type BlueprintLookupHint added in v0.9.0 

type BlueprintLookupHint struct {
	EntriesCalldata []uint32
}

BlueprintLookupHint is a blueprint that facilitates the lookup of values in a table. It is essentially a hint to the solver, but enables storing the table entries only once.

func (*BlueprintLookupHint) CalldataSize added in v0.9.0 

func (b *BlueprintLookupHint) CalldataSize() int

func (*BlueprintLookupHint) NbConstraints added in v0.9.0 

func (b *BlueprintLookupHint) NbConstraints() int

func (*BlueprintLookupHint) NbOutputs added in v0.9.0 

func (b *BlueprintLookupHint) NbOutputs(inst Instruction) int

NbOutputs return the number of output wires this blueprint creates.

func (*BlueprintLookupHint) Solve added in v0.9.0 

func (b *BlueprintLookupHint) Solve(s Solver, inst Instruction) error

func (*BlueprintLookupHint) WireWalker added in v0.9.0 

func (b *BlueprintLookupHint) WireWalker(inst Instruction) func(cb func(wire uint32))

Wires returns a function that walks the wires appearing in the blueprint. This is used by the level builder to build a dependency graph between instructions.

type BlueprintR1C added in v0.9.0 

type BlueprintR1C interface {
	Blueprint
	CompressR1C(c *R1C, to *[]uint32)
	DecompressR1C(into *R1C, instruction Instruction)
}

BlueprintR1C indicates that the blueprint and associated calldata encodes a R1C

type BlueprintSolvable added in v0.9.0 

type BlueprintSolvable interface {
	Blueprint
	// Solve may return an error if the decoded constraint / calldata is unsolvable.
	Solve(s Solver, instruction Instruction) error
}

BlueprintSolvable represents a blueprint that knows how to solve itself.

type BlueprintSparseR1C added in v0.9.0 

type BlueprintSparseR1C interface {
	Blueprint
	CompressSparseR1C(c *SparseR1C, to *[]uint32)
	DecompressSparseR1C(into *SparseR1C, instruction Instruction)
}

BlueprintSparseR1C indicates that the blueprint and associated calldata encodes a SparseR1C.

type BlueprintSparseR1CAdd added in v0.9.0 

type BlueprintSparseR1CAdd struct{}

BlueprintSparseR1CAdd implements Blueprint, BlueprintSolvable and BlueprintSparseR1C. Encodes 

qL⋅xa + qR⋅xb + qC == xc

func (*BlueprintSparseR1CAdd) CalldataSize added in v0.9.0 

func (b *BlueprintSparseR1CAdd) CalldataSize() int

func (*BlueprintSparseR1CAdd) CompressSparseR1C added in v0.9.0 

func (b *BlueprintSparseR1CAdd) CompressSparseR1C(c *SparseR1C, to *[]uint32)

func (*BlueprintSparseR1CAdd) DecompressSparseR1C added in v0.9.0 

func (b *BlueprintSparseR1CAdd) DecompressSparseR1C(c *SparseR1C, inst Instruction)

func (*BlueprintSparseR1CAdd) NbConstraints added in v0.9.0 

func (b *BlueprintSparseR1CAdd) NbConstraints() int

func (*BlueprintSparseR1CAdd) NbOutputs added in v0.9.0 

func (b *BlueprintSparseR1CAdd) NbOutputs(inst Instruction) int

func (*BlueprintSparseR1CAdd) Solve added in v0.9.0 

func (blueprint *BlueprintSparseR1CAdd) Solve(s Solver, inst Instruction) error

func (*BlueprintSparseR1CAdd) WireWalker added in v0.9.0 

func (b *BlueprintSparseR1CAdd) WireWalker(inst Instruction) func(cb func(wire uint32))

type BlueprintSparseR1CBool added in v0.9.0 

type BlueprintSparseR1CBool struct{}

BlueprintSparseR1CBool implements Blueprint, BlueprintSolvable and BlueprintSparseR1C. Encodes 

qL⋅xa + qM⋅(xa*xa)  == 0
that is v + -v*v == 0

func (*BlueprintSparseR1CBool) CalldataSize added in v0.9.0 

func (b *BlueprintSparseR1CBool) CalldataSize() int

func (*BlueprintSparseR1CBool) CompressSparseR1C added in v0.9.0 

func (b *BlueprintSparseR1CBool) CompressSparseR1C(c *SparseR1C, to *[]uint32)

func (*BlueprintSparseR1CBool) DecompressSparseR1C added in v0.9.0 

func (b *BlueprintSparseR1CBool) DecompressSparseR1C(c *SparseR1C, inst Instruction)

func (*BlueprintSparseR1CBool) NbConstraints added in v0.9.0 

func (b *BlueprintSparseR1CBool) NbConstraints() int

func (*BlueprintSparseR1CBool) NbOutputs added in v0.9.0 

func (b *BlueprintSparseR1CBool) NbOutputs(inst Instruction) int

func (*BlueprintSparseR1CBool) Solve added in v0.9.0 

func (blueprint *BlueprintSparseR1CBool) Solve(s Solver, inst Instruction) error

func (*BlueprintSparseR1CBool) WireWalker added in v0.9.0 

func (b *BlueprintSparseR1CBool) WireWalker(inst Instruction) func(cb func(wire uint32))

type BlueprintSparseR1CMul added in v0.9.0 

type BlueprintSparseR1CMul struct{}

BlueprintSparseR1CMul implements Blueprint, BlueprintSolvable and BlueprintSparseR1C. Encodes 

qM⋅(xaxb)  == xc

func (*BlueprintSparseR1CMul) CalldataSize added in v0.9.0 

func (b *BlueprintSparseR1CMul) CalldataSize() int

func (*BlueprintSparseR1CMul) CompressSparseR1C added in v0.9.0 

func (b *BlueprintSparseR1CMul) CompressSparseR1C(c *SparseR1C, to *[]uint32)

func (*BlueprintSparseR1CMul) DecompressSparseR1C added in v0.9.0 

func (b *BlueprintSparseR1CMul) DecompressSparseR1C(c *SparseR1C, inst Instruction)

func (*BlueprintSparseR1CMul) NbConstraints added in v0.9.0 

func (b *BlueprintSparseR1CMul) NbConstraints() int

func (*BlueprintSparseR1CMul) NbOutputs added in v0.9.0 

func (b *BlueprintSparseR1CMul) NbOutputs(inst Instruction) int

func (*BlueprintSparseR1CMul) Solve added in v0.9.0 

func (b *BlueprintSparseR1CMul) Solve(s Solver, inst Instruction) error

func (*BlueprintSparseR1CMul) WireWalker added in v0.9.0 

func (b *BlueprintSparseR1CMul) WireWalker(inst Instruction) func(cb func(wire uint32))

type Commitment 

type Commitment interface{}

type CommitmentConstraint added in v0.9.0 

type CommitmentConstraint uint32
const (
	NOT        CommitmentConstraint = 0
	COMMITTED  CommitmentConstraint = 1
	COMMITMENT CommitmentConstraint = 2
)

type Commitments added in v0.9.0 

type Commitments interface{ CommitmentIndexes() []int }

func NewCommitments added in v0.9.0 

func NewCommitments(t SystemType) Commitments

type Compressible added in v0.9.0 

type Compressible interface {
	// Compress interprets the objects as a LinearExpression and encodes it as a []uint32.
	Compress(to *[]uint32)
}

Compressible represent an object that knows how to encode itself as a []uint32.

type ConstraintSystem 

type ConstraintSystem interface {
	io.WriterTo
	io.ReaderFrom
	Field
	Resolver
	CustomizableSystem

	// IsSolved returns nil if given witness solves the constraint system and error otherwise
	// Deprecated: use _, err := Solve(...) instead
	IsSolved(witness witness.Witness, opts ...solver.Option) error

	// Solve attempts to solve the constraint system using provided witness.
	// Returns an error if the witness does not allow all the constraints to be satisfied.
	// Returns a typed solution (R1CSSolution or SparseR1CSSolution) and nil otherwise.
	Solve(witness witness.Witness, opts ...solver.Option) (any, 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

	GetNbInstructions() 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.
	// Providing the function f is optional. If it is provided, id will be ignored and one will be derived from f's name.
	// Otherwise, the provided id will be used to register the hint with,
	AddSolverHint(f solver.Hint, id solver.HintID, input []LinearExpression, nbOutput int) (internalVariables []int, err error)

	AddCommitment(c Commitment) error
	GetCommitments() Commitments
	AddGkr(gkr GkrInfo) 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 Element, variableID int) Term

	// AddCoeff adds a coefficient to the underlying constraint system. The system will not store duplicate,
	// but is not purging for unused coeff either, so this grows memory usage.
	AddCoeff(coeff Element) uint32

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

	// AttachDebugInfo enables attaching debug information to multiple constraints.
	// This is more efficient than using the AddR1C(.., 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

	GetInstruction(int) Instruction

	GetCoefficient(i int) Element
}

ConstraintSystem interface that all constraint systems implement.

type CustomizableSystem added in v0.9.0 

type CustomizableSystem interface {
	// AddBlueprint registers the given blueprint and returns its id. This should be called only once per blueprint.
	AddBlueprint(b Blueprint) BlueprintID

	// AddInstruction adds an instruction to the system and returns a list of created wires
	// if the blueprint declared any outputs.
	AddInstruction(bID BlueprintID, calldata []uint32) []uint32
}

type DebugInfo 

type DebugInfo LogEntry

type Element added in v0.9.0 

type Element [6]uint64

Element 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 (*Element) Bytes added in v0.9.0 

func (z *Element) Bytes() [48]byte

Bytes return the Element as a big-endian byte slice

func (*Element) IsZero added in v0.9.0 

func (z *Element) IsZero() bool

IsZero returns true if coefficient == 0

func (*Element) SetBytes added in v0.9.0 

func (z *Element) SetBytes(b [48]byte)

SetBytes sets the Element from a big-endian byte slice

type Field added in v0.9.0 

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

Field capability to perform arithmetic on Coeff

type GkrCircuit added in v0.9.0 

type GkrCircuit []GkrWire

func (GkrCircuit) Chunks added in v0.9.0 

func (c GkrCircuit) Chunks(nbInstances int) []int

Chunks returns intervals of instances that are independent of each other and can be solved in parallel

type GkrInfo added in v0.9.0 

type GkrInfo struct {
	Circuit     GkrCircuit
	MaxNIns     int
	NbInstances int
	HashName    string
	SolveHintID solver.HintID
	ProveHintID solver.HintID
}

func (*GkrInfo) AssignmentOffsets added in v0.9.0 

func (d *GkrInfo) AssignmentOffsets() []int

AssignmentOffsets returns the index of the first value assigned to a wire TODO: Explain clearly

func (*GkrInfo) Compile added in v0.9.0 

func (d *GkrInfo) Compile(nbInstances int) (GkrPermutations, error)

Compile sorts the circuit wires, their dependencies and the instances

func (*GkrInfo) Is added in v0.9.0 

func (d *GkrInfo) Is() bool

func (*GkrInfo) NewInputVariable added in v0.9.0 

func (d *GkrInfo) NewInputVariable() GkrVariable

type GkrPermutations added in v0.9.0 

type GkrPermutations struct {
	SortedInstances      []int
	SortedWires          []int
	InstancesPermutation []int
	WiresPermutation     []int
}

type GkrVariable added in v0.9.0 

type GkrVariable int // Just an alias to hide implementation details. May be more trouble than worth

type GkrWire added in v0.9.0 

type GkrWire struct {
	Gate            string // TODO: Change to description
	Inputs          []int
	Dependencies    []InputDependency // nil for input wires
	NbUniqueOutputs int
}

func (GkrWire) IsInput added in v0.9.0 

func (w GkrWire) IsInput() bool

func (GkrWire) IsOutput added in v0.9.0 

func (w GkrWire) IsOutput() bool

type Groth16Commitment added in v0.9.0 

type Groth16Commitment struct {
	PublicAndCommitmentCommitted []int // PublicAndCommitmentCommitted sorted list of id's of public and commitment committed wires
	PrivateCommitted             []int // PrivateCommitted sorted list of id's of private/internal committed wires
	CommitmentIndex              int   // CommitmentIndex the wire index of the commitment
	HintID                       solver.HintID
	NbPublicCommitted            int
}

func (Groth16Commitment) GetCommitmentCommitted added in v0.9.0 

func (c Groth16Commitment) GetCommitmentCommitted() []int

func (Groth16Commitment) GetPublicCommitted added in v0.9.0 

func (c Groth16Commitment) GetPublicCommitted() []int

type Groth16Commitments added in v0.9.0 

type Groth16Commitments []Groth16Commitment

func (Groth16Commitments) CommitmentIndexes added in v0.9.0 

func (c Groth16Commitments) CommitmentIndexes() []int

func (Groth16Commitments) GetPrivateCommitted added in v0.9.0 

func (c Groth16Commitments) GetPrivateCommitted() [][]int

func (Groth16Commitments) GetPublicAndCommitmentCommitted added in v0.9.0 

func (c Groth16Commitments) GetPublicAndCommitmentCommitted(committedTranslationList []int, offset int) [][]int

GetPublicAndCommitmentCommitted returns the list of public and commitment committed wires if committedTranslationList is not nil, commitment indexes are translated into their relative positions on the list plus the offset

type HintMapping added in v0.9.0 

type HintMapping struct {
	HintID      solver.HintID      // Hint function id
	Inputs      []LinearExpression // Terms to inject in the hint function
	OutputRange struct {
		Start, End uint32
	}
}

HintMapping mark a list of output variables to be computed using provided hint and inputs.

type InputDependency added in v0.9.0 

type InputDependency struct {
	OutputWire     int
	OutputInstance int
	InputInstance  int
}

type Instruction added in v0.9.0 

type Instruction struct {
	ConstraintOffset uint32
	WireOffset       uint32
	Calldata         []uint32
}

Instruction is the lowest element of a constraint system. It stores all the data needed to reconstruct a constraint of any shape or a hint at solving time.

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) Compress added in v0.9.0 

func (l LinearExpression) Compress(to *[]uint32)

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 PackedInstruction added in v0.9.0 

type PackedInstruction struct {
	// BlueprintID maps this instruction to a blueprint
	BlueprintID BlueprintID

	// ConstraintOffset stores the starting constraint ID of this instruction.
	// Might not be strictly necessary; but speeds up solver for instructions that represents
	// multiple constraints.
	ConstraintOffset uint32

	// WireOffset stores the starting internal wire ID of this instruction. Blueprints may use this
	// and refer to output wires by their offset.
	// For example, if a blueprint declared 5 outputs, the first output wire will be WireOffset,
	// the last one WireOffset+4.
	WireOffset uint32

	// The constraint system stores a single []uint32 calldata slice. StartCallData
	// points to the starting index in the mentioned slice. This avoid storing a slice per
	// instruction (3 * uint64 in memory).
	StartCallData uint64
}

PackedInstruction is the lowest element of a constraint system. It stores just enough data to reconstruct a constraint of any shape or a hint at solving time.

func (PackedInstruction) Unpack added in v0.9.0 

func (pi PackedInstruction) Unpack(cs *System) Instruction

Unpack returns the instruction corresponding to the packed instruction.

type PlonkCommitment added in v0.9.0 

type PlonkCommitment struct {
	Committed       []int // sorted list of id's of committed variables in groth16. in plonk, list of indexes of constraints defining committed values
	CommitmentIndex int   // CommitmentIndex index of the constraint defining the commitment
	HintID          solver.HintID
}

type PlonkCommitments added in v0.9.0 

type PlonkCommitments []PlonkCommitment

func (PlonkCommitments) CommitmentIndexes added in v0.9.0 

func (c PlonkCommitments) CommitmentIndexes() []int

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

type R1CIterator added in v0.9.0 

type R1CIterator struct {
	R1C
	// contains filtered or unexported fields
}

R1CIterator facilitates iterating through R1C constraints.

func (*R1CIterator) Next added in v0.9.0 

func (it *R1CIterator) Next() *R1C

Next returns the next R1C or nil if end. Caller must not store the result since the same memory space is re-used for subsequent calls to Next.

type R1CS 

type R1CS interface {
	ConstraintSystem

	// AddR1C adds a constraint to the system and returns its id
	// This does not check for validity of the constraint.
	AddR1C(r1c R1C, bID BlueprintID) int

	// GetR1Cs return the list of R1C
	// See StringBuilder for more info.
	// ! this is an experimental API.
	GetR1Cs() []R1C

	// GetR1CIterator returns an R1CIterator to iterate on the R1C constraints of the system.
	GetR1CIterator() R1CIterator
}

type Resolver 

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

Resolver allows pretty printing of constraints.

type Solver added in v0.9.0 

type Solver interface {
	Field

	GetValue(cID, vID uint32) Element
	GetCoeff(cID uint32) Element
	SetValue(vID uint32, f Element)
	IsSolved(vID uint32) bool

	// Read interprets input calldata as a LinearExpression,
	// evaluates it and return the result and the number of uint32 word read.
	Read(calldata []uint32) (Element, int)
}

Solver represents the state of a constraint system solver at runtime. Blueprint can interact with this object to perform run time logic, solve constraints and assign values in the solution.

type SparseR1C 

type SparseR1C struct {
	XA, XB, XC         uint32
	QL, QR, QO, QM, QC uint32
	Commitment         CommitmentConstraint
}

SparseR1C represent a PlonK-ish constraint qL⋅xa + qR⋅xb + qO⋅xc + qM⋅(xaxb) + qC -committed?*Bsb22Commitments-commitment?*commitmentValue == 0

func (*SparseR1C) Clear added in v0.9.0 

func (c *SparseR1C) Clear()

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

type SparseR1CIterator added in v0.9.0 

type SparseR1CIterator struct {
	SparseR1C
	// contains filtered or unexported fields
}

SparseR1CIterator facilitates iterating through SparseR1C constraints.

func (*SparseR1CIterator) Next added in v0.9.0 

func (it *SparseR1CIterator) Next() *SparseR1C

Next returns the next SparseR1C or nil if end. Caller must not store the result since the same memory space is re-used for subsequent calls to Next.

type SparseR1CS 

type SparseR1CS interface {
	ConstraintSystem

	// AddSparseR1C adds a constraint to the constraint system.
	AddSparseR1C(c SparseR1C, bID BlueprintID) int

	// GetSparseR1Cs return the list of SparseR1C
	// See StringBuilder for more info.
	// ! this is an experimental API.
	GetSparseR1Cs() []SparseR1C

	// GetSparseR1CIterator returns an SparseR1CIterator to iterate on the SparseR1C constraints of the system.
	GetSparseR1CIterator() SparseR1CIterator
}

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

	Type SystemType

	Instructions []PackedInstruction
	Blueprints   []Blueprint
	CallData     []uint32 // huge slice.

	// can be != than len(instructions)
	NbConstraints int

	// 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

	// maps hintID to hint string identifier
	MHintsDependencies map[solver.HintID]string

	// 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 Commitments
	GkrInfo        GkrInfo
	// contains filtered or unexported fields
}

System contains core elements for a constraint System

func NewSystem 

func NewSystem(scalarField *big.Int, capacity int, t SystemType) System

NewSystem initialize the common structure among constraint system

func (*System) AddBlueprint added in v0.9.0 

func (system *System) AddBlueprint(b Blueprint) BlueprintID

AddBlueprint adds a blueprint to the system and returns its ID

func (*System) AddCommitment 

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

func (*System) AddGkr added in v0.9.0 

func (system *System) AddGkr(gkr GkrInfo) error

func (*System) AddInstruction added in v0.9.0 

func (cs *System) AddInstruction(bID BlueprintID, calldata []uint32) []uint32

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) AddR1C added in v0.9.0 

func (cs *System) AddR1C(c R1C, bID BlueprintID) int

func (*System) AddSecretVariable 

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

func (*System) AddSolverHint 

func (system *System) AddSolverHint(f solver.Hint, id solver.HintID, input []LinearExpression, nbOutput int) (internalVariables []int, err error)

func (*System) AddSparseR1C added in v0.9.0 

func (cs *System) AddSparseR1C(c SparseR1C, bID BlueprintID) int

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) CheckUnconstrainedWires added in v0.9.0 

func (cs *System) CheckUnconstrainedWires() error

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) GetCommitments added in v0.9.0 

func (cs *System) GetCommitments() Commitments

func (*System) GetInstruction added in v0.9.0 

func (system *System) GetInstruction(id int) Instruction

GetInstruction returns the instruction at index id

func (*System) GetNbConstraints added in v0.9.0 

func (cs *System) GetNbConstraints() int

GetNbConstraints returns the number of constraints

func (*System) GetNbInstructions added in v0.9.0 

func (system *System) GetNbInstructions() int

GetNbInstructions returns the number of instructions in the system

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) GetR1CIterator added in v0.9.0 

func (cs *System) GetR1CIterator() R1CIterator

func (*System) GetSparseR1CIterator added in v0.9.0 

func (cs *System) GetSparseR1CIterator() SparseR1CIterator

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 SystemType added in v0.9.0 

type SystemType uint16
const (
	SystemUnknown SystemType = iota
	SystemR1CS
	SystemSparseR1CS
)

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) Compress added in v0.9.0 

func (t Term) Compress(to *[]uint32)

Compress compresses the term into a slice of uint32 words. For compatibility with test engine and LinearExpression, the term is encoded as: 1, CID, VID (i.e a LinearExpression with a single term)

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.