ir

Documentation

Overview

Package ir implements the internal representation (IR) and related functionalities for the GKR compiler.

Index

• Constants
• func GetCircuitVariables(assignment frontend.Circuit, field field.Field) []constraint.Element
• func IsAllHintsSolvingTimeDeterminable(rc *RootCircuit) bool
• func Validate(rc *RootCircuit) error
• func ValidateForLayering(rc *RootCircuit) error
• type Circuit
  • func (ci *Circuit) Print(field field.Field)
• type CircuitForSerialization
• type CircuitSolveInfo
• type InputOrder
• type InputOrderInstruction
• type InputSolver
  • func DeserializeInputSolver(data []byte) *InputSolver
  • func GetInputSolver(rc *RootCircuit, od *InputOrder) *InputSolver
  • func (is *InputSolver) Serialize() []byte
  • func (solver *InputSolver) SolveInput(assignment frontend.Circuit, nbThreads int) (Witness, error)
  • func (solver *InputSolver) SolveInputAuto(assignment frontend.Circuit) (Witness, error)
• type InputSolverForSerialization
• type Instruction
  • func NewCustomGateInstruction(f solver.Hint, gateType uint64, inputs []expr.Expression, outputId int) Instruction
  • func NewGetRandomInstruction(outputId int) Instruction
  • func NewHintInstruction(f solver.Hint, inputs []expr.Expression, outputIds []int) Instruction
  • func NewInternalVariableInstruction(e expr.Expression, o int) Instruction
  • func NewSubCircuitInstruction(subId uint64, inputs []expr.Expression, outputsIds []int) Instruction
• type InstructionForSerialization
• type InstructionType
• type RootCircuit
  • func AdjustForLayering(rc *RootCircuit) *RootCircuit
  • func (rc *RootCircuit) GetStats() Stats
  • func (rc *RootCircuit) Print()
• type Stats
• type Witness
  • func (w Witness) Serialize() []byte

Constants

const NbFieldOperationsPerGroup = 1024

NbFieldOperationsPerGroup represents the rough number of field operations (multiplications) per group, where a group is the minimum scheduling unit.

Functions

func GetCircuitVariables

func GetCircuitVariables(assignment frontend.Circuit, field field.Field) []constraint.Element

GetCircuitVariables reimplements frontend.NewWitness to support fields that are not present in gnark.

func IsAllHintsSolvingTimeDeterminable

func IsAllHintsSolvingTimeDeterminable(rc *RootCircuit) bool

IsAllHintsSolvingTimeDeterminable checks if every input variable of hints is solving time determinable. It returns false if the output of GetRandomValue is used in hints, as these cannot be determined at solving time.

func Validate

func Validate(rc *RootCircuit) error

Validate checks if the circuit is valid by ensuring that all instructions are well-formed.

func ValidateForLayering

func ValidateForLayering(rc *RootCircuit) error

ValidateForLayering checks if the circuit is valid for layering. It requires that all outputs, constraints, and sub-circuit inputs are single variables.

Types

type Circuit

type Circuit struct {
	// each instruction specifies the method to calculate some variables
	// the output id must be sequential
	Instructions []Instruction
	// each constraint constrains some expression to be zero
	Constraints []expr.Expression
	// each output gate of the circuit
	Output []expr.Expression
	// number of input gates
	NbExternalInput int
}

Circuit defines an arithmetic circuit which may contain calls to other Circuits. Each instruction specifies the method to calculate some variables with the output IDs being sequential. Constraints enforce certain expressions to be zero, while Outputs define the output gates of the circuit. NbExternalInput specifies the number of input gates.

func (*Circuit) Print

func (ci *Circuit) Print(field field.Field)

Print outputs the circuit for debugging purposes.

type CircuitForSerialization

type CircuitForSerialization struct {
	Instructions    []InstructionForSerialization
	Constraints     []expr.Expression
	Output          []expr.Expression
	NbExternalInput int
}

CircuitForSerialization is used for serializing a Circuit to be stored or transmitted.

type CircuitSolveInfo

type CircuitSolveInfo struct {
	// the dimensions are: which layer -> eval group -> instructions
	SolveOrder [][][]int
	NbVars     int
	// number of necessary done signals for each layer ( = num group + num sub_circuit)
	LayerDoneSignals []int
	MaxChanSize      int
}

CircuitSolveInfo contains information required to solve a single circuit's inputs. It details the order of solving for instructions within evaluation groups by layer, the total number of variables, and the number of necessary done signals for each layer, which equals the number of groups plus the number of sub-circuits.

type InputOrder

type InputOrder struct {
	Insn            []InputOrderInstruction
	CircuitInputIds []int
	InputLen        int
}

InputOrder maps the circuit inputs (including user and hint inputs) to their final order in the circuit.

type InputOrderInstruction

