how circom works

This note tries to document how the circom code is compiled to constraints and witness calculation executables.

A paper explain in details on the features of the circom lang: https://www.computer.org/csdl/journal/tq/2023/06/10002421/1Jv6BEAupcA

AST parser

It uses lalrpop parser framework: https://github.com/iden3/circom/blob/736c554551ac8a29a28d9eac53d1700f47c07f89/parser/src/lang.lalrpop#L211
1. this grammar definition file could be used as a clue to find the internal code based on the syntax naming
2. book: https://lalrpop.github.io/lalrpop/

ast nodes

Below are some of the key AST nodes in circom:

assign op

pub enum AssignOp {
	AssignVar, // =
	AssignSignal, // <--
	AssignConstraintSignal, // <==
}

statement

pub enum Statement {

	IfThenElse {
	...
	},
	
	While {
	...
	},
	
	Return {
	...
	},
	
	InitializationBlock {
	...
	},
	
	Declaration {
	...
	},
	
	Substitution { // this is assignment, such as =
	...
	},
	...
	ConstraintEquality { // ===
	...
	},
	
	LogCall {
	...
	},
	
	Block { // a block statement can contain a list of this statement structure
	...
	},
	
	Assert {
	...
	},
	
}

In the a Substitution statement, when there is a AssignOp::AssignConstraintSignal, it will add constraints for that statement. Syntactically, this is <==.

In a ConstraintEquality, it will add constraints. Syntactically, this is === .

block type

enum BlockType {
	Known,
	Unknown,
}

arithmetic expression
Each statement can contain a set of expressions. These expressions can be folded if the involved arithmetic expressions are deterministic.

pub enum ArithmeticExpression<C>
where
C: Hash + Eq,

{
	Number {
		value: BigInt,
	},
	Signal {
		symbol: C,
	},
	Linear {
		// Represents the expression: c1*s1 + .. + cn*sn + C
		// where c1..cn are integers modulo a prime and
		// s1..sn are signals. C is a constant value
		coefficients: HashMap<C, BigInt>,
	},
	Quadratic {
		// Is a quadratic expression of the form:
		// a*b + c
		// Where a,b and c are linear expression
		a: HashMap<C, BigInt>,
		b: HashMap<C, BigInt>,
		c: HashMap<C, BigInt>,
	},
	NonQuadratic,
}

During the folding process, when it encounters an non-deterministic arithmetic such as divide operation, the resulted folded expression will be NonQuadratic.

The side effect of folding these expressions when walking through the statements is to allocate memory slices, which might be similar to witness vector in noname. The funciton perform_assign might provide the clues on how the memory slice works.

/*
Represents the value stored in a element of a circom program.
The attribute route stores the dimensions of the slice, used to navigate through them.
The length of values is equal to multiplying all the values in route.
*/

pub struct MemorySlice<C> {
	route: Vec<SliceCapacity>,
	values: Vec<C>,
	number_inserts: usize,
}

overall compilation pipeline

fn start() -> Result<(), ()> {
	// parse ast
	let mut program_archive = parser_user::parse_project(&user_input)?;
	
	// type check
	type_analysis_user::analyse_project(&mut program_archive)?;
	
	// generate circuit constraints
	let circuit = execution_user::execute_project(program_archive, config)?;
	
	// generate witness calculation executable
	compilation_user::compile(compilation_config)?;
}

type checker

pub fn check_types(){
	// Structural analyses
	program_level_analyses(program_archive, &mut errors);
	
	template_level_analyses(program_archive, &mut errors);
	
	function_level_analyses(program_archive, &mut errors);
	
	// Decorators
	
	template_level_decorators(program_archive, &mut errors);
	
	function_level_decorators(program_archive, &mut errors);
	
	// Type analysis
	
	let typing_result = type_check(program_archive);

	// Semantics analyses
	semantic_analyses(program_archive, &mut errors, &mut warnings);
}

generic

build_template_instances: maybe this is the same concept as function instantiation for generic in noname: https://github.com/iden3/circom/blob/5991d900d64df43f69e4a9ca2d01fe663820b542/compiler/src/circuit_design/build.rs#L23

circuit / constraint generation

the workflow is like

  1. walk blocks
  2. walk statements
    1. walk expressions
      1. fold the arithmetic expressions
      2. when it encounters an arithmetic expression that can't be expressed in quadratic form, it is marked as non quadratic, take div for example:
      3. stores the expressions as memory slice, which is kind of like a symbolic / witness value vector
    2. if it is === constraint equality statement
      1. returns error if it is non quadratic value
      2. otherwise transform the expression as a constraint
    3. if it is <==
      1. returns error if it is non quadratic value
      2. otherwise transform the expression as a constraint

The way it manage the memory slice is bit tricky to understand. I am yet to full understand it. It seems to be related to how to allocate the cells for constraints, as well as to wire with the variables to be calculated in the generated witness calculator.

So how are signal / witness vector might be built?

witness generation

Below is the generated c++ code for the Num2Bits circuit.

circom code:
Screenshot 2024-09-02 at 18.07.49.png

generated c++:
Screenshot 2024-08-31 at 11.40.47.png

How does it generate this witness calculator from circom code?

what is next?

conclusion so far