Noir Circuit Optimizations Write-up

Overview of Clap paper

Paper: https://arxiv.org/pdf/2405.12115

The CLAP paper provides Semantics-preserving compilation(proved in Agda) and Safe automatic optimizations that match or sometimes outperform manual optimizations. CLAP paper also validates the thesis on the Boojum circuits are used in production by ZKsync Era and tested the expressivity and efficiency of CLAP on an implementation of the Poseidon2 and SHA2-256 hash functions.

Here, we will focus only on the circuit optimizations discussed in the CLAP paper and check if they are present in or can be implemented in the Noir circuit.

Section IV of the CLAP paper describes 5 optimizations at the circuit level in order to achieve the same (or better) circuit sizes.

1. Linear Inlining

2. Boolean Inlining

3. Circuit flattening

4. Common sub-expression elimination

5. Duplicate range-checks

6. Gate Conversions

Description of each optimization

1. Linear Inlining:

Substituting (inlining) the first equation into the second, we can eliminate first equation(intermediate witness) completely and simplify the circuit.

Example from CLAP:

$x_1 := c0 · x0 + c1$
$x3 := ql · x1 + qr · x2 + qm · (x1 · x2) + qc$

$x3 := (ql · c1) · x0 + (qr + qm · c2) · x2
+(qm · c1) · x0 · x2 + (ql · c2 + qc)$

2. Boolean Inlining:

Knowledge of a variable being boolean allows inlining opportunities because its degree does not increase. Using the fact that $a^2=a$ for booleans one can remove the squaring of boolean wires.

Example from CLAP:

$x := ql · b + qm · b^2 + qc$ where $b ∈ {0, 1}$

x := (ql + qm) · b + qc

3. Circuit flattening

Plonkish proving systems allow custom gates, where multiple arithmetic operations can be batched into one high-degree polynomial constraint. Custom gates allow to dramatically reduce the size of a circuit by encoding a potentially large computation as a single gate, provided that the degree is not too large. A smaller circuit requires less proving time but each custom gate adds to verification time and proof size, a trade-off that is sensible if the gate is used extensively.

4. Common sub-expression elimination

There are many occasions where the same expression is used multiple times in a circuit. In this optimization, the optimizer finds variables that are the output of the same gate and keeps only one, significantly reducing duplication and unnecessary intermediate variables.

5. Duplicate range-checks

This can be considered as a special case of common sub-expression eleminition when there is a multiple range check over the same variable. For instance, if a gate that receives as input is checked to be in range of u32 is later also checked to be in range of u64 when chained will give 2 constraint out of which one is redundant since if a variable fits into u32 will also fit into u64. Such duplicate checks can be avoided in this optimization.

6. Gate conversions

If multiple arithmetic gates are chained in a linear way, CLAP optimizes it by replacing them with a linear combination gate, saving many intermediate variables.

Example from CLAP:

$x1 := q0 · y0$
$x2 := q1 · y1 + x1$
$x3 := q2 · y2 + x2$

$x3 := \sum_{i=0}^{2} qi·yi$

We also looked into the optimizations Noir circuit provides and tried to map it with mentioned CLAP optimizations.

Noir program and circuit definition

A program in Noir is defined by:

/// A program represented by multiple ACIR [circuit][Circuit]'s. The execution trace of these
/// circuits is dictated by construction of the [crate::native_types::WitnessStack].
#[derive(Clone, PartialEq, Eq, Serialize, Deserialize, Default, Hash)]
#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
pub struct Program<F: AcirField> {
    pub functions: Vec<Circuit<F>>,
    pub unconstrained_functions: Vec<BrilligBytecode<F>>,
}

/// A program represented by multiple ACIR [circuit][Circuit]'s. The execution trace of these
/// circuits is dictated by construction of the [crate::native_types::WitnessStack].
#[derive(Clone, PartialEq, Eq, Serialize, Deserialize, Default, Hash)]
#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
pub struct Program<F: AcirField> {
    pub functions: Vec<Circuit<F>>,
    pub unconstrained_functions: Vec<BrilligBytecode<F>>,
}

/// A program represented by multiple ACIR [circuit][Circuit]'s. The execution trace of these
/// circuits is dictated by construction of the [crate::native_types::WitnessStack].
#[derive(Clone, PartialEq, Eq, Serialize, Deserialize, Default, Hash)]
#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
pub struct Program<F: AcirField> {
    pub functions: Vec<Circuit<F>>,
    pub unconstrained_functions: Vec<BrilligBytecode<F>>,
}

where Circuit is a single ACIR circuit