type InputOrderInstruction struct {
	// if this is a hint instruction, InputIds[i] == j means that insn.OutputIds[i] should be put to j-th global input
	CircuitInputIds []int
	// if this is a sub circuit instruction, solve it recursively
	SubCircuit []InputOrderInstruction
}

InputOrderInstruction represents instructions for ordering inputs within the circuit, specifically for hints and sub-circuit calls.

type InputSolver

type InputSolver struct {
	RootCircuit       *RootCircuit
	InputOrder        *InputOrder
	CircuitsSolveInfo map[uint64]*CircuitSolveInfo
}

InputSolver is responsible for solving the entire circuit's inputs. It uses RootCircuit for the circuit structure, InputOrder for the ordering of inputs, and CircuitsSolveInfo for solving information for each sub-circuit.

func DeserializeInputSolver

func DeserializeInputSolver(data []byte) *InputSolver

DeserializeInputSolver creates an InputSolver from serialized data.

func GetInputSolver

func GetInputSolver(rc *RootCircuit, od *InputOrder) *InputSolver

GetInputSolver calculates the input solver for the given root circuit and input order by performing a topological sort on the instructions.

func (*InputSolver) Serialize

func (is *InputSolver) Serialize() []byte

Serialize converts the InputSolver into a byte slice for storage or transmission.

func (*InputSolver) SolveInput

func (solver *InputSolver) SolveInput(assignment frontend.Circuit, nbThreads int) (Witness, error)

SolveInput is the entry point to solve the final input of the given assignment using a specified number of threads.

func (*InputSolver) SolveInputAuto

func (solver *InputSolver) SolveInputAuto(assignment frontend.Circuit) (Witness, error)

SolveInputAuto solves the final input of the given assignment, automatically determining the number of threads to use.

type InputSolverForSerialization

type InputSolverForSerialization struct {
	Field             *big.Int
	Circuits          map[uint64]*CircuitForSerialization
	InputOrder        *InputOrder
	CircuitsSolveInfo map[uint64]*CircuitSolveInfo
}

InputSolverForSerialization is used for serializing an InputSolver.

type Instruction

type Instruction struct {
	Type           InstructionType
	HintFunc       solver.Hint
	SubCircuitId   uint64
	CustomGateType uint64
	Inputs         []expr.Expression
	OutputIds      []int
}

Instruction represents a computation step within a circuit. It can be:

1. an internal variable, which compress an expression into a single variable
2. a hint, as in gnark
3. a sub circuit
4. a random value
5. a custom gate

func NewCustomGateInstruction

func NewCustomGateInstruction(f solver.Hint, gateType uint64, inputs []expr.Expression, outputId int) Instruction

func NewGetRandomInstruction

func NewGetRandomInstruction(outputId int) Instruction

func NewHintInstruction

func NewHintInstruction(f solver.Hint, inputs []expr.Expression, outputIds []int) Instruction

func NewInternalVariableInstruction

func NewInternalVariableInstruction(e expr.Expression, o int) Instruction

func NewSubCircuitInstruction

func NewSubCircuitInstruction(subId uint64, inputs []expr.Expression, outputsIds []int) Instruction

type InstructionForSerialization

type InstructionForSerialization struct {
	Type           InstructionType
	HintID         solver.HintID
	SubCircuitId   uint64
	CustomGateType uint64
	Inputs         []expr.Expression
	OutputIds      []int
}

InstructionForSerialization is used for serializing an Instruction.

type InstructionType

type InstructionType int

InstructionType enumerates the types of instructions that can be part of a Circuit.

const (
	IInternalVariable InstructionType = iota
	IHint
	ISubCircuit
	IGetRandom
	ICustomGate
)

type RootCircuit

type RootCircuit struct {
	Field field.Field
	// circuit list, we assume idx 0 is the root circuit
	Circuits map[uint64]*Circuit
}

RootCircuit represents a compiled circuit, containing multiple "Circuit" components. The circuit at index 0 is considered the entry point of the RootCircuit.

func AdjustForLayering

func AdjustForLayering(rc *RootCircuit) *RootCircuit

AdjustForLayering adjusts the circuit for layering, ensuring it meets the requirements of ValidateForLayering.

func (*RootCircuit) GetStats

func (rc *RootCircuit) GetStats() Stats

GetStats retrieves statistical information about the circuit, such as the number of input gates, terms, and constraints.

func (*RootCircuit) Print

func (rc *RootCircuit) Print()

Print outputs the RootCircuit for debugging purposes.

type Stats

type Stats struct {
	// number of input gates in root circuit
	NbRootInput int
	// number of terms in all expressions, including instructions, outputs, and constraints
	NbTotTerms int
	// number of terms if all circuits are expanded
	NbExpandedTerms int
	// number of constraints in expanded circuit
	NbConstraints int
}

type Witness

type Witness []*big.Int

Witness represents the solved values of the circuit's inputs.

func (Witness) Serialize

func (w Witness) Serialize() []byte

Serialize converts the Witness into a byte slice for storage or transmission.