# CCS

## Customizable Constraint System

**Definition 2.1 (R1CS).** An R1CS structure $$\mathcal{S}$$ consists of:

* size bounds $$m, n, N,\ell \in \mathbb{N}$$ where $$n > \ell$$
* and three matrices $$\bm{A},\bm{B},\bm{C} \in  \mathbb{F}^{m\times n}$$ with at most $$N = \Omega(\mathsf{max}(m, n))$$ non-zero entries in total. 

An R1CS instance consists of public input $$\bm{x} \in F^\ell$$. An R1CS witness consists of a vector $$\bm{w} ∈ F^{n−\ell−1}$$. An R1CS structure-instance tuple $$(\mathcal{S}, \bm{x})$$ is satisfied by an R1CS witness $$\bm{w}$$ if:

$$
(\bm{A} \cdot \bm{z}) \circ (\bm{B} \cdot \bm{z}) − \bm{C} \cdot \bm{z} = \bm{0}
$$

where

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

 Here, $$\bm{A}\cdot \bm{z}$$ denotes a matrix-vector multiplication operation, $$\circ$$ denotes the Hadamard (i.e., entry-wise) product between vectors, and $$\bold{0}$$ is a zero vector in $$\mathbb{F}^m$$. 

**Definition 2.2 (CCS)**. A CCS structure $$\mathcal{S}$$ consists of:

* size bounds $$m, n, N, \ell, t, q, d \in \mathbb{N}$$ where $$n > \ell$$
* a sequence of matrices $$\bm{M}*0,\dots ,\bm{M}*{t−1}\in \mathbb{F}\_{m\times n}$$ with at most $$N = \Omega(\mathsf{max}(m, n))$$ non-zero entries in total
* a sequence of $$q$$ multisets $$\[S\_0,\dots, S\_{q−1}]$$, where an element in each multi-set is from the domain $${0, . . . , t − 1}$$ and the cardinality of each multi-set is at most $$d$$
* a sequence of $$q$$ constants $$\[c\_0,\dots, c\_{q−1}]$$, where each constant is from $$\mathbb{F}$$

A CCS instance consists of public input $$\bm{x} \in \mathbb{F}^{\ell}$$. A CCS witness consists of a vector $$\bm{w}\in\mathbb{F}^{n-\ell-1}$$. Then, a CCS structure-instance tuple $$(\mathcal{S}, \bm{x})$$ is satisfied by a CCS witness $$\bm{w}$$ if:

$$
\sum^{q-1}*{i=0}c\_i\cdot \bigcirc*{j\in S\_{i}}\bm{M}\_j\cdot \bm{z}=\bold{0}
$$

where

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

$$\bm{M}\_j \cdot \bm{z}$$ denotes matrix-vector multiplication, $$\bigcirc$$ denotes the Hadamard product between vectors, and $$\bold{0}$$ is a zero vector in $$\mathbb{F}^m$$.

{% hint style="info" %}
CCS can be easily converted to R1CS. I will leave it as a thought exercise.
{% endhint %}

### Representing Plonkish with CCS

Let's recall the Plonkish constraint system first.

**Definition 2.3 (Plonkish)**. A Plonkish structure $$\mathcal{S}$$ consists of:

* size bounds $$m, n, \ell, t, q, d, e \in \mathbb{N}$$;
* a multivariate polynomial $$g$$ in $$t$$ variables, where $$g$$ is expressed as a sum of $$q$$ monomials and each monomial has a total degree at most $$d$$;
* a vector of constants called selectors $$\bm{s} \in \mathbb{F}^e$$; and
* a set of $$m$$ constraints. Each constraint $$i$$ is specified via a vector $$\bm{T}\_i$$ of length $$t$$, with entries in the range $${0, . . . , n + e − 1}$$. $$\bm{T}\_i$$ is interpreted as specifying $$t$$ entries of a purported satisfying assignment $$z$$ to feed into $$g$$.

A Plonkish instance consists of public input $$\bm{x} \in \mathbb{F}^\ell$$. A Plonkish witness consists of a vector $$\bm{w} \in F^{n−\ell}$$. A Plonkish structure-instance tuple $$(\mathcal{S}, \bm{x})$$ is satisfied by a Plonkish witness $$\bm{w}$$ if:

$$
\forall i \in {0,\dots,m-1}: g(\bm{z}\[\bm{T}\_i\[1]], . . . , \bm{z}\[\bm{T}\_i\[t]]) = 0
$$

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

### Representing AIR with CCS

**Definition 2.4 (AIR)**. An AIR structure $$\mathcal{S}$$ consists of:

* size bounds $$m, t, q, d \in \mathbb{N}$$, where $$t$$ is even;
* a multivariate polynomial $$g$$ in $$t$$ variables (also known as state transition constraint), where $$g$$ is expressed as a sum of $$q$$ monomials and each monomial has total degree at most $$d$$.

An AIR instance consists of public input and output $$\bm{x} \in \mathbb{F}^t$$. An AIR witness consists of a vector $$\bm{w} ∈ \mathbb{F}^{(m−1)\cdot t/2}$$. Let

