Review

Check out my notes on Polynomial Factorization.

R1CS Problem Statement

Given a polynomial where we know secret value \(x\) and a polynomial which evalutes to a public computation:

\[\displaylines{ x^3 + 5 + 5 = n\\ \\ x^3 + x + 5 = 35 }\]

Expand Statement into an arithmetic circuit

\[\begin{array}{|c|c|c|} \hline a = x \times x & x^2\\ \hline b = a \times x & x^3\\ \hline c = b + x & x^3 + x\\ \hline d = c + 5 & x^3 + x + 5\\ \hline \end{array}\]

Arithmetic Circuit

graph LR
   ci3 --> sq2[MUL] --> ci5((b))
   ci4((x)) --> sq2
   ci5 --> sq3
   sq3 --> ci7((c))
   ci8((5)) --> sq4[ADD]
   sq4 --> si9((d)) --> di{35}
   ci7 --> sq4
   ci6((x)) --> sq3[ADD]
   ci1((x)) --> sq1[MUL] --> ci3((a))
   ci2((x)) --> sq1

This circuit has 6 variables and 4 gates

\[\displaylines{ variables = \begin{bmatrix} 1 & x & a & b & c & d\\ \end{bmatrix}\\ gates = \begin{bmatrix} a & b & c & d \end{bmatrix} = \begin{bmatrix} \times & \times & + & + \end{bmatrix} }\]

Converting the circut into a set of constraint vectors

This will be a vector of \(s\) values where \(s\) is is the number of variables

Our solution vector \(S\)

\[\displaylines{ (a_s) \times (b_s) = c_s \\ \begin{array}{|c|c|c|c|c|c|c|} \hline S = & 1 & x & a & b & c & d\\ \hline x = & 1 & 3 & 9 & 27 & 30 & 35\\ \hline \end{array}\\ \\ a = x \times x\\ \begin{array}{|c|c|c|c|c|c|c|} \hline S = & 1 & x & a & b & c & d\\ \hline x = & 1 & 3 & 9 & 27 & 30 & 35\\ \hline a = & 0 & 1 & 0 & 0 & 0 & 0\\ \hline b = & 0 & 1 & 0 & 0 & 0 & 0\\ \hline c = & 0 & 0 & 1 & 0 & 0 & 0\\ \hline \end{array}\\ \\ b = a \times x\\ \begin{array}{|c|c|c|c|c|c|c|} \hline S = & 1 & x & a & b & c & d\\ \hline x = & 1 & 3 & 9 & 27 & 30 & 35\\ \hline a = & 0 & 0 & 1 & 0 & 0 & 0\\ \hline b = & 0 & 1 & 0 & 0 & 0 & 0\\ \hline c = & 0 & 0 & 0 & 1 & 0 & 0\\ \hline \end{array}\\ \\ c = b + x \times 1\\ \begin{array}{|c|c|c|c|c|c|c|} \hline S = & 1 & x & a & b & c & d\\ \hline x = & 1 & 3 & 9 & 27 & 30 & 35\\ \hline a = & 0 & 1 & 0 & 1 & 0 & 0\\ \hline b = & 1 & 0 & 0 & 0 & 0 & 0\\ \hline c = & 0 & 0 & 0 & 0 & 1 & 0\\ \hline \end{array}\\ \\ d = c + 5 \times 1\\ \begin{array}{|c|c|c|c|c|c|c|} \hline S = & 1 & x & a & b & c & d\\ \hline x = & 1 & 3 & 9 & 27 & 30 & 35\\ \hline a = & 5 & 0 & 0 & 0 & 1 & 0\\ \hline b = & 1 & 0 & 0 & 0 & 0 & 0\\ \hline c = & 0 & 0 & 0 & 0 & 0 & 1\\ \hline \end{array} }\]

R1CS to QAP

Determine the degree of polynomial. Our example has 4 equations so we will need a polynomial of degree 3

We will need 6 polynomials of degree 3 such that it evaluates at 1

\[\displaylines{ a = x \times x\\ a_1(1) = 0 & b_1(1) = 0 & c_1(1) = 0\\ a_2(1) = 1 & b_2(1) = 1 & c_2(1) = 0\\ a_3(1) = 0 & b_3(1) = 0 & c_3(1) = 1\\ a_4(1) = 0 & b_4(1) = 0 & c_4(1) = 0\\ a_5(1) = 0 & b_5(1) = 0 & c_5(1) = 0\\ a_6(1) = 0 & b_6(1) = 0 & c_6(1) = 0\\ }\] \[\displaylines{ b = a \times x\\ a_1(2) = 0 & b_1(2) = 0 & c_1(2) = 0\\ a_2(2) = 0 & b_2(2) = 1 & c_2(2) = 0\\ a_3(2) = 1 & b_3(2) = 0 & c_3(2) = 0\\ a_4(2) = 0 & b_4(2) = 0 & c_4(2) = 1\\ a_5(2) = 0 & b_5(2) = 0 & c_5(2) = 0\\ a_6(2) = 0 & b_6(2) = 0 & c_6(2) = 0\\ }\] \[\displaylines{ c = b + x \times 1\\ a_1(3) = 0 & b_1(3) = 1 & c_1(3) = 0\\ a_2(3) = 1 & b_2(3) = 0 & c_2(3) = 0\\ a_3(3) = 0 & b_3(3) = 0 & c_3(3) = 0\\ a_4(3) = 1 & b_4(3) = 0 & c_4(3) = 0\\ a_5(3) = 0 & b_5(3) = 0 & c_5(3) = 1\\ a_6(3) = 0 & b_6(3) = 0 & c_6(3) = 0\\ }\] \[\displaylines{ d = c + 5 \times 1\\ a_1(4) = 5 & b_1(4) = 1 & c_1(4) = 0\\ a_2(4) = 0 & b_2(4) = 0 & c_2(4) = 0\\ a_3(4) = 0 & b_3(4) = 0 & c_3(4) = 0\\ a_4(4) = 0 & b_4(4) = 0 & c_4(4) = 0\\ a_5(4) = 1 & b_5(4) = 0 & c_5(4) = 0\\ a_6(4) = 0 & b_6(4) = 0 & c_6(4) = 1\\ }\] \[\displaylines{ a_1(1) = 0 & b_1(1) = 0 & c_1(1) = 0\\ a_1(2) = 0 & b_1(2) = 0 & c_1(2) = 0\\ a_1(3) = 0 & b_1(3) = 1 & c_1(3) = 0\\ a_1(4) = 5 & b_1(4) = 1 & c_1(4) = 0\\ }\]

Create the constraint

\[\displaylines{ (a_1 \cdot 1) + (a_2 \cdot x) + (a_3 \cdot a) + (a_4 \cdot b) + (a_5 \cdot c) + (a_6 \cdot d)\\ \times\\ (b_1 \cdot 1) + (b_2 \cdot x) + (b_3 \cdot a) + (b_4 \cdot b) + (b_5 \cdot c) + (b_6 \cdot d)\\ =\\ (c_1 \cdot 1) + (c_2 \cdot x) + (c_3 \cdot a) + (c_4 \cdot b) + (c_5 \cdot c) + (c_6 \cdot d)\\ \\ x = 1, 2, 3, 4 \\ }\]

---