/// Representation of a single ACIR circuit. The execution trace of this structure
/// is dictated by the construction of a [crate::native_types::WitnessMap]
#[derive(Clone, PartialEq, Eq, Serialize, Deserialize, Default, Hash)]
#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
pub struct Circuit<F: AcirField> {
    /// current_witness_index is the highest witness index in the circuit. The next witness to be added to this circuit
    /// will take on this value. (The value is cached here as an optimization.)
    pub current_witness_index: u32,
    /// The circuit opcodes representing the relationship between witness values.
    ///
    /// The opcodes should be further converted into a backend-specific circuit representation.
    /// When initial witness inputs are provided, these opcodes can also be used for generating an execution trace.
    pub opcodes: Vec<Opcode<F>>,
    /// Maximum width of the [expression][Expression]'s which will be constrained
    pub expression_width: ExpressionWidth,

    /// The set of private inputs to the circuit.
    pub private_parameters: BTreeSet<Witness>,
    // ACIR distinguishes between the public inputs which are provided externally or calculated within the circuit and returned.
    // The elements of these sets may not be mutually exclusive, i.e. a parameter may be returned from the circuit.
    // All public inputs (parameters and return values) must be provided to the verifier at verification time.
    /// The set of public inputs provided by the prover.
    pub public_parameters: PublicInputs,
    /// The set of public inputs calculated within the circuit.
    pub return_values: PublicInputs,
    /// Maps opcode locations to failed assertion payloads.
    /// The data in the payload is embedded in the circuit to provide useful feedback to users
    /// when a constraint in the circuit is not satisfied.
    ///
    // Note: This should be a BTreeMap, but serde-reflect is creating invalid
    // c++ code at the moment when it is, due to OpcodeLocation needing a comparison
    // implementation which is never generated.
    pub assert_messages: Vec<(OpcodeLocation, AssertionPayload<F>)>,
}

/// Representation of a single ACIR circuit. The execution trace of this structure
/// is dictated by the construction of a [crate::native_types::WitnessMap]
#[derive(Clone, PartialEq, Eq, Serialize, Deserialize, Default, Hash)]
#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
pub struct Circuit<F: AcirField> {
    /// current_witness_index is the highest witness index in the circuit. The next witness to be added to this circuit
    /// will take on this value. (The value is cached here as an optimization.)
    pub current_witness_index: u32,
    /// The circuit opcodes representing the relationship between witness values.
    ///
    /// The opcodes should be further converted into a backend-specific circuit representation.
    /// When initial witness inputs are provided, these opcodes can also be used for generating an execution trace.
    pub opcodes: Vec<Opcode<F>>,
    /// Maximum width of the [expression][Expression]'s which will be constrained
    pub expression_width: ExpressionWidth,

    /// The set of private inputs to the circuit.
    pub private_parameters: BTreeSet<Witness>,
    // ACIR distinguishes between the public inputs which are provided externally or calculated within the circuit and returned.
    // The elements of these sets may not be mutually exclusive, i.e. a parameter may be returned from the circuit.
    // All public inputs (parameters and return values) must be provided to the verifier at verification time.
    /// The set of public inputs provided by the prover.
    pub public_parameters: PublicInputs,
    /// The set of public inputs calculated within the circuit.
    pub return_values: PublicInputs,
    /// Maps opcode locations to failed assertion payloads.
    /// The data in the payload is embedded in the circuit to provide useful feedback to users
    /// when a constraint in the circuit is not satisfied.
    ///
    // Note: This should be a BTreeMap, but serde-reflect is creating invalid
    // c++ code at the moment when it is, due to OpcodeLocation needing a comparison
    // implementation which is never generated.
    pub assert_messages: Vec<(OpcodeLocation, AssertionPayload<F>)>,
}

/// Representation of a single ACIR circuit. The execution trace of this structure
/// is dictated by the construction of a [crate::native_types::WitnessMap]
#[derive(Clone, PartialEq, Eq, Serialize, Deserialize, Default, Hash)]
#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
pub struct Circuit<F: AcirField> {
    /// current_witness_index is the highest witness index in the circuit. The next witness to be added to this circuit
    /// will take on this value. (The value is cached here as an optimization.)
    pub current_witness_index: u32,
    /// The circuit opcodes representing the relationship between witness values.
    ///
    /// The opcodes should be further converted into a backend-specific circuit representation.
    /// When initial witness inputs are provided, these opcodes can also be used for generating an execution trace.
    pub opcodes: Vec<Opcode<F>>,
    /// Maximum width of the [expression][Expression]'s which will be constrained
    pub expression_width: ExpressionWidth,

