UPA protocol specification

Version 1.0.0

Overview

Application developers register Groth16 verification keys (VKs) for their circuits with the UpaProofReceiver contract. Upon registration, each VK is assigned a $\mathsf{circuitId}$ (the Poseidon hash of the VK).

Application Clients submit proofs and public inputs (PIs) to the UpaProofReceiver contract as tuples $(\pi, \mathsf{PI}, \mathsf{circuitId})$ , where $\pi$ is expected to be a proof that $\mathsf{PI}$ is an instance of the circuit with circuit id $\mathsf{circuitId}$ .

A single call to the contract submits an ordered list $(\pi_i, \mathsf{PI}_i, \mathsf{circuitId}_i)_{i=0}^{n-1}$ (of any size $n$ up to some implementation-defined maximum $N$ ) of these tuples. This ordered list of tuples is referred to as a Submission. Submissions of more than 1 proof allow the client to amortize the cost of submitting proofs. Note that there is no requirement for the $\mathsf{circuitId}_i$ s to match. A single Submission may contain proofs for multiple application circuits.

Each tuple in a submission is assigned:

$\mathsf{proofId}$ - a unique proof id (equal to the Keccak hash of the circuit ID and PIs), and
$\mathsf{proofIndex}$ - a proof index (a simple incrementing counter, used later for censorship resistance).

Each submission is assigned:

a Submission Id $\mathsf{submissionId}$ , computed as the Merkle root of the list of $\mathsf{proofId}_i$ s, padded to the nearest power of 2 with bytes32(0).
a submission index $\mathsf{submissionIndex}$ , a simple incrementing counter of submissions, used later for censorship resistance.

Note that:

for submissions that consist of a single proof, $\mathsf{proofId}_0 = \mathsf{submissionId}$ , and the submitted proof can be referenced by $\mathsf{proofId}_0$ , whereas
for submissions of multiple proofs, each proof is referred to by $\mathsf{submissionId}$ along with an index (or location) of the proof within the submission. Where required, a Merkle proof can be used to show that a proof with $\mathsf{proofId}_i$ is indeed at the given index within the submission $\mathsf{submissionId}$ .

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. The contract stores information about the submission (including $\mathsf{submissionIndex}$ , $n$ and some further metadata), indexed by the $\mathsf{submissionId}$ .

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 Censorship Resistance).

As UPA receives and verifies batches, the UpaVerifier contract marks the corresponding proof ids as verified. Note that, for proofs that are part of a multi-proof submission, the contract actually records the fact that the proof at index $i$ of submission $\mathsf{submissionId}$ was verified.

An application client can then submit a transaction to the application circuit (optionally with some ProofReference metadata), and the application contract can verify the existence of an associated valid 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 $\mathsf{PI}$ , the circuit Id $\mathsf{circuitId}$ , and any ProofReference metadata.
The UpaVerifier contract computes $\mathsf{proofId} = \mathsf{keccak}(\mathsf{circuitId}, \mathsf{PI})$ from the public inputs.
- If the proof was submitted by itself, $\mathsf{proofId}$ is equal to the submission ID, and the contract can immediately check whether a valid proof has been seen as part of an aggregated proof.
- If the proof was part of a multi-proof submission, the ProofReference metadata includes the $\mathsf{submissionId}$ , index $i$ of the proof within the submission $\mathsf{submissionId}$ , and a Merkle proof that $\mathsf{proofId}$ is indeed the $i$ -th leaf of the submission. After checking this Merkle proof, the contract can immediately verify that proof $i$ of submission $\mathsf{submissionId}$ has been seen as part of an aggregated proof batch.
The UpaVerifier returns true if it has marked $(\mathsf{circuitId}, \mathsf{proofId})$ as verified and false otherwise.

Protocol

Circuit registration

The application developer submits a transaction calling the registerVK method on the UpaProofReceiver contract, passing their verification key $\mathsf{VK}$ .

The circuit's $\mathsf{circuitId}$ is computed as

\mathsf{circuitId} = \mathsf{poseidon}(\mathsf{VK})

(We assume $\mathsf{VK}$ is serialized using SnarkJS or by following exactly the same protocol as SnarkJS).

