# Emulated Pairing Circuits
$\newcommand{\FF}{\mathbb{F}}
\newcommand{\fptwelve}{\mathbb{F}_{p^{12}}}
\newcommand{\fp}{\mathbb{F}_p}$
Notes on `@feltroidprime`'s [proposal](https://hackmd.io/@feltroidprime/B1eyHHXNT#5-Benchmarks) for efficient pairing checks in-circuit.

## Statement
Let $\fptwelve$ be the extension field of $\fp$ defined by an irreducible degree 12 polynomial $P(X)$: $$\fptwelve \cong \fp[X]/(P)$$
Let $A_i, B_i, R_i \in \fptwelve$ for $i=1, \ldots N$. We wish to show that $A_i \cdot B_i = R_i$ for each $i$.

## Method
Considering $\fptwelve$ as $\fp[X]/(P)$, each $A_i, B_i, R_i$ is uniquely represented as a polynomial $A_i(X), B_i(X), R_i(X)$ of degree $<12$.
> Q: The representation is only unique if we require degree $<12$. Do we impose this as a constraint? For example by using a PCS that can only commit to deg $<12$ ?

The statement $A_i \cdot B_i = R_i$ is equivalent to the existence of a polynomial $Q_i(X)$ such that $$A_i(X) B_i(X) = Q_i(X) P(X) + R_i(X)$$
The usual Schwarz-Zippel argument implies that this can be checked to hold with high probability by checking the condition at a point $z_i$ chosen by the verifier (or provided by Fiat-Shamir). By requiring the Prover to commit to all witnesses in advance, we may take all $z_i$ equal to a single point $z$.

We can then use random coefficients $c_i$ to reduce the $N$ claims to
$$\sum_{i=1}^N c_i A_i(z) B_i(z) = P(z) \sum_{i=1}^N c_i Q_i(z) + \sum_{i=1}^N c_i R_i(z)$$

## Interactive Protocol

- Prover and Verifier both have list of pairs $(A_i, B_i), i=1,\ldots N$
- Prover has polynomials $Q_i, R_i$, $i=1,\ldots N$
> Q: Or do we consider Verifier to also hold the list $R_i$ ? It's a little unclear to me what we should consider to be the "private" part of the witness. It would also make sense to me to say the triple $(A_i, B_i, R_i)$ is public and only $Q_i$ is private.

1. Prover computes commitments $C(Q_i), C(R_i)$, $i=1,\ldots N$, sends to Verifier.
2. Verifier now holds $A_i, B_i, C(Q_i), C(R_i)$, $i=1,\ldots,N$. Verifier samples $z, c_i \in \fp$, $i=1,\ldots,N$, sends to Prover.
> Q: $c_i$ needs to be an $\fp$ point, right? I think sampling it from $\FF_r$ leads to an ill-defined multiplication of $\fp$ and $\FF_r$ points.
> A: Ah, I see now that we actually take $c_i \in [0, 2^k)$ for some $k$, so the $\FF_r, \fp$ distinction is not of practical importance.
4. Prover evaluates $a_i = A_i(z), b_i = B_i(z), q_i = Q_i(z), r_i = R_i(z)$ and sends these evaluations to Verifier, together with...?
> Q! : What else does the Prover send? Evaluation proofs for the $a_i, b_i$? Opening proofs for $q_i, r_i$? Or does the Verifier compute $a_i, b_i$ directly?
5. Verifier computes $\sum_1^N c_i a_i b_i$ and $\left( P(z)\sum_1^N c_i q_i + \sum_1^N c_i r_i \right)$. Verifier accepts iff these are equal.
> Q: Or do we have the Prover compute these expressions and send something like an IPA proof that the final result is correct?

## More Questions
(Some of these things might just be unclear to me because I'm unfamiliar with Cairo programs -- much more used to thinking about R1CS/Plonk circuits.)

- Is this protocol thought of as somehow taking place in a circuit? In other words, do we write out the Verifier's checks as circuit constraints and generate a witness? I'm wondering about the efficiency of having the polynomial commitment openings checked in-circuit.
- [Section 4](https://hackmd.io/@feltroidprime/B1eyHHXNT#Verifying-a-single-equation-with-a-polynomial-commitment-scheme) of the original note says "At a given multiplication $i$, we derive the next $z$ and $c_i$ by computing..." What is meant by "next $z$"? The RLC trick assumes we use a single common point $z$ in order to factor out the $P(z)$ term