CCS

Table of contents

• CCS
• Credits
• CCS and R1CS (an intro)
  • CCS in general
  • R1CS -> CCS
• CCS and Plonkish (intro)
  • Plonkish -> CCS
    • Matrix derivation
    • Obtaining c
    • Obtaining S
    • Code to verify the previous example
• SuperSpartan
  • SuperSpartan - IOP for CCS to Snark for CCS
• CCS+ & SuperSpartan+
  • CCS+
  • SuperSpartan+
• Questions left:

Credits

This document has been possible thanks to the reviews of @asn-d6 and @oskarth as well as the immense help from @arnaucube and Edu(from PSE) who almost completely derived R1CS&Plonkish -> CCS.
Also thanks to Srinath Setty for his help on any question we've had while reading his paper as well as while elaborating this doc.

CCS and R1CS (an intro)

Due to NP-completeness equivalence, we can easily translate any R1CS statement and translate it into a CCS statement which is completelly equivalent.

To do so, it contais certain information as:

• $m$ = Number of constraints.
• $n$ = Number of columns of matrices.
• $N$ = Number of non-zero entries on rows.
• $l$ = Size of the public input vector.
• $x$ = A vector containing public input instances.
• $w$ = A vector containing the witness that satisfies the instance
  $\mathbb{S}$.

An R1CS structure

$\mathbb{S}$ is satisfied if:

$$(A\cdot z)\circ (B\cdot z)-(C\cdot z)=0$$ where

$z=(w,1,x)\in {\mathbb{F}}^n$

CCS in general

In general, a CCS structure

$\mathbb{S}$ consists of:

• Size bounds {
  $m,n,N,l,t,q,d\in \mathbb{N}$ where
  $n<l$ }
  • $t$ => Maximum size of the domain of the multisets.
  • $q$ => Number of multisets used within the CCS instance.
  • $d$ => Represents the maximum cardinality of each multiset. Which translates to the amount of different elements contained inside each multiset.
• A sequence of matrices
  $M_0..M_{t-1}$ that define the fixed parts of our circuit.
• A sequence of multisets
  $S_0,...,S_{q-1}$ where
  $\mathrm{\forall }s\in S_i$,
  $dom(s)=\{0..t-1\}$
• A sequence of constants
  $[c_0,...,c_{q-1}]$

Some of thesedon't really translate to any property in particular. Indeed they're just parameters that are used to be able to adapt all the arithmetizations into CCS.

A CCS instance

$(\mathbb{S},x)$ is satisfied if only if:

$$\sum _{i=0}^{q-1}{c}_i\cdot {◯}_{j\in S_i}(M_j\cdot \overrightarrow{z})=\overrightarrow{0}$$

If we re-write this a bit, we get:

$$\begin{gathered} \{c_0\cdot \{(M_{S_0[0]}\cdot z)\circ (M_{S_0[1]}\cdot z)\circ ...\circ (M_{S_0[t-1]}\cdot z){\}}_{\mathrm{\forall }{M}_i\in {\mathbb{S}}_0}\cdot z\} \\ \mathtt{\text{+}}...\mathtt{\text{+}} \\ \{c_{q-1}\cdot \{(M_{S_{q-1}[0]}\cdot z)\circ (M_{S_{q-1}[1]}\cdot z)\circ ...\circ (M_{S_{q-1}[t-1]}\cdot z){\}}_{\mathrm{\forall }{M}_i\in {\mathbb{S}}_{q-1}}\cdot z\}=0 \end{gathered}$$

R1CS -> CCS

Let's actually see how we can translate R1CS into CCS:

To do so, we need to set some parameters:

• $m$ =
  $m$ in the R1CS instance.
• $n$ =
  $n$ in the R1CS instance.
• $N$ =
  $N$ in the R1CS instance.
• $l$ =
  $l$ in the R1CS instance.
• $t$ = 3
• $q$ = 2
• $d$ = 2
• $\overrightarrow{M}$ =
  $[M_A,M_B,M_C]$ (R1CS matrices A, B and C)
