# 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 $$x \in \mathbb{F}^{\ell}$$. A CCS witness consists of a vector $$w\in\mathbb{F}^{n-\ell-1}$$. Then, a CCS structure-instance tuple $$(\mathcal{S}, x)$$ is satisfied by a CCS witness $$w$$ if:

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

where

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

$$M\_j \cdot 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 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, 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}
$$

This $$g$$ can be also called as state transition constraint.

#### 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. TODO