constraint

package
v1.0.1 Latest Latest
Warning

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

 Go to latest Published: Dec 19, 2023 License: Apache-2.0 Imports: 22 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 = 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 

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

Types

type Blueprint 

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

	// UpdateInstructionTree updates the instruction tree;
	// since the blue print knows which wires it references, it updates
	// the instruction tree with the level of the (new) wires.
	UpdateInstructionTree(inst Instruction, tree InstructionTree) Level
}

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 

type BlueprintGenericHint struct{}

func (*BlueprintGenericHint) CalldataSize 

func (b *BlueprintGenericHint) CalldataSize() int

func (*BlueprintGenericHint) CompressHint 

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

func (*BlueprintGenericHint) DecompressHint 

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

func (*BlueprintGenericHint) NbConstraints 

func (b *BlueprintGenericHint) NbConstraints() int

func (*BlueprintGenericHint) NbOutputs 

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

func (*BlueprintGenericHint) UpdateInstructionTree 

func (b *BlueprintGenericHint) UpdateInstructionTree(inst Instruction, tree InstructionTree) Level

type BlueprintGenericR1C 

type BlueprintGenericR1C struct{}

BlueprintGenericR1C implements Blueprint and BlueprintR1C. Encodes 

L * R == 0

func (*BlueprintGenericR1C) CalldataSize 

func (b *BlueprintGenericR1C) CalldataSize() int

func (*BlueprintGenericR1C) CompressR1C 

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

func (*BlueprintGenericR1C) DecompressR1C 

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

func (*BlueprintGenericR1C) NbConstraints 

func (b *BlueprintGenericR1C) NbConstraints() int

func (*BlueprintGenericR1C) NbOutputs 

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

func (*BlueprintGenericR1C) UpdateInstructionTree 

func (b *BlueprintGenericR1C) UpdateInstructionTree(inst Instruction, tree InstructionTree) Level

type BlueprintGenericSparseR1C 

type BlueprintGenericSparseR1C struct {
}

BlueprintGenericSparseR1C implements Blueprint and BlueprintSparseR1C. Encodes 

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

func (*BlueprintGenericSparseR1C) CalldataSize 

func (b *BlueprintGenericSparseR1C) CalldataSize() int

func (*BlueprintGenericSparseR1C) CompressSparseR1C 

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

func (*BlueprintGenericSparseR1C) DecompressSparseR1C 

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

func (*BlueprintGenericSparseR1C) NbConstraints 

func (b *BlueprintGenericSparseR1C) NbConstraints() int

func (*BlueprintGenericSparseR1C) NbOutputs 

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

func (*BlueprintGenericSparseR1C) Solve 

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

func (*BlueprintGenericSparseR1C) UpdateInstructionTree 

func (b *BlueprintGenericSparseR1C) UpdateInstructionTree(inst Instruction, tree InstructionTree) Level

type BlueprintHint 

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 

type BlueprintID uint32

type BlueprintLookupHint 

type BlueprintLookupHint struct {
	EntriesCalldata []uint32
	// contains filtered or unexported fields
}

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 

func (b *BlueprintLookupHint) CalldataSize() int

func (*BlueprintLookupHint) NbConstraints 

func (b *BlueprintLookupHint) NbConstraints() int

func (*BlueprintLookupHint) NbOutputs 

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

NbOutputs return the number of output wires this blueprint creates.

func (*BlueprintLookupHint) Reset 

func (b *BlueprintLookupHint) Reset()

func (*BlueprintLookupHint) Solve 

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

func (*BlueprintLookupHint) UpdateInstructionTree 

func (b *BlueprintLookupHint) UpdateInstructionTree(inst Instruction, tree InstructionTree) Level

type BlueprintR1C 

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 

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 

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 

type BlueprintSparseR1CAdd struct{}

BlueprintSparseR1CAdd implements Blueprint, BlueprintSolvable and BlueprintSparseR1C. Encodes 

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

func (*BlueprintSparseR1CAdd) CalldataSize 

func (b *BlueprintSparseR1CAdd) CalldataSize() int

func (*BlueprintSparseR1CAdd) CompressSparseR1C 

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

func (*BlueprintSparseR1CAdd) DecompressSparseR1C 

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

func (*BlueprintSparseR1CAdd) NbConstraints 

func (b *BlueprintSparseR1CAdd) NbConstraints() int

func (*BlueprintSparseR1CAdd) NbOutputs 

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

func (*BlueprintSparseR1CAdd) Solve 

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

func (*BlueprintSparseR1CAdd) UpdateInstructionTree 

func (b *BlueprintSparseR1CAdd) UpdateInstructionTree(inst Instruction, tree InstructionTree) Level

type BlueprintSparseR1CBool 

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 

func (b *BlueprintSparseR1CBool) CalldataSize() int

func (*BlueprintSparseR1CBool) CompressSparseR1C 

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

func (*BlueprintSparseR1CBool) DecompressSparseR1C 

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

func (*BlueprintSparseR1CBool) NbConstraints 

func (b *BlueprintSparseR1CBool) NbConstraints() int

func (*BlueprintSparseR1CBool) NbOutputs 

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

func (*BlueprintSparseR1CBool) Solve 

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

func (*BlueprintSparseR1CBool) UpdateInstructionTree 

