# Delegation of Non-native Operations

<br />

# Commitment Scheme over Cycle Curves

## IPA over Grumpkin Curve

The core of IPA is "divide and conquer", obviousely it's comunication cost is $\log n$. But why does it work? we'll detail the protocol and prove for that next.

<br />

### Protocol Spec

First of all, prover compute:
$$
C = \vec{a} \cdot \vec{g} + \vec{b} \cdot \vec{h} + \langle \vec{a}, \vec{b} \rangle \cdot q
$$

where $\vec{a}, \vec{b} \in \mathbb{F}_r$ are public and private scalars seperately, $\vec{g}, \vec{h}, q \in E(\mathbb{F}_p)$ are public group elements.

<br />

And then sends commitment of inner product $\langle \vec{a}, \vec{b} \rangle$ which equals $C$ to verifier .

<br />

#### prover side

prover compute the <span style="color: red">halved commitments of cross part</span>:
$$
\begin{aligned}
C_L &= \vec{a}_R \cdot \vec{g}_L + \vec{b}_L \cdot \vec{h}_R + \langle \vec{a}_R, \vec{b}_L \rangle \cdot q \\
C_R &= \vec{a}_L \cdot \vec{g}_R + \vec{b}_R \cdot \vec{h}_L + \langle \vec{a}_L, \vec{b}_R \rangle \cdot q \\
\end{aligned}
$$

where $\vec{a}_L, \vec{b}_L, \vec{g}_L, \vec{h}_L$ are the left parts of $\vec{a}, \vec{b}, \vec{g}, \vec{h}$ respectively, and $\vec{a}_R, \vec{b}_R, \vec{g}_R, \vec{h}_R$ are the right parts of that.

<br />

and prover send $C_L, C_R$ to verifier, verfier sends a challenge factor $x$ as a response to prover, or through Fiat-Shamir mechanic to generate $x$:
$$
x \leftarrow RO(C_L, C_R) \\
$$

<br />

After that prover compute the halved commitment $C_{prover}'$:
$$
C_{prover}' = \vec{a'} \cdot \vec{g'} + \vec{b'} \cdot \vec{h'} + \langle \vec{a'} \cdot \vec{b'} \rangle \cdot q
$$

where:
$$
\begin{aligned}
&x \in \mathbb{F}_r \Rightarrow
\begin{cases}
\vec{a'} &= \vec{a}_L + x \cdot \vec{a}_R \\
\vec{b'} &= \vec{b}_L + x^{-1} \cdot \vec{b}_R \\
\vec{g'} &= \vec{g}_L + x^{-1} \cdot \vec{g}_R \\
\vec{h'} &= \vec{h}_L + x \cdot \vec{h}_R \\
\end{cases}
\end{aligned}
$$

<br />

After then prover sends commitment of the halved vectors $C_{prover}'$ to verifier.

<br />

#### verifier side

compute halved commitment $C_{verifier}'$:
$$
C_{verifier}' = x \cdot C_L + C + x^{-1} \cdot C_R
$$

update halved basis (points):
$$
\begin{aligned}
\vec{g'} &= \vec{g}_L + x^{-1} \cdot \vec{g}_R \\
\vec{h'} &= \vec{h}_L + x \cdot \vec{h}_R \\
\end{aligned}
$$

and then verify the equality:
$$
C_{verifier}' \overset{?}= C_{prover}'
$$

:::info
**Round Conclusion**

the original commitment $C = \vec{a} \cdot \vec{g} + \vec{b} \cdot \vec{h} + \langle \vec{a}, \vec{b} \rangle \cdot q$ holds, if and only if the halved commitment $C_{prover}'$ holds. So, verification for $C$ is reduced to verification of $C'$.
:::

<br />

#### Next Rounds of Protocol

We will step into the next round and repeat the process above until the last round where prover only need to send the last single scalars of $\vec{a'}, \vec{b'}$ to verifier for the final verification.

<br />

### Mathmatical Prove for Divide and Conquer

$$
x \cdot C_L + C + x^{-1} \cdot C_R \overset{?}= \vec{a'} \cdot \vec{g'} + \vec{b'} \cdot \vec{h'} + \langle \vec{a'}, \vec{b'} \rangle \cdot q
$$

we will stretch the left and right part respectively, and see if it works!

...

<br />

## KZG over BN254 Curve

### curve features

- $\mathbb{G}_1$ over $\mathbb{F}_p$ with order $r$, generator $G_1$
- $\mathbb{G}_2$ over $\mathbb{F}_{p^2}$ with order $r$, generator $G_2$
- $\mathbb{G}_T$ over $\mathbb{F}_{p^{2k}}$ where $k = 6$, with embedding degree-12, order $r$, and generator $G_T$

<br />

### pcs protocol spec

- $(vk, \vec{pk}) \leftarrow setup(\tau, 1^\lambda)$

$$
\begin{aligned}
&\tau \in \mathbb{F}_r \\
&pk_i = \tau^i \cdot G_1, i \in [1, m] \\
&vk = \tau \cdot G_2 \\
\end{aligned}
$$

- $C \leftarrow commit(\vec{pk}, \vec{p})$

$\vec{p}$ is the coefficients of polynomial $p(x)$

$$
\begin{aligned}
p(x) &\in \mathbb{F}_r[x] \\
\\
C &= p(\tau) \cdot G_1 \\
&= \sum_i p_i \cdot (\tau^i \cdot G_1) \\
&= \sum_i p_i \cdot pk_i
\end{aligned}
$$

- $\pi \leftarrow open(\vec{p}, z, y)$ where $y, z \in \mathbb{F}_r$

$$
\begin{aligned}
q(x) &= \frac{p(x) - y}{x - z} \\
\Downarrow \\
\pi &= q(\tau) \cdot G_1 \\
&= \sum_i q_i \cdot (\tau^i \cdot G_1) \\
&= \sum_i q_i \cdot pk_i
\end{aligned}
$$

- $0/1 \leftarrow verify(C, \pi, vk)$

$$
\begin{aligned}
e(\boxed{C + z \cdot \pi - y \cdot G_1}, G_2) &\overset{?}= e(\pi, \tau \cdot G_2) \\
\Updownarrow \\
e(G_1, G_2)^{p(\tau) + z \cdot q(\tau) - y} &\overset{?}= e(G_1, G_2)^{q(\tau) \cdot \tau} \\
\Updownarrow \\
G_T^{p(\tau) + z \cdot q(\tau) - y} &\overset{?}= G_T^{q(\tau) \cdot \tau}
\end{aligned}
$$

<br />

$G_2, \tau \cdot G_2, \pi, G_1, C$ are already provided, verifier needs to do:
- two scalar-mul $z \cdot \pi$ and $y \cdot G_1$, and two point addition $C + z \cdot \pi - y \cdot G_1$
- two bilinear mappings for $e(\boxed{C + z \cdot \pi - y \cdot G_1}, G_2)$ and $e(\pi, \tau \cdot G_2)$

<br />