• $\overrightarrow{\mathbb{S}}$ =
  $[S_0=\{0,1\},S_1=\{2\}]$
• $\overrightarrow{c}$ =
  $\{c_0=1,c_1=-1\}$

If we apply these constants to the aformentioned equation of a CCS instance:

$$1\cdot \{A\cdot z\circ B\cdot z\}\mathtt{\text{-}}1\cdot \{C\cdot z\}=0$$

Let's actually see a sage example done by @arnaucube:

# R1CS-to-CCS (https://eprint.iacr.org/2023/552) Sage prototype

# utils
def matrix_vector_product(M, v):
    n = M.nrows()
    r = [F(0)] * n
    for i in range(0, n):
        for j in range(0, M.ncols()):
            r[i] += M[i][j] * v[j]
    return r
def hadamard_product(a, b):
    n = len(a)
    r = [None] * n
    for i in range(0, n):
        r[i] = a[i] * b[i]
    return r
def vec_add(a, b):
    n = len(a)
    r = [None] * n
    for i in range(0, n):
        r[i] = a[i] + b[i]
    return r
def vec_elem_mul(a, s):
    r = [None] * len(a)
    for i in range(0, len(a)):
        r[i] = a[i] * s
    return r
# end of utils


# can use any finite field, using a small one for the example
F = GF(101)

# R1CS matrices for: x^3 + x + 5 = y (example from article
# https://www.vitalik.ca/general/2016/12/10/qap.html )
A = matrix([
    [F(0), 1, 0, 0, 0, 0],
    [0, 0, 0, 1, 0, 0],
    [0, 1, 0, 0, 1, 0],
    [5, 0, 0, 0, 0, 1],
    ])
B = matrix([
    [F(0), 1, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0],
    [1, 0, 0, 0, 0, 0],
    [1, 0, 0, 0, 0, 0],
    ])
C = matrix([
    [F(0), 0, 0, 1, 0, 0],
    [0, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0, 1],
    [0, 0, 1, 0, 0, 0],
    ])

print("R1CS matrices:")
print("A:", A)
print("B:", B)
print("C:", C)


z = [F(1), 3, 35, 9, 27, 30]
print("z:", z)

assert len(z) == A.ncols()

n = A.ncols() # == len(z)
m = A.nrows()
#  l = len(io) # not used for now

# check R1CS relation
Az = matrix_vector_product(A, z)
Bz = matrix_vector_product(B, z)
Cz = matrix_vector_product(C, z)
print("\nR1CS relation check (Az ∘ Bz == Cz):", hadamard_product(Az, Bz) == Cz)
assert hadamard_product(Az, Bz) == Cz


# Translate R1CS into CCS:
print("\ntranslate R1CS into CCS:")

# fixed parameters (and n, m, l are direct from R1CS)
t=3
q=2
d=2
S1=[0,1]
S2=[2]
S = [S1, S2]
c0=1
c1=-1
c = [c0, c1]

M = [A, B, C]

print("CCS values:")
print("n: %s, m: %s, t: %s, q: %s, d: %s" % (n, m, t, q, d))
print("M:", M)
print("z:", z)
print("S:", S)
print("c:", c)

# check CCS relation (this is agnostic to R1CS, for any CCS instance)
r = [F(0)] * m
for i in range(0, q):
    hadamard_output = [F(1)]*m
    for j in S[i]:
        hadamard_output = hadamard_product(hadamard_output,
                matrix_vector_product(M[j], z))

    r = vec_add(r, vec_elem_mul(hadamard_output, c[i]))

print("\nCCS relation check (∑ cᵢ ⋅ ◯ Mⱼ z == 0):", r == [0]*m)
assert r == [0]*m

Output:

CCS and Plonkish (intro)

Before starting, there are a few new things to notice here:
We define a plonkish instance

$\mathbb{S}$ to have the following:

• $m$ = Number of constraints.
• $n$ = Number of public and private witness.
• $l$ = Size of the public input vector.
• $e$ = Size of the selectors vector (amount of different selector values).
• $t$ = Domain of the
  $\mathbb{S}$ instance. Translates to the length of a
  $T_i$ instance. ie. Number of columns involved on a constraint inside
  $\mathbb{T}$.