$$
\begin{equation}
\bm{z} = (\bm{x}\[..t/2], \bm{w}, \bm{x}\[t/2 + 1..]) \in (\mathbb{F}^{t/2})^{m+1} \tag{6}
\end{equation}
$$

Notice that, $$\bm{z}$$ can be viewed as $$\mathbb{F}^{(m+1)\times t/2}$$ matrix. Let us index the $$m + 1$$ “rows” of $$\bm{z}$$ as $$0, 1, . . . , m$$. An AIR structure-instance tuple $$(\mathcal{S}, \bm{x})$$ is satisfied by an AIR witness $$w$$ if:

$$
\begin{equation}
\forall i ∈ {1, . . . , m}: g(\bm{z}\[i − 1], \bm{z}\[i]) = 0. \tag{7}
\end{equation}
$$

#### Handling many AIR constraint polynomials

To represent the constraints capturing a single step of a CPU, typically many polynomials $$g$$ will be needed, say $$g\_1, . . . , g\_k$$. In practice, $$k$$ may be in the many dozens to hundreds \[GPR21, BGtRZt23]. There is, however, a straightforward and standard randomized reduction from AIR with $$k > 1$$ constraint polynomials to AIR with a single constraint polynomial $$g$$: the verifier picks a random $$r \in \mathbb{F}$$ and sends it to the prover, and the prover replaces $$g\_1, . . . , g\_k$$ with the single constraint polynomial

$$
\begin{equation}
g:=\sum^{k-1}\_{i=0}r^i\cdot g\_i \tag{8}
\end{equation}
$$

If Equation (7) holds for all $$g\_1, \dots , g\_k$$ in place of $$g$$, then with probability 1 over the choice of $$r$$ the same will hold for the random linear combination $$g$$. Meanwhile, if it fails to hold for any $$g\_i$$ then with probability at least $$1 − \frac{(k − 1)}{|\mathbb{F}|}$$, it will fail to hold for the random linear combination $$g$$. You could also get $$k$$ random values for each polynomial, which improves the soundness error to $$\frac{1}{|\mathbb{F}|}$$.

**Lemma 3** (AIR to CCS transformation). Given an AIR structure $$\mathcal{S}*{AIR} = (m, t, q, d,g)$$, instance $$\mathcal{I}*{AIR} = \bm{x}$$, and witness $$\bm{w}*{AIR} = \bm{w}$$, there exists a CCS structure $$\mathcal{S}*{CCS}$$ such that the tuple $$(\mathcal{S}*{CCS}, \bm{x})$$ is satisfied by $$\bm{w}$$ if and only if $$(\mathcal{S}*{AIR},\bm{x})$$ is satisfied by $$\bm{w}$$. The natural NP checker’s time to verify the tuple $$((\mathcal{S}*{CCS}, \bm{x}), \bm{w})$$ is identical to the runtime of the NP checker that evaluates $$g$$ monomial-by-monomial when checking that $$((\mathcal{S}*{AIR}, \bm{x}), \bm{w})$$ satisfies Equation (7).

*Proof*.

* Let $$\bm{w}*{CCS} = \bm{w}*{AIR}$$ and $$\mathcal{I}*{CCS} = \mathcal{I}*{AIR}$$.
* Let $$\mathcal{S}*{CCS}= (m, n, N, \ell, t, q, d, \[\bm{M}*0, \dots , \bm{M}*{t−1}], \[s\_0, \dots , s*{q−1}], \[c\_0, \dots , c\_{q−1}])$$ where:
  * $$m,t,q,d$$ are from the $$\mathcal{S}\_{AIR}$$
  * $$\ell \leftarrow t/2, n\leftarrow (m+1)\cdot t/2$$

*Deriving* $$\bm{M}*0, \dots , \bm{M}*{t−1}$$*, and* $$N$$*.* 

Recall that $$g$$ in $$\mathcal{S}*{AIR}$$ is a multivariate polynomial in $$t$$ variables. There is a CCS row for each of the $$m$$  transition constraints in $$\mathcal{S}*{AIR}$$, so, if we index the CCS rows by $${0,\dots, m − 1}$$, it suffices to specify how the $$i$$th row of these matrices is set. We consider three cases:

For all  $$i \in {0,\dots,m-1}, j \in {0, 1 . . . , t − 1}$$, let $$k\_j = i \cdot t/2 + j$$.

* If $$i = 0$$ and $$j < t/2$$, we set $$\bm{M}*j\[i]\[j + |\bm{w}*{AIR}|]=1$$.&#x20;
* If $$i = m − 1$$ and $$j \ge t/2$$, we set $$\bm{M}*j\[i]\[j + |\bm{w}*{AIR}| + t/2] = 1$$.
* Otherwise, we set $$\bm{M}\_j\[i]\[k\_j] = 1$$.

NOTE: In this version, I think the authors assumed:

$$
\begin{equation}
\bm{z} = (\bm{w}, \bm{x}\[..t/2], \bm{x}\[t/2 + 1..]) \in \mathbb{F}^{t/2\cdot(m+1)}
\end{equation}
$$