# Deferred Computation

Let $F_{p}$ and $F_{q}$ be the two fields, with $∣E_{p}(F_{q})∣=p$, $∣E_{q}(F_{p})∣=q$ for Elliptic curves $E_{p}(F_{q})$ and $E_{q}(F_{p})$. Assume $q>p$. We have a proof system (Kimchi) over $F_{p}$ and $F_{q}$, where commitments to public inputs are:

$P_{p}=⟨e,H⟩∈E_{p}(F_{q})P_{q}=⟨e,G⟩∈E_{q}(F_{p})$

Respectively. See Pasta Curves for more details.

When referring to the $F_{q}$-side we mean the proof system for circuit over the field $F_{q}$.

## Public Inputs / Why Passing

In pickles-rs we have the notion of “passing” a variable (including the transcript) from one side to the other. e.g. when a field element $α∈F_{p}$ needs to be used as a scalar on $F_{q}$.

This document explains what goes on “under the hood”. Let us start by understanding why:

Let $v∈F_{q}$ be a scalar which we want to use to do both:

- Field arithmetic in $F_{q}$
- Scalar operations on $E_{q}(F_{p})$

In order to do so efficiently, we need to split these operations across two circuits (and therefore proofs) because:

- Emulating $F_{q}$ arithmetic in $F_{p}$ is very expensive, e.g. computing $v⋅w$ requires $O(g(q)_{2})$ multiplications over $F_{p}$: 100’s of gates for a single multiplication.
- Since $E_{q}(F_{p})⊆F_{p}×F_{p}$ we cannot compute $[v]⋅H∈E_{q}(F_{p})$ over $F_{q}$ efficiently, because, like before, emulating $F_{p}$ arithmetic in $F_{q}$ is very expensive…

### Solution

The solution is to “pass” a value $v$ between the two proofs, in other words to have two values $v∈F_{p}$ and $v∈F_{q}$ which are equal as integers i.e. $lift(v)=lift(v)∈Z$: they represent “the same number”. A naive first attempt would be to simply add $v~∈F_{p}$ to the witness on the $F_{p}$-side, however this has two problems:

**Insufficient Field Size:** $p<q$ hence $v$ cannot fit in $F_{p}$.

**No Binding:** More concerning, there is *no binding* between the $v~$ in the $F_{p}$-witness and the $v$ in the $F_{q}$-witness: a malicious prover could choose completely unrelated values. This violates soundness of the overall $F_{q}/F_{q}$-relation being proved.

#### Problem 1: Decompose

The solution to the first problem is simple:

In the $F_{q}$-side decompose $v=2⋅h+l$ with $h∈[0,2_{⌊logp⌋})$ (high bits) and $l∈{0,1}$ (low bit). Note $l,h<p$ since $2p>q$; always the case for any cycle of curves, $p$ is only $≈q $ smaller than $q$, by Hasse. Now “$v$” is “represented” by the two values $h,l~∈F_{p}$.

Note that no decomposition is nessary if the “original value” $v$ was in $F_{p}$, since $F_{q}$ is big enough to hold the lift of any element in $F_{p}$.

#### Problem 2: Compute Commitment to the Public Input of other side

To solve the binding issue we will add $l,h$ to the public inputs on the $F_{p}$-side, for simplicity we will describe the case where $l,h$ are the only public inputs in the $F_{p}$-side, which means that the commitment $P_{p}∈E_{p}(F_{q})$ to the public inputs on the $F_{p}$ side is:

$P_{p}=[h]⋅G_{h}+[l]⋅G_{l}∈E_{p}(F_{q})$

At this point it is *important to note* that $E_{p}$ is defined over $F_{q}$!

Which means that we can compute $P_{p}∈E_{p}(F_{q})$ **efficiently** on the $F_{q}$-side!

Therefore to enforce the binding, we:

- Add a sub-circuit which checks: $P_{p}=[h]⋅G_{h}+[l]⋅G_{l}∈E_{p}(F_{q}),∣h∣=⌊gp⌋∣l∣=1$
- Add $P_{p}=(x,y)∈F_{q}×F_{q}$ to the public input on the $F_{q}$-side.

### We recurse onwards…

At this point the statement of the proof in $F_{q}$-side is: the $F_{q}$-proof is sound, **condition** on providing an opening of $P_{p}$ that satisifies the $F_{p}$-relation.

At this point you can stop and verify the proof (in the case of a “step proof” you would), by recomputing $P_{p}$ outside the circuit while checking the $F_{p}$-relation manually “in the clear”.

However, when recursing (e.g. wrapping in a “wrap proof”) we need to “ingest” this public input $P_{p}$; after all, to avoid blowup in the proof size everything (proofs/accumulators/public inputs etc.) must eventually become part of the witness and every computation covered by a circuit…

To this end, the wrap proof is a proof for the $F_{p}$-relation with the public input $P_{p}$ which additionally verifies the $F_{q}$-proof.

The next “step” proof then verifies this wrap proof which means that $P_{p}$ then becomes part of the witness!

### In Pickles

We can arbitrarily choose which side should compute the public input of the other, in pickles we let “wrap” compute the commitment to the public input.

## Enforcing Equality

Enforces that the public input of the proof verified on the Fr side is equal to the Fp input computed on Fr side.