# Verification of SPS

## Non-relaxed verification of SPS

$$
V_{sps}(pi, [m_i]_{i = 1}^k, [r_i]_{i = 1}^{k - 1}) := \sum_{j = 0}^{d} f_j^{V_{sps}}(pi, [m_i]_{i = 1}^k, [r_i]_{i = 1}^{k - 1}) \overset{?}= \vec{0}
$$

The job of verifier of SPS is to check if the summation result within above equation equals $\vec{0}$, which is a vector with length $l$.

<br />

Watch closely into the summation expression you can get:
1. it has $d + 1$ items, each of which is a degree $j$ sub-expression $f_j^{V_{sps}}$ of the whole algebraic expression $f^{V_{sps}}$, if the degree of $f^{V_{sps}}$ is $d$
2. it has multiple prover messages $m_i$, and challenge factors $r_i$ in the whole SPS protocol
3. we can customize the sub-expression $f_j^{V_{sps}}$ in our protocol

<br />

## Relaxed verification of SPS
Similarly we can get the relaxed verification equation:
$$
V_{sps}(pi, \pi.x, \pi.\mathbf{w}, [r_i]_{i = 1}^{k - 1}, \mu) := \sum_{j = 0}^{d} \mu^{d - j} * f_j^{V_{sps}}(pi, \pi.\mathbf{w}, [r_i]_{i = 1}^{k - 1}) \overset{?}= \mathbf{e}
$$

while:
$$
\pi.x = [C_i]_{i = 1}^k, \pi.\mathbf{w} = [m_i]_{i = 1}^k
$$

<br />

In relaxed mode the result of algebraic expression being verified would be cross term $E$ with length $l$, not a zero vector $\vec{0}$ anymore here.

## $f_j^{V_{sps}}$ in relaxed R1CS

In the first place, let's see how does it like in relaxed R1CS relation $\cal{R_{r1cs}}$:
$$
A z \circ B z - u C z = E
$$

Ignoring the public inputs/outpus, we can easily get the sub-expressions like:
$$
\begin{aligned}
f_0^{V_{sps}}(-,[z], []) &= 0 \\
\\
f_1^{V_{sps}}(-,[z], []) &= (-C z) \\
\\
f_2^{V_{sps}}(-,[z], []) &= (A z \circ B z) \\
\end{aligned}
$$

<br />

It's simple indeed, we can grab three import things here:

1. since $k = 1$ in **R1CS SPS protocol**, so there's no random challenge factor $r_i$
2. there is only **ONE** witness vector $z$
3. the maximum degree of the SPS verification polynomial is 2, yes $d = 2$ precisely speaking

<br />

## $f_j^{V_{sps}}$ in relaxed Plonkish

Before approching relaxed plonkish, let's see what the non-relaxed (standard) plonkish one looks like.

#### verification of Gate/Wiring constrain
$$
\vec{0} \overset{?}= \underbrace{q_L(X) * \color{red}{w_a(X)}}_{m_1} + \underbrace{q_R(X) * \color{red}{w_b(X)}}_{m2} + \underbrace{q_M(X) * \color{red}{w_a(X)} * \color{red}{w_b(X)}}_{m3} - \underbrace{q_O(X) * \color{red}{w_c(X)}}_{m_4} + \underbrace{q_C(X)}_{m_5} + \underbrace{\color{red}{\phi(X)}}_{m_6}
$$

<br />

It's a much more sophisticated verification identity than R1CS! No worry, let's grab two import informations here:

1. since $k = 1$ in **Gate/Wiring SPS protocol**, so there's no random challenge factor $r_i$

<br />

2. the red color indicates witness vector/polynomial, so there are **FOUR** witness vectors/polynomials in total, they are $w_a(X), w_b(X), w_c(X), \phi(X)$

<br />

3. the maximum degree of the SPS verification polynomial is 2, yes $d = 2$ precisely speaking

<br />

#### compute $f_j^{V_{sps}}$ one-by-one

$$
\begin{aligned}
f_0^{V_{sps}}(pi, \{w_a(X), w_b(X), w_c(X), \phi(X), z(X), t(X)\}, []) &= q_C(X) \\
\\
f_1^{V_{sps}}(pi, \{w_a(X), w_b(X), w_c(X), \phi(X), z(X), t(X)\}, []) &= q_L(X) * \color{red}{w_a(X)} + q_R(X) * \color{red}{w_b(X)} + (-q_O(X)) * \color{red}{w_c(X)} + \color{red}{\phi(X)} \\
\\
f_2^{V_{sps}}(pi, \{w_a(X), w_b(X), w_c(X), \phi(X), z(X), t(X)\}, []) &= q_M(X) * \color{red}{w_a(X) w_b(X)} \\
\end{aligned}
$$

