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_circuitStep 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 runAdding 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 runThis 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 runOutput
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.
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.
🚀 Discover More Free Software Engineering Content! 🌟
If you enjoyed this post, be sure to explore my new software engineering blog, packed with 200+ in-depth articles, 🎥 explainer videos, 🎙️ a weekly software engineering podcast, 📚 books, 💻 hands-on tutorials with GitHub code, including:
🌟 Developing a Fully Functional API Gateway in Rust — Discover how to set up a robust and scalable gateway that stands as the frontline for your microservices.
🌟 Implementing a Network Traffic Analyzer — Ever wondered about the data packets zooming through your network? Unravel their mysteries with this deep dive into network analysis.
🌟Implementing a Blockchain in Rust — a step-by-step breakdown of implementing a basic blockchain in Rust, from the initial setup of the block structure, including unique identifiers and cryptographic hashes, to block creation, mining, and validation, laying the groundwork.
and much more!
✅ 200+ In-depth software engineering articles
🎥 Explainer Videos — Explore Videos
🎙️ A brand-new weekly Podcast on all things software engineering — Listen to the Podcast
📚 Access to my books — Check out the Books
💻 Hands-on Tutorials with GitHub code
📞 Book a Call
👉 Visit, explore, and subscribe for free to stay updated on all the latest: Home Page
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:
- LinkedIn: Join my professional network for more insightful discussions and updates. Connect on LinkedIn
- X: 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@luissoares.dev
Lead Software Engineer | Blockchain & ZKP Protocol Engineer | 🦀 Rust | Web3 | Solidity | Golang | Cryptography | Author
