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 (the keccak hash of the VK).
Application Clients submit proofs and public inputs (PIs) to the UpaVerifier
contract as tuples(π,PI,circuitId), where π is expected to be a (compressed) proof of knowledge that PI is an instance of the circuit with circuit id circuitId.
A single call to the contract submits an ordered list (πi,PIi,circuitIdi)i=0n−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 circuitIdis to match. A single Submission may contain proofs for multiple application circuits.
proofId - a unique proof id (equal to the Keccak hash of the circuit ID and PIs)
a Submission Id submissionId, computed as the Merkle root of the list of proofIdis, padded to the nearest power of 2 with bytes32(0)
.
a submission index submissionIndex, a simple incrementing counter of submissions, used later for censorship resistance.
for submissions that consist of a single proof, submissionId=keccak(proofId0), whereas
for submissions of multiple proofs, each proof is referred to by 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 is indeed at the given index within the submission 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, n and some further metadata), indexed by the submissionId.
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, the contract does not mark the proof as verified until the entire submission has been verified.
The application contract calls isProofVerified
on the UpaVerifier
contract, passing in the public inputs PI, the circuit Id circuitId, and a ProofReference
(when required).
The UpaVerifier
contract computes proofId=keccak(circuitId,PI) from the public inputs and then checks that ProofReference
contains a valid Merkle proof that proofId belongs to a verified submission.
The UpaVerifier
returns true
if it has a record of a valid proof for (circuitId,proofId), and false
otherwise.
Application contract computes an array of public inputs [PIi] where the i-th entry corresponds to the i-th proof of a submission with submissionId.
Application contract submits an array of tuples [(circuitIdi,PIi)] to the UPA contract.
The UPA contract computes the (unique) submissionId corresponding to the submitted array of circuit ids and public inputs.
The UPA contract returns 1 if it has verified the submission submissionId (i.e. it has verified all of the proofs within submissionId), and 0 otherwise.
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.
The circuit's circuitId is computed as
circuitId=keccak(DTcircuitId∣∣VK) where DTcircuitId 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 is stored on the contract (for censorship resistance) in a mapping indexed by circuitId, and the aggregator is notified via an event. This circuitId will be used to reference the circuit for future operations.
The application client creates the parameters for its smart contract as normal, including one or more proofs πi and public inputs PIi. It then passes these, along with the relevant (pre-registered) circuit Ids circuitIdi, to the submit
method on the IUpaProofReceiver
interface, paying the aggregation fee in ether:
computes proofIdi=keccak(circuitIdi,PIi) for i=0,…,n−1.
computes a proofDigest
proofDigest for each proof, as keccak(πi)
computes the submission Id submissionId as the Merkle root of the list (keccak(proofIdi))i=0n−1 (padded as required to the nearest power of 2)
computes the digestRoot
as the Merkle root of the list (proofDigesti)i=0n−1 (again padded as required to the nearest power of 2)
rejects the tx if an entry for submissionId already exists
assigns a submissionIndex to the submission (using a single incrementing counter)
assigns a proofIndexi to each (πi,PIi) (using a single incrementing counter)
emits an event for each proof, including (circuitIdi,πi,PIi,proofIndexi)
updates the contract state to record the fact that a submission with id submissionId has been made, mapping it to digestRoot
, submissionIndex, n and the block number at submission time.
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.
for each proofId in proofIds
:
skips proofId if it corresponds to a dummy proof,
checks that proofId has been submitted to the contract, and that proofs appear in the aggregated batch in the order of submission (see below)
marks proofId as valid (see below)
if proofId is the last proof in a submission submissionId, emit an event indicating that the submission submissionId has been verified
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 submissionId==i
For each proofId in proofIds
:
If 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). If such a submission exists:
The proof was submitted as a single-proof submission. The contract extracts the submissionIndex from the submission data and then checks that submissionIndex is greater than or equal tonextSubmissionIdxToVerify
. If not reject the transaction.
The entry numVerifiedInSubmission[
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 submissionId=keccak(proofId))
the proof is expected to be part of a multi-proof submission with submissionIndex≥ 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 ]
should contain the number of entries already verified.
the submissionId for the submission to be verified
Determine the number m
of entries in proofIds
, including the current proofId, that belong to this submission, as follows:
Let numProofIdsRemaining
be the number of entries (including proofId) still unchecked in proofIds
.
Look up the submission data for submissionId, in particular submissionIndex and n.
Let numUnverifiedFromSubmission =
n - numVerifiedInSubmission[
submissionIndex ]
.
The number m
of entries from proofIds
to consider as part of submissionId is given by Min(numUnverifiedFromSubmission, numProofIdsRemaining)
.
Use the submission Id 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)) indeed belong to the submission submissionId. Reject the transaction if this check fails.
Increment the entry numVerifiedInSubmission[
submissionIndex ]
by m
, indicating that m
additional proofs from the submission have been verified.
receives proofId or computes proofId from the public inputs
(using the ProofReference
if necessary) confirms that proofId belongs to a submission submissionId.
Checks if there was an on-chain submission for submissionId, and if so reads the stored submission index submissionIdx and the total number of proofs numProofs
contained in the submission submissionId. If it finds that numVerifiedInSubmission[
submissionIdx] == numProofs
then the submission submissionId was verified, and therefore so was the proof proofId.
receives submissionId or computes submissionId from the public inputs
Looks up the number of proofs numProofsInSubmission
in submissionId and then checks if numVerifiedInSubmission[
submissionIdx] = numProofsInSubmission
.
A censorship event is considered to have occurred for a submission with Id submissionId (with submission index submissionIndex, consisting of n entries) if all of the following are satisfied:
a submission with Id 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 remain unverified, namely
numVerifiedInSubmission[
submissionIndex] <
n
one or more proofs from a submission with index greater than submissionIndex (the submission index of the submission with id submissionId) have been included in an aggregated batch
namely, there exists j>submissionIndex s.t. numVerifiedInSubmission[
j] > 0
the valid tuple (circuitId,π,PI), or circuitId
, proof
and publicInputs
, the claimed next unverified entry in the submission
submissionId or submissionId
j or laterSubmissionIdx
A Merkle proof that proofIdi (computed from circuitIdi and PI belongs to the submission (at the "next index" - see below)
A Merkle proof that πi belongs to the submission's proofDigest
entry (at the "next index" - see below)
looks up the verification key VK using circuitId and performs the full proof verification for (VK,π,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]
checks the condition numVerifiedInSubmission[
submissionIndex] == n
(where n
is the number of proofs in the original submission submissionId).
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 is not dependent on the proof data.
Batches of n application proofs are verified in a batch verify circuit.
A keccak circuit computes all circuitIds and proofIds of application proofs appearing in the batch verify proof, along with a final digest (the keccak hash of these proofIds, 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 circuitIds, proofIds and final digest is verified in an outer circuit.
On-chain verification of an outer circuit proof thereby attests to the validity of n×N application proofs with given proofIds.
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.
(ℓi,VKi,PIi)i=1n where
PIi=(xi,j)j=1ℓi is the public inputs to the i-th proof
PIi=PIi∣{0}j=ℓi+1L is PIi after zero-padded to extend it to length L
VKi - application verification keys, each padded to length L
(πi)i=1n - application proofs
PIi=truncate(ℓi,PIi)∣{0}j=ℓi+1L
Groth16.Verify(VKi,πi,PIi)=1 for i=1,…,n
truncate(ℓ,VK) is the truncation of the size L verification key VK to a verification key of size ℓ, and
truncate(ℓ,PI) is the truncation of the public inputs to an array of size ℓ
Computes the proofId for each entry in each application proof in one or more verify circuit proofs.
c∗,(ℓi,VKi,circuitIdi,PIi)i=1n×N where
PIi=(xi,j)j=1ℓi is the public inputs to the i-th proof
PIi=PIi∣{0}j=ℓi+1L is PIi after zero-padded to extend it to length L
VKi - application verification keys, each padded to length L
c∗=(c1∗,c2∗) (digest, which consists of 32 bytes and is represented by two field elements)
ci=keccak(circuitIdi∣∣truncate(ℓi,PIi))
c∗=keccak(c1∣∣c2∣∣…∣∣cn×N)
circuitIdi=keccak(truncate(ℓi,VKi))
This step aggregates N batch verify proofs πbv(j),j=1,…N as well as a single corresponding Keccak proof πkeccak.
c∗ - final 32-byte public input digest, encoded as (c1,c2)∈Fr2
(L,R)∈G12 - overall KZG accumulator, encoded as 12 = 4 * \texttt{num_limbs} points of Fr
(ℓi,j,VKi,j,PIi,j) for i=1,…,n,j=1,…,N: the number of public inputs, the padded verifying key, and padded public inputs for the i-th application proof in the j-th BV proof.
for j=1,…,N BV proofs
πkeccak the Keccak proof for the public inputs
{(ℓi,j,VKi,j,PIi,j}i=1,…,nj=1,…,N(ℓ1,N,circuitId1,N,PI1,N),(ℓ2,N,circuitId2,N,PI2,N),…,(ℓn,N,circuitIdn,N,PIn,N),
All BV proofs are valid, and therefore there exist valid application proofs for each PIi,j: SNARKBV.Verify(πbv(j),(ℓi,j,VKi,j,PIi,j)i=1n,VKBV) for j=1,…,N
Keccak proof is valid, and therefore c∗ 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
"Succinct" Plonk verification (SuccinctVerify) namely "GWC Steps 1-11" using Shplonk, without final pairing, for random challenge scalar r:
(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=1∑N+1rj(Lj,Rj)
Verification: The EVM verifier does the following, given (πouter,L,R,c∗).
(Louter,Router):=SuccinctVerify(PIouter,L,R,c∗,VKouter)
e(L+r′Louter,[τ]2)=?e(R+r′Router,[1]2) for random challenge scalar r′
The same witness values PIi,j are used to verify πbv(j) and π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′Louter,[τ]2)=?e(R+r′Router,[1]2), for random scalar r′, therefore implies their validity.
[Batch verifier circuit] The Pedersen proof is verified: e(comm,h1)e(pok,h2)=1, where
h1,h2∈G2 is the Pedersen verification key (which is part of the corresponding app VK).
comm is the Pedersen commitment point and 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). Note that this last public input is not used in the computation of the proof Id.f(x)=x∗e2piiξx