    /// The set of private inputs to the circuit.
    pub private_parameters: BTreeSet<Witness>,
    // ACIR distinguishes between the public inputs which are provided externally or calculated within the circuit and returned.
    // The elements of these sets may not be mutually exclusive, i.e. a parameter may be returned from the circuit.
    // All public inputs (parameters and return values) must be provided to the verifier at verification time.
    /// The set of public inputs provided by the prover.
    pub public_parameters: PublicInputs,
    /// The set of public inputs calculated within the circuit.
    pub return_values: PublicInputs,
    /// Maps opcode locations to failed assertion payloads.
    /// The data in the payload is embedded in the circuit to provide useful feedback to users
    /// when a constraint in the circuit is not satisfied.
    ///
    // Note: This should be a BTreeMap, but serde-reflect is creating invalid
    // c++ code at the moment when it is, due to OpcodeLocation needing a comparison
    // implementation which is never generated.
    pub assert_messages: Vec<(OpcodeLocation, AssertionPayload<F>)>,
}

The circuit contains Vec and the enum Opcodes contains AssertZero(Expression<F>) opcode primiraly express a constraint on witnesses. Whereas, BlackBoxFuncCall opcode is for supporting specilized constraints.

Here,

pub struct Expression<F> {
    pub mul_terms: Vec<(F, Witness, Witness)>,
    pub linear_combinations: Vec<(F, Witness)>,
    pub q_c: F,
}

pub struct Expression<F> {
    pub mul_terms: Vec<(F, Witness, Witness)>,
    pub linear_combinations: Vec<(F, Witness)>,
    pub q_c: F,
}

pub struct Expression<F> {
    pub mul_terms: Vec<(F, Witness, Witness)>,
    pub linear_combinations: Vec<(F, Witness)>,
    pub q_c: F,
}

An expression representing a quadratic polynomial.
This struct is primarily used to express arithmetic relations between variables. It includes multiplication terms, linear combinations, and a constant term.

Optimizations in Noir circuit

The following optimizations are present in the Noir circuit:

1. General Optimizers

   • remove_zero_coefficients

   • simplify_mul_terms

   • simplify_linear_terms

2. eliminate_intermediate_variable and merging expressions

3. redundant range constraint optimization

4. Unused memory optimizations

Description of each optimization

remove_zero_coefficients

Remove all terms with zero as a coefficient in an expression.

Example: $0 w_1 w_5 + w_2 w_3 + 0 w_6 - w_4 + 12 = 0$

without optimization:

Expression {
    mul_terms: vec![
        (F::from(0), Witness(1), Witness(5)),
        (F::from(1), Witness(2), Witness(3))
    ],
    linear_combinations: vec![
        (F::from(0), Witness(6)),
        (F::from(-1), Witness(4))
    ],
    q_c: F::from(12)
}

Expression {
    mul_terms: vec![
        (F::from(0), Witness(1), Witness(5)),
        (F::from(1), Witness(2), Witness(3))
    ],
    linear_combinations: vec![
        (F::from(0), Witness(6)),
        (F::from(-1), Witness(4))
    ],
    q_c: F::from(12)
}

Expression {
    mul_terms: vec![
        (F::from(0), Witness(1), Witness(5)),
        (F::from(1), Witness(2), Witness(3))
    ],
    linear_combinations: vec![
        (F::from(0), Witness(6)),
        (F::from(-1), Witness(4))
    ],
    q_c: F::from(12)
}

After optimization:

Expression {
    mul_terms: vec![
        (F::from(1), Witness(2), Witness(3))
    ],
    linear_combinations: vec![
        (F::from(-1), Witness(4))
    ],
    q_c: F::from(12)
}

Expression {
    mul_terms: vec![
        (F::from(1), Witness(2), Witness(3))
    ],
    linear_combinations: vec![
        (F::from(-1), Witness(4))
    ],
    q_c: F::from(12)
}

Expression {
    mul_terms: vec![
        (F::from(1), Witness(2), Witness(3))
    ],
    linear_combinations: vec![
        (F::from(-1), Witness(4))
    ],
    q_c: F::from(12)
}

simplify_mul_terms

Simplifies all mul terms with the same bi-variate variables in an expression

Example: $3 \cdot w_1 w_2 + 5 \cdot w_2 w_1 + 4 \cdot w_3 w_4$

before:

Expression{
    mul_terms: vec![
        (F::from(3), Witness(1), Witness(2)),
        (F::from(5), Witness(2), Witness(1)),
        (F::from(4), Witness(3), Witness(4)),
    ],
    linear_combinations: vec![],
    q_c: F::from(0)
}

