Implementing an Arithmetic Circuit Compiler in Rust

Implementing an arithmetic circuit compiler in Rust involves creating a system that can parse a polynomial expression, construct an arithmetic circuit, and evaluate it. Below is a step-by-step guide to implementing a simple arithmetic circuit compiler in Rust.

As a bonus, we are also generating a Solidity Smart Contract as the output, so we can easily deploy a verifier on Ethereum.

Let’s go!

Step 1: Setting Up the Project

First, create a new Rust project:

cargo new arithmetic_circuit
cd arithmetic_circuit        

Step 2: Define the Circuit Components

Define the basic components of an arithmetic circuit: nodes, gates, and the circuit itself.

src/lib.rs

pub mod circuit;

fn main() {
    // Example usage
    use circuit::ArithmeticCircuit;
    let expr = "(x + y) * y";
    let circuit = ArithmeticCircuit::from_expression(expr);
    let result = circuit.evaluate(&[("x", 2), ("y", 3)]);
    println!("Result: {}", result); // Should print 15
}        

src/circuit.rs

use std::collections::HashMap;

#[derive(Debug)]
pub enum Gate {
    Input(String),
    Add(Box<Node>, Box<Node>),
    Mul(Box<Node>, Box<Node>),
    Const(i32),
}

#[derive(Debug)]
pub struct Node {
    gate: Gate,
    value: Option<i32>,
}

impl Node {
    pub fn new(gate: Gate) -> Self {
        Node { gate, value: None }
    }

    pub fn evaluate(&mut self, inputs: &HashMap<String, i32>) -> i32 {
        if let Some(val) = self.value {
            return val;
        }
        let result = match &self.gate {
            Gate::Input(name) => *inputs.get(name).unwrap(),
            Gate::Add(left, right) => left.evaluate(inputs) + right.evaluate(inputs),
            Gate::Mul(left, right) => left.evaluate(inputs) * right.evaluate(inputs),
            Gate::Const(val) => *val,
        };
        self.value = Some(result);
        result
    }
}

pub struct ArithmeticCircuit {
    root: Node,
}

impl ArithmeticCircuit {
    pub fn new(root: Node) -> Self {
        ArithmeticCircuit { root }
    }

    pub fn from_expression(expr: &str) -> Self {
        // For simplicity, this example will manually create the circuit.
        // You can replace this with a proper expression parser.
        let x = Node::new(Gate::Input("x".to_string()));
        let y = Node::new(Gate::Input("y".to_string()));
        let add = Node::new(Gate::Add(Box::new(x), Box::new(y)));
        let mul = Node::new(Gate::Mul(Box::new(add), Box::new(Node::new(Gate::Input("y".to_string())))));
        ArithmeticCircuit::new(mul)
    }

    pub fn evaluate(&mut self, inputs: &[(&str, i32)]) -> i32 {
        let input_map: HashMap<String, i32> = inputs.iter().cloned().map(|(k, v)| (k.to_string(), v)).collect();
        self.root.evaluate(&input_map)
    }
}        

Step 3: Parsing the Expression

In a real-world scenario, you’d want to parse the input expression into an arithmetic circuit. However, for simplicity, this example hardcodes the parsing logic. A proper implementation would involve tokenizing the input expression and building the circuit dynamically.

Step 4: Evaluation

The evaluate function recursively computes the value of the circuit by traversing the DAG from the output node back to the input nodes.

Step 5: Testing the Implementation

To test the implementation, you can run the main function defined in lib.rs. It should construct the circuit for the expression (x + y) * y and evaluate it with the given inputs.

cargo run        

Adding Expression Parsing

To add expression parsing to our arithmetic circuit compiler, we can use the nom crate, a powerful parser generator for Rust. 

Step 1: Add Dependencies

First, add nom to your Cargo.toml.

[dependencies]
nom = "7.1"        

Step 2: Implement the Parsing Logic

Modify src/circuit.rs to include the parsing logic and build the circuit based on the parsed expression.

src/circuit.rs

use nom::{
    branch::alt,
    character::complete::{char, digit1},
    combinator::{map, map_res},
    multi::fold_many0,
    sequence::{delimited, pair},
    IResult,
};
use std::collections::HashMap;
use std::str::FromStr;

#[derive(Debug, Clone)]
pub enum Gate {
    Input(String),
    Add(Box<Node>, Box<Node>),
    Sub(Box<Node>, Box<Node>),
    Mul(Box<Node>, Box<Node>),
    Div(Box<Node>, Box<Node>),
    Const(i32),
}

