# The APK SNARK (the Fiat-Shamir transform)

###### tags: `arithmetization, APK SNARK, non-interactive protocol via Fiat-Shamir transform`

## Mathematical fundamentals
For some preliminary mathematical fundamentals of why the constraints that define the problem are chosen the way they are, you can read more [here](https://hackmd.io/C6L1SIgxSSmVHAvQ9Ck4gw).

## Summary of the efficiency of the SNARK
The proof size, in its shortest form, (including commitment $[t]_{1}$ and excluding commitments $([t_{lo}]_{1}, [t_{mid}]_{1}, [t_{hi}]_{1})$) is $4$ field elements shorter than the proof obtained [here](https://hackmd.io/bn1wtqwmQ-eXdrx5dCOeMA?view#Accountable-problem-verification-summary). I have included a couple of worked examples [here](https://hackmd.io/NlES9mnjTr-GPFFtNU6AbA?view) that detail how that method is used.

Also, it explicitly describes the computation of the verifier, which, [after re-writing the constraints](https://hackmd.io/VV3lHdX7SEWUw8lz7JY8FQ?view), allowed for further optimisations in terms of reducing the number of computations. Most specifically, the verifier does not have to compute $\omega^{n-1}$.

## Succinct non-interactive proof for the accountable problem

**Notation used to obtain the Fiat-Shamir transform:**
- In the following, by **transcript** we denote the concatenation of the common preprocessed input, the public trusted input, the public input, and the proof elements written by the
prover up to a certain point in time.
- We use $\mathcal{R}$ to refer to a hash function, $\mathcal{R} : \{0, 1\} \rightarrow \mathbb{F}_{p}$, that emulates the random oracle.

**COMMON PREPROCESSED INPUT:**
$n, [1]_{1}, [x]_{1}, [x^2]_{1}, \ldots, [x^{3n-3}]_{1}, [1]_{2}, [x]_{2}, (A_0, \ldots, A_{n-1}).$

**PUBLIC TRUSTED INPUT:**
$[pkx]_{1}$, $[pky]_{1}.$
**FOOTNOTE** *about public trusted input computation:* *The public trusted input described above is an input that is computed by a trusted validators set as follows: Given public key vector $(pk_0, \ldots, pk_{n-1})$, compute $pkx = (pkx_0, \ldots, pkx_{n-1})$ and $pky = (pky_0, \ldots, pky_{n-1})$ such that $\forall i \in \{0, \ldots, n-1\}$, $pk_i$ as an element of the curve $E$ has the affine representation $(pkx_i, pky_i)$. Then compute the polynomials $pkx(X) = \sum_{i=0}^{n-1} pkx_i \cdot L_i(X)$ and $pky(X) = \sum_{i=0}^{n-1} pky_i \cdot L_i(X)$ and, finally, compute the polynomial commitments $[pkx]_{1} = pkx(x) \cdot [1]_{1}$ and $[pky]_{1} = pky(x) \cdot [1]_{1}$.*

**PUBLIC INPUT CHECKED IN THE CIRCUIT:**
$h$ (allegedly not in $\mathbb{G}_1$), $apk$ (allegedly in $\mathbb{G}_1$), $b=(b_0, \ldots, b_{n-1})$ (alleged bitvector).

**PROVER ALGORITHM:**

**Prover Input:**
Witness vector $pk = (pk_0, \ldots, pk_{n-1})$.

$P^{apk}([pkx]_{1}, [pky]_{1}, h, apk, (b_0, \ldots, b_{n-1}); (pk_0, \ldots, pk_{n-1})):$

**Step 1:**
Compute $pkx = (pkx_0, \ldots, pkx_{n-1})$ and $pky = (pky_0, \ldots, pky_{n-1})$ such that $\forall i \in \{0, \ldots, n-1\}$, $pk_i$ as an element of the curve $E$ has the affine representation $(pkx_i, pky_i)$.

Compute the affine representation $h = (h_x, h_y)$ and $apk \oplus h = ((apk \oplus h)_{x}, (apk \oplus h)_{y})$.

Compute the polynomials
$$b(X) = \sum_{i=0}^{n-1} b_i \cdot L_i(X).$$

$$kaccx(X) = \sum_{i=0}^{n-1} kaccx_i \cdot L_i(X).$$

$$kaccy(X) = \sum_{i=0}^{n-1} kaccy_i \cdot L_i(X).$$

$$pkx(X) = \sum_{i=0}^{n-1} pkx_i \cdot L_i(X).$$

$$pky(X) = \sum_{i=0}^{n-1} pky_i \cdot L_i(X).$$

Compute $[b]_{1} = b(x)\cdot[1]_{1}$, $[kaccx]_{1} = kaccx(x) \cdot [1]_{1}$, $[kaccy]_{1} = kaccy(x)\cdot [1]_{1}$.
The first output of the prover is $([b]_{1}, [kaccx]_{1}, [kaccy]_{1})$.

Note that if we assume the commitments $[pkx]_{1}$ and $[pky]_{1}$ are generated by a trusted third party (or, in our case, by a set of trusted validators), then it should hold that $[pkx]_{1} = pkx(x)\cdot [1]_{1}$ and $[pky]_{1} = pky(x)\cdot [1]_{1}.$

**Step 2:**
Compute the sum challenge $r = \mathcal{R}(\mathbf{transcript})$.

Compute the vector of field elements $(b^{(0)}, \ldots, b^{(n/256 -1)})$, where $b^{(j)}$ is the field element formed by the $j$-th block of 256 consecutive bits that are part of vector $b$.

Compute $sum = \sum_{j=0}^{n/256-1} b^{(j)} r^j$.

Compute: $\frac{r}{2^{255}}, r^{\frac{n}{256}}$.

Compute polynomials

$$c(X) = \sum_{i=0}^{n-1} c_i \cdot L_{i}(X),$$
where $c_i$ is defined in the above section.

$$acc(X) = \sum_{i=0}^{n-1} acc_i \cdot L_{i}(X),$$
where $acc_i$ is defined in the above section.

Compute $[c]_{1} = c(x) \cdot [1]_{1}$, $[acc]_{1} = acc(x) \cdot [1]_{1}$.

The second output of the prover is $([c]_{1}, [acc]_{1})$.

**Step 3:**
Compute the quotient challenge $\alpha = \mathcal{R}(\mathbf{transcript})$.

Compute the polynomial $t(X)$
where
\begin{align*}
t(X)(X^n-1) = \ & a_1(X)(X-\omega^{n-1})+\alpha a_2(X)(X-\omega^{n-1}) +\alpha^2 a_3(X) \\
& +\alpha^3 a_4(X) +\alpha^4 a_5(X)+\alpha^5 a_6(X)+\alpha^6 a_7(X) \; .
\end{align*}

or, if we expand all the constraints defined by the polynomials $a_1(X), \ldots, a_7(X)$, we have:

\begin{align*}
t(X)(X^n-1) &= \\
&(X-\omega^{n-1}) \cdot [b(X) \cdot ((kaccx(X)-pkx(X))^2 \cdot (kaccx(X)+ pkx(X) - kaccx(\omega\cdot X)) - (pky(X)-kaccy(X))^2) + \\ &+ (1-b(X))\cdot (kaccy(\omega\cdot X) - kaccy(X))] + \\
& +\alpha (X-\omega^{n-1})\cdot [b(X) \cdot ((kaccx(X) - pkx(X)) \cdot (kaccy(\omega \cdot X) + kaccy(X)) - (pky(X) - kaccy(X)) \cdot (kaccx(\omega \cdot X) - kaccx(X))) + \\
&+(1-b(X)) \cdot (kaccx(\omega \cdot X) - kaccx(X))] + \\
& +\alpha^2 \cdot [b(X) \cdot (1-b(X))] + \\
& +\alpha^3 \cdot [c(\omega \cdot X) - c(X)\cdot (2+ (\frac{r}{2^{255}} -2) \cdot A(\omega \cdot X)) - (1 - r^{\frac{n}{256}}) \cdot L_{n-1}(X)] + \\
& +\alpha^4 \cdot [(kaccx(X) - h_x)\cdot L_0(X) + (kaccx(X) - (h\oplus apk)_{x}) \cdot L_{n-1}(X)] + \\
& +\alpha^5 \cdot [(kaccy(X) - h_y)\cdot L_0(X) + (kaccy(X) - (h\oplus apk)_{y}) \cdot L_{n-1}(X)] + \\
& +\alpha^6 \cdot [ acc(\omega \cdot X) - acc(X) - b(X)\cdot c(X) + \mathit{sum} \cdot L_{n-1}(X)] \; .
\end{align*}

Polynomial $t(X)$ has degree at most $3\cdot n - 3$.

Compute $[t]_{1} = t(x) \cdot [1]_{1}$.
The third output of the prover is $[t]_{1}$.

**Step 4:**
Compute evaluation challenge $\zeta = \mathcal{R}(\mathbf{transcript})$.

Compute opening evaluations:

$\overline{pkx} = pkx(\zeta), \overline{pky}=pky(\zeta), \overline{b}=b(\zeta), \overline{kaccx}=kaccx(\zeta), \overline{kaccy}=kaccy(\zeta), \\
\overline{c}=c(\zeta), \overline{acc}=acc(\zeta), \overline{t}=t(\zeta).$

Compute linearization polynomial:

\begin{align*}
r(X) = (\zeta - \omega^{n-1}) \cdot &[-\bar{b} \cdot (\overline{kaccx} - \overline{pkx})^2 \cdot kaccx( X) + (1 - \bar{b})\cdot kaccy(X)]+ \\
&+ \alpha \cdot (\zeta - \omega^{n-1}) \cdot [\bar{b} \cdot ((\overline{kaccx} - \overline{pkx}) \cdot kaccy(X) - (\overline{pky} - \overline{kaccy}) \cdot kaccx(X)) + (1 - \bar{b}) \cdot kaccx(X)]+ \\
&+\alpha^3 \cdot c(X)+ \\
&-\alpha^3 \cdot \bar{c} \cdot (2+ (\frac{r}{2^{255}}- 2) \cdot A(X))+ \\
&+\alpha^6 \cdot acc(X).
\end{align*}

Compute $\overline{r_{\omega}} = r(\omega \cdot \zeta)$.

The fourth output of the prover is $(\overline{pkx}, \overline{pky}, \overline{b}, \overline{kaccx}, \overline{kaccy}, \overline{c}, \overline{acc},\overline{r_{\omega}})$.

**Step 5:**
Compute opening/batching challenge $\nu = \mathcal{R}(\mathbf{transcript})$.

Compute opening proof polynomial.

\begin{align*}
W_{\zeta}(X) = \frac{1}{X-\zeta}&(t(X) - \bar{t}+ \\
&+ \nu(pkx(X) - \overline{pkx}) +\\
&+ \nu^2(\cdot pky(X) - \overline{pky}) + \\
&+ \nu^3 (b(X) - \bar{b}) + \\
&+ \nu^4( kaccx(X) - \overline{kaccx}) + \\
&+ \nu^5(kaccy(X) - \overline{kaccy}) + \\
&+ \nu^6 (c(X) -\bar{c}) + \\
&+ \nu^7 (acc(X) - \overline{acc}))
\end{align*}

and opening proof polynomial

\begin{align*}
W_{\zeta \cdot \omega}(X) = \frac{1}{X-\zeta \cdot \omega}&(r(X) - \overline{r_{\omega}}).
\end{align*}
Compute $[W_{\zeta}]_{1} = W_{\zeta}(x) \cdot [1]_{1}$ and $[W_{\zeta \cdot \omega}]_{1} = W_{\zeta \cdot \omega}(x) \cdot [1]_{1}.$

The fifth output of the prover is $([W_{\zeta}]_{1}, [W_{\zeta \cdot \omega}]_{1})$.

Return $\pi_{APK \ SNARK}$ where $\pi_{APK \ SNARK} = ([b]_{1}, [kaccx]_{1}, [kaccy]_{1}, [c]_{1}, [acc]_{1}, [t]_{1}, [W_{\zeta}]_{1}, [W_{\zeta \cdot \omega}]_{1}, \\ \overline{pkx}, \overline{pky}, \overline{b}, \overline{kaccx}, \overline{kaccy}, \overline{c}, \overline{acc}, \overline{r}_{\omega}).$

Compute the multipoint evaluation challenge $u = \mathcal{R}(transcript)$.

**VERIFIER ALGORITHM:**

**Verifier Preprocessed Input:**
$[A]_{1} = A(x) \cdot [1]_{1}.$

**$V^{apk}([pkx]_{1}, [pky]_{1}, h, apk, (b_0, \ldots, b_{n-1}) ,\pi_{APK \ SNARK}):$**

**Step 1:**
Compute the affine representation $h = (h_x, h_y)$ and $apk \oplus h = ((apk \oplus h)_{x}, (apk \oplus h)_{y})$.

**Step 2:**
Validate $\mathbb{G}_1$ proof elements $([b]_{1}, [kaccx]_{1}, [kaccy]_{1}, [c]_{1}, [acc]_{1}, [t]_{1}, [W_{\zeta}]_{1}, [W_{\zeta \cdot \omega}]_{1}) \in \mathbb{G}_1^{10}.$

**Step 3:**
Validate $\mathbb{F}_p$ proof elements $(\overline{pkx}, \overline{pky}, \overline{b},\overline{kaccx}, \overline{kaccy}, \overline{c}, \overline{acc}, \overline{r}_{\omega}) \in \mathbb{F}_p^{8}.$

**Step 4:**
Compute challenges $(r, \alpha, \zeta, \nu, u)$ as in the prover $P^{apk}$ description from the common input, trusted public input, public input and respective necessary parts of the $\mathbf{transcript}$ using elements of $\pi_{APK \ SNARK}$.

**Step 5:**
Compute the vector of field elements $(b^{(0)}, \ldots, b^{(n/256 -1)})$, where $b^{(j)}$ is the field element formed by the $j$-th block of 256 consecutive bits that are part of vector $b$.

Compute evaluation using challenge $r$: $sum = \sum_{j=0}^{n/256-1} b^{(j)} r^j$.

Compute: $\frac{r}{2^{255}}, r^{\frac{n}{256}}$.

**Step 6:**
Compute element power $\omega^{n-1}$ and polynomial evaluation $\zeta^{n} -1$ and Lagrange basis polynomials $L_0(\zeta)= \frac{\zeta^n - 1}{n \cdot (\zeta-1)}$ and $L_{n-1}(\zeta)= \frac{(\zeta^n - 1) \cdot \omega^{n-1}}{n \cdot (\zeta - \omega^{n-1})}$.

**Step 7:**
**FOOTNOTE:** *This step can be optimised in obvious ways in order to reduce the number of field operations necessary to compute $\bar{t}$. We choose to include the non-compact formula in this write-up such that the reader is able to follow the linearisation process to a larger extent than via a more compact formula.*

Compute quotient polynomial evaluation $$\bar{t} =
\frac{\overline{r_{\omega}} + [\bar{b}((\overline{kaccx} - \overline{pkx})^2 \cdot (\overline{kaccx} + \overline{pkx})- (\overline{pky} - \overline{kaccy})^2) - (1-\bar{b})\cdot \overline{kaccy}]\cdot (\zeta - \omega^{n-1})}{\zeta^{n} - 1} +$$

$$+ \frac{\alpha \cdot [\bar{b} \cdot ((\overline{kaccx} - \overline{pkx}) \cdot \overline{kaccy} + (\overline{pky} - \overline{kaccy}) \cdot \overline{kaccx}) - (1 - \bar{b}) \cdot \overline{kaccx}] \cdot (\zeta - \omega^{n-1})}{\zeta^{n} - 1}+$$

$$+\frac{\alpha^2 \cdot \bar{b} \cdot (1 - \bar{b})}{\zeta^{n} - 1} +$$

$$-\frac{\alpha^3 \cdot[(1 - r^{\frac{n}{256}}) \cdot L_{n-1}(\zeta)]}{\zeta^{n} - 1} +$$

$$+\frac{\alpha^4 \cdot [(\overline{kaccx} - h_x) \cdot L_0(\zeta) + (\overline{kaccx} - (h\oplus apk)_x) \cdot L_{n-1}(\zeta)]}{\zeta^{n} - 1} +$$

$$+\frac{\alpha^5 \cdot[(\overline{kaccy} - h_y) \cdot L_0(\zeta) + (\overline{kaccy} - (h\oplus apk)_y) \cdot L_{n-1}(\zeta)]}{\zeta^{n} - 1} +$$

$$+\frac{\alpha^6 \cdot [- \overline{acc} - \bar{b} \cdot \bar{c} + \mathit{sum} \cdot L_{n-1}(\zeta)]}{\zeta^{n} - 1}.$$

**Step 8:**
Compute full batched polynomial commitment $[F]_{1}$

\begin{align*}
[F]_{1} =& [t]_{1} + \nu \cdot [pkx]_{1} + \nu^2 \cdot [pky]_{1} + \nu^3 \cdot [b]_{1} \ + \\
& + (u \cdot (\zeta - \omega^{n-1})\cdot (-\bar{b} \cdot ((\overline{kaccx} - \overline{pkx})^2 + \alpha \cdot (\overline{pky} - \overline{kaccy}))+\alpha \cdot (1 - \bar{b})) + \nu^4) \cdot [kaccx]_{1} \ + \\
& +(u \cdot (\zeta - \omega^{n-1})(\alpha \cdot \bar{b}(\overline{kaccx} - \overline{pkx})+ (1- \bar{b})) + \nu^5) \cdot [kaccy]_{1} \ + \\
& +(u\cdot \alpha^3+ \nu^6) \cdot [c]_{1} \ + \\
& +(u\cdot \alpha^6+ \nu^7)\cdot [acc]_{1} \ +\\
& -u \cdot \alpha^3 \cdot \bar{c} \cdot (2+ (\frac{r}{2^{255}} -2)\cdot [A]_{1}).
\end{align*}

**Step 9:**
Compute group-encoded batch evaluation $[E]_{1}$

$$[E]_{1} = (\bar{t} + \nu \cdot \overline{pkx} + \nu^2 \cdot \overline{pky} + \nu^3 \cdot \bar{b} +
\nu^4 \cdot \overline{kaccx} + \nu^5 \cdot \overline{kaccy} + \nu^6 \cdot \bar{c} + \nu^7 \cdot \overline{acc} + u \cdot \overline{r_{w}}) \cdot [1]_{1}$$

**Step 10:**
Batch validate all evaluations by checking that the following holds
$$e([W_{\zeta}]_{1} + u \cdot [W_{\zeta \cdot \omega}]_{1},[x]_{2}) = e(\zeta \cdot [W_{\zeta}]_{1} + u \cdot \zeta \cdot \omega \cdot [W_{\zeta \cdot \omega}]_{1} + [F]_{1} - [E]_{1}, [1]_{2}).$$