<br />

# Uncompressed Relaxed Plonk Proving System

Let's recall the relaxed verification of SPS:
$$
V_{sps}(pi, \pi.x, \pi.\mathbf{w}, [r_i]_{i = 1}^{k - 1}, \mu) := \sum_{j = 0}^{d} \mu^{d - j} * f_j^{V_{sps}}(pi, \pi.\mathbf{w}, [r_i]_{i = 1}^{k - 1}) \overset{?}= \mathbf{e}
$$

So in plonkish **Gate/Wiring SPS protocol**, we can instantiate it like below:
$$
\begin{aligned}
V_{sps}(pi, \{\widetilde{w_a}, \widetilde{w_b}, \widetilde{w_c}, \widetilde{\phi}\}, \{\color{red}{w_a}, \color{red}{w_b}, \color{red}{w_c}, \color{red}{\phi}\}, [-], \mu) &= \mu^4 * f_0 + \mu^3 * f_1 + \mu^2 * f_2 + \mu^1 * f_3 + \mu^0 * f_1 \\
&\overset{?}= \mathbf{e}\\
\end{aligned}
$$

<br />

The incremetal **relaxed instance-witness pair** would be like:
$$
\pi.\mathbf{w} = \{\color{red}{w_a}, \color{red}{w_b}, \color{red}{w_c}, \color{red}{\phi}, \mathbf{0}\}\\
\\
\pi.x = \{pi,\widetilde{w_a}, \widetilde{w_b}, \widetilde{w_c}, \widetilde{\phi}, \widetilde{0}, 1\}\\
$$

While the running **relaxed instance-witness pair** would be like:
$$
acc.\mathbf{w} = \{\color{red}{w_a}, \color{red}{w_b}, \color{red}{w_c}, \color{red}{\phi}, \color{red}{e}\}\\
\\
acc.x = \{pi, \widetilde{w_a}, \widetilde{w_b}, \widetilde{w_c}, \widetilde{\phi}, \widetilde{e}, \mu\}\\
$$

<br />

The plonkish backend should take $acc$ as input, and generate proofs for the **relaxed verification of SPS**, kzg10 opening proofs for the **4 + 1** witness polynomials precisely speaking.

<br />

# Uncompressed Cross Term Underneath of SPS

For simplicity we take a NARK verification example like this:

$$
1 * a(X) * b(X) * c(X) * d(X) + 2 * e(X) * f(X) * g(X) + 3 * h(X) * i(X) + 4 * j(X) + 5 = 0
$$

<br />

two NARK verification to be folded:
$$
\begin{aligned}
u_1^0 * 1 * a_1(X) * b_1(X) * c_1(X) * d_1(X) + u_1^1 * 2 * e_1(X) * f_1(X) * g_1(X) + u_1^2 * 3 * h_1(X) * i_1(X) + u_1^3 * 4 * j_1(X) + u_1^4 * 5 &= E_1 \\
\\
u_2^0 * 1 * a_2(X) * b_2(X) * c_2(X) * d_2(X) + u_2^1 * 2 * e_2(X) * f_2(X) * g_2(X) + u_2^2 * 3 * h_2(X) * i_2(X) + u_2^3 * 4 * j_2(X) + u_2^4 * 5 &= E_2 \\
\end{aligned}
$$

while $u_2 = 1, E_2 = 0$

<br />

Our target is to get a folded NARK verification like this:
$$
u_3^0 * 1 * a_3(X) * b_3(X) * c_3(X) * d_3(X) + u_3^1 * 2 * e_3(X) * f_3(X) * g_3(X) + u_3^2 * 3 * h_3(X) * i_3(X) + u_3^3 * 4 * j_3(X) + u_3^4 * 5 = E_3 \\
$$

while the witness part and slack variable are:
$$
\begin{aligned}
u_3 &= u_1 + r * u_2 \\
a_3 &= a_1 + r * a_2 \\
b_3 &= b_1 + r * b_2 \\
c_3 &= c_1 + r * c_2 \\
d_3 &= d_1 + r * d_2 \\
e_3 &= e_1 + r * e_2 \\
f_3 &= f_1 + r * f_2 \\
g_3 &= g_1 + r * g_2 \\
h_3 &= h_1 + r * h_2 \\
i_3 &= i_1 + r * i_2 \\
j_3 &= j_1 + r * j_2 \\
\end{aligned}
$$

<br />

and the error term part will be:
$$
E_3 = E_1 + r^4 * E_2 + \boxed{r^3 * T_3 + r^2 * T_2 + r^1 * T_1}
$$

<br />