#[derive(Debug, Clone)]
pub struct Node {
    gate: Gate,
    value: Option<i32>,
}

impl Node {
    pub fn new(gate: Gate) -> Self {
        Node { gate, value: None }
    }

    pub fn evaluate(&mut self, inputs: &HashMap<String, i32>) -> i32 {
        if let Some(val) = self.value {
            return val;
        }

        let result = match &mut self.gate {
            Gate::Input(name) => *inputs.get(name).unwrap(),
            Gate::Add(left, right) => left.evaluate(inputs) + right.evaluate(inputs),
            Gate::Sub(left, right) => left.evaluate(inputs) - right.evaluate(inputs),
            Gate::Mul(left, right) => left.evaluate(inputs) * right.evaluate(inputs),
            Gate::Div(left, right) => left.evaluate(inputs) / right.evaluate(inputs),
            Gate::Const(val) => *val,
        };

        self.value = Some(result);
        result
    }
}

pub struct ArithmeticCircuit {
    root: Node,
}

impl ArithmeticCircuit {
    pub fn new(root: Node) -> Self {
        ArithmeticCircuit { root }
    }

    pub fn from_expression(expr: &str) -> Self {
        let root = Self::parse_expression(expr).expect("Failed to parse expression").1;
        ArithmeticCircuit::new(root)
    }

    fn parse_expression(input: &str) -> IResult<&str, Node> {
        let (input, init) = Self::parse_term(input)?;
        fold_many0(
            pair(alt((char('+'), char('-'))), Self::parse_term),
            move || init.clone(),
            |acc, (op, val): (char, Node)| {
                if op == '+' {
                    Node::new(Gate::Add(Box::new(acc), Box::new(val)))
                } else {
                    Node::new(Gate::Sub(Box::new(acc), Box::new(val)))
                }
            },
        )(input)
    }

    fn parse_term(input: &str) -> IResult<&str, Node> {
        let (input, init) = Self::parse_factor(input)?;
        fold_many0(
            pair(alt((char('*'), char('/'))), Self::parse_factor),
            move || init.clone(),
            |acc, (op, val): (char, Node)| {
                if op == '*' {
                    Node::new(Gate::Mul(Box::new(acc), Box::new(val)))
                } else {
                    Node::new(Gate::Div(Box::new(acc), Box::new(val)))
                }
            },
        )(input)
    }

    fn parse_factor(input: &str) -> IResult<&str, Node> {
        alt((
            map_res(digit1, |digit_str: &str| {
                i32::from_str(digit_str).map(|val| Node::new(Gate::Const(val)))
            }),
            map(Self::parse_identifier, |id: &str| {
                Node::new(Gate::Input(id.to_string()))
            }),
            delimited(
                char('('),
                Self::parse_expression,
                char(')'),
            ),
        ))(input)
    }

    fn parse_identifier(input: &str) -> IResult<&str, &str> {
        nom::character::complete::alpha1(input)
    }

    pub fn evaluate(&mut self, inputs: &[(&str, i32)]) -> i32 {
        let input_map: HashMap<String, i32> = inputs.iter().cloned().map(|(k, v)| (k.to_string(), v)).collect();
        self.root.evaluate(&input_map)
    }
}        

Step 3: Update the Main Function

Update the main function to test the expression parsing and circuit evaluation.

src/main.rs

use arithmetic_circuit::circuit::ArithmeticCircuit;

fn main() {
    let expr = "(x + y) * y";
    let mut circuit = ArithmeticCircuit::from_expression(expr);
    let result = circuit.evaluate(&[("x", 2), ("y", 3)]);
    println!("Result: {}", result); // Should print 15
}        

Step 4: Run the Project

Run the project to see the results.

cargo run        

This should output Result: 15.

Generating a Solidity Smart Contract that can verify arithmetic circuit proofs

To generate a Solidity smart contract that can verify arithmetic circuit proofs, we’ll need to translate the arithmetic circuit into Solidity code. This involves generating a contract that can take inputs and compute the output based on the circuit.

Let’s enhance our Rust program to generate Solidity code for the arithmetic circuit.

Step 1: Enhance the Rust Program

First, we’ll update the Rust program to generate Solidity code based on the parsed arithmetic circuit.

src/circuit.rs

Add a method to generate Solidity code for the arithmetic circuit:

