Arithemetic Circuit (RUST)

Arithemetic Circuit implementated in the RUST programming langauge...

Arithmetic circuits RUST implementation

Arithmetic circuits come to us from a field of research called "computational complexity theory" (CCT), and are used as the standard model for computing polynomials. An arithmetic circuit is an abstract concept, but it operates similar to a logic circuit: it takes variables and numbers as inputs, which go through arithmetic gates such as "add" or "multiply", like on the image below. Red boxes are input variables, grey octagon is a constant, green circles are operation gates, and a blue box on the right is the output. 1

arithmetic circuit

The design approach we would be taking is very similar to the implementations in this book.

1. Design the structural interface and Data structures

2. Comment out the step needed for implementing this interface

3. Implement the complete interface

4. Write Unit test. :)

you can find the complete code implementation here

Interface and Data Structure

This circuit need just one method, this method would be responsible for evaluating the circuit on some given input.\

pub trait CircuitInterface {
    fn evaluate<F>(&self, input: &[F]) -> CircuitEvaluation<F>
    where
        F: Add<Output = F> + Mul<Output = F> + Copy;
}

Data Structure

#[derive(Clone, PartialEq, Eq, Hash, Default, Debug)]
pub struct Circuit {
    pub layers: Vec<CircuitLayer>,
}

#[derive(Clone, PartialEq, Eq, Hash, Default, Debug)]
pub struct CircuitLayer {
    pub layer: Vec<Gate>,
}

#[derive(Clone, PartialEq, Eq, Hash, Debug)]
pub struct Gate {
    pub g_type: GateType,
    pub inputs: [usize; 2],
}

#[derive(Clone, PartialEq, Eq, Hash, Debug)]
pub enum GateType {
    Add,
    Mul,
}

Circuit: Represents the entire arithmetic circuit. It contains multiple layers of gates.

CircuitLayer: Represents a single layer within the circuit. Each layer contains multiple gates. This struct helps in organizing gates into different layers, which can be useful for implementing and understanding the flow of computations.

Gate: Represents an individual gate within a layer. Each gate has a type and inputs. The Gate struct represents an individual gate with a specific type and inputs. g_type indicates the type of operation the gate performs (Add or Mul). inputs is an array of two usize values representing the indices of the input gates. These indices refer to the outputs of gates from previous layers or input values.

GateType: Enum defining the types of operations that a gate can perform (addition or multiplication).

An example on how this gate would be constructed is given by;

    // sample circuit evaluation
    //      100(*)    - layer 0
    //     /     \
    //   5(+)_0   20(*)_1 - layer 1
    //   / \    /  \
    //  2   3   4   5
    let layer_0 = CircuitLayer::new(vec![Gate::new(GateType::Mul, [0, 1])]);
    let layer_1 = CircuitLayer::new(vec![
        Gate::new(GateType::Add, [0, 1]),
        Gate::new(GateType::Mul, [2, 3]),
    ]);
    let circuit = Circuit::new(vec![layer_0, layer_1]);

Interface Implementation

In this section, we will discuss the implementation of the CircuitInterface trait for the Circuit struct. This implementation provides a method to evaluate the circuit given some input values. The evaluation involves computing the outputs of each gate in the circuit layer by layer, starting from the inputs.

pub trait CircuitInterface {
    fn evaluate<F>(&self, input: &[F]) -> CircuitEvaluation<F>
    where
        F: Add<Output = F> + Mul<Output = F> + Copy;
}

The evaluate method takes a reference to a slice of inputs and returns a CircuitEvaluation<F>, where F is a generic type that supports addition and multiplication.

The CircuitEvaluation struct holds the results of the circuit evaluation. It contains a vector of layers, where each layer is a vector of values representing the outputs of the gates in that layer.

impl CircuitInterface for Circuit {
    fn evaluate<F>(&self, input: &[F]) -> CircuitEvaluation<F>
    where
        F: Add<Output = F> + Mul<Output = F> + Copy,
    {
        let mut layers = vec![];
        let mut current_input = input;
        layers.push(input.to_vec());

        for layer in self.layers.iter().rev() {
            let temp_layer: Vec<_> = layer
                .layer
                .iter()
                .map(|e| match e.g_type {
                    GateType::Add => current_input[e.inputs[0]] + current_input[e.inputs[1]],
                    GateType::Mul => current_input[e.inputs[0]] * current_input[e.inputs[1]],
                })
                .collect();
            layers.push(temp_layer);
            current_input = &layers[layers.len() - 1];
        }

        layers.reverse();
        CircuitEvaluation { layers }
    }
}

The evaluate method processes the circuit in a reverse manner, starting from the input layer and working backwards through the layers of gates.

Explanation

1. Initialization:

• The method starts by initializing an empty vector layers to hold the results of each layer.

• current_input is set to the initial input provided to the evaluate method. • The initial input is added to the layers vector.

1. Layer Processing: • The method iterates over the circuit layers in reverse order using self.layers.iter().rev(). • For each layer, it processes each gate by iterating over layer.layer. • Depending on the gate type (GateType::Add or GateType::Mul), it evaluates the gate using the current inputs. • The results of the gates in the current layer are collected into temp_layer. • temp_layer is added to the layer's vector. • current_input is updated to refer to the outputs of the current layer.

2. Finalization: • After processing all layers, the layers vector is reversed to get the correct order of layers from input to output. • A CircuitEvaluation struct is created with the layer's vector and returned.

Here is a sample code for building and executing a Circuit given some input.

    // sample circuit evaluation
    //      100(*)    - layer 0
    //     /     \
    //   5(+)_0   20(*)_1 - layer 1
    //   / \    /  \
    //  2   3   4   5
    
	let layer_0 = CircuitLayer::new(vec![Gate::new(GateType::Mul, [0, 1])]);
    let layer_1 = CircuitLayer::new(vec![
        Gate::new(GateType::Add, [0, 1]),
        Gate::new(GateType::Mul, [2, 3]),
    ]);
    let circuit = Circuit::new(vec![layer_0, layer_1]);
    let input = [
        Fr::from(2u32),
        Fr::from(3u32),
        Fr::from(4u32),
        Fr::from(5u32),
    ];
    let evaluation = circuit.evaluate(&input);