Circom 2.0: A Scalable Circuit Compiler

1. introduction

This article is mainly from IDEN3 The team Albert Rubio stay Compiler and Composability in ZKP The speech on .

2. What is the Circom?

What is the Circom?
==>circom

• For programming languages and compilers
• from Jordi Baylina Created , in the light of ZK The circuit design in the Protocol DSL Language
• by iden3 Part of the project
• circom 2.0 The compiler is mainly composed of UCM Team development in universities
• circom 2.0 The compiler is completely open source and is provided by Rust language , It provides faster circuit compilation and better security
• circom The community is rapidly carrying
• Community for circom The success of

One circom program There are mainly two purposes ：

• 1） Provide a symbolic description of the corresponding circuit ： There is a set of R1CS constraint .
• 2） Provide an efficient way to calculate based on input witness：
  • There will be WebAssembly（wasm） Code and the JS Or mainstream browsers
  • It provides C++ Code （ Such as ZK-Rollups for Layer 2）

circom Support developers to design from the bottom arithmetic circuit （ Similar to designing electronic circuits ）.
stay circom in , All constraints must be explicitly added by the developer .
Constraints can be simplified , It can be removed at compile time signals, however Never introduce new signals.

stay circom, The actual circuit is called components, and component Is based on template Instantiated ,template For the parametric description of the circuit , Such as ：

Above , circuit Multiplier receive 2 Inputs , Then the output signal Is the product of the two .

circom A key feature of is that it provides different instructions to ：

• stay symbolic Layer defines new constraints ：

  out === in1 * in2; // symbolic level "only"
  

  Will generate constraints in1 * in2 - out = 0.
• stay computational Layer computing a signal：

  out<-- in1 * in2; // computational level only
  

  Will generate something like out := in1 * in2 Code for .
• Or with the help of <== The operator ：

  out <== in1 * in2; // symbolic and computational level
  

  Will generate constraint in1 * in2 - out = 0 and Code out := in1 * in2.

It is usually required to use <== The operator , But sometimes you don't need . Such as , Definition check input Is it 0 Circuit , Should be ：

Use <-- and === The operator , There is no guarantee that the circuit is symbolic Layer and the computational Equivalence of layers , The developer should be responsible for realizing the corresponding equivalence .

Can be based on circomlib Library etc templates Make combinations to build circuits ：

Above , Using variables sum To settle accounts loop Addition in a loop , Introduce parameters n To limit input signals The number of .
When building constraints , A variable is symbolic expression ; And calculation witness when , The variable corresponds to field The number .

circomlib The library contains some useful circuit implementations , It can be used as primitive templates, Specific have ：

• Binary transformers and operations
• Comparators
• hash function ：mimc、pedersen、sha256
• Elliptic curves：babyjubjub（twisted Edwards）,Montgomery
• Sparse Merkle Trees

It fully shows Circom The power of language , And how to quadratic constraints To encode complex calculations .

3. Constraint simplification

Describing cryptographic protocols arithmetic circuits The resulting constraint system may contain millions of constraints , Many constraints can usually be removed from it . Simplifying the constraint system is an important work to improve efficiency in the next stage . The upper limit of the number of constraints that most constraint systems can handle is about $2^{17}$.
Without modifying the circuit behavior and retaining R1CS In the case of expression ,Circom Support simplification of constraints .

Such as MultiAND() The constraint system of circuit generation is ：

Can simplify its linear constraints, Only 2 individual R1CS Equivalent system of constraints ：

circom Medium and efficient implementation of linear constraint Simplification of ：

• Compiler Application clustering Parallelization simplifies work ;
• Use Gauss-Jordan remove To achieve linear simplify ;
• Iterate the whole process until there is nothing left linear constraints;
• Can be achieved about 80% Of reduction;
• During compilation, the most expensive Part of the ：
  • Super large circuits need about 750GB Of local memory（ need swapping）.
  • Can make an appointment 6.5 Billion constraints reduce by 1.3 One hundred million .
  • stay 64 nucleus 512GB RAM On the machine , The compilation time is about 3 Hours （ If you use the old version circom, It takes several days ）.
  • Including simplified R1CS The binary file size of is about 50GB.
  • have 1 Thousands of constrained circuits are compiled on notebook computers （ And completely simplify ） Time usage 8 minute .

The above simplified technology ：

• Will not introduce new signals,
• It should be possible to achieve ,
• Is a new type of code optimization
• circom The simplification technology in is much stronger than Zokrates Medium
• It can be used independently for R1CS Restraint system Simplification of

4. Summary

• circom To face the bottom arithmetic Circuit design DSL
• circom It supports developers to describe how to generate circuit constraints , It also supports developers to calculate efficiently according to any specified input witness
• stay circom in , The developer completely controls the circuit definition
• circomlib The library contains many circuit templates, It can reduce the workload of developers
• circom There is a large and active community
• circom But with iden3 proving system Use a combination of , Such as snarkjs/wasmsnark/rapidsnark
• zkREPL, by zkSNARKs Online development environment , Is based on circom Built