UPA protocol specification

Version 1.2.0

Overview

Application developers register Groth16 verification keys (VKs) for their circuits with the UpaVerifier contract (through the IUpaProofReceiver interface). Upon registration, each VK is assigned a circuitId\mathsf{circuitId} (the keccak hash of the VK).

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

A single call to the contract submits an ordered list (πi,PIi,circuitIdi)i=0n1(\pi_i, \mathsf{PI}_i, \mathsf{circuitId}_i)_{i=0}^{n-1} (of any size nn up to some implementation-defined maximum NN) 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 circuitIdi\mathsf{circuitId}_is to match. A single Submission may contain proofs for multiple application circuits.

Each tuple in a submission is assigned:

  • proofId\mathsf{proofId} - a unique proof id (equal to the Keccak hash of the circuit ID and PIs)

Each submission is assigned:

  • a Submission Id submissionId\mathsf{submissionId}, computed as the Merkle root of the list of proofIdi\mathsf{proofId}_is, padded to the nearest power of 2 with bytes32(0).

  • a submission index submissionIndex\mathsf{submissionIndex}, a simple incrementing counter of submissions, used later for censorship resistance.

Note that:

  • for submissions that consist of a single proof, submissionId=keccak(proofId0)\mathsf{submissionId} = \mathsf{keccak}(\mathsf{proofId_0}), whereas

  • for submissions of multiple proofs, each proof is referred to by submissionId\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 proofIdi\mathsf{proofId}_i is indeed at the given index within the submission submissionId\mathsf{submissionId}.

The proof and public inputs are not stored on-chain. The aggregator monitors for transactions submitting proofs to the contract and pulls this information from the transaction calldata. The contract stores information about the submission (including submissionIndex\mathsf{submissionIndex}, nn and some further metadata), indexed by the submissionId\mathsf{submissionId}.

There is a single Aggregator that puts together batches of proofs with increasing submission index values. The proofs in a batch must be ordered exactly as they appear within submissions. Aggregated batches do not need to align with submissions- a batch may contain multiple submissions, and a submission may span multiple batches. If a submission contains any invalid proofs, the entire submission is considered invalid. The aggregator may skip only invalid submissions. If the Aggregator skips a valid submission, it will be punished (see Censorship Resistance).

Once a submission is verified by the UPA contract, its submission id is marked as verified. Applications can confirm that an individual proof id is verified by providing a ProofReference, which is a Merkle proof that the proof id was included in a verified submission. Note that for proofs in a multi-proof submission with submissionId\mathsf{submissionId}, the contract does not mark the proof as verified until the entire submission has been verified.

Once the UPA contract marks a proof (or the submission containing a proof) as verified, an application client can submit a transaction to the application contract (optionally with some ProofReference metadata), 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 isProofVerified on the UpaVerifier contract, passing in the public inputs PI\mathsf{PI}, the circuit Id circuitId\mathsf{circuitId}, and a ProofReference (when required).

  • The UpaVerifier contract computes proofId=keccak(circuitId,PI)\mathsf{proofId} = \mathsf{keccak}(\mathsf{circuitId}, \mathsf{PI}) from the public inputs and then checks that ProofReference contains a valid Merkle proof that proofId\mathsf{proofId} belongs to a verified submission.

  • The UpaVerifier returns true if it has a record of a valid proof for (circuitId,proofId)(\mathsf{circuitId}, \mathsf{proofId}), and false otherwise.

Application contracts can also verify the existence of multiple ZKPs belonging to the same submission. In this case:

  • Application contract computes an array of public inputs [PIi][\mathsf{PI}_i] where the ii-th entry corresponds to the ii-th proof of a submission with submissionId\mathsf{submissionId}.

  • Application contract submits an array of tuples [(circuitIdi,PIi)][(\mathsf{circuitId}_i, \mathsf{PI}_i)] to the UPA contract.

  • The UPA contract computes the (unique) submissionId\mathsf{submissionId} corresponding to the submitted array of circuit ids and public inputs.

  • The UPA contract returns 1 if it has verified the submission submissionId\mathsf{submissionId} (i.e. it has verified all of the proofs within submissionId\mathsf{submissionId}), and 0 otherwise.

Note that in this case, there is no need to submit a ProofReference.

Protocol

Circuit registration

Before submitting proofs on-chain, the application developer submits a transaction calling the registerVK method to the UPA contract (through the IUpaProofReceiver interface), passing their verification key VK\mathsf{VK}.

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