Expression{
    mul_terms: vec![
        (F::from(3), Witness(1), Witness(2)),
        (F::from(5), Witness(2), Witness(1)),
        (F::from(4), Witness(3), Witness(4)),
    ],
    linear_combinations: vec![],
    q_c: F::from(0)
}

Expression{
    mul_terms: vec![
        (F::from(3), Witness(1), Witness(2)),
        (F::from(5), Witness(2), Witness(1)),
        (F::from(4), Witness(3), Witness(4)),
    ],
    linear_combinations: vec![],
    q_c: F::from(0)
}

After:

Expression{
    mul_terms: vec![
        (F::from(8), Witness(1), Witness(2)),
        (F::from(4), Witness(3), Witness(4)),
    ],
    linear_combinations: vec![],
    q_c: F::from(0)
    }

Expression{
    mul_terms: vec![
        (F::from(8), Witness(1), Witness(2)),
        (F::from(4), Witness(3), Witness(4)),
    ],
    linear_combinations: vec![],
    q_c: F::from(0)
    }

Expression{
    mul_terms: vec![
        (F::from(8), Witness(1), Witness(2)),
        (F::from(4), Witness(3), Witness(4)),
    ],
    linear_combinations: vec![],
    q_c: F::from(0)
    }

simplify_linear_terms

Simplifies all linear terms with the same variables within an expression

Example: $2 w_1 + 5 w_1 - 7 w_3 + 7 w_3$
Before:

Expression{
    mul_terms: vec![],
    linear_combinations: vec![
        (F::from(2), Witness(1)),
        (F::from(5), Witness(1)),
        (F::from(-7), Witness(3)),
        (F::from(7), Witness(3)),
    ],
    q_c: F::from(0)
}

Expression{
    mul_terms: vec![],
    linear_combinations: vec![
        (F::from(2), Witness(1)),
        (F::from(5), Witness(1)),
        (F::from(-7), Witness(3)),
        (F::from(7), Witness(3)),
    ],
    q_c: F::from(0)
}

Expression{
    mul_terms: vec![],
    linear_combinations: vec![
        (F::from(2), Witness(1)),
        (F::from(5), Witness(1)),
        (F::from(-7), Witness(3)),
        (F::from(7), Witness(3)),
    ],
    q_c: F::from(0)
}

After:

Expression{
    mul_terms: vec![],
    linear_combinations: vec![
        (F::from(7), Witness(1))
        // Witness(3) term dropped because final coeff = 0
    ],
    q_c: F::from(0)
}

Expression{
    mul_terms: vec![],
    linear_combinations: vec![
        (F::from(7), Witness(1))
        // Witness(3) term dropped because final coeff = 0
    ],
    q_c: F::from(0)
}

Expression{
    mul_terms: vec![],
    linear_combinations: vec![
        (F::from(7), Witness(1))
        // Witness(3) term dropped because final coeff = 0
    ],
    q_c: F::from(0)
}

eliminate_intermediate_variable

This optimization analyzes the circuit and identifies intermediate variables that are only used in two arithmetic opcodes. It then merges the opcode which produces the intermediate variable into the second one that uses it.

First, the optimizer computes, for every witness, which opcodes use it. For each candidate witness, the opcode with the smallest index is merged into the other one via Gaussian elimination.

Example from Noir:

/// [(1, _2,_3), (2, _2), (2, _1), (1, _3)]
/// [(2, _3, _4), (2,_1), (1, _4)]
/// We will remove the first one and modify the second one like this:
/// [(2, _3, _4), (1, _4), (-1, _2), (-1/2, _3), (-1/2, _2, _3)]

/// [(1, _2,_3), (2, _2), (2, _1), (1, _3)]
/// [(2, _3, _4), (2,_1), (1, _4)]
/// We will remove the first one and modify the second one like this:
/// [(2, _3, _4), (1, _4), (-1, _2), (-1/2, _3), (-1/2, _2, _3)]

/// [(1, _2,_3), (2, _2), (2, _1), (1, _3)]
/// [(2, _3, _4), (2,_1), (1, _4)]
/// We will remove the first one and modify the second one like this:
/// [(2, _3, _4), (1, _4), (-1, _2), (-1/2, _3), (-1/2, _2, _3)]

Expression1: $1 \cdot (w_2 \cdot w_3) + 2 \cdot w_2 + 2 \cdot w_1 + 1 \cdot w_3 = 0$
Expression 2: $2 \cdot (w_3 \cdot w_4) + 2 \cdot w_1 + 1 \cdot w_4 = 0$

After optimization:

