Definition of Arithmetic Circuit
Let \(C: \ \mathbb{F}^n \ \rightarrow \ \mathbb{F}^k\) be a map which takes \(n\) arguments from a finite field \(\mathbb{F}\) as inputs and compute \(k\) outputs in \(\mathbb{F}\). \(C\) is an arithmetic circuit if the outputs are determined by the operations \(+\) and \(\times\) to the inputs. We assign the wires in the circuit as \(a_i \) where \(\ i \in {0,…,m}, a_0=1\). We may designate some of the input/output wires as a statement and use the left wires as a witness. A relation \(R\) is a statement that describes some witness wires satisfy the arithmetic circuit.
Given an example:
Transfer Arithmetic Circuit to Polynomials
The goal of Quadratic Arithmetic Programs in zk-SANRK is to transform the circuit to polynomials. Then the fact that a prover knows the coefficients of these polynomials is equivalent to that this prover knows valid assignments \((a_1,a_2,…,a_m)\in \mathbb{F}\) to the circuit.
QAP: Quadratic Arithmetic Programs
For a given circuit \(C\) with assignments \((a_1,a_2,…,a_m)\in \mathbb{F}\), a Quadratic Arithmetic Program \(Q(C)=(\{u_i(x)\}_{i=0}^m,\ \{v_i(x)\}_{i=0}^m,\ \{w_i(x)\}_{i=0}^m,t(x))\) is a set of polynomials satisfy the following equation:
$$\sum\limits_{i=0}^m a_i u_i(x) \cdot \sum\limits_{i=0}^m a_i v_i(x)=\sum\limits_{i=0}^m a_i w_i(x) + h(x)\cdot t(x)$$
The polynomial \(t(x)\) is called target polynomial.
Construction of QAP
In this section we describe how to construct an Quadratic Arithmetic Program for a circuit.
1. Write down all the constraint equation of the gates in the circuit in the format of:
(Left input) operator (right input) = output
For example:
\(a_i \times a_j=a_k\) for multiplication gate
\(1 \times (a_j+a_i)=a_k\) for addition gate
For circuit that has \(n\) gates, we will have \(n\) such equations.
From these equations, we construct:
\(u_{i,j}\) is the coefficient of \(a_i\) in the left input of the \(j\)-th constraint equation. \(v_{i,j}\) is the coefficient of \(a_i\) in the right input of the \(j\)-th constraint equation. \(w_{i,j}\) is the coefficient of \(a_i\) in the output of \(j\)-th constraint equation. \(\circ\) is an element-wise product operation.
For example:
A circuit has two constraints equation from two gates, they are:
\(a_1 \cdot a_2 = a_3\)
\(1 + (a_1+a_2)=a_4\)
Then we can have:
2. For every input \(a_i\), we use its coefficients \(\{u_{i,j}\}_{j=1}^n\) in different constraint to construct a polynomial \(u_i(x)\) with degree at most \(n-1\). Randomly choose \(r_1,…r_n\), let the construction of \(u_i(x)\) satisfies \(u_i(r_j)=u_{i,j}\). Use the same way to construct \(v_i(x),w_i(x)\).
After this step, we transfer the previous matrix equation in step 1 to a equation as following:
3. we get three set of polynomials:
\(\{u_i(x)\}_{i=0}^m\),\(\{v_i(x)\}_{i=0}^m\), \(\{w_i(x)\}_{i=0}^m\)
The following equation holds when \(x \in \{r_1,r_2,…,r_n\}\)
$$\sum\limits_{i=0}^m a_i u_i(x) \cdot \sum\limits_{i=0}^m a_i v_i(x)=\sum\limits_{i=0}^m a_i w_i(x) $$
Let
$$P(x)=\sum\limits_{i=0}^m a_i u_i(x) \cdot \sum\limits_{i=0}^m a_i v_i(x)-\sum\limits_{i=0}^m a_i w_i(x) $$
\(P(x)\) has roots \(r_1,r_2,…,r_n\).
Thus
$$P(x)=\sum\limits_{i=0}^m a_i u_i(x) \cdot \sum\limits_{i=0}^m a_i v_i(x)-\sum\limits_{i=0}^m a_i w_i(x)=h(x)t(x) $$
Then we get:
$$\sum\limits_{i=0}^m a_i u_i(x) \cdot \sum\limits_{i=0}^m a_i v_i(x)=\sum\limits_{i=0}^m a_i w_i(x) + h(x)\cdot t(x)$$
The equation above is called a quadratic arithmetic program for a circuit.
After almost 2 years working in the industry, I start miss the cryptographic challenges again, so I will start picking up my old notes that were written during my PhD, refine them and hope they can bring my old challenges back.
Thanks for sharing. I read many of your blog posts, cool, your blog is very good.