$\mathsf{VK}$ is stored on the contract (for censorship resistance), indexed by $\mathsf{circuitId}$ , 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 $\mathsf{circuitId}$ will be used to reference the circuit for future operations.

Proof submission

The application client creates the parameters for its smart contract as normal, including one or more proofs $\pi_i$ and public inputs $\mathsf{PI}_i$ . It then passes these, along with the relevant (pre-registered) circuit Ids $\mathsf{circuitId}_i$ , to the submit method on the UpaProofReceiver contract, paying the aggregation fee in ether:

contract UpaProofReceiver
{
    ...
    function submit(
        uint256[] calldata circuitIds,
        Proof[] calldata proofs,
        uint256[][] calldata publicInputs
    ) public payable override returns (bytes32 submissionId)
    ...
}

The UpaProofReceiver.submit method:

computes $\mathsf{proofId}_i = \mathsf{keccak}(\mathsf{circuitId}_i, \mathsf{PI}_i)$ for $i = 0, \ldots, n-1$ .
computes a proofDigest $\mathsf{proofDigest}$ for each proof, as $\mathsf{keccak}(\pi_i)$
computes the submission Id $\mathsf{submissionId}$ as the Merkle root of the list $(\mathsf{proofId}_i)_{i=0}^{n-1}$ (padded as required to the nearest power of 2)
computes the digestRoot as the Merkle root of the list $(\mathsf{proofDigest}_i)_{i=0}^{n-1}$ (again padded as required to the nearest power of 2)
rejects the tx if an entry for $\mathsf{submissionId}$ already exists
assigns a $\mathsf{submissionIndex}$ to the submission (using a single incrementing counter)
assigns a $\mathsf{proofIndex}_i$ to each $(\pi_i, \mathsf{PI}_i)$ (using a single incrementing counter)
emits an event for each proof, including $(\mathsf{circuitId}_i, \pi_i, \mathsf{PI}_i, \mathsf{proofIndex}_i)$
updates the contract state to record the fact that a submission with id $\mathsf{submissionId}$ has been made, mapping it to digestRoot, $\mathsf{submissionIndex}$ , $n$ and the block number at submission time.

