UPA protocol specification

Version 1.2.0

Overview

Each tuple in a submission is assigned:

Each submission is assigned:

Note that:

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 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.

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

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

Protocol

Circuit registration

Application proof submission

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

The UpaProofReceiver.submit method:

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

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

State: the contract holds

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

      • Update nextSubmissionIdxToVerify in contract state

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

        • a Merkle "interval" proof for a contiguous set of entries from that submission.

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

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:

Censorship resistance

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:

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

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

  • if this final condition holds then validity of all proofs in the submission has been shown and the aggregator is punished.

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

Batch Verify Circuit: Groth16 batch verifier

The batch verify circuit corresponds to the following relation:

  • Public inputs:

  • Witness values:

  • Statement:

    • where

Keccak Circuit: ProofIds and Final Digest

  • Public inputs:

  • Witness values: (none)

  • Statement:

Outer Circuit: Recursive verification of Batch Verifier and Keccak circuits

  • Public Inputs:

  • Witness values:

  • "Equivalent Statement": (actual statement is shown as multiple sub-statements, given below)

  • Actual Statement:

Note that:

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

Last updated