use nom::{
    branch::alt,
    character::complete::{char, digit1},
    combinator::{map, map_res},
    multi::fold_many0,
    sequence::{delimited, pair},
    IResult,
};
use std::collections::HashMap;
use std::str::FromStr;

#[derive(Debug)]
pub enum Gate {
    Input(String),
    Add(Box<Node>, Box<Node>),
    Sub(Box<Node>, Box<Node>),
    Mul(Box<Node>, Box<Node>),
    Div(Box<Node>, Box<Node>),
    Const(i32),
}

#[derive(Debug)]
pub struct Node {
    gate: Gate,
    value: Option<i32>,
}

impl Node {
    pub fn new(gate: Gate) -> Self {
        Node { gate, value: None }
    }

    pub fn evaluate(&mut self, inputs: &HashMap<String, i32>) -> i32 {
        if let Some(val) = self.value {
            return val;
        }

        let result = match &mut self.gate {
            Gate::Input(name) => *inputs.get(name).unwrap(),
            Gate::Add(left, right) => left.evaluate(inputs) + right.evaluate(inputs),
            Gate::Sub(left, right) => left.evaluate(inputs) - right.evaluate(inputs),
            Gate::Mul(left, right) => left.evaluate(inputs) * right.evaluate(inputs),
            Gate::Div(left, right) => left.evaluate(inputs) / right.evaluate(inputs),
            Gate::Const(val) => *val,
        };

        self.value = Some(result);
        result
    }

    pub fn to_solidity(&self, counter: &mut usize) -> String {
        match &self.gate {
            Gate::Input(name) => format!("{}[{}]", name, counter),
            Gate::Add(left, right) => {
                let left_sol = left.to_solidity(counter);
                *counter += 1;
                let right_sol = right.to_solidity(counter);
                *counter += 1;
                format!("{} + {}", left_sol, right_sol)
            }
            Gate::Sub(left, right) => {
                let left_sol = left.to_solidity(counter);
                *counter += 1;
                let right_sol = right.to_solidity(counter);
                *counter += 1;
                format!("{} - {}", left_sol, right_sol)
            }
            Gate::Mul(left, right) => {
                let left_sol = left.to_solidity(counter);
                *counter += 1;
                let right_sol = right.to_solidity(counter);
                *counter += 1;
                format!("{} * {}", left_sol, right_sol)
            }
            Gate::Div(left, right) => {
                let left_sol = left.to_solidity(counter);
                *counter += 1;
                let right_sol = right.to_solidity(counter);
                *counter += 1;
                format!("{} / {}", left_sol, right_sol)
            }
            Gate::Const(val) => format!("{}", val),
        }
    }
}

impl Clone for Node {
    fn clone(&self) -> Self {
        Node {
            gate: match &self.gate {
                Gate::Input(name) => Gate::Input(name.clone()),
                Gate::Add(left, right) => Gate::Add(left.clone(), right.clone()),
                Gate::Sub(left, right) => Gate::Sub(left.clone(), right.clone()),
                Gate::Mul(left, right) => Gate::Mul(left.clone(), right.clone()),
                Gate::Div(left, right) => Gate::Div(left.clone(), right.clone()),
                Gate::Const(val) => Gate::Const(*val),
            },
            value: self.value,
        }
    }
}

pub struct ArithmeticCircuit {
    root: Node,
}

impl ArithmeticCircuit {
    pub fn new(root: Node) -> Self {
        ArithmeticCircuit { root }
    }

    pub fn from_expression(expr: &str) -> Self {
        let root = Self::parse_expression(expr).expect("Failed to parse expression").1;
        ArithmeticCircuit::new(root)
    }

    fn parse_expression(input: &str) -> IResult<&str, Node> {
        let (input, init) = Self::parse_term(input)?;
        fold_many0(
            pair(alt((char('+'), char('-'))), Self::parse_term),
            move || init.clone(),
            |acc, (op, val): (char, Node)| {
                if op == '+' {
                    Node::new(Gate::Add(Box::new(acc), Box::new(val)))
                } else {
                    Node::new(Gate::Sub(Box::new(acc), Box::new(val)))
                }
            },
        )(input)
    }

    fn parse_term(input: &str) -> IResult<&str, Node> {
        let (input, init) = Self::parse_factor(input)?;
        fold_many0(
            pair(alt((char('*'), char('/'))), Self::parse_factor),
            move || init.clone(),
            |acc, (op, val): (char, Node)| {
                if op == '*' {
                    Node::new(Gate::Mul(Box::new(acc), Box::new(val)))
                } else {
                    Node::new(Gate::Div(Box::new(acc), Box::new(val)))
                }
            },
        )(input)
    }