circuitId=keccak(DTcircuitIdVK)\mathsf{circuitId} = \mathsf{keccak}(\mathsf{DT}_\mathsf{circuitId} || \mathsf{VK})

where DTcircuitId\mathsf{DT}_\mathsf{circuitId} denotes a domain tag derived from a string describing the context, such as UPA Groth16 circuit id (See the Universal Batch Verifier specification for details.)

VK\mathsf{VK} is stored on the contract (for censorship resistance) in a mapping indexed by circuitId\mathsf{circuitId}, and the aggregator is notified via an event. This circuitId\mathsf{circuitId} will be used to reference the circuit for future operations.

Application proof submission

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

interface IUpaProofReceiver
{
    ...
    function submit(
        uint256[] calldata circuitIds,
        Proof[] calldata proofs,
        uint256[][] calldata publicInputs
    ) external payable override returns (bytes32 submissionId)
    ...
}

The UpaProofReceiver.submit method:

  • computes proofIdi=keccak(circuitIdi,PIi)\mathsf{proofId}_i = \mathsf{keccak}(\mathsf{circuitId}_i, \mathsf{PI}_i) for i=0,,n1i = 0, \ldots, n-1.

  • computes a proofDigest proofDigest\mathsf{proofDigest} for each proof, as keccak(πi)\mathsf{keccak}(\pi_i)

  • computes the submission Id submissionId\mathsf{submissionId} as the Merkle root of the list (keccak(proofIdi))i=0n1(\mathsf{\mathsf{keccak}(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 (proofDigesti)i=0n1(\mathsf{proofDigest}_i)_{i=0}^{n-1} (again padded as required to the nearest power of 2)

  • rejects the tx if an entry for submissionId\mathsf{submissionId} already exists

  • assigns a submissionIndex\mathsf{submissionIndex} to the submission (using a single incrementing counter)

  • assigns a proofIndexi\mathsf{proofIndex}_i to each (πi,PIi)(\pi_i, \mathsf{PI}_i) (using a single incrementing counter)

  • emits an event for each proof, including (circuitIdi,πi,PIi,proofIndexi)(\mathsf{circuitId}_i, \pi_i, \mathsf{PI}_i, \mathsf{proofIndex}_i)

  • updates the contract state to record the fact that a submission with id submissionId\mathsf{submissionId} has been made, mapping it to digestRoot, submissionIndex\mathsf{submissionIndex}, nn and the block number at submission time.

NOTE: Proof data itself does not appear in the input data used to compute proofId\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 element that is hard to compute without the corresponding private witness (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

There is a single (permissioned) Aggregator that submits aggregated proofs to the Upa.verifyAggregatedProof method. Each aggregated proof attests to the validity of a batch of application proofs. In return, the aggregator can claim submission fees (for on-chain submissions). An aggregated batch may contain proofs from both on-chain and off-chain submissions, as well as dummy proofs which are used to fill partial batches.

function verifyAggregatedProof(
        bytes calldata proof,
        bytes32[] calldata proofIds,
        uint16 numOnchainProofs,
        SubmissionProof[] calldata submissionProofs,
        uint256 offChainSubmissionMarkers
) external onlyWorker

proof - An aggregated proof for the validity of this batch.

proofIds - The list of proofIds that are verified by the aggregated proof proof. These are assumed to be arranged in the order: [On-chain, Dummy, Off-chain]. Furthermore, it is assumed that if there are dummy proofIds in this batch, these appear after the last proof in a submission. I.e. where dummy proof ids are used, the on-chain proof ids do not end with a partial submission.

numOnChainProofs - The number of proofIds that were from on-chain submissions. This count includes dummy proofs.

submissionProofs - An array of 0 or more Merkle proofs, each showing that some of the entries in proofIds belong to a specific multi-proof on-chain submission. These are required as we do not have a map from proofId to submissionId or submissionIdx. See the algorithm below for details.

offChainSubmissionMarkers - Represents a bool[] marking each off-chain member of proofIds with a 0 or 1. A proofId is marked with a 1 precisely when the proofId is the last one in an off-chain submission. This bool[] is packed into a uint256 to compress calldata.

The UpaVerifier contract:

  • checks that proof is valid for proofIds

  • for each proofId\mathsf{proofId} in proofIds:

    • skips proofId\mathsf{proofId} if it corresponds to a dummy proof,

    • checks that proofId\mathsf{proofId} has been submitted to the contract, and that proofs appear in the aggregated batch in the order of submission (see below)

    • marks proofId\mathsf{proofId} as valid (see below)

    • if proofId\mathsf{proofId} is the last proof in a submission submissionId\mathsf{submissionId}, emit an event indicating that the submission submissionId\mathsf{submissionId} 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 ii-th entry corresponds to the number of proofs that have been verified (in order) of the submission with submissionId==i\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 proofId\mathsf{proofId} in proofIds:

    • If proofId\mathsf{proofId} corresponds to a dummy proof, then the rest of the proofs in the batch are assumed to be dummy proofs. No more proofs from this batch will be marked as valid.

    • Attempt to lookup the submission data (see Proof Submission) for a submission with Id keccak(proofId)\mathsf{keccak}(\mathsf{proofId}). If such a submission exists:

      • The proof was submitted as a single-proof submission. The contract extracts the submissionIndex\mathsf{submissionIndex} from the submission data and then checks that submissionIndex\mathsf{submissionIndex} is greater than or equal tonextSubmissionIdxToVerify. If not reject the transaction.

      • The entry numVerifiedInSubmission[ submissionIndex\mathsf{submissionIndex} ] should logically be 0 (this can be sanity checked by the contract). Set this entry to 1

      • Update nextSubmissionIdxToVerify in contract state

    • Otherwise (if no submission data was found for submissionId=keccak(proofId)\mathsf{submissionId} = \mathsf{keccak}(\mathsf{proofId}))

      • the proof is expected to be part of a multi-proof submission with submissionIndex\mathsf{submissionIndex} \geq nextSubmissionIdxToVerify.

        • Note that if a previous aggregated proof verified some subset, but not all, of the entries in the submission, nextSubmissionIdxToVerify would still refer to the partially verified submission at this stage. In this case, numVerifiedInSubmission[ submissionIndex\mathsf{submissionIndex} ] should contain the number of entries already verified.

      • Take the next entry in submissionProofs. This includes the following information:

        • the submissionId\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 proofId\mathsf{proofId}, that belong to this submission, as follows:

    • Let numProofIdsRemaining be the number of entries (including proofId\mathsf{proofId}) still unchecked in proofIds.

    • Look up the submission data for submissionId\mathsf{submissionId}, in particular submissionIndex\mathsf{submissionIndex} and nn.

    • Let numUnverifiedFromSubmission = nn - numVerifiedInSubmission[ submissionIndex\mathsf{submissionIndex} ].

    • The number m of entries from proofIds to consider as part of submissionId\mathsf{submissionId} is given by Min(numUnverifiedFromSubmission, numProofIdsRemaining).

  • Use the submission Id submissionId\mathsf{submissionId} and the Merkle "interval" proof from the submission proof, to check that the hashes of the m next entries from proofIds (including keccak(proofId)\mathsf{keccak}(\mathsf{proofId})) indeed belong to the submission submissionId\mathsf{submissionId}. Reject the transaction if this check fails.

  • Increment the entry numVerifiedInSubmission[ submissionIndex\mathsf{submissionIndex} ] by m, indicating that m additional proofs from the submission have been verified.

  • update nextSubmissionIdxToVerify in the contract state

NOTE: The arguments offChainSubmissionMarkers and numOnchainProofs are there for future off-chain submission support. For now, aggregators call this function with numOnchainProofs = BATCH_SIZE, which will skip the off-chain logic of this function.

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 isProofVerified on the UpaVerifier contract (using the ProofReference if given) to confirm the existence of a corresponding verified proof.

For proofs from single-entry submissions, the UPA provides the entry points:

function isProofVerified(
        uint256 circuitId,
        uint256[] calldata publicInputs)
    external
    view
    returns (bool);

function isProofVerified(bytes32 proofId) external view returns (bool);

For proofs from multi-entry submissions, the UPA provides entry points:

function isProofVerified(
        uint256 circuitId,
        uint256[] calldata publicInputs,
        ProofReference calldata proofRef)
    external
    view
    returns (bool);

function isProofVerified(
        bytes32 proofId,
        ProofReference calldata proofReference
    ) external view returns (bool);

The UPA contract:

  • receives proofId\mathsf{proofId} or computes proofId\mathsf{proofId} from the public inputs

  • (using the ProofReference if necessary) confirms that proofId\mathsf{proofId} belongs to a submission submissionId\mathsf{submissionId}.

  • Checks if there was an on-chain submission for submissionId\mathsf{submissionId}, and if so reads the stored submission index submissionIdx\mathsf{submissionIdx} and the total number of proofs numProofs contained in the submission submissionId\mathsf{submissionId}. If it finds that numVerifiedInSubmission[submissionIdx\mathsf{submissionIdx}] == numProofs then the submission submissionId\mathsf{submissionId} was verified, and therefore so was the proof proofId\mathsf{proofId}.

The application contract can also look up the verification status of entire submissions by computing the corresponding (nested) array of public inputs. The contract can then either use a submissionId computed from this array, or the array itself, to query the submission's status in the UPA contract.

The UPA provides the entry points:

// If all proofs have the same circuitId.
function isSubmissionVerified(
    uint256 circuitId,
    uint256[][] memory publicInputsArray
) external view returns (bool);

function isSubmissionVerified(
    uint256[] calldata circuitIds,
    uint256[][] memory publicInputsArray
) external view returns (bool);

function isSubmissionVerified(
    bytes32 submissionId
) external view returns (bool);

The UPA contract:

  • receives submissionId\mathsf{submissionId} or computes submissionId\mathsf{submissionId} from the public inputs

  • Looks up the number of proofs numProofsInSubmission in submissionId\mathsf{submissionId} and then checks if numVerifiedInSubmission[submissionIdx\mathsf{submissionIdx}] = numProofsInSubmission.

Censorship resistance

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

  • a submission with Id submissionId\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 submissionId\mathsf{submissionId} remain unverified, namely

    • numVerifiedInSubmission[submissionIndex\mathsf{submissionIndex}] < nn

  • one or more proofs from a submission with index greater than submissionIndex\mathsf{submissionIndex} (the submission index of the submission with id submissionId\mathsf{submissionId}) have been included in an aggregated batch

    • namely, there exists j>submissionIndexj > \mathsf{submissionIndex} s.t. numVerifiedInSubmission[jj] > 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 the Aggregator can be proven by a claimant, by calling the method:

function challenge(
        bytes32 circuitId,
        Groth16Proof calldata proof,
        uint256[] calldata publicInputs,
        bytes32 submissionId,
        bytes32[] calldata proofIdMerkleProof,
        bytes32[] calldata proofDataMerkleProof
) external returns (bool challengeSuccessful);

providing:

  • the valid tuple (circuitId,π,PI)(\mathsf{circuitId}, \pi, \mathsf{PI}), or circuitId, proof and publicInputs, the claimed next unverified entry in the submission

  • submissionId\mathsf{submissionId} or submissionId

  • jj or laterSubmissionIdx

  • A Merkle proof that proofIdi\mathsf{proofId}_i (computed from circuitIdi\mathsf{circuitId}_i and PI\mathsf{PI} belongs to the submission (at the "next index" - see below)

  • A Merkle proof that πi\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 VK\mathsf{VK} using circuitId\mathsf{circuitId} and performs the full proof verification for (VK,π,PI)(\mathsf{VK}, \pi, \mathsf{PI}). The transaction is rejected if the proof is not valid or if the verification key hasn't been registered.

  • increments the stored count numVerifiedInSubmission[submissionIndex\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[submissionIndex\mathsf{submissionIndex}] == n (where n is the number of proofs in the original submission submissionId\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 proofId\mathsf{proofId} is not dependent on the proof data.

Collecting Aggregation Fees

The application contract pays an aggregation fee at submission time. These fees are held in the UPA contract. In order for the aggregator to claim the fees for a given submission, the UPA contract must have verified that submission.

The aggregator collects fees in two steps. First it calls

function allocateAggregatorFee(uint64 lastSubmittedSubmissionIdx)

which stores the current value of lastSubmittedSubmissionIdx and allocates all fees collected up to now to be claimable by the aggregator once it has verified the submission at lastSubmittedSubmissionIdx (which implies that all previous submissions have also been verified). Once the aggregator has done this, it can call

function claimAggregatorFee(
    address aggregator,
    uint64 lastVerifiedSubmissionIdx
)

to withdraw the previously allocated fees.

Circuit Statements

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

A keccak circuit computes all circuitId\mathsf{circuitId}s and proofId\mathsf{proofId}s of application proofs appearing in the batch verify proof, along with a final digest (the keccak hash of these proofId\mathsf{proofId}s, used to reduce the public input size of the outer circuit below).

A collection of NN batch verify proofs along with the keccak proof for their circuitId\mathsf{circuitId}s, proofId\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×Nn \times N application proofs with given proofId\mathsf{proofId}s.

nn - inner batch size. Application proofs per batch verify circuit.

NN - outer batch size. Number of batch-verify circuits per outer proof.

LL - 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:

    • (i,VKi,PIi)i=1n(\ell_i, \overline{\mathsf{VK}}_i, \overline{\mathsf{PI}}_i)_{i=1}^n where

      • PIi=(xi,j)j=1i\mathsf{PI}_i = (x_{i,j})_{j=1}^{\ell_i} is the public inputs to the ii-th proof

      • PIi=PIi{0}j=i+1L\overline{\mathsf{PI}}_i = \mathsf{PI}_i | \{0\}_{j=\ell_i + 1}^{L} is PIi\mathsf{PI}_i after zero-padded to extend it to length LL

      • VKi\overline{\mathsf{VK}}_i - application verification keys, each padded to length LL

  • Witness values:

    • (πi)i=1n(\pi_i)_{i=1}^n - application proofs

  • Statement:

    • PIi=truncate(i,PIi){0}j=i+1L\mathsf{PI}_i = \mathsf{truncate}(\ell_i, \overline{\mathsf{PI}}_i) | \{0\}_{j=\ell_i + 1}^{L}

    • Groth16.Verify(VKi,πi,PIi)=1\mathsf{Groth16.Verify}(\overline{\mathsf{VK}}_i, \pi_i, \overline{\mathsf{PI}}_i) = 1 for i=1,,ni=1,\ldots,n

    • where

      • truncate(,VK)\mathsf{truncate}(\ell, \overline{\mathsf{VK}}) is the truncation of the size LL verification key VK\overline{\mathsf{VK}} to a verification key of size \ell, and

      • truncate(,PI)\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 proofId\mathsf{proofId} for each entry in each application proof in one or more verify circuit proofs.

  • Public inputs:

    • c,(i,VKi,circuitIdi,PIi)i=1n×Nc^*, (\ell_i, \overline{\mathsf{VK}}_i, \mathsf{circuitId}_i, \overline{\mathsf{PI}}_i)_{i=1}^{n \times N} where

      • PIi=(xi,j)j=1i\mathsf{PI}_i = (x_{i,j})_{j=1}^{\ell_i} is the public inputs to the ii-th proof

      • PIi=PIi{0}j=i+1L\overline{\mathsf{PI}}_i = \mathsf{PI}_i | \{0\}_{j=\ell_i + 1}^{L} is PIi\mathsf{PI}_i after zero-padded to extend it to length LL

      • VKi\overline{\mathsf{VK}}_i - application verification keys, each padded to length LL

      • c=(c1,c2)c^* = (c^*_1, c^*_2) (digest, which consists of 32 bytes and is represented by two field elements)

  • Witness values: (none)

  • Statement:

    • ci=keccak(circuitIditruncate(i,PIi))c_i = \mathsf{keccak}(\mathsf{circuitId}_i || \mathsf{truncate}(\ell_i, \overline{\mathsf{PI}}_i))

    • c=keccak(c1c2cn×N)c^* = \mathsf{keccak}(c_1 || c_2 || \ldots || c_{n \times N})

    • circuitIdi=keccak(truncate(i,VKi))\mathsf{circuitId}_i = \mathsf{keccak}(\mathsf{truncate}(\ell_i, \overline{\mathsf{VK}}_i))

Outer Circuit: Recursive verification of Batch Verifier and Keccak circuits

This step aggregates NN batch verify proofs πbv(j),j=1,N{\pi_{\text{bv}}}^{(j)}, j = 1, \ldots N as well as a single corresponding Keccak proof πkeccak\pi_{keccak}.

  • Public Inputs:

    • cc^* - final 32-byte public input digest, encoded as (c1,c2)Fr2(c_1, c_2) \in \mathbb{F}_r^2

    • (L,R)G12(L, R) \in \mathbb{G}_1^2 - overall KZG accumulator, encoded as 12 = 4 * \texttt{num_limbs} points of Fr\mathbb{F}_r

  • Witness values:

    • (i,j,VKi,j,PIi,j) for i=1,,n,j=1,,N(\ell_{i,j}, \overline{\mathsf{VK}}_{i, j}, \overline{\mathsf{PI}}_{i,j}) \text{ for } i=1,\ldots, n, j=1, \ldots, N: the number of public inputs, the padded verifying key, and padded public inputs for the ii-th application proof in the jj-th BV proof.

    • for j=1,,Nj=1, \ldots, N BV proofs

    • πkeccak\pi_{\mathsf{keccak}} the Keccak proof for the public inputs

      • cc^*, and

      • {(i,j,VKi,j,PIi,j}i=1,,nj=1,,N\{ (\ell_{i, j}, \overline{\mathsf{VK}}_{i, j}, \overline{\mathsf{PI}}_{i, j} \}_{\substack{i=1,\ldots, n \\ j=1,\ldots, N}}(1,N,circuitId1,N,PI1,N),(2,N,circuitId2,N,PI2,N),,(n,N,circuitIdn,N,PIn,N),(\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 PIi,j\mathsf{PI}_{i,j}: SNARKBV.Verify(πbv(j),(i,j,VKi,j,PIi,j)i=1n,VKBV)\textsf{SNARK}_{\text{BV}}.\textsf{Verify} \left( \pi_{\text{bv}}^{(j)}, (\ell_{i,j}, \overline{\mathsf{VK}}_{i,j}, \overline{\mathsf{PI}}_{i,j})_{i=1}^n, \mathsf{VK}_{\text{BV}} \right) for j=1,,Nj=1,\ldots, N

    • Keccak proof is valid, and therefore cc^* is the final digest for all application PIs and vk hashes: SNARKkeccak.Verify(πkeccak,c,(i,j,VKi,j,PIi,j)i=1,,nj=1,,N,VKkeccak)=1\textsf{SNARK}_{\mathsf{keccak}}.\textsf{Verify} \left(\pi_\mathsf{keccak}, c^*,(\ell_{i,j}, \overline{\mathsf{VK}}_{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 (SuccinctVerify\textsf{SuccinctVerify}) namely "GWC Steps 1-11" using Shplonk, without final pairing, for random challenge scalar rr:

    (Lj,Rj)=SuccinctVerify(πbv(j),(i,j,VKi,j,PIi,j)i=1n,VKBV)  for j=1,N(LN+1,RN+1)=SuccinctVerify(πkeccak,c,(i,j,VKi,j,PIi,j)i=1,,nj=1,,N,VKkeccak)(L,R)=j=1N+1rj(Lj,Rj)\begin{gathered} (L_j, R_j) = \textsf{SuccinctVerify} \left( \pi_{\text{bv}}^{(j)}, (\ell_{i,j}, \overline{\mathsf{VK}}_{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}, \overline{\mathsf{VK}}_{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 (πouter,L,R,c)(\pi_{\text{outer}}, L, R, c^*).

    • (Louter,Router):=SuccinctVerify(PIouter,L,R,c,VKouter)(L_\text{outer}, R_\text{outer}) := \textsf{SuccinctVerify}(\mathsf{PI}_\text{outer}, L, R, c^*, \mathsf{VK}_\text{outer})

    • e(L+rLouter,[τ]2)=?e(R+rRouter,[1]2)e(L + r' L_\text{outer}, [\tau]_2) \stackrel{?}{=} e(R + r' R_\text{outer}, [1]_2) for random challenge scalar rr'

Note that:

  • The same witness values PIi,j\overline{\mathsf{PI}}_{i,j} are used to verify πbv(j)\pi_{\text{bv}}^{(j)} and πkeccak\pi_{\mathsf{keccak}}, implying that cc^* 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)(L,R). Checking that e(L+rLouter,[τ]2)=?e(R+rRouter,[1]2)e(L + r' L_\text{outer}, [\tau]_2) \stackrel{?}{=} e(R + r' R_\text{outer}, [1]_2), for random scalar rr', therefore implies their validity.

  • In the case there is a Pedersen commitment point for proofs coming from e.g. gnark, the statements of the batch verifier and keccak circuits are a bit different. For each application proof:

    • [Batch verifier circuit] The Pedersen proof is verified: e(comm,h1)e(pok,h2)=1e(\mathsf{comm}, h_1) e( \mathsf{pok}, h_2) = 1, where

      • h1,h2G2h_1, h_2 \in \mathbb{G}_2 is the Pedersen verification key (which is part of the corresponding app VK\mathsf{VK}).

      • comm\mathsf{comm} is the Pedersen commitment point and pok\mathsf{pok} the corresponding Pedersen proof of knowledge.

    • [Keccak circuit] The last public input is computed as the keccak hash of the commitment point: PI+1=keccak(comm)\overline{PI}_{\ell + 1} = \mathsf{keccak}(\mathsf{comm}). Note that this last public input is not used in the computation of the proof Id.f(x)=xe2piiξxf(x) = x * e^{2 pi i \xi x}

Last updated