# Hypernova study notes
*May 2023* - Notes on [Hypernova](https://eprint.iacr.org/2023/573).

> An updated version of this hackmd can be found at https://github.com/arnaucube/math/blob/master/notes_hypernova.pdf , if somebody wants to modify stuff feel free to do a PR, or if you prefer working in a hackmd, we can update this hackmd and work here (if so, please ping me).

<!--
<br>

> ++Table of contents:++
> [TOC]

## CCS recap
### R1CS to CCS overview
- R1CS instance: $S_{R1CS} = (m, n, N, l, A, B, C)$
where $m, n$ are such that $A \in \mathbb{F}^{m \times n}$, and $l$ such that the public inputs $x \in \mathbb{F}^l$. Also $z=(w, 1, x) \in \mathbb{F}^n$, thus $w \in \mathbb{F}^{n-l-1}$.
- CCS instance: $S_{CCS} = (m, n, N, l, t, q, d, M, S, c)$
where we have the same parameters than in $S_{R1CS}$, but additionally:
$t=|M|$, $q = |c| = |S|$, $d$= max degree in each variable.
- R1CS-to-CCS parameters: $n=n,~ m=m,~ N=N,~ l=l,~ t=3,~ q=2,~ d=2$, $M=\{A,B,C\}$, $S=\{\{0,~1\},~ \{2\}\}$, $c=\{1,-1\}$

The CCS relation check:
$$\sum_{i=0}^{q-1} c_i \cdot \bigcirc_{j \in S_i} M_j \cdot z ==0$$
where $z=(w, 1, x) \in \mathbb{F}^n$.

In our R1CS-to-CCS parameters is equivalent to

\begin{align*}
&c_0 \cdot ( (M_0 z) \circ (M_1 z) ) + c_1 \cdot (M_2 z) ==0\\
\Longrightarrow &1 \cdot ( (A z) \circ (B z) ) + (-1) \cdot (C z) ==0\\
\Longrightarrow &( (A z) \circ (B z) ) - (C z) ==0
\end{align*}

which is equivalent to the R1CS relation: $Az \circ Bz == Cz$

An example of the conversion from R1CS to CCS implemented in Sage [can be found here](https://github.com/arnaucube/math/blob/master/r1cs-ccs.sage).

Similar relations between Plonkish and AIR arithmetizations to CCS are shown in the [CCS paper](https://eprint.iacr.org/2023/552), but for now with the R1CS we have enough to see the CCS generalization idea and to use it for the HyperNova scheme.

### Committed CCS
$R_{CCCS}$ instance: $(C, \mathsf{x})$, where $C$ is a commitment to a multilinear polynomial in $s'-1$ variables.

Sat if:
- i. $\text{Commit}(pp, \widetilde{w}) = C$
- ii. $\sum_{i=1}^q c_i \cdot \left( \prod_{j \in S_i} \left( \sum_{y \in \{0,1\}^{\log m}} \widetilde{M}_j(x, y) \cdot \widetilde{z}(y) \right) \right)$
where $\widetilde{z}(y) = \widetilde{(w, 1, \mathsf{x})}(x) ~\forall x \in \{0, 1\}^{s'}$

### Linearized Committed CCS
$R_{LCCCS}$ instance: $(C, u, \mathsf{x}, r, v_1, \ldots, v_t)$, where $C$ is a commitment to a multilinear polynomial in $s'-1$ variables, and $u \in \mathbb{F},~ \mathsf{x} \in \mathbb{F}^l,~ r \in \mathbb{F}^s,~ v_i \in \mathbb{F} ~\forall i \in [t]$.

Sat if:
- i. $\text{Commit}(pp, \widetilde{w}) = C$
- ii. $\forall i \in [t],~ v_i = \sum_{y \in \{0,1\}^{s'}} \widetilde{M}_i(r, y) \cdot \widetilde{z}(y)$
where $\widetilde{z}(y) = \widetilde{(w, u, \mathsf{x})}(x) ~\forall x \in \{0, 1\}^{s'}$

<br><br><br>

## Multifolding Scheme for CCS
Recall sum-check protocol notation: $C \leftarrow \langle P, V(r) \rangle (g, l, d, T)$ means
$$T=\sum_{x_1 \in \{0,1\}} \sum_{x_2 \in \{0,1\}} \cdots \sum_{x_l \in \{0,1\}} g(x_1, x_2, \ldots, x_l)$$
where $g$ is a $l$-variate polynomial, with degree at most $d$ in each variable, and $T$ is the claimed value.

Let $s= \log m,~ s'= \log n$.

1. $V \rightarrow P: \gamma \in^R \mathbb{F},~ \beta \in^R \mathbb{F}^s$
2. $V: r_x' \in^R \mathbb{F}^s$
3. $V \leftrightarrow P$: sum-check protocol:
$$c \leftarrow \langle P, V(r_x') \rangle (g, s, d+1, \underbrace{\sum_{j \in [t]} \gamma^j \cdot v_j}_\text{T})$$
(in fact, $T=(\sum_{j \in [t]} \gamma^j \cdot v_j) \underbrace{+ \gamma^{t+1} \cdot Q(x)}_{=0}) = \sum_{j \in [t]} \gamma^j \cdot v_j$)
where:
\begin{align*}
g(x) &:= \underbrace{\left( \sum_{j \in [t]} \gamma^j \cdot L_j(x) \right)}_\text{LCCCS check} + \underbrace{\gamma^{t+1} \cdot Q(x)}_\text{CCCS check}\\
\text{for LCCCS:}~ L_j(x) &:= \widetilde{eq}(r_x, x) \cdot \left(
\underbrace{\sum_{y \in \{0,1\}^{s'}} \widetilde{M}_j(x, y) \cdot \widetilde{z}_1(y)}_\text{this is the check from LCCCS}
\right)\\
\text{for CCCS:}~ Q(x) := &\widetilde{eq}(\beta, x) \cdot \left(
\underbrace{ \sum_{i=1}^q c_i \cdot \prod_{j \in S_i} \left( \sum_{y \in \{0, 1\}^{s'}} \widetilde{M}_j(x, y) \cdot \widetilde{z}_2(y) \right) }_\text{this is the check from CCCS}
\right)
\end{align*}
Notice that
$$v_j= \sum_{y\in \{0,1\}^{s'}} \widetilde{M}_j(r, y) \cdot \widetilde{z}(y) = \sum_{x\in \{0,1\}^s} L_j(x)$$
4. $P \rightarrow V$: $\left( (\sigma_1, \ldots, \sigma_t), (\theta_1, \ldots, \theta_t) \right)$, where $\forall j \in [t]$,
$$\sigma_j = \sum_{y \in \{0,1\}^{s'}} \widetilde{M}_j(r_x', y) \cdot \widetilde{z}_1(y)$$
$$\theta_j = \sum_{y \in \{0, 1\}^{s'}} \widetilde{M}_j(r_x', y) \cdot \widetilde{z}_2(y)$$
where $\sigma_j,~\theta_j$ are the checks from LCCCS and CCCS respectively with $x=r_x'$.
5. V: $e_1 \leftarrow \widetilde{eq}(r_x, r_x')$, $e_2 \leftarrow \widetilde{eq}(\beta, r_x')$
check:
$$c = \left( \sum_{j \in [t]} \gamma^j e_1 \sigma_j + \gamma^{t+1} e_2 \left( \sum_{i=1}^q c_i \cdot \prod_{j \in S_i} \sigma \right) \right)$$
which should be equivalent to the $g(x)$ computed by $V,P$ in the sum-check protocol.
6. $V \rightarrow P: \rho \in^R \mathbb{F}$
7. $V, P$: output the folded LCCCS instance $(C', u', \mathsf{x}', r_x', v_1', \ldots, v_t')$, where $\forall i \in [t]$:
\begin{align*}
C' &\leftarrow C_1 + \rho \cdot C_2\\
u' &\leftarrow u + \rho \cdot 1\\
\mathsf{x}' &\leftarrow \mathsf{x}_1 + \rho \cdot \mathsf{x}_2\\
v_i' &\leftarrow \sigma_i + \rho \cdot \theta_i
\end{align*}
7. $P$: output folded witness: $\widetilde{w}' \leftarrow \widetilde{w}_1 + \rho \cdot \widetilde{w}_2$.

participant P
participant V

V->V: γ ∈ 𝔽, β ∈ 𝔽ˢ, rₓ' ∈ 𝔽ˢ
V->P: γ, β, rₓ'
P->P: Sum-Check prove
P->V: c, π
V->V: Sum-Check verify
P->P: {σⱼ}, {thetaⱼ} ∀ j ∈ [t]
P->V: {σⱼ}, {thetaⱼ}
V->V: verify c relation with {σⱼ}, {thetaⱼ}
V->V: ρ ∈ 𝔽
V->P: ρ
P->P: fold LCCCS instance
V->V: fold LCCCS instance
P->P: fold w̃

<br><br><br>

Now, to see the verifier check from step 5, observe that in LCCCS, since $\widetilde{w}$ satisfies,
\begin{align*}
v_j &= \sum_{y \in \{0,1\}^{s'}} \widetilde{M}_j(r_x, y) \cdot \widetilde{z}_1(y)\\
&= \sum_{x \in \{0,1\}^s}
\underbrace{
\widetilde{eq}(r_x, x) \cdot \left( \sum_{y \in \{0,1\}^{s'}} \widetilde{M}_j(x, y) \cdot \widetilde{z}_1(y) \right)
}_{L_j(x)}\\
&= \sum_{x \in \{0,1\}^s} L_j(x)
\end{align*}

Observe also that in CCCS, since $\widetilde{w}$ satisfies,
$$
0=\sum_{i=1}^q c_i \cdot \prod_{j \in S_i} \left( \sum_{y \in \{0, 1\}^{s'}} \widetilde{M}_j(x, y) \cdot \widetilde{z}_2(y) \right)
$$

we have that
$$
G(X) = \sum_{x \in \{0,1\}^s} eq(X, x) \cdot q(x)
$$
is multilinear, and can be seen as a Lagrange polynomial where coefficients are evaluations of $q(x)$ on the hypercube.

For an honest prover, all these coefficients are zero, thus $G(X)$ must necessarily be the zero polynomial. Thus $G(\beta)=0$ for $\beta \in^R \mathbb{F}^s$.

\begin{align*}
0&=G(\beta) = \sum_{x \in \{0,1\}^s} eq(\beta, x) \cdot q(\beta)\\
&= \sum_{x \in \{0,1\}^s}
\underbrace{\widetilde{eq}(\beta , x) \cdot
\overbrace{
\sum_{i=1}^q c_i \cdot \prod_{j \in S_i} \left( \sum_{y \in \{0, 1\}^{s'}} \widetilde{M}_j(x, y) \cdot \widetilde{z}_2(y) \right)
}^{q(x)}
}_{Q(x)}\\
&= \sum_{x \in \{0,1\}^s} Q(x)
\end{align*}

> **Note**: notice that this past equation is related to [Spartan paper](https://eprint.iacr.org/2019/550), lemmas 4.2 and 4.3, where instead of
>
> $$q(x) = \sum_{i=1}^q c_i \cdot \prod_{j \in S_i} \left( \sum_{y \in \{0, 1\}^{s'}} \widetilde{M}_j(x, y) \cdot \widetilde{z}_2(y) \right)$$
>
> for our R1CS example, we can restrict it to just $M_0,M_1,M_2$, which would be
>
> $$=\left( \sum_{y \in \{0,1\}^s} \widetilde{M_0}(x, y) \cdot \widetilde{z}(y) \right) \cdot \left( \sum_{y \in \{0,1\}^s} \widetilde{M_1}(x, y) \cdot \widetilde{z}(y) \right) - \sum_{y \in \{0,1\}^s} \widetilde{M_2}(x, y) \cdot \widetilde{z}(y)$$
>
> and we can see that $q(x)$ is the same equation $\widetilde{F}_{io}(x)$ that we had in Spartan:
>
> $$
> \widetilde{F}_{io}(x)=\left( \sum_{y \in \{0,1\}^s} \widetilde{A}(x, y) \cdot \widetilde{z}(y) \right) \cdot \left( \sum_{y \in \{0,1\}^s} \widetilde{B}(x, y) \cdot \widetilde{z}(y) \right) - \sum_{y \in \{0,1\}^s} \widetilde{C}(x, y) \cdot \widetilde{z}(y)
> $$
>
> where
> $$Q_{io}(t) = \sum_{x \in \{0,1\}^s} \widetilde{F}_{io}(x) \cdot \widetilde{eq}(t,x)=0$$
> and V checks $Q_{io}(\tau)=0$ for $\tau \in^R \mathbb{F}^s$, which in HyperNova is $G(\beta)=0$ for $\beta \in^R \mathbb{F}^s$.
>
> $Q_{io}(\cdot)$ is a zero-polynomial ($G(\cdot)$ in HyperNova), it evaluates to zero for all points in its domain iff $\widetilde{F}_{io}(\cdot)$ evaluates to zero at all points in the $s$-dimensional boolean hypercube.
> \begin{align*}
> \text{Spartan} &\longleftrightarrow \text{HyperNova}\\
> \tau &\longleftrightarrow \beta\\
> \widetilde{F}_{io}(x) &\longleftrightarrow q(x)\\
> Q_{io}(\tau) &\longleftrightarrow G(\beta)
> \end{align*}

Comming back to HyperNova equations, we can now see that

\begin{align*}
c &= g(r_x')\\
&= \left( \sum_{j \in [t]} \gamma^j \cdot L_j(r_x') \right) + \gamma^{t+1} \cdot Q(r_x')\\
&= \left( \sum_{j \in [t]} \gamma^j \cdot \overbrace{e_1 \cdot \sigma_j}^{L_j(r_x')} \right) + \gamma^{t+1} \cdot \overbrace{e_2 \cdot \sum_{i \in [q]} c_i \prod_{j \in S_i} \theta_j}^{Q(x)}
\end{align*}

where $e_1 = \widetilde{eq}(r_x, r_x')$ and $e_2=\widetilde{eq}(\beta, r_x')$.

Which is the check that $V$ performs at step $5$.

An implementation of the Multifolding scheme can be found at https://github.com/privacy-scaling-explorations/multifolding-poc

-->

<!-- CSS hacks -->
<!-- Arnau note: I've put this to have section numbers (both in the content & in the table of contents), if you don't want numbers we can remove this -->
<style>
/* CSS hack to add section numbers to titles,
starting from h2.*/
/* Titles numbers */
.markdown-body h1 {counter-reset: h2}
.markdown-body h2 {counter-reset: h3}
.markdown-body h3 {counter-reset: h4}
.markdown-body h4 {counter-reset: h5}
.markdown-body h5 {counter-reset: h6}
.markdown-body h2:before {counter-increment: h2; content: counter(h2) ". "}
.markdown-body h3:before {counter-increment: h3; content: counter(h2) "." counter(h3) ". "}
.markdown-body h4:before {counter-increment: h4; content: counter(h2) "." counter(h3) "." counter(h4) ". "}
.markdown-body h5:before {counter-increment: h5; content: counter(h2) "." counter(h3) "." counter(h4) "." counter(h5) ". "}
.markdown-body h6:before {counter-increment: h6; content: counter(h2) "." counter(h3) "." counter(h4) "." counter(h5) "." counter(h6) ". "}
.markdown-body h2.nocount:before, .markdown-body h3.nocount:before, .markdown-body h4.nocount:before, .markdown-body h5.nocount:before, .markdown-body h6.nocount:before { markdown-body: ""; counter-increment: none }
.markdown-body h1:before, .markdown-body h2:before, .markdown-body h3:before, .markdown-body h4:before, .markdown-body h5:before, .markdown-body h6:before {
color: #737373!important;
}

/* TOC numbers */
.toc ul li ul {
counter-reset: section;
list-style-type: none;
}
.toc ul li ul li::before {
color: #919191!important;
counter-increment: section;
content: counters(section, ".") " ";
}
</style>