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 (*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

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

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL