Someone's Intermediate Representation


Linear PCP and Random Stuffs

Just trying to take notes about R1CS/QAP/SSP/PCP and sort out things.

Partly adopted from QAP from Zero to Hero by Vitalik Buterin.

graph LR
P(Problem) -->|Flatten| C(Circuit)
subgraph Problem Translate
C -->|Synthesize| R(R1CS)
R -->|FFT| Q(QAP)
subgraph Verification
Q -->|Create Proof| Pr(Proof)
Q -->|Setup| Pa(Params)
Pa -->|Create Proof| Pr
Pr -->|Verify Proof| V(Verify)
Pa -->|Verify Proof| V

R1CS and QAP

If we want to prove that we have a solution for something without sending all these solutions in clear to verifier, we will need these techniques.

We constrain the context into proving we know solution for a polynomial function $f(x_1,\dots, x_k)$.

R1CS Definition

The relation $\mathcal{R}_{\text{R1CS}}$ consists of a set of all pairs $((\mathbb{F}, k, m, n, A,B,C,v), w)$ where

  • $\mathbb{F}$ is a finite field
  • $k$ be the number of inputs
  • $n$ be the number of variables
  • $m$ be the number of constraints
  • $A,B,C\in\mathbb{F}^{m\times (n+1)}$
  • $v \in \mathbb{F}^{k}$
  • $w \in \mathbb{F}^{n-k}$

If a pair is in such relation set, it must satisfy $(A \cdot z) \circ (B\cdot z) = C\cdot z$ where $z = (1, v,w)$ and $\circ$ stands for Hadamard Production (entry-wise product).

R1CS and Polynomial, or Arithmetic Circuit

So, obviously, a polynomial of form $f(x_1, \dots, x_k)$ with operation $+,\times$ can be written or flatten into an arithmetic circuit with binary gates of $+,\times$.

By R1CS, a gate means one constraint. So each entry of $A,B,C$, donated by $A_i,B_i,C_i$ where $i \in \lbrack 1,m \rbrack$ must satisfy $\langle A_i, z\rangle \cdot \langle B_i ,z\rangle = \langle C_i,z\rangle$.

In this way, the matrix-vector production checks each matrix entry for $m$ times by $(A_1,\dots, A_m)^\top\cdot z \equiv (\langle A_1,z\rangle,\dots,\langle A_m,z\rangle)^\top$.

The problem then lies in each entry, why we need to satisfy $\langle A_i, z\rangle \cdot \langle B_i ,z\rangle = \langle C_i,z\rangle$.

We let the $\langle C_i,z\rangle$ be the output for this gate, where $\langle C_i,z\rangle \in \lbrace w_i\rbrace$.

The left side of the previous entry equation represents the computation of the gate.

  • If the gate is an add gate $+$, then $\langle A_i,z\rangle$ can represent the addition, while $\langle B_i,z\rangle$ represents the constant 1. Such addition gate is satisfied. (vise versa for $A,B$)
  • If the gate is an mult gate $\times$, then $\langle A_i,z\rangle$ represents the left input, while $\langle B_i,z\rangle$ represents the right input. The scalar multiplication does the gate computation.


So far, we have $A,B,C \in \mathbb{F}^{m\times (n+1)}$ and $z \in \mathbb{F}^{n+1}$. If we want to hide $z$ witness better, then we need to transfer R1CS to QAP.

For a matrix $M \in \mathbb{F}^{m\times(n+1)}$, we can represent the columns as $M_i(x)$ for $i \in \lbrack 1, n+1\rbrack$ with a corresponding $\lbrace x_i\rbrace$. Then $M = (M_1(x),\dots,M_{n+1}(x))\ |_{x_1,\dots,x_m}$.

If we transform $A,B,C$ to such form, then we have $\langle A,z\rangle \cdot \langle B,z\rangle =_{\text{polynomial}} \langle C,z\rangle$ to be checked.