NOTE: Proof data itself does not appear in the input data used to compute $\mathsf{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.

NOTE: 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 demonstrates that a batch of previously submitted application proofs is valid. In return, aggregators receive batch submission fees.

function verifyAggregatedProof(
        bytes calldata proof,
        bytes32[] calldata proofIds,
        SubmissionProof[] calldata submissionProofs)
    external;

The UpaVerifier contract:

checks that proof is valid for proofIds
for each $\mathsf{proofId}$ in proofIds:
- checks that $\mathsf{proofId}$ has been submitted to the contract, and that proofs appear in the aggregated batch in the order of submission (see below)
- marks $\mathsf{proofId}$ as valid (see below)
- emits an event indicating that $\mathsf{proofId}$ has been verified

Specifically, the algorithm for verifying (in the correct order) submissions of proofIds and marking them as verified, is as follows.

State: the contract holds

a dynamic array uint16[] numVerifiedInSubmission of counters, where the $i$ -th entry corresponds to the number of proofs that have been verified (in order) of the submission with $\mathsf{submissionId} == i$
the submission index lastVerifiedSubmissionIdx of the last submission from which a proof was verified.

Given a list of proofIds and submissionProofs, the contract verifies that proofIds appear in previous submissions as follows:

For each $\mathsf{proofId}$ in proofIds:
- Attempt to lookup the submission data (see Proof Submission) for a submission whose $\mathsf{submissionId}$ is the same as $\mathsf{proofId}$ . If such a submission exists:
  - The proof was submitted as a single-proof submission. The contract extracts the $\mathsf{submissionIndex}$ from the submission data and then checks that $\mathsf{submissionIndex}$ is greater than lastVerifiedSubmissionIdx. If not reject the transaction.
  - The entry numVerifiedInSubmission[ $\mathsf{submissionIndex}$ ] should logically be 0 (this can be sanity checked by the contract). Set this entry to 1
- Otherwise (if no submission data was found for $\mathsf{submissionId} = \mathsf{proofId}$ )
  - the proof is expected to be part of a multi-proof submission with $\mathsf{submissionIndex} \geq$ lastVerifiedSubmissionIdx.
    Note that equality here is possible if a previous aggregated proof verified a strict subset of the entries in the submission. In this case, numVerifiedInSubmission[ $\mathsf{submissionIndex}$ ] should contain the number of entries already verified.
  - Take the next entry in submissionProofs. This includes the following information:
    the $\mathsf{submissionId}$ for the submission to be verified
    a Merkle "interval" proof for a contiguous set of entries from that submission.
Determine the number m of entries in proofIds, including the current $\mathsf{proofId}$ , that belong to this submission, as follows:
- Let numProofIdsRemaining be the number of entries (including $\mathsf{proofId}$ ) still unchecked in proofIds.
- Look up the submission data for $\mathsf{submissionId}$ , in particular $\mathsf{submissionIndex}$ and $n$ .
- Let numUnverifiedFromSubmission = $n$ - numVerifiedInSubmission[ $\mathsf{submissionIndex}$ ].
- The number m of entries from proofIds to consider as part of $\mathsf{submissionId}$ is given by Min(numUnverifiedFromSubmission, numProofIdsRemaining).
- Use the submission Id $\mathsf{submissionId}$ and the Merkle "interval" proof from the submission proof, to check that the m next entries from proofIds (including $\mathsf{proofId}$ ) indeed belong to the submission $\mathsf{submissionId}$ . Reject the transaction if this check fails.
- Increment the entry numVerifiedInSubmission[ $\mathsf{submissionIndex}$ ] by m, indicating that m additional proofs from the submission have been verified.
update lastVerifiedSubmissionIdx in the contract state

Proof verification by the application

The application client now creates the transaction calling the application's smart contract to perform the business logic. Since the proof has already been submitted to UPA, the proof is not required in this transaction. If the proof was submitted as part of a multi-entry submission, the client must compute and send a ProofReference structure indicating which submission the proof belongs to, and its "location" (or index) within it.

The application contract computes the public inputs, exactly as it otherwise would under normal operation, and queries the isVerified on the UpaVerifier contract (using the ProofReference if given) to confirm the existence of a corresponding verified proof.

// For single-proof submissions
function isVerified(
    uint256 circuitId,
    uint256[] calldata publicInputs
) external view returns (bool);

// For multi-proof submissions
function isVerified(
    uint256 circuitId,
    uint256[] calldata publicInputs,
    ProofReference calldata proofReference
) external view returns (bool);

The isVerified method:

computes $\mathsf{proofId}$ from the public inputs
(using the ProofReference if necessary) confirms that $\mathsf{proofId}$ belongs to a submission $\mathsf{submissionId}$ and reads the submission index $\mathsf{submissionIndex}$ .
given $\mathsf{submissionIndex}$ and the index i of the proof within the submission (taken from the ProofReference, or implicitly 0 for the single-entry submission case), the existence of a verified proof is given by the boolean value:
- numVerifiedInSubmission[ $\mathsf{submissionIndex}$ ] > i

Censorship resistance

A censorship event is considered to have occurred for a submission with Id $\mathsf{submissionId}$ (with submission index $\mathsf{submissionIndex}$ , consisting of $n$ entries) if all of the following are satisfied:

a submission with Id $\mathsf{submissionId}$ has been made, and all proofs in the submission are valid for the corresponding public inputs and circuit Ids
some of the entries in $\mathsf{submissionId}$ remain unverified, namely
- numVerifiedInSubmission[ $\mathsf{submissionIndex}$ ] < $n$
one or more proofs from submission with index greater than $\mathsf{submissionIndex}$ (the submission index of the submission with id $\mathsf{submissionId}$ ) have been included in an aggregated batch
- namely, there exists $j > \mathsf{submissionIndex}$ s.t. numVerifiedInSubmission[ $j$ ] > 0

Note that, if one or more entries in a submission are invalid, aggregators are not obliged to verify any proofs from that submission.

Censorship by an aggregator can be proven by a claimant, by calling the method:

function challenge(
    uint256 circuitId,
    Proof calldata proof,
    uint256[] calldata publicInputs,
    bytes32 submissionId,
    uint64 laterSubmissionIdx,
    bytes32[] proofIdMerkleProof,
    bytes32[] proofDigestMerkleProof,
) external;

providing:

the valid tuple $(\mathsf{circuitId}, \pi, \mathsf{PI})$ , or circuitId, proof and publicINputs, the claimed next unverified entry in the submission
$\mathsf{submissionId}$ or submissionId
$j$ or laterSubmissionIdx
A Merkle proof that $\mathsf{proofId}_i$ (computed from $\mathsf{circuitId}_i$ and $\mathsf{PI}$ belongs to the submission (at the "next index" - see below)
A Merkle proof that $\pi_i$ belongs to the submission's proofDigest entry (at the "next index" - see below)

On receipt of a transaction calling this method, the contract:

checks that the conditions above hold and that the provided proof has indeed been skipped
looks up the verification key $\mathsf{VK}$ using $\mathsf{circuitId}$ and performs the full proof verification for $(\mathsf{VK}, \pi, \mathsf{PI})$ . The transaction is rejected if the proof is not valid.
increments the stored count numVerifiedInSubmission[ $\mathsf{submissionIndex}$ ]

The aggregator is punished only when all proofs in the submission have been shown to be valid. As such, after the above, the contract:

checks the condition numVerifiedInSubmission[ $\mathsf{submissionIndex}$ ] == n (where n is the number of proofs in the original submission $\mathsf{submissionId}$ ).
if this final condition holds then validity of all proofs in the submission has been shown and the aggregator is punished.

Note: 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 $\mathsf{proofId}$ is not dependent on the proof data.

Circuit Statements

Batches of $n$ application proofs are verified in a batch verify circuit.

A keccak circuit computes all $\mathsf{proofId}$ s of application proofs appearing in the batch verify proof, along with a final digest (the keccak hash of these $\mathsf{proofId}$ 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 $\mathsf{proofId}$ 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 $\mathsf{proofId}$ 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, \mathsf{circuitId}_i, \overline{\mathsf{PI}}_i)_{i=1}^n$ where
  - $\mathsf{PI}_i = (x_{i,j})_{j=1}^{\ell_i}$ is the public inputs to the $i$ -th proof
  - $\overline{\mathsf{PI}}_i = \mathsf{PI}_i | \{0\}_{j=\ell_i + 1}^{L}$ is $\mathsf{PI}_i$ after zero-padded to extend it to length $L$
Witness values:
- $\overline{\mathsf{VK}}_i$ - application verification keys, each padded to length $L$
- $(\pi_i)_{i=1}^n$ - application proofs
Statement:
- $\mathsf{circuitId}_i = \mathsf{poseidon}(\mathsf{truncate}(\ell_i, \overline{\mathsf{VK}}_i))$
- $\overline{\mathsf{PI}}_i = \mathsf{truncate}(\ell_i, \overline{\mathsf{PI}}_i) | \{0\}_{j=\ell_i + 1}^{L}$
- Groth16.Verify $(\overline{\mathsf{VK}}_i, \pi_i, \overline{\mathsf{PI}}_i) = 1$ for $i=1,\ldots,n$
- where
  - $\mathsf{truncate}(\ell, \overline{\mathsf{VK}})$ is the truncation of the size $L$ verification key $\overline{\mathsf{VK}}$ to a verification key of size $\ell$ , and
  - $\mathsf{truncate}(\ell, \overline{\mathsf{PI}})$ is the truncation of the public inputs to an array of size $\ell$

Keccak Circuit: ProofIds and Final Digest

Computes the $\mathsf{proofId}$ for each entry in each application proof in one or more verify circuit proofs.

Public inputs:
- $c^*, (\ell_i, \mathsf{circuitId}_i, \overline{\mathsf{PI}}_i)_{i=1}^{n \times N}$ where
  - $\mathsf{PI}_i = (x_{i,j})_{j=1}^{\ell_i}$ is the public inputs to the $i$ -th proof
  - $\overline{\mathsf{PI}}_i = \mathsf{PI}_i | \{0\}_{j=\ell_i + 1}^{L}$ is $\mathsf{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 = \mathsf{keccak}(\mathsf{circuitId}_i || \mathsf{truncate}(\ell_i, \overline{\mathsf{PI}}_i))$
- $c^* = \mathsf{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 ${\pi_{\text{bv}}}^{(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}, \mathsf{circuitId}_{i,j}, \overline{\mathsf{PI}}_{i,j}, \mathsf{proofId}_{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.
- for $j=1, \ldots, N$ BV proofs
- $\pi_{\mathsf{keccak}}$ the Keccak proof for the public inputs
  - $c^*$ , and
  - $(\ell_{1,1}, \mathsf{circuitId}_{1,1}, \overline{\mathsf{PI}}_{1,1}), (\ell_{2,1}, \mathsf{circuitId}_{2,1}, \overline{\mathsf{PI}}_{2,1}), \ldots , (\ell_{n,1}, \mathsf{circuitId}_{n,1}, \overline{\mathsf{PI}}_{n,1}),$ $(\ell_{1,2}, \mathsf{circuitId}_{1,2}, \overline{\mathsf{PI}}_{1,2}), (\ell_{2,2}, \mathsf{circuitId}_{2,2}, \overline{\mathsf{PI}}_{2,2}), \ldots , (\ell_{n,2}, \mathsf{circuitId}_{n,2}, \overline{\mathsf{PI}}_{n,2}),$ $\cdots$ $(\ell_{1,N}, \mathsf{circuitId}_{1,N}, \overline{\mathsf{PI}}_{1,N}), (\ell_{2,N}, \mathsf{circuitId}_{2,N}, \overline{\mathsf{PI}}_{2,N}), \ldots , (\ell_{n,N}, \mathsf{circuitId}_{n,N}, \overline{\mathsf{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 $\mathsf{PI}_{i,j}$ : $\textsf{SNARK}_{\text{BV}}.\textsf{Verify} \left( \pi_{\text{bv}}^{(j)}, (\ell_{i,j}, \mathsf{circuitId}_{i,j}, \overline{\mathsf{PI}}_{i,j})_{i=1}^n, \mathsf{VK}_{\text{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: $\textsf{SNARK}_{\mathsf{keccak}}.\textsf{Verify} \left(\pi_\mathsf{keccak}, c^*,(\ell_{i,j}, \mathsf{circuitId}_{i,j}, \overline{\mathsf{PI}}_{i,j})_{\substack{i=1,\ldots, n \\ j=1,\ldots, N}}, \mathsf{VK}_\mathsf{keccak} \right)=1$
Actual Statement:
- "Succinct" Plonk verification ( $\textsf{SuccinctVerify}$ ) namely "GWC Steps 1-11" using Shplonk, without final pairing, for random challenge scalar $r$ :
$\begin{gathered} (L_j, R_j) = \textsf{SuccinctVerify} \left( \pi_{\text{bv}}^{(j)}, (\ell_{i,j}, \mathsf{circuitId}_{i,j}, \overline{\mathsf{PI}}_{i,j})_{i=1}^n, \mathsf{VK}_{\text{BV}} \right) ~\text{ for } j=1,\ldots N \\ (L_{N+1}, R_{N+1}) = \textsf{SuccinctVerify} \left( \pi_\mathsf{keccak}, c^*,(\ell_{i,j}, \mathsf{circuitId}_{i,j}, \overline{\mathsf{PI}}_{i,j})_{\substack{i=1,\ldots, n \\ j=1,\ldots, N}}, \mathsf{VK}_\mathsf{keccak} \right) \\ (L, R) = \sum_{j=1}^{N+1} r^j (L_j, R_j) \end{gathered}$
Verification: The EVM verifier does the following, given $(\pi_{\text{outer}}, L, R, c^*)$ .
- $(L_\text{outer}, R_\text{outer}) := \textsf{SuccinctVerify}(\mathsf{PI}_\text{outer}, L, R, c^*, \mathsf{VK}_\text{outer})$
- $e(L + r' L_\text{outer}, [\tau]_2) \stackrel{?}{=} e(R + r' R_\text{outer}, [1]_2)$ for random challenge scalar $r'$

Note that:

The same witness values $\overline{\mathsf{PI}}_{i,j}$ are used to verify $\pi_{\text{bv}}^{(j)}$ and $\pi_{\mathsf{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_\text{outer}, [\tau]_2) \stackrel{?}{=} e(R + r' R_\text{outer}, [1]_2)$ , for random scalar $r'$ , therefore implies their validity.

PreviousDeployments

Last updated 4 months ago