    fn parse_factor(input: &str) -> IResult<&str, Node> {
        alt((
            map_res(digit1, |digit_str: &str| {
                i32::from_str(digit_str).map(|val| Node::new(Gate::Const(val)))
            }),
            map(Self::parse_identifier, |id: &str| {
                Node::new(Gate::Input(id.to_string()))
            }),
            delimited(
                char('('),
                Self::parse_expression,
                char(')'),
            ),
        ))(input)
    }

    fn parse_identifier(input: &str) -> IResult<&str, &str> {
        nom::character::complete::alpha1(input)
    }

    pub fn evaluate(&mut self, inputs: &[(&str, i32)]) -> i32 {
        let input_map: HashMap<String, i32> = inputs.iter().cloned().map(|(k, v)| (k.to_string(), v)).collect();
        self.root.evaluate(&input_map)
    }

    pub fn to_solidity(&self) -> String {
        let mut counter = 0;
        let body = self.root.to_solidity(&mut counter);
        format!(
            r#"
pragma solidity ^0.8.0;

contract ArithmeticCircuit {{
    function verify(int256[] memory x, int256[] memory y) public pure returns (int256) {{
        return {};
    }}
}}
"#,
            body
        )
    }
}        

Step 2: Update the Main Function

Update the main function to generate the Solidity smart contract code based on the parsed expression.

src/main.rs

use arithmetic_circuit::circuit::ArithmeticCircuit;

fn main() {
    let expr = "(x+y)*y";
    let mut circuit = ArithmeticCircuit::from_expression(expr);
    let result = circuit.evaluate(&[("x", 2), ("y", 3)]);
    println!("Result: {}", result); // Should print 15
    let solidity_code = circuit.to_solidity();
    println!("{}", solidity_code);
}        

Step 3: Run the Project

Run the project to see the generated Solidity code.

cargo run        

Output

The output should be the Solidity code for a contract that can verify the proof for the given arithmetic circuit. For the expression (x + y) * y, the generated Solidity code would look like this:

pragma solidity ^0.8.0;

contract ArithmeticCircuit {
    function verify(int256[] memory x, int256[] memory y) public pure returns (int256) {
        return x[0] + y[1] * y[2];
    }
}        

You can find the full implementation in my Github repo here.

Conclusion

You now have a Rust program that can parse arithmetic expressions, build arithmetic circuits, evaluate them, and generate Solidity code for a smart contract to verify the proof. This example can be extended to handle more complex expressions and additional operations, making it a versatile tool for generating verifiable computations in Solidity.

🚀 Explore More by Luis Soares

📚 Learning Hub: Expand your knowledge in various tech domains, including Rust, Software Development, Cloud Computing, Cyber Security, Blockchain, and Linux, through my extensive resource collection:

• Hands-On Tutorials with GitHub Repos: Gain practical skills across different technologies with step-by-step tutorials, complemented by dedicated GitHub repositories. Access Tutorials
• In-Depth Guides & Articles: Deep dive into core concepts of Rust, Software Development, Cloud Computing, and more, with detailed guides and articles filled with practical examples. Read More
• E-Books Collection: Enhance your understanding of various tech fields with a series of e-Books, including titles like “Mastering Rust Ownership” and “Application Security Guide” Download eBook
• Project Showcases: Discover a range of fully functional projects across different domains, such as an API Gateway, Blockchain Network, Cyber Security Tools, Cloud Services, and more. View Projects
• LinkedIn Newsletter: Stay ahead in the fast-evolving tech landscape with regular updates and insights on Rust, Software Development, and emerging technologies by subscribing to my newsletter on LinkedIn. Subscribe Here

🔗 Connect with Me:

• Medium: Read my articles on Medium and give claps if you find them helpful. It motivates me to keep writing and sharing Rust content. Follow on Medium
• LinkedIn: Join my professional network for more insightful discussions and updates. Connect on LinkedIn
• Twitter: Follow me on Twitter for quick updates and thoughts on Rust programming. Follow on Twitter

Wanna talk? Leave a comment or drop me a message!

All the best,

Luis Soares luis.soares@linux.com

Lead Software Engineer | Blockchain & ZKP Protocol Engineer | 🦀 Rust | Web3 | Solidity | Golang | Cryptography | Author