The detail for such transform lies in Lagrange Polynomial Interpolation.

The polynomial $\langle A , z \rangle \cdot \langle B,z\rangle - \langle C , z \rangle$ should be able to be divided by $\prod (x - x_i)$ without remainder, which means $\exists H(x), \langle A , z \rangle \cdot \langle B,z\rangle - \langle C , z \rangle = H(x) \prod (x - x_i)$.

It seems more interesting to have QAP than R1CS since the elements are all polynomials.

Schwartz-Zippel Lemma

Consider polynomials over $\mathbb{F}_p$, $P(X_1,\dots,X_n)$. They compute functions $\mathbb{F}_p^n \to \mathbb{F}_p$. There exists $p^{p^n}$ such functions, but there are infinitely many polynomials.

$X_1,\dots,X_n$ has $p^n$ and output $p$ probabilities. Thus $p^{p^n}$ such functions exists.

In this way, we can have multiple non identical polynomials representing the same function. The differentiation of these polynomials is zero function.

E.g., $X^p - X$ for $\mathbb{F}_p$.

Given any $P \in \mathbb{F}_p \lbrack X_1,\dots,X_n\rbrack$ can reduce each $X^m$ to $X^{m\mod p}$. So these individual degrees (for each variable) are smaller than or equal to $p - 1$.

Thus the total reduced degree (the largest degree of monomial) is $p^n$, and the reduced polynomial number is $p^{p^n}$.

In this way, we let $P \in \mathbb{F}_p\lbrack X_1,\dots,X_n\rbrack$ be reduced nonzero polynomial of total degree $\le d < p$. We also let $\alpha_1,\dots,\alpha_n \overset{R}{\leftarrow} \mathbb{F}_p$. Then $\Pr\lbrack P(\alpha_1,\dots,\alpha_n) = 0\rbrack \le \dfrac{d}{p}$.

If $p = 2$ then $\Pr\lbrack P(\alpha_1,\dots,\alpha_n) \neq 0\rbrack \ge \dfrac{1}{2^d}$.

We assume the theorem is true for $n-1$ variables. Let $k$ be the largest individual degree for $X_1$ in any monomial, then $P(X_1,\dots,X_n) = \sum\limits^k_{i=0} X_1^i \cdot q_i(X_2, \dots, X_n)$.

$q_k$ degree is at most $d - k$, by induction $\Pr\lbrack q_k(y_2,\dots,y_n) = 0\rbrack \le \dfrac{d - k}{p}$ for $y_2,\dots,y_n \overset{R}{\leftarrow} \mathbb{F}_p$.

Donate $q_k(y_2,\dots,y_n) = 0$ as event $\varepsilon_1$, $f(X_1) = P(X_1, y_2,\dots,y_n)$. By induction we also have $\Pr\lbrack f(y_1) = 0 | \neg \varepsilon_1\rbrack \le \dfrac{k}{p}$ for $y_1 \overset{R}{\leftarrow} \mathbb{F}_p$.
\Pr\lbrack f(y_1 ) = 0\rbrack &= \Pr\lbrack f(y_1 ) = 0 | \varepsilon_1\rbrack \cdot \Pr \lbrack \varepsilon_1\rbrack + \Pr\lbrack f(y_1 ) = 0 | \neg \varepsilon_1\rbrack \cdot \Pr \lbrack \neg \varepsilon_1\rbrack\newline
&\le \Pr\lbrack f(y_1 ) = 0 | \varepsilon_1\rbrack \cdot \dfrac{d- k}{p} + \dfrac{k}{p}\newline
&\le \dfrac{d}{p}

QAP and SWH-Encryption

SWH means somewhat-homomorphic encryption.

We denote public inputs to be $\boldsymbol{x}$ and private inputs to be $\boldsymbol{w}$. We have proof to be $\pi = \left[ 1,\boldsymbol{x},\boldsymbol{w} \right]^\top$.