We have four degree-parts to be crossed:

|Degree|Slack|M_1|M_2|M_3|M_4|
|--|---|---|---|---|---|
|4|-|$a(X)$|$b(X)$|$c(X)$|$d(X)$|
|3|$u^1$|$e(X)$|$f(X)$|$g(X)$|-|
|2|$u^2$|$h(X)$|$i(X)$|-|-|
|1|$u^3$|$j(X)$|-|-|-|
|0|$u^4$|-|-|-|-|

<br />

cross terms degree-by-degree:
$$
\begin{aligned}
T^{(4)} &= r^3 * T^{(4)}_3 + r^2 * T^{(4)}_2 + r^1 * T^{(4)}_1 \\
T^{(3)} &= r^3 * T^{(3)}_3 + r^2 * T^{(3)}_2 + r^1 * T^{(3)}_1 \\
T^{(2)} &= r^2 * T^{(2)}_2 + r^1 * T^{(2)}_1 \\
T^{(1)} &= r^1 * T^{(1)}_1 \\
\end{aligned}
$$

<br />

the cross terms :
$$
\begin{aligned}
T^{(4)}_3 &= a_1(X) * b_2(X) * c_2(X) * d_2(X) + a_2(X) * b_1(X) * c_2(X) * d_2(X) + a_2(X) * b_2(X) * c_1(X) * d_2(X) + a_2(X) * b_2(X) * c_2(X) * d_1(X) \\
\\
T^{(4)}_2 &= a_1(X) * b_1(X) * c_2(X) * d_2(X) + a_1(X) * b_2(X) * c_1(X) * d_2(X) + a_2(X) * b_1(X) * c_1(X) * d_2(X) + a_1(X) * b_2(X) * c_2(X) * d_1(X) + a_2(X) * b_1(X) * c_2(X) * d_1(X) + a_2(X) * b_2(X) * c_1(X) d_1(X)\\
\\
T^{(4)}_1 &= a_1(X) * b_1(X) * c_1(X) * d_2(X) + a_1(X) * b_1(X) * c_2(X) * d_1(X) + a_1(X) * b_2(X) * c_1(X) * d_1(X) + a_2(X) * b_1(X) * c_1(X) * d_1(X) \\
\\
T^{(3)}_3 &= u_1^3 * e_2(X) * f_2(X) * g_2(X) + u_2^3 * e_1(X) * f_2(X) * g_2(X) + u_2^3 * e_2(X) * f_1(X) * g_2(X) + u_2^3 * e_2(X) * f_2(X) * g_1(X)\\
\\
T^{(3)}_2 &= u_1^3 * e_1(X) * f_2(X) * g_2(X) + u_1^3 * e_2(X) * f_1(X) * g_2(X) + u_2^3 * e_1(X) * f_1(X) * g_2(X) + u_1^3 * e_2(X) * f_2(X) * g_1(X) + u_2^3 * e_1(X) * f_2(X) * g_1(X) + u_2^3 * e_2(X) * f_1(X) * g_1(X)\\
\\
T^{(3)}_1 &= u_1^3 * e_1(X) * f_1(X) * g_2(X) + u_1^3 * e_1(X) * f_2(X) * g_1(X) + u_1^3 * e_2(X) * f_1(X) * g_1(X) + u_2^3 * e_1(X) * f_1(X) * g_1(X)\\
\\
T^{(2)}_2 &= u_1^2 * h_2(X) * i_2(X) + u_2^2 * h_1(X) * i_2(X) + u_2^2 * h_2(X) * i_1(X) \\
\\
T^{(2)}_1 &= u_1^2 * h_1(X) * i_2(X) + u_1^2 * h_2(X) * i_1(X) + u_2^2 * h_1(X) * i_1(X) \\
\\
T^{(1)}_1 &= u_1^1 * j_2(X) + u_2^1 * j_1(X) \\
\end{aligned}
$$

<br />

So the cross terms aggregated together will be like:
$$
\begin{aligned}
T_3 &= T^{(4)}_3 + T^{(3)}_3 \\
T_2 &= T^{(4)}_2 + T^{(3)}_2 + T^{(2)}_2 \\
T_1 &= T^{(4)}_1 + T^{(3)}_1 + T^{(2)}_1 + T^{(1)}_1 \\
\end{aligned}
$$

<br />

# Compressed Cross Term Underneath of SPS

# Compressed Relaxed Plonk Proving System

# Reference
[1] protostar: https://eprint.iacr.org/2023/620.pdf
[2] plonk constrain system: https://learn.z2o-k7e.world/plonk-intro-cn/plonk-constraints.html
[3] protostar compressed verification in R1CS: https://learnblockchain.cn/article/6503