Extension of R1CS to express poseidon's s-box more efficiently

[kunxian-xia]

1. Background

R1CS is not good at expressing high degree multiplications. For example, in order to compute poseidon's s-box ($x \rightarrow x^7$) we have to allocate four more variables ($x_2 = x^2, x_4 = x^4, x_3 = x^3, x_7 = x^7$) with the following constraints:

x * x = x2
x * x2 = x3
x2 * x2 = x4
x3 * x4 = x7

And the poseidon permutation over the goldilocks field has 8 full rounds and 22 partial rounds.
Each full round has to do

1. add round constant for 12 state elements: new_state[i] = state[i] + c[i];
2. s-box applied to 12 state elements: new_state[i] = new_state[i]^7;
3. mds layer applied to 12 state elements: new_state[i] = inner_product(new_state, mds_matrix.row[i]);

The cost is like this

routine	num_constraints generated	num intermediate variables
ARC	12	12
s-box	12 * 4	12 * 4
mds layer	12	12
total	72	72

Partial round differs from full round in that it only applies s-box to one state element.
Therefore the cost for partial round is like

routine	num_constraints generated	num intermediate variables
ARC	12	12
s-box	4	4
mds layer	12	12
total	28	28

Therefore,

1. the number of R1CS constraints will be 72 * 8 + 28 * 22 = 1192.
2. the number of variables will be 72 * 8 + 28 * 22 + 12 = 1204.

If we combined ARC at round $j+1$ with mds layer at round $j$ together, then the total number of R1CS constraints and intermediate variables will be 844 and 856 respectively.

2. Proposal

Let's extend the R1CS constraint ($Az * Bz = Cz$) to the new form $Az * Bz + (Dz)^7 = Cz$. This can reduce the cost of s-box from 4 to 1. And since we have to do (8*12 + 22 = 118) s-box.

This can save us 354 variables and constraints. That is, the number of R1CS' constraints and variables will be 490 and 502 respectively (both less than 2^9).

2.1 Changes to 1st phase sumcheck

This new form means that the 1st phase sumcheck will look like this: $0 = \sum_b \textrm{eq}(\tau, b) * (\tilde{A_z}(b) * \tilde{B_z}(b) - \tilde{C_z}(b)) + \sum_b \textrm{eq}(\tau, b) * \tilde{D_z}^7(b) = \sum_b f(b) + \sum_b g(b)$
where

1. $f(x) = \textrm{eq}(\tau, x) * (\tilde{A_z}(x) * \tilde{B_z}(x) - \tilde{C_z}(x))$; it has degree 3.
2. $g(x) = \textrm{eq}(\tau, x) * \tilde{D_z}^7(x)$; it has degree 8.

@spherel suggests that we can modify the sumcheck prover to send two univariate polynomials at round $j$

1. $p(X) = \sum_{\vec{b}} f(\vec{r_j}, X, \vec{b})$; since it has degree 3, we can just send $p(0), p(1), p(2), p(3)$;
2. $q(X) = \sum_{\vec{b}} g(\vec{r_j}, X, \vec{b})$; since it has degree 8, we need to send $q(0), ..., q(8)$.

That is, the 1st phase sumcheck per round proof's size is increased from 4 to 13 (3 to 11, if we use the compressed univariate polynomial trick).

2.2 Changes to 2nd phase sumcheck

The 2nd sumcheck becomes $r_a * v_a + r_b * v_b + r_c * v_c + r_d * v_d = \sum_y [r_a * A(r_x, y) + r_b * B(r_x, y) + r_c * C(r_x, y) + r_d * D(r_x, y)] * z(y)$.

In the end, we need to evaluate one more sparse polynomial $D(x, y)$ using SPARK.