By previous QAP construction, we want to hide the R1CS coefficients so that verifiers cannot guess the proof private inputs.

Denote $t \overset{R}{\leftarrow}\mathbb{F}$ and $A_t,B_t,C_t, H_t$ be the QAP polynomial matrices evaluated on $t$. Then we want to satisfy that $\langle A_t, \pi\rangle \cdot \langle B_t,\pi\rangle - \langle C_t , \pi \rangle = H_t \cdot \prod (t - x_i)$.

Generate some $t$ and send SWH encrypted $\lbrace A_t, B_t, C_t, H_t \rbrace$ as common reference string to public.

By SWH encryption scheme feature, the linear combination on $\pi$ proof should hold.

FFT and Polynomial

For previously talked about QAP, we have to interpolate polynomials. We are transforming $A \cdot z$ to $\langle A_p, z\rangle$ where $A_p$ is the vector of polynomials for $A$ over $x_1,\dots,x_m$ for $m$ constraints.

$A_p = (A_{p_0}(x), \dots, A_{p_{n+1}}(x))$, so $A_p|_{x_1,\dots,x_m} = (A_p(x_1),\dots,A_p(x_m))^\top$.

For every column, we get a $A_{p_i}$ for some $i \in \lbrack 1 ,m \rbrack$. Consider for one $A_{p_i}$ (to represent $A$ column $i$) we have
1 & x_1 & \dots &x_1^{m-1} \newline
\vdots & \vdots & &\vdots \newline
1 & x_m & \dots &x_m^{m-1}
\end{bmatrix} \cdot
a_0 \newline \vdots \newline a_m
\end{bmatrix} =
A\text{ column }i

The basic idea was to use $g(x) = \sum\limits^{m-1}_{i=0} f_i I_i(x)$, where $I_i(x_j) = \begin{cases} 0 &i \neq j \newline 1 & i = j \end{cases}$.

We can have $I_i(x) = \prod\limits_{k \in \lbrack 0, m-1 \rbrack \backslash \lbrace i \rbrace}\dfrac{x - x_k}{x_i - x_k}$.

Still, to evaluate such $\prod (x - x_k)$ will need $O(n^2)$ if we go brute force.

FFT/IFFT and Polynomial Multiplication/Interpolation

If we want the brute force $A(x) \cdot B(x)$ or do interpolation for some $A(x)$, then it is obvious that $O(n^2)$.

We consider $n$ to be the power of 2 for simplicity.

Consider $\omega_n$ be a root of unity, then it has feature $\omega_n^n \equiv 1$. In this way we have

  • $\omega^{2k}_{2n} = \omega^k_n$.
  • $\omega_n^{k + \frac{n}{2}} = -\omega_n^k$.

Considering interpolation, where we are considering $\lbrack A(\omega_n^0),\dots,A(\omega_n^{n-1})\rbrack$ for $x = \omega_n^0,\dots,\omega^{n-1}_n$.

We can separate $A=\sum\limits^{n-1}_{i=0}a_i x^i$ into $A = A^{\lbrack 1\rbrack}(x^2) + xA^{\lbrack 2\rbrack}(x^2)$ where

  • $A^{\lbrack 1\rbrack}(x^2) = \sum\limits_{i = 0,2,\dots,n-2} a_i x^i = \sum\limits_{i = 0,2,\dots,n-2} a_i (x^2)^{\frac{i}{2}}$. So $A^{\lbrack 1\rbrack} = \sum\limits_{i = 0,2,\dots,n-2} a_i x^{\frac{i}{2}}$.
  • $xA^{\lbrack 2\rbrack}(x^2) = \sum\limits_{i = 1,3,\dots,n-1} a_i x^i = x \sum\limits_{i = 0, 2, \dots, n-2}a_{i+1}x^i = x \sum\limits_{i = 0, 2, \dots, n-2}a_{i+1}(x^2)^{\frac{i}{2}}$. So $A^{\lbrack 2\rbrack} = \sum\limits_{i = 0, 2, \dots, n-2}a_{i+1}x^{\frac{i}{2}}$.