func (b *BlueprintSparseR1CBool) UpdateInstructionTree(inst Instruction, tree InstructionTree) Level

type BlueprintSparseR1CMul 

type BlueprintSparseR1CMul struct{}

BlueprintSparseR1CMul implements Blueprint, BlueprintSolvable and BlueprintSparseR1C. Encodes 

qM⋅(xaxb)  == xc

func (*BlueprintSparseR1CMul) CalldataSize 

func (b *BlueprintSparseR1CMul) CalldataSize() int

func (*BlueprintSparseR1CMul) CompressSparseR1C 

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

func (*BlueprintSparseR1CMul) DecompressSparseR1C 

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

func (*BlueprintSparseR1CMul) NbConstraints 

func (b *BlueprintSparseR1CMul) NbConstraints() int

func (*BlueprintSparseR1CMul) NbOutputs 

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

func (*BlueprintSparseR1CMul) Solve 

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

func (*BlueprintSparseR1CMul) UpdateInstructionTree 

func (b *BlueprintSparseR1CMul) UpdateInstructionTree(inst Instruction, tree InstructionTree) Level

type BlueprintStateful 

type BlueprintStateful interface {
	BlueprintSolvable

	// Reset is called by the solver between invocation of Solve.
	Reset()
}

BlueprintStateful indicates that the blueprint can be reset to its initial state.

type Commitment 

type Commitment interface{}

type CommitmentConstraint 

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

type Commitments 

type Commitments interface{ CommitmentIndexes() []int }

func NewCommitments 

func NewCommitments(t SystemType) Commitments

type Compressible 

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 

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 

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 

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

Bytes return the Element as a big-endian byte slice

func (*Element) IsZero 

func (z *Element) IsZero() bool

IsZero returns true if coefficient == 0

func (*Element) SetBytes 

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

SetBytes sets the Element from a big-endian byte slice

type Field 

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 

type GkrCircuit []GkrWire

func (GkrCircuit) Chunks 

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 

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

func (*GkrInfo) AssignmentOffsets 

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

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

func (*GkrInfo) Compile 

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

Compile sorts the circuit wires, their dependencies and the instances

func (*GkrInfo) Is 

func (d *GkrInfo) Is() bool

func (*GkrInfo) NewInputVariable 

func (d *GkrInfo) NewInputVariable() GkrVariable

type GkrPermutations 

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

type GkrVariable 

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

type GkrWire 

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

func (GkrWire) IsInput 

func (w GkrWire) IsInput() bool

func (GkrWire) IsOutput 

func (w GkrWire) IsOutput() bool

type Groth16Commitment 

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
	NbPublicCommitted            int
}

func (Groth16Commitment) GetCommitmentCommitted 

func (c Groth16Commitment) GetCommitmentCommitted() []int

func (Groth16Commitment) GetPublicCommitted 

func (c Groth16Commitment) GetPublicCommitted() []int

type Groth16Commitments 

type Groth16Commitments []Groth16Commitment

func (Groth16Commitments) CommitmentIndexes 

func (c Groth16Commitments) CommitmentIndexes() []int

func (Groth16Commitments) GetPrivateCommitted 

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

func (Groth16Commitments) GetPublicAndCommitmentCommitted 

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 

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 

type InputDependency struct {
	OutputWire     int
	OutputInstance int
	InputInstance  int
}

type Instruction 

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 InstructionTree 

type InstructionTree interface {
	// InsertWire inserts a wire in the instruction tree at the given level.
	// If the wire is already in the instruction tree, it panics.
	InsertWire(wire uint32, level Level)

	// HasWire returns true if the wire is in the instruction tree.
	// False if it's a constant or an input.
	HasWire(wire uint32) bool

	// GetWireLevel returns the level of the wire in the instruction tree.
	// If HasWire(wire) returns false, behavior is undefined.
	GetWireLevel(wire uint32) Level
}

type Level 

type Level int
const (
	LevelUnset Level = -1
)

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 

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 

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 

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

Unpack returns the instruction corresponding to the packed instruction.

type PlonkCommitment 

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
}

type PlonkCommitments 

type PlonkCommitments []PlonkCommitment

func (PlonkCommitments) CommitmentIndexes 

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 

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

R1CIterator facilitates iterating through R1C constraints.

func (*R1CIterator) Next 

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 

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 

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 

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

SparseR1CIterator facilitates iterating through SparseR1C constraints.

func (*SparseR1CIterator) Next 

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 

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 

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

func (*System) AddInstruction 

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 

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 

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 

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 

func (cs *System) GetCommitments() Commitments

func (*System) GetInstruction 

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

GetInstruction returns the instruction at index id

func (*System) GetNbConstraints 

func (cs *System) GetNbConstraints() int

GetNbConstraints returns the number of constraints

func (*System) GetNbInstructions 

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 

func (cs *System) GetR1CIterator() R1CIterator

func (*System) GetSparseR1CIterator 

func (cs *System) GetSparseR1CIterator() SparseR1CIterator

func (*System) GetWireLevel 

func (system *System) GetWireLevel(wireID uint32) Level

func (*System) HasWire 

func (system *System) HasWire(wireID uint32) bool

func (*System) InsertWire 

func (system *System) InsertWire(wireID uint32, level Level)

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 

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 

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.