• $g$ = A multivariate polynomial with
  $t$ variables which is represented as a sum of
  $q$ monomials of at most degree
  $d$.
• $s$ = A vector of constants called selectors of size
  $e$.
• $\mathbb{T}$ = A matrix which contains the indexes of values at
  $z$ which build up to
  $g$.

Plonkish -> CCS

Let's actually see how we can translate Plonkish into CCS:

Before starting, there are a few new things to notice here:
Differently from R1CS translation which is direct, we have some work to do which isn't simply set

$\overrightarrow{\mathbb{S}}$ and

$\overrightarrow{c}$.

Note that the vanilla plonk equation is:

$q_{m}ab+q_{l}a+q_{r}b+q_{o}c+q_c=0$

$$Plonkish=\left[\begin{array}{cccccccc}qm& ql& qr& qo& qc& a& b& c\\ 1& 0& 0& -1& 0& x_0& x_0& x_0\\ 1& 0& 0& -1& 0& x_1& x_1& x_1\\ 0& 2& 2& -1& 0& x_2& x_3& x_4\\ 0& 0& 0& 0& 0& x_5& x_5& x_5\end{array}\right]$$

Note that the Vanilla Plonk on the top is doing:

$r_0$ -> Bool check of

$x_0$

$r_1$ -> Bool check of

$x_1$

$r_2$ -> Addition check:

$2\cdot a\mathtt{\text{+}}2\cdot b\mathtt{\text{=}}c$

$r_3$ -> Null constrait (this checks nothing)

After seeing the Plonkish we want to translate, we alreay can infer some things:

