Circuit Specification

Let \(\mathbb{F}\) be a finite field. In this section, we describe the arithmetic circuit whose operations are over \(\mathbb{F}\).

Let \(\ell_{\mathsf{in}} \in \mathbb{N}\) be the number of input wires of the circuit \(\mathcal{C}\). Assume that \(\mathcal{C}\) has exactly \(n\) gates. Each gate takes at most \(2\) wires as inputs and returns \(1\) output wires. In particular,

• Addition and multiplications gates takes \(2\) inputs and return \(1\) output.
• Gates of additions and multiplications with constants take \(1\) input and return \(1\) output.

Let's take a look at the following example.

Assume that \(f(u, v) = u^2 + 3uv + v + 5\). Then the sequence are arranged in the following constraints, wrapped as below. $$ \begin{cases} z_1 = u \cdot u &\text{(multiplication)},\\ z_2 = u \cdot v &\text{(multiplication)},\\ z_3 = z_2 \cdot 3 &\text{(multiplication with constant)},\\ z_4 = z_1 + z_3 &\text{(addition)},\\ z_5 = z_4 + v &\text{(addition)},\\ z_6 = z_5 + 5 &\text{(addition with constant)}. \end{cases} $$ The input size is \(\ell_{\mathsf{in}} = 2\) for variables \(u, v\) and the output is \(z_6\).