$(2) \cdot (w_3 w_4) + (1) \cdot w_4 + (-1) \cdot w_2 + (-1/2) \cdot w_3 + (-1/2) \cdot (w_2 w_3) = 0$

Since witness 1 is used in exactly 2 constraint,
the expression with smaller index get merged into another via Gaussian elimination.

redundant range constraint

This optimization removes any redundant range constraint which doesn't result in additional restrictions on the value of witnesses.

Example from Noir:

//! ```noir
//! let z1 = x as u16;
//! let z2 = x as u32;
//! ```
//! It is clear that if `x` fits inside of a 16-bit integer,
//! it must also fit inside of a 32-bit integer.
//!
//! The generated ACIR may produce two range opcodes however;
//! - One for the 16 bit range constraint of `x`
//! - One for the 32-bit range constraint of `x`
//!
//! This optimization pass will keep the 16-bit range constraint
//! and remove the 32-bit range constraint opcode.

//! ```noir
//! let z1 = x as u16;
//! let z2 = x as u32;
//! ```
//! It is clear that if `x` fits inside of a 16-bit integer,
//! it must also fit inside of a 32-bit integer.
//!
//! The generated ACIR may produce two range opcodes however;
//! - One for the 16 bit range constraint of `x`
//! - One for the 32-bit range constraint of `x`
//!
//! This optimization pass will keep the 16-bit range constraint
//! and remove the 32-bit range constraint opcode.

//! ```noir
//! let z1 = x as u16;
//! let z2 = x as u32;
//! ```
//! It is clear that if `x` fits inside of a 16-bit integer,
//! it must also fit inside of a 32-bit integer.
//!
//! The generated ACIR may produce two range opcodes however;
//! - One for the 16 bit range constraint of `x`
//! - One for the 32-bit range constraint of `x`
//!
//! This optimization pass will keep the 16-bit range constraint
//! and remove the 32-bit range constraint opcode.

Unused memory optimizations

This optimization removes initializations of any memory blocks which are unused. It start with a HashSet containing all memory blocks that were initialized. Then iterating over opcode, if MemoryOp uses that block or is used in BrilligCall, then it is removed from the HashSet. At the end whatever remains is the unused memory block.

Comparing the Noir and CLAP optimizations

The Noir Compiler implements most of the optimizations mentioned in CLAP paper and the rest a few optimizations are not applicable because of the use of BlackBoxFuncCall opcode for specialized computation such as AES encryption, Bitwise oerations, range, hashing, ecdsa signing etc.

Although every computation can be done using only assert-zero opcodes, the circuit constructed using that opcode is not always very efficient. hence, the BlackBoxFuncCall opcode is used.

Here we analyze all the optimizations mentioned in CLAP wrt Noir.

1. Linear Inlining:

   Linear Inlining is basically substituting (inlining) the first equation into the second. In Noir that is done using MergeExpressionsOptimizer which identifies intermediate variables that are only used in two arithmetic opcodes. It then merges the opcode which produces the intermediate variable into the second one that uses it.

2. Boolean Inlining:

   Knowledge of a variable being boolean can allow certain optimizations such as removing squaring of the boolean wires. This is not applicable in case of Noir because Noir uses BlackBoxFuncCall opcode for bitwise operations such as AND and XOR instead of AssertZero.

3. Circuit flattening

   This was not straightforward and require changes to the circuit design as the Expression defined in the Noir compiler is explicitly of degree less or equal to 2 and does not allow batching multiple arithmetic operations into one high-degree polynomial constraint. That being said, batching multiple arithmetic as a BlackBoxFuncCall would have been the choice but that also require changes in the circuit design and adding arbitrary operations in BlackBoxFuncCall was not possible.

4. Common sub-expression elimination

   common expression used multiple times in a circuit can be optimized by keeps only one thus reducing duplication and unnecessary intermediate variables. In Noir, eliminate_intermediate_variable of the MergeExpressionsOptimizer serves the same purpose of eliminating the common sub-expression by merging one expression with smallest index into the other one via Gaussian elimination.

5. Duplicate range-checks

   Redundant range check can be avoided over the same variable under this optimization. In Noir, this optimization is done in RangeOptimizer where each Witness is only range constrained once to the lowest number bit size possible.

6. Gate conversions

   This optimization allows replacing multiple arithmetic gates chained in a linear way with a linear combination gate. In Noir, this can be done using eliminate_intermediate_variable of the MergeExpressionsOptimizer along with the GeneralOptimizer which includes remove_zero_coefficients, simplify_mul_terms and simplify_linear_terms.

This shows that all the optimizations mentioned in CLAP paper is directly or indirectly implemented in Noir.