If we want to know $A(\omega_n^k)$, we do $A(\omega_n^k) = A^{\lbrack 1 \rbrack} (\omega^k_{\frac{n}{2}}) + \omega_n^k A^{\lbrack 2\rbrack}(\omega^k_{\frac{n}{2}})$. ($k \in \lbrack 0, \dfrac{n}{2} - 1\rbrack$)

If we want to know $k + \dfrac{n}{2}$ scenario, $A(\omega_n^{k + \frac{n}{2}}) = A^{\lbrack 1 \rbrack} (\omega^k_{\frac{n}{2}}) - \omega_n^k A^{\lbrack 2\rbrack}(\omega^k_{\frac{n}{2}})$.

If we know $A^{\lbrack 1\rbrack},A^{\lbrack 2\rbrack}$ for $\omega_{\frac{n}{2}}^k$ $\forall k \in \lbrack 0, \dfrac{n}{2} - 1\rbrack$, we can solve $\forall k \in \lbrack 0, n-1 \rbrack, A(x)|_{x = \omega_n^k}$ in $O(n)$.

By $T(n) = 2 T(\dfrac{n}{2}) + O(n)$ we have $T(n) = O(n\log n)$.

IFFT is used to get $(a_0,\dots,a_{n-1})$ coefficients by $(A(\omega_n^{0}),\dots,A(\omega_n^{n-1}))$, which is used for fast interpolation.

Since we the required value $\lbrace A(\omega_n^i)\rbrace$ is given by the R1CS, then we don’t need to worry about these computations for $\lbrace A(\omega_n^i)\rbrace$.

IFFT follows a similar step like FFT. We construct polynomial $F(x) = \sum\limits^{n-1}_{i=0} d_i x^i$ where $\lbrace d_i\rbrace = (A(\omega_n^{0}),\dots,A(\omega_n^{n-1}))$.

We use the polynomial to FFT get $(c_0, \dots,c_{n-1})$ for $(F(\omega_n^{0}),\dots,F(\omega_n^{-(n-1)}))$ or $\lbrace F(\omega_n^{-k})\rbrace$.

$c_k = \sum\limits^{n-1}_{i = 0} \lbrack \sum \limits^{n-1}_{j=0} a_j \cdot (\omega_n^i)^j\rbrack \cdot (\omega^{-k}_n)^i = \sum\limits^{n-1}_{i = 0}\lbrack \sum \limits^{n-1}_{j = 0} a_j \cdot (\omega_n^i)^{j-k}\rbrack$. It is obvious that $c_k = n a_k$. Thus $\lbrace a_k \rbrace = \lbrace \dfrac{c_k}{n}\rbrace$.

IFFT takes also $O(n\log n)$ like FFT.

The polynomial multiplication brute force can be considered as $A:a_0,\dots,a_{n-1}, B:b_0,\dots,b_{n-1}$ to $C: c_0,\dots,c_{2n-1}$ which takes $O(n^2)$.

With FFT/IFFT we can finish following process:

  • $A:a_0,\dots,a_{n-1}, B:b_0,\dots,b_{n-1}$ to $\lbrace A(\omega_{2n}^k)\rbrace, \lbrace B(\omega_{2n}^k)\rbrace$ takes $O(n\log n)$.
  • $\lbrace A(\omega_{2n}^k)\rbrace, \lbrace B(\omega_{2n}^k)\rbrace$ to $\lbrace C(\omega_{2n}^k)\rbrace$ takes $O(n)$.
  • $\lbrace C(\omega_{2n}^k)\rbrace$ to $C : c_0 ,\dots,c_{2n-1}$.

So the total cost comes to $O(n\log n)$.