• $m$ = 4 (4 rows in our plonkish = 4 constraints).
• $n$ =
  ${\mathbb{F}}^n$ = 6 (We have 6 different witness variables
  $\{x_0...x_5\}$.
  We will go through each
  $T_i$ and each value of the row
  $i$ is the index of the vector
  $s$ from which we will get a value from to set it in our matrix.
• $t$ =
  $8$ (Number of Plonkish instance columns).
• $e$ =
  $5$ (Number of different values ammong the selectors).
• $d$ =
  $3$ Note that
  $q_{m}ab$ has degree 3.

To start, we need to define our selectors

$s$ instance and also, our witness instance

$w$.

$$\begin{gathered} \overrightarrow{s}=[0,1,-1,2] \\ \overrightarrow{w}=[x_0,x_1,x_2,x_3,x_4,x_5] \end{gathered}$$

With this, we can define our instance

$z$.
Remember that in the paper, we have 2

$z$ instances defined. The plonkish one and the CCS one.
If we focus on the Plonkish one, we can see the definition:

$z=(w,x,s)\in {\mathbb{F}}^{n+e}$.

Hence, this means we can define

$z$ as the union of

$w$ and

$s$ (and also

$x$ but we don't have public witness in this scheme).

$$z_{Plonkish}=[x_0,x_1,x_2,x_3,x_4,x_5,0,1,-1,2]$$
Note that we have also our

$z$ definition for CCS. Which will also be used here.

$$\begin{gathered} z_{CCS}=\{w,1,x\}\in {\mathbb{F}}^n \\ {z}_{CCS}=[x_0,x_1,x_2,x_3,x_4,x_5,1] \end{gathered}$$

Remember that we can see

$g$ as a multivariate polynomial from it's definition if we consider each of the plonkish instance columns one variable:

$$g(q_m,q_m,q_l,q_o,q_c,a,b,c)=q_{m}ab+q_{l}a+q_{r}b+q_{o}c+q_c$$

The next step is to define

$T$. Which remember, indexes into

$g$ elements of

$z_{Plonkish}$ (which is collecting all the values that are used in the plonkish instance) and setting them into

$g$.

With that, we define

$T$ for this example as:

$$T=\left[\begin{array}{cccccccc}0& 0& 0& 7& 6& 6& 8& 6\\ 1& 1& 1& 7& 6& 6& 8& 6\\ 2& 3& 4& 6& 9& 9& 7& 6\\ 5& 5& 5& 6& 6& 6& 6& 6\end{array}\right]$$

Matrix derivation

The following rust code summarizes the actual algorithm to derive the matrixes for the CCS instance

# The following CCS instance values have been provided by Carlos
# (https://github.com/CPerezz) and Edu (https://github.com/ed255),
# and this sage script was made to check the CCS relation.
T = [
    [0, 0, 0, 7, 6, 6, 8, 6],
    [1, 1, 1, 7, 6, 6, 8, 6],
    [2, 3, 4, 6, 9, 9, 7, 6],
    [5, 5, 5, 6, 6, 6, 6, 6]
]

# z_plonkish = [F(1), 0, 1, 2, 3, 10, 42, 0,1,-1,2]
# z_ccs = [F(1), 0, 1, 2, 3, 10, 42, 1]

z_plonkish = [x_0,x_1,x_2,x_3,x_4,x_5,0,1,-1,2,]
z_ccs = [1,x_0,x_1,x_2,x_3,x_4,x_5]
## Checks performed by this Plonk/CCS instance:
# - binary check for x0, x1
# - 2*x2 + 2*x3 == x4


# CCS parameters
q=5
d=3
S = [[3,0,1], [4,0], [5,1], [6,2], [7]]
c = [1, 1, 1, 1, 1]
t = 8
n = 6
l = 0
m=4

# Initialize the result matrixes
matrixes = [[[0 for _ in range(t-1)] for _ in range(m)] for _ in range(t)]

# Iterate over i and j
for i in range(m):
    for j in range(t):
        k_j = T[i][j]
        if k_j >= n:
            matrixes[j][i][n - l - 1] = z_plonkish[k_j - n]  
        elif k_j >= n - l - 1:
            matrixes[j][i][k_j + 1] = 1
        else:
            matrixes[j][i][k_j] = 1

Let's run the first iteration of this step explaining it here. Then the rest can be inferred.

Step i=0, j=0..t-1

Here, we select the row

$i$ from

$T$ and call it

$T_i$.

$T_0=[0,0,0,7,6,6,8,6]$

• When
  $j=0$ ->
  $k_j=0$.

Note that

$z_{Plonkish}[0]=0$ (which indexes to

$x_0$ in

$z$).

So following the algorithm above, sice

$k_j<n$ we select

$1$.
Then we can set the coeff of

$M[0{]}_{0,0}=1$ ->

$M[0{]}_{00}=1$.

• When

  $j=1$ ->
  $k_j=0$ -> We therefore select
  $1$.
  Then we set
  $M[1{]}_{0,0}=1$

• When

  $j=2$ ->
  $k_j=0$. -> We therefore select
  $1$.
  Then we set
  $M[2{]}_{0,0}=1$

• When

  $j=3$ ->
  $k_j=7$. Note now we fall into the
  $k_j\ge n$. Hence we take
  $k_j-n$ as result.

$z_{Plonkish}[7-6]=1$ (Note here that this 1 points to the second position of

$s$ which actually corresponds to the value 1 of the selector).

Then we set

$M[3{]}_{i_0}=s[k_j-n]$ ->

$M[3{]}_{0,0}=1$.

• When

  $j=4$ ->
  $k_j=6$ ->
  $s[6-6]=s[0]=0$
  Then we set
  $M[4{]}_{0,0}=0$

• When

  $j=5$ -> Happens the same as above.
  Then we set
  $M[5{]}_{0,0}=0$

• When

  $j=6$ ->
  $k_j=8$ ->
  $s[8-6]=s[2]=-1$ (Assume
  $-1$ in some
  $GF$ is essentially a positive number (p-1)).
  Then we set
  $M[6{]}_{0,0}=-1$

• When

  $j=7$ ->
  $k_j=6$ ->
  $s[6-6]=s[0]=0$
  Then we set
  $M[7{]}_{0,0}=0$

Up to this point, we should have the following matrixes:

$$M_0=\left[\begin{array}{cccccc}1& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\end{array}\right]$$

$$M_1=\left[\begin{array}{cccccc}1& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\end{array}\right]$$

$$M_2=\left[\begin{array}{cccccc}1& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\end{array}\right]$$

$$M_3=\left[\begin{array}{cccccc}1& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\end{array}\right]$$

$$M_4=\left[\begin{array}{cccccc}0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\end{array}\right]$$

$$M_5=\left[\begin{array}{cccccc}0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\end{array}\right]$$

$$M_6=\left[\begin{array}{cccccc}-1& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\end{array}\right]$$

$$M_7=\left[\begin{array}{cccccc}0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\end{array}\right]$$

Note that in the paper is mentioned that any coefficient of the matrixes contained in

$\overrightarrow{M}$ that is not set is equal to 0!

Step i=3, j=7 (end of the algorithm)

After the 4th iteration (So

$i=3$,

$j=7$) the algorithm stops and we should obtain the following matrix vector

$\overrightarrow{M}$ as a result:

$$M_0=\left[\begin{array}{cccccc}1& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0& 1\end{array}\right]$$

$$M_1=\left[\begin{array}{cccccc}1& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0\\ 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 0& 1\end{array}\right]$$

$$M_2=\left[\begin{array}{cccccc}1& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0& 1\end{array}\right]$$

$$M_3=\left[\begin{array}{cccccc}1& 0& 0& 0& 0& 0\\ 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\end{array}\right]$$

$$M_4=\left[\begin{array}{cccccc}0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 2& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\end{array}\right]$$

$$M_5=\left[\begin{array}{cccccc}0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 2& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\end{array}\right]$$

$$M_6=\left[\begin{array}{cccccc}-1& 0& 0& 0& 0& 0\\ -1& 0& 0& 0& 0& 0\\ -1& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\end{array}\right]$$

$$M_7=\left[\begin{array}{cccccc}0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0& 0\end{array}\right]$$

Now that we have obtained

$\overrightarrow{M}$ it's time to get

$\overrightarrow{c}$ and

$\overrightarrow{S}$. And it's also time to add the 1 fixed instance for which we have padded our matrixes to our vector

$z$.

Leading on

$z=[1,x_0,x_1,x_2,x_3,x_4,x_5,0,1,-1,2]$

Obtaining c

$c$ is defined in a CCS instance as a vector of constants.
In the paper, we read:

For

$i\in \{0,1,...,q-1\}$, set

$c_i$ to the coefficient of the

$i$th monomial of

$g$.

This is easy to see. If we represent the multivariate polynomial

$g$ understanding each column name as a variable:

$$g=q_{m}ab+q_{l}a+q_{r}b+q_{o}c+q_c$$
where the monomials that form it are:

$$\{q_{m}ab,q_{l}a,q_{r}b,q_{o}c,q_c\}$$

We can easily see that we don't have any constants/coefficients multiplying any of the monomials.
Hence, we conclude that they're all

$1$.

$$\overrightarrow{c}=[1,1,1,1,1]$$

Obtaining S

$\overrightarrow{S}$ is defined as multisets of domain

$t-1$.
This has a really easy translation if we actually name things.

Let's name each variable of the

$g$ polynomial (same as naming each column of the plonkish instance).

In this case, if we recall, the plonkish instance was:

$$Plonkish=\left[\begin{array}{cccccccc}a& b& c& qm& ql& qr& qo& qc\\ x_0& x_0& x_0& 1& 0& 0& -1& 0& \\ x_1& x_1& x_1& 1& 0& 0& -1& 0\\ 0& 2& 2& -1& 0& x_2& x_3& x_4\\ 0& 0& 0& 0& 0& x_5& x_5& x_5\end{array}\right]$$

We will name/index all the columns in the

$\mathbb{PLONKISH}$ matrix from

$\{0..7\}$.

Naming therefore ->

$\{q_m=0,q_l=1,q_r=2,q_o=3,q_c=4,a=5,b=6,c=7\}$.

Then we read in the paper:

For

$i\in \{0,1,...,q-1\}$, set if the

$i$th monomial contains a variable

$j$, where

$j\in \{0,1,...,t-1\}$, add

$j$ to the multiset

$S_i$ with multiplicity equal to the degree of the variable.

Note that if we represent the multivariate polynomial

$g$ with the indexes instead of the string-based representation of them we obtain:

$$\overrightarrow{S}=[[3,0,1],[4,0],[5,1][6,2],[7]]$$

Code to verify the previous example

@arnaucube provided a modified version of the above code in which we can verify the instance used for the example on it.

# Plonk-CCS (https://eprint.iacr.org/2023/552) Sage prototype

# utils
def matrix_vector_product(M, v):
    n = M.nrows()
    r = [F(0)] * n
    for i in range(0, n):
        for j in range(0, M.ncols()):
            r[i] += M[i][j] * v[j]
    return r
def hadamard_product(a, b):
    n = len(a)
    r = [None] * n
    for i in range(0, n):
        r[i] = a[i] * b[i]
    return r
def vec_add(a, b):
    n = len(a)
    r = [None] * n
    for i in range(0, n):
        r[i] = a[i] + b[i]
    return r
def vec_elem_mul(a, s):
    r = [None] * len(a)
    for i in range(0, len(a)):
        r[i] = a[i] * s
    return r
# end of utils


# can use any finite field, using a small one for the example
F = GF(101)

# The following CCS instance values have been provided by Carlos
# (https://github.com/CPerezz) and Edu (https://github.com/ed255),
# and this sage script was made to check the CCS relation.

## Checks performed by this Plonk/CCS instance:
# - binary check for x0, x1
# - 2*x2 + 2*x3 == x4
M0 = matrix([
    [F(0),   1, 0, 0, 0, 0, 0],
    [0,   0, 1, 0, 0, 0, 0],
    [0,   0, 0, 1, 0, 0, 0],
    [0,   0, 0, 0, 0, 0, 1],
    ])
M1 = matrix([
    [F(0),   1, 0, 0, 0, 0, 0],
    [0,   0, 1, 0, 0, 0, 0],
    [0,   0, 0, 0, 1, 0, 0],
    [0,   0, 0, 0, 0, 0, 1],
    ])
M2 = matrix([
    [F(0),   1, 0, 0, 0, 0, 0],
    [0,   0, 1, 0, 0, 0, 0],
    [0,   0, 0, 0, 0, 1, 0],
    [0,   0, 0, 0, 0, 0, 1],
    ])
M3 = matrix([
    [F(1), 0, 0, 0, 0, 0,   0],
    [1, 0, 0, 0, 0, 0,   0],
    [0, 0, 0, 0, 0, 0,   0],
    [0, 0, 0, 0, 0, 0,   0],
    ])
M4 = matrix([
    [F(0), 0, 0, 0, 0, 0,   0],
    [0, 0, 0, 0, 0, 0,   0],
    [2, 0, 0, 0, 0, 0,   0],
    [0, 0, 0, 0, 0, 0,   0],
    ])
M5 = matrix([
    [F(0), 0, 0, 0, 0, 0,   0],
    [0, 0, 0, 0, 0, 0,   0],
    [2, 0, 0, 0, 0, 0,   0],
    [0, 0, 0, 0, 0, 0,   0],
    ])
M6 = matrix([
    [F(-1), 0, 0, 0, 0, 0,   0],
    [-1, 0, 0, 0, 0, 0,   0],
    [-1, 0, 0, 0, 0, 0,   0],
    [0, 0, 0, 0, 0, 0,    0],
    ])
M7 = matrix([
    [F(0), 0, 0, 0, 0, 0,   0],
    [0, 0, 0, 0, 0, 0,   0],
    [0, 0, 0, 0, 0, 0,   0],
    [0, 0, 0, 0, 0, 0,   0],
    ])

z = [F(1), 0, 1, 2, 3, 10, 42]

print("z:", z)

assert len(z) == M0.ncols()

# CCS parameters
n = M0.ncols() # == len(z)
m = M0.nrows()
t=8
q=5
d=3
S = [[3,0,1], [4,0], [5,1], [6,2], [7]]
c = [1, 1, 1, 1, 1]

M = [M0,M1,M2,M3,M4,M5,M6,M7]

print("CCS values:")
print("n: %s, m: %s, t: %s, q: %s, d: %s" % (n, m, t, q, d))
print("M:", M)
print("z:", z)
print("S:", S)
print("c:", c)

# check CCS relation (this is agnostic to Plonk, for any CCS instance)
r = [F(0)] * m
for i in range(0, q):
    hadamard_output = [F(1)]*m
    for j in S[i]:
        hadamard_output = hadamard_product(hadamard_output,
                matrix_vector_product(M[j], z))

    r = vec_add(r, vec_elem_mul(hadamard_output, c[i]))

print("\nCCS relation check (∑ cᵢ ⋅ ◯ Mⱼ z == 0):", r == [0]*m)
assert r == [0]*m

The most important thing for the code above is if we use the example with symbols rather than GF elements. If we do this symbolic analisis, we get the following r relation as a result of applying all the Haddamard products.

r = [x0^2 - x0, x1^2 - x1, 2*x2 + 2*x3 - x4, 0]

If we see the following r expresion that results from each of it's elements represent exactly the constraints our plonkish instance had.
If you recall, our plonkish instance was defined as:

$r_0$ -> Bool check of

$x_0$

$r_1$ -> Bool check of

$x_1$

$r_2$ -> Addition check:

$2\cdot a\mathtt{\text{+}}2\cdot b\mathtt{\text{=}}c$

$r_3$ -> Null constrait (this checks nothing)

So as you see, each row of Plonkish has translated into an element of the vector r which represents the symbolic result of

$S_{CCS}$.

• The first and the second elements of
  $r$ actually encode the same operation: x^2 - x Which is the boolean constraint!.
• The third element of
  $r$ actually contains the third constraint in the plonkish instance. Is obvious that 2*x2 + 2*x3 - x4 is doublings of two variables and equaling it to another one as a constraint.
• Finally, the last is a null constraint, hence the last element of r equals 0.

SuperSpartan

SuperSpartan translates to simply to the classical Spartan protocol but using CCS as arithmetization system.

To check the correctness of

$(I,W)\in R_{CCS}$ (instance

$(I,W)$ actually satisfies the RCCS structure) is based on checking that the following identity holds:

$$0\stackrel{?}{=}\sum _{a\in \{0,1{\}}^{lo{g}_m}}\widetilde{eq}(\tau ,a)\cdot \sum _{i=0}^{q-1}{c}_i\cdot \prod _{j\in S_i}(\sum _{y\in \{0,1{\}}^{lo{g}_m}}\widetilde{M_j}(a,y)\cdot \tilde{Z}(y))(1)$$

What this is saying, is that if

$(I,W)\in R_{CCS}$, then, we can apply the sumcheck protocol to the polynomial:

$$g(a):=\widetilde{eq}(\tau ,a)\cdot \sum _{i=0}^{q-1}{c}_i\prod _{j\in S_i}(\sum _{y\in \{0,1{\}}^{lo{g}_m}}\widetilde{M_j}(a,y)\cdot \tilde{Z}(y))(2)$$
This is esentially saving to the verifier the costs of computing the right hand side of the first equation of this section to actually evaluate

$g$ at a random input

$r_a$.

So once we are here, we can see that the problem can actually be translated to compute

$t$ sumchecks in parallel for:

$$\mathrm{\forall }j\in \{0,..,t-1\}\sum _{y\in \{0,1{\}}^{lo{g}_m}}\widetilde{M_j}(r_a,y)\cdot \tilde{Z}(y)(3)$$

Note that here

$\tilde{Z}$ is defined as:

$$\tilde{Z}(X_0,..,X_{logn-1})=(1-X_0)\cdot \tilde{W}(X_1,..,X_{logn-1})\mathtt{\text{+}}{X}_0\cdot \widetilde{(1,x)}(X_1,..,X_{logn-1})(4)$$

In Spartan we use a trick to actually move from N sumchecks to 2 using fiat shamir. But here we have

$t$. But here there's no mention on how we do reduce the sumcheck number so that we can actually lower the work load

SuperSpartan - IOP for CCS to Snark for CCS

In this section we get a clear description of the protocol which I think is worth rephrasing here:

Prover's work

1. Commit to an
   $O(logn)$-variate polynomial
   $\tilde{Z}$.
2. Performs the sumcheck of equation:
   
   $$\tilde{Z}(X_0,..,X_{logn-1})=(1-X_0)\cdot \tilde{W}(X_1,..,X_{logn-1})\mathtt{\text{+}}{X}_0\cdot \widetilde{(1,x)}(X_1,..,X_{logn-1})$$
3. Proves the evaluations of
   $\tilde{Z}$ at particular random points sampled by the Verifier.
4. If the CCS instance is not uniform (Different
   $M_i$'s within the same
   $R_{CCS}$), prove one evaluation at a random point sampled by de Verifier (
   $r_y,r_a$) of each of the
   $[M_0,..,M_{t-1}]$ instances.
   Note that it's possible depending on the proving system to actually batch together all the
   $M$ instances so that a single evaluation can be performed instead of
   $t-1$

Verifier's work

1. Participates in the sumcheck protocol over:
   
   $$\tilde{Z}(X_0,..,X_{logn-1})=(1-X_0)\cdot \tilde{W}(X_1,..,X_{logn-1})\mathtt{\text{+}}{X}_0\cdot \widetilde{(1,x)}(X_1,..,X_{logn-1})$$
   I should elaborate more on what that exactly means.
2. Verifies the proofs of the evaluations of
   $\tilde{Z}$.
3. If the CCS instance is not uniform (Different
   $M_i$'s within the same
   $R_{CCS}$), verify the evaluation at a random point previously sampled (
   $r_y,r_a$) for each of the
   $[M_0,..,M_{t-1}]$ instances.
   Note that it's possible depending on the proving system to actually batch together all the
   $M$ instances so that a single evaluation can be performed instead of
   $t-1$

CCS+ & SuperSpartan+

The paper also mentions the existance of an extension over SuperSpartan called SuperSpartan+ and an extension over CCS called CCS+.

CCS+

The description for this is very brief. Indeed it only mentions that in addition to the terms we already know a CCS instance has, a CCS+ instance also contains:

• A lookup table
  $T$ which is a set of field elements.
• A sequence of lookup operations
  $L$ where each entry is in the range
  $[n]$.

Then, it's mentioned that in addition to all the previous requirements for a

$R_{C}CS$ instance to be correct, now, in addition,

$\mathrm{\forall }o\in L,z[o]\in T$ (for each lookup operation

$o$ in

$L$, the witness

$z[o]$ actually needs to be inside of the lookup table

$T$ for the

$R_{CCS+}$ instance to actually be valid).

SuperSpartan+

In order for this to work, the Verifier needs to have oracle access to the polynomials

$T$ and

$a$ where

$T$ is the table that encodes the range or set and

$a$ the values claimed to be inside of

$T$.

In order to support lookups, SuperSpartan+ encodes all the lookup operations

$L$ in a sparse matrix

$M_L$ where

$\mathrm{\forall }i\in [L],M_L[i][L[i]]=1$ and all other entries are set to 0.

Then the prover sets the polynomial

$\tilde{a}$ together with

$\tilde{w}$ and

$a$ is claimed to be the MLE of the vector

$M_L\cdot z$
As done in the original protocol, using the sum-check invocation the problem is reduced to check that the claimed relationship

$M_L\cdot z=a$

Questions left:

• How do we go from
  $t-1$ sumchecks to just 1 for the
  $M_i$ instances? I assume doing the same tricks as in Spartan. But it's not clear.
• Is the mermaid diagram acurate? Is it missing anything? Does it relate/map 1:1 to this section?
• How do lookups fit into this? CCS+ does not define any equation that considers it.