$\newcommand{\cid}{\mathsf{circuitId}}
\newcommand{\pid}{\mathsf{proofId}}
\newcommand{\pidx}{\mathsf{proofIndex}}
\newcommand{\poseidon}{\mathsf{poseidon}}
\newcommand{\keccak}{\mathsf{keccak}}
\newcommand{\PI}{\mathsf{PI}}
\newcommand{\vk}{\mathsf{VK}}
\newcommand{\pk}{\mathsf{PK}}
\newcommand{\VK}{\mathsf{VK}}
\newcommand{\isnark}{\mathsf{SNARK_{\text{bv}}}}
\newcommand{\ipi}{\pi_{\text{bv}}}
\newcommand{\ivk}{\vk^{\text{bv}}}
\newcommand{\ipk}{\pk^{\text{bv}}}
\newcommand{\app}{\text{app}}
\newcommand{\snark}{\textsf{SNARK}}
\newcommand{\Verify}{\textsf{Verify}}
\newcommand{\sv}{\textsf{SuccinctVerify}}
\newcommand{\BV}{\text{BV}}
\newcommand{\truncate}{\mathsf{truncate}}
\newcommand{\outer}{\text{outer}}$
# Overview
*Application developers* register Groth16 *verification keys* (VKs) for their circuits with the `UpaProofReceiver` contract. Eack VK is assigned a $\cid$ (the Poseidon hash of the VK).
*Application clients* submit proofs and public inputs (PIs) to the `UpaProofReceiver` contract, along with the $\cid$ for the proofs. Each *submission* may contain one or more proof/PI pairs. Each proof/PI pair is assigned:
- a unique $\pid$ (equal to the Keccak hash of the circuit ID and PIs), and
- a $\pidx$ (a simple incrementing counter, used later for censorship resistance).
The proof and public inputs are not stored on-chain. Instead, events are emitted containing the proof and public input data for *aggregators* to monitor and receive.
*Aggregators* aggregate *batches* of proofs with *increasing* proof index values. A batch can aggregate proofs for many different circuits. In the case where invalid proofs have been submitted, aggregators may skip *only* submissions containing invalid proofs. Aggregators that skip valid submissions will be punished (see below).
As UPA receives and verifies batches, the corresponding proof ids are marked as verified in the `UpaVerifier` contract.
An application client can then submit a transaction to the application circuit (without proof), and the application contract can verify the existence of an associated ZKP as follows:
- The application computes the public inputs for the proof, exactly as it would in the absence of UPA
- The application contract calls `isVerified` on the `UpaVerifier` contract, passing in the public inputs $\PI$, along with the circuit id $\cid$.
- The `UpaVerifier` contract computes $\pid = \keccak(\cid, \PI)$ from the public inputs and returns `true` if it has marked $(\cid, \pid)$ as verified.
## Protocol
### Circuit registration
The application developer submits a transaction calling the `registerVK` method on the `UpaProofReceiver` contract, passing their verification key $\VK$.
The circuit's $\cid$ is computed as
$$
\cid = \poseidon(\vk)
$$
(We assume $\vk$ is serialized using [SnarkJS](https://github.com/iden3/snarkjs) or by following exactly the same protocol as SnarkJS).
$\VK$ is stored on the contract (for censorship resistance), indexed by $\cid$, and aggregators (who are assumed to be monitoring the contract) are notified via an event.
> NOTE: The Poseidon hash is expensive to compute in the EVM, but this operation is only performed once at registration time. This $\cid$ will be used to reference the circuit for future operations.
### Proof submission
The application client computes a transaction with proof $\pi$ and public inputs $\PI$, as it normally would. It then calls `submit` on the `UpaProofReceiver` contract, paying the aggregation fee in ether:
```solidity
contract UpaProofReceiver
{
...
function submit(
uint256[] calldata circuitIds,
Proof[] calldata proofs,
uint256[][] calldata publicInputs
) public payable override returns (bytes32 submissionId)
...
}
```
The `UpaProofReceiver.submit` method:
- computes $\pid = \keccak(\cid, \PI)$
- computes `proofDigest` as $\keccak(\pi)$
- rejects the tx if a proof with the same `proofId` (and `circuitId`) has already been submitted
- assigns a $\pidx$ to $(\pi, \PI)$ (using a single incrementing counter)
- emits an event which includes $(\pi, \PI)$
- updates contract state to record the fact that a proof for `proofId` has been submitted with $\pidx$ and `proofDigest`.
> Note: Proof data itself does not appear in the input data used to compute `proofId`. This is because when the proof is verified by the application, the application does not have access to (and does not require) any proof data. The application is only verifying the *existence* of a valid proof for the given circuit and public inputs.
> Application authors must ensure that the public inputs to their ZKPs contain some random or unpredictable elements (and in general this will already be the case for sound protocols, in order to prevent replay attacks). If the set of public inputs can be predicted by a malicious party, that malicious party can submit an invalid proof for the public inputs, preventing submission of further (valid) proofs for that same set of public inputs.
### Aggregated proof submission
Aggregators submit *aggregated proofs* to the `UpaVerifier.verifyAggregatedProof` method. Each aggregated proof shows that a batch of application proofs is valid. In return, aggregators receive batch submission fees.
```solidity!
function verifyAggregatedProof(
bytes calldata proof,
bytes32[] calldata proofIds)
external;
```
The `UpaVerifier` contract:
- checks that `proof` is valid for `proofIds`
- for each $\pid$ in `proofIds`:
- checks that $\pid$ has been submitted to the contract
- checks that $\pidx$ for $\pid$ is monotonically increasing (where the last seen $\pidx$ is recorded in contract state)
- marks $\pid$ as valid
- emits an event indicating that $\pid$ has been verified
### Proof verification by the application
The application wallet now creates the transaction calling the application's smart contract to perform the business logic. The application contract computes the public inputs, exactly as it would without UPA, and queries the `UpaVerifier.isVerified` method to confirm the existence of a corresponding proof.
```solidity!
function isVerified(uint256 circuitId, uint256[] calldata publicInputs)
external
view
returns (bool);
```
The `isVerified` method:
- computes $\pid$ from the public inputs
- checks for the existence of a verified proof for $\pid$.
## Censorship resistance
Censorship by an aggregator can be proven by a *claimant* as follows:
Let $\pidx$ be the proof index of a valid proof $\pid$ which has been skipped by an aggregator. The following should hold:
- $\pidx \neq 0$
- $\pidx$ is equal to the registered proof index for $\pid$
- $\pidx$ is less than the last verified `ProofIdx` (stored on the `UpaProofReceiver` contract)
The *claimant* must call a method on the `UpaVerifier` contract
```solidity!
function challenge(
uint256 circuitId,
Proof calldata proof,
uint256[] calldata publicInputs)
external;
```
which performs the following:
- compute $\pid$ from `circuitId` and `publicInputs`
- lookup the `proofDigest` and `proofIdx` for $\pid$
- require that `proofDigest == keccak(proof)`
- require that `proofIdx < lastVerifiedProofIdx`
- lookup the application `vk`, given `circuitId`
- require that `Groth16.Verify(vk, proof, publicInputs) == 1`
If the above conditions are all satisfied, the `UpaVerifier` contract pays the caller (the claimant) using the aggregator's stake
> Note: we currently assume a single aggregator. For multiple aggregators, we must record extra information in order to determine which aggregator skipped a valid proof.
> Note: the `proofDigest` is used here to prevent malicious clients from submitting invalid proofs, forcing aggregators to skip their proofs, and then later providing valid proofs for the same public inputs. This would otherwise be an attack vector since `proofId` is not dependent on the proof data.
> We may need to introduce some time interval during which claims can be made (e.g. claims must be made before the proof index increases more than 2^12, say). Similarly, if penalties are to be paid from stake, aggregators should have an "unbonding period" of at least this interval
## Circuit Statements
Batches of $n$ application proofs are verified in a *batch verify circuit* using [batched Groth16 verification](https://hackmd.io/ll9PUdzSSO2nUvfNn5Y_0g).
A *keccak circuit* computes all $\pid$s of application proofs appearing in the *batch verify proof*, along with a *final digest* (the keccak hash of these $\pid$s, used to reduce the public input size of the outer circuit below).
A collection of $N$ *batch verify proofs* along with the *keccak proof* for their $\pid$s and *final digest* is verified in an *outer circuit*.
On-chain verification of an outer circuit proof thereby attests to the validity of $n \times N$ application proofs with given $\pid$s.
$n$ - inner batch size. Application proofs per batch verify circuit.
$N$ - outer batch size. Number of batch-verify circuits per outer proof.
$L$ - the maximum number of public inputs for an application circuit.
### Batch Verify Circuit: Groth16 batch verifier
The batch verify circuit corresponds to the following relation:
- *Public inputs*:
- $(\ell_i, \cid_i, \overline{\PI}_i)_{i=1}^n$ where
- $\PI_i = (x_{i,j})_{j=1}^{\ell_i}$ is the public inputs to the $i$-th proof
- $\overline{\PI}_i = \PI_i | \{0\}_{j=\ell_i + 1}^{L}$ is $\PI_i$ after zero-padded to extend it to length $L$
- *Witness values*:
- $\overline{\vk}_i$ - application verification keys, each padded to length $L$
- $(\pi_i)_{i=1}^n$ - application proofs
- *Statement*:
- $\cid_i = \poseidon(\truncate(\ell_i, \overline{\vk}_i))$
- $\overline{\PI}_i = \truncate(\ell_i, \overline{\PI}_i) | \{0\}_{j=\ell_i + 1}^{L}$
- `Groth16.Verify`$(\overline{\vk}_i, \pi_i, \overline{\PI}_i) = 1$ for $i=1,\ldots,n$ ([batched G16](https://hackmd.io/PZmhPljxRZm_IA7FC4Gu7A))
- where
- $\truncate(\ell, \overline \vk)$ is the truncation of the size $L$ verification key $\overline \VK$ to a verification key of size $\ell$, and
- $\truncate(\ell, \overline \PI)$ is the truncation of the public inputs to an array of size $\ell$
### Keccak Circuit: ProofIds and Final Digest
Computes the $\pid$ for each entry in each application proof in one or more verify circuit proofs.
- *Public inputs*:
- $c^*, (\ell_i, \cid_i, \overline{\PI}_i)_{i=1}^{n \times N}$ where
- $\PI_i = (x_{i,j})_{j=1}^{\ell_i}$ is the public inputs to the $i$-th proof
- $\overline{\PI}_i = \PI_i | \{0\}_{j=\ell_i + 1}^{L}$ is $\PI_i$ after zero-padded to extend it to length $L$
- $c^* = (c^*_1, c^*_2)$ (digest, which consists of 32 bytes and is represented by two field elements)
- *Witness values*: (none)
- *Statement*:
- $c_i = \keccak(\cid_i || \truncate(\ell_i, \overline \PI_i))$
- $c^* = \keccak(c_1 || c_2 || \ldots || c_{n \times N})$
### Outer Circuit: Recursive verification of Batch Verifier and Keccak circuits
This step aggregates $N$ batch verify proofs ${\ipi}^{(j)}, j = 1, \ldots N$ as well as a single corresponding Keccak proof $\pi_{keccak}$.
- Public Inputs:
- $c^*$ - final 32-byte public input digest, encoded as $(c_1, c_2) \in \mathbb{F}_r^2$
- $(L, R) \in \mathbb{G}_1^2$ - overall KZG accumulator, encoded as $12 = 4 * \texttt{num_limbs}$ points of $\mathbb{F}_r$
- Witness values:
- $(\ell_{i,j}, \cid_{i,j}, \overline \PI_{i,j}, \pid_{i,j}) \text{ for } i=1,\ldots, n, j=1, \ldots, N$: the number of public inputs, the circuit ID, padded public inputs and proof ID for the $i$-th application proof in the $j$-th BV proof.
- $(\ipi^{(j)})$ for $j=1, \ldots, N$ BV proofs
- $\pi_{\keccak}$ the Keccak proof for the public inputs
- $c^*$, and
- $(\ell_{1,1}, \cid_{1,1}, \overline{\PI}_{1,1}), (\ell_{2,1}, \cid_{2,1}, \overline{\PI}_{2,1}), \ldots , (\ell_{n,1}, \cid_{n,1}, \overline{\PI}_{n,1}),$
$(\ell_{1,2}, \cid_{1,2}, \overline{\PI}_{1,2}), (\ell_{2,2}, \cid_{2,2}, \overline{\PI}_{2,2}), \ldots , (\ell_{n,2}, \cid_{n,2}, \overline{\PI}_{n,2}),$
$\cdots$
$(\ell_{1,N}, \cid_{1,N}, \overline{\PI}_{1,N}), (\ell_{2,N}, \cid_{2,N}, \overline{\PI}_{2,N}), \ldots , (\ell_{n,N}, \cid_{n,N}, \overline{\PI}_{n,N}),$
- "Equivalent Statement": (actual statement is shown as multiple sub-statements, given below)
- All BV proofs are valid, and therefore there exist valid application proofs for each $\PI_{i,j}$:
$$\snark_{\BV}.\Verify \left( \ipi^{(j)}, (\ell_{i,j}, \cid_{i,j}, \overline \PI_{i,j})_{i=1}^n, \vk_{\BV} \right)$$
for $j=1,\ldots, N$
- Keccak proof is valid, and therefore $c^*$ is the final digest for all application PIs and vk hashes:
$$\snark_{\keccak}.\Verify \left(\pi_\keccak, c^*,(\ell_{i,j}, \cid_{i,j}, \overline \PI_{i,j})_{\substack{i=1,\ldots, n \\ j=1,\ldots, N}}, \vk_\keccak \right)=1$$
- Actual Statement:
- "Succinct" Plonk verification ($\sv$) namely "GWC Steps 1-11" using Shplonk, without final pairing:
$$\begin{gathered}
(L_j, R_j) = \sv \left( \ipi^{(j)}, (\ell_{i,j}, \cid_{i,j}, \overline \PI_{i,j})_{i=1}^n, \vk_{\BV} \right) ~\text{ for } j=1,\ldots N \\
(L_{N+1}, R_{N+1}) = \sv \left( \pi_\keccak, c^*,(\ell_{i,j}, \cid_{i,j}, \overline \PI_{i,j})_{\substack{i=1,\ldots, n \\ j=1,\ldots, N}}, \vk_\keccak \right) \\
(L, R) = \sum_{j=1}^{N+1} r^j (L_j, R_j)
\end{gathered}$$
for random challenge scalar $r$.
- Verification: The EVM verifier does the following, given $(\pi_{\text{outer}}, L, R, c^*)$.
- $(L_\outer, R_\outer) := \sv(\pi_\outer, L, R, c^*, \vk_\outer)$
- $e(L + r' L_\outer, [\tau]_2) \stackrel{?}{=} e(R + r' R_\outer, [1]_2)$ for random challenge scalar $r'$
Note that:
- The same witness values $\overline \PI_{i,j}$ are used to verify $\ipi^{(j)}$ and $\pi_{keccak}$, implying that $c^*$ is indeed the commitment to all application public inputs and circuit IDs.
- The outer circuit does not include the pairing checks, therefore its statement is not that the BV/Keccak proofs are *valid*, but rather that they have been correctly accumulated into a single KZG accumulator $(L,R)$. Checking that $e(L + r' L_\outer, [\tau]_2) \stackrel{?}{=} e(R + r' R_\outer, [1]_2)$, for random scalar $r'$, therefore implies their validity.
## Gas Cost Estimation
### Using NEBRA on L1 (Ethereum Deployment)
Verifying a Groth16 proof costs ([reference](https://hackmd.io/@nebra-one/ByoMB8Zf6)):
$$\approx 200 + 6 \ell ~~~ \textsf{(K Gas)}$$
where $\ell$ is the size of public input (in terms number of $F_r$). For example, the semaphore circuit has $\ell = 4$ elements of $F_r$ and its the verification cost is roughly 224K gas.
Using NEBRA UPA, the verification cost breaks into three parts:
- the cost of submission cost of individual (batched) proofs
- the cost of verifying aggregated proofs (amortized among individual proofs)
- NEBRA's protocol charges
As shown before, the proof submission could be done using `submitProof`, or `submitBatchedProofs`. The later has a lower amortized cost. The table below details the gas cost of using NEBRA:
| method | cost |
| ----------------------- | ------- |
| `submitProof` | 84K |
| `submitBatchedProofs` | ~84K |
| `verifyAggregatedProof` | 700K |
#### Amortized Cost per Proof
NEBRA would support deployment under different configurations. Let $n$ be the number of proofs aggregated per batch, and $m$ be the number of proofs submitted in the batched submission mode, then the individual cost would be:
$$ \frac{84}{m} + \frac{700}{n} ~~~ \textsf{K Gas} $$
> Note: there is a variable cost related to public input size, but since we are handling Keccak **in circuit**, the additional cost of Keccak in contract is neglegible, given a reasonable public input size.
- Case 1:
Let $n=32, m = 10$, the gas cost per proofs would be $30.4$ K Gas plus NEBRA's protocol surcharges.
- Case 2:
Let $n=32, m = 32$, the gas cost per proofs would be $24.5$ K Gas plus NEBRA's protocol surcharges.
Sign in with Wallet
Connect another wallet