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…
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
