Try   HackMD

Aztec Yellow Paper

Revised 12-03-2021
Ariel Gabizon | Zac Williamson | Tom Walton-Pocock

This document provides details on the protocol specification for Aztec 2.0, deployed to Ethereum mainnet, verifier address 0x737901bea3eeb88459df9ef1BE8fF3Ae1B42A2ba, on 15 March 2021.

The protocol is principally designed by Zac Williamson, and built on work by Zac and Ariel Gabizon, the creators of Aztec 2.0's cryptosystems PLONK and Plookup.

Background

Aztec 2.0 is a multi-asset private rollup service on Ethereum.

The protocol supports transactions in up to 3 ERC-20 assets, as well as ETH. The protocol will be modified to support all ERC20s in the future.

The protocol consists of:

  • Crypto Primitives: The elliptic curve and associated Ate pairing, and hash specifications
  • Notes and Commitments: Data structures for our private UTXO system, similar to Zcash
  • State: The two-tree state model, which registers unspent and spent notes in Aztec 2.0
  • Circuits:
    • I. Joinsplit Circuit: Logic governing the spend of Aztec notes
    • II. Account Circuit: Administration of keys in Aztec's username system
    • III. Rollup Circuit: Logic governing the rollup that aggregates ZK proofs
    • IV. Escape-Hatch Circuit: An "outer circuit" allowing users to withdraw funds without a rollup proof
    • V. Root Rollup Circuit: Aggregates multiple rollup proofs
  • Global Constants: Parameters and other data not included elsewhere in the protocol spec

The Protocol in a Nutshell

  • Clients make Joinsplit proofs to privately transfer value between accounts.
  • A client can also make an Account proof to change the set of keys that are authorized to spend notes from an account.
  • The rollup provider batches multiple Joinsplit proofs into a single Rollup proof that validates the transactions in the batch.
  • The rollup provider then batches multiple rollup proofs into a Root Rollup proof that validates at once all the transactions in all these rollups. This root rollup proof is what is put on chain.
  • If a client's transaction is being censored by the rollup provider; they can submit it separately to the blockchain via an Escape hatch proof.

Cryptography Primitives

1. Pairing Groups on BN-254

Aztec uses the Ethereum-native version of the BN254 elliptic curve for its principal group:

◈ First pairing source group

A BN curve of size

2254, with field size
2254
, and security of roughly 110 bits (practically, this can be closer to 128 bits as the stronger attacks require unproven assumptions related to number field sive algorithms and have never been fully specified or implemented).

  • Equation
    E:X2=Y3+3
  • Parameters
    • Field
      Fp
      for prime
      p=21888242871839275222246405745257275088696311157297823662689037894645226208583
      in decimal representation (size
      2254
      )
    • Group
      G1=E/Fp
      of prime order
      r=21888242871839275222246405745257275088548364400416034343698204186575808495617
      (size
      2254
      )
    • Generator
      P1=(1,2)G1

We have

2253<r<p<2254.
As usual, we use a subgroup of a twist of the above curve for efficient pairings:

◈ Second pairing source group

A subgroup of size

2254, of a curve over field size
2254×2
. This is a degree-2 field extension of
Fq
, via
Fq2=Fq[X]/(X2+1)
. Note that
(X2+1)
is the ideal generated by
f(X)=X2+1
, whose roots are
±i
.

  • Equation
    E:X2=Y3+3(i+9)
  • Parameters
    • Field
      Fp2
      for
      p
      as above.
    • Group
      G2
      = subgroup of
      E/Fp2
      of the same prime order
      r
      as
      G1
      .
    • Generator
      P2=(11559732032986387107991004021392285783925812861821192530917403151452391805634i+10857046999023057135944570762232829481370756359578518086990519993285655852781,4082367875863433681332203403145435568316851327593401208105741076214120093531i+8495653923123431417604973247489272438418190587263600148770280649306958101930)G2

◈ Pairing

We use the Ethereum-native Ate pairing, a bilinear map taking:

ϵ:G1×G2GT

Where

GT is a field extension of
Fq
of degree 12.

Further details may be found here.

2. Grumpkin - A curve on top of BN-254 for SNARK efficient group operations.

Grumpkin is in fact a curve cycle together with BN-254, meaning that the field and group order of Grumpkin are equal to the group and field order of (the first pairing group of) BN-254:

  • Equation
    E:Y2=X317
  • Parameters
    • Group
      G
      of order
      p=21888242871839275222246405745257275088696311157297823662689037894645226208583
    • Base field
      Fr
      for
      r=21888242871839275222246405745257275088548364400416034343698204186575808495617

3. Hashes

The Aztec 2.0 system relies on two types of hashes:

  • Pedersen Hashes (for collision resistance)
  • Blake2 Hashes (for pseudorandomness)

Aztec relies overwhelmingly on Pedersen Hashes; as most of the time collision resistance is sufficient.

Pedersen Hashes

Let

G be an additive group of prime order
p
.

In its classical setting a pedersen hash is defined as a map

H:F×FG as follows:

H(m1,m2)=m1.g+m2.h,

for generators

g,hG chosen independently by public randomness (e.g. hueristically as distinct outputs of a random oracle simulating hash function).

We wish to define a variant of Pedersen to enable hashing strings of any desired length. As our group

G we will use the Grumpkin curve group described above.

We generate a sequence of generators

h0,...hk as hash outputs these are network parameters, fixed for the life of the protocol. They are simply chosen to be the first Keccak-256 outputs that correspond to group elements. See the derive_generators method in the barretenberg code and the Global Constants section below for exact details.

Hashing field elements

Our basic component for hashing will be the hash_single method.
Given a field element

aFr and hash index
i
, we essentially hash 252 bits of
a
with
h2i
and the the remaining 2 bits of
a
with
h2i+1
. This is not precisely the case, as we use a wnaf representation - see page 4 here. See the comments above hash_single in the code for exact details. The point is that while enforcing the wnaf representation to represent an integer smaller than
r
, this is a collision resistant function from
Fr
under DL, even when outputting only the
x
-coordinate.

Now, given a vector

a1,,atFr we define the pedersen hash as
H(a1,,at)=i=1thash_single(ai,i).x

Hashing byte arrays:

Given a message

M of arbitrary size, we first divide it up into
31
-byte chunks
M=M0M2...Mk
; in other words:

M=i=0kMi.231i.

We now identify each

Mi with a field element
aiFr
in the natural way.
and now we define
H(M)H(a1,,at)

For details on how

hi have been generated, please see Global Constants.

Blake2s Hash

We use the Blake2s Hash more sparingly, because it is not SNARK-friendly, but it does exhibit psuedorandomness not offered by Pedersen. That is, it is considered a reasonable hueristic to use it in place of a random oracle used for a security proof.

We employ the standard implementation of the Blake2s hash, which is fully documented here.

The Blake2s hash is utilized for computing nullifiers and for generating pseudorandom challenges, when verifying Schnorr signatures and when recursively verifying Plonk proofs.

3. Global Constants & Other Data

Global network constants

  • NUM_ASSETS_BIT_LENGTH = 2
  • NUM_ASSETS = 1
  • DATA_TREE_DEPTH = 32
  • NULL_TREE_DEPTH = 256
  • ROOT_TREE_DEPTH = 28
  • MAX_TXS_BIT_LENGTH = 10
  • NOTE_VALUE_BIT_LENGTH = 252
  • TX_FEE_BIT_LENGTH = 254 - MAX_TXS_BIT_LENGTH

Pedersen Hash 'h' Elements

There are additionally

{hi}G1 elliptic curve group points used in the computation of Pedersen hashes.

For example:

  1. hi,i>0
    : used to compute hashes for large data strings with inputs of size
    >31 bytes
  2. h0,h1,h2,h3
    are used for all Pedersen Hashes in the Note Tree and Nullifier Tree

The generator algorithm for computing the

hi in pseudocode is:

counter = 0
h = []

do
  {
    compute x = keccak256(pad(i)), pad(i) = 32-byte pad of i 
    find y = sqrt (x³ + ax + b))
    if y = error
      {
        \\ unsuccessful: point does not exist (50% chance)
      }
    else
      {
        \\ successful: point exists and add to list (50% chance)
        set h[counter] = (x, y)
      }
    counter = counter + 1
  }
while counter < 1024

Notes and Commitments

A Note is encoded as follows:

  • note.nonce
  • note.asset_id
  • note.val
  • note.secret
  • note.owner.x
  • note.owner.y

Note: The nonce plays a role in enabling the revocation of spending keys. The secret is to construct a hiding Pedersen commitment to hide the note details.

Each is a field element in

Fp from the BN254 spec. So a note is an element of
Fp6
.

A Note Commitment is a Pedersen Commitment:

Comm(Note)=note.valueh0+note.secreth1+note.assetidh2
+note.owner.xh3+note.owner.yh4+note.nonceh5

An Account Note associates a spending key with an account. It consists of the following three field elements.

  • account_alias_id- a concatentation of the 224 bit alias_hash, with the 32-bit nonce. account_alias_id is enforced to be smaller than
    p
    (the bn-254 curve size), thus not all 32 byte values are possible.
  • account_public_key.x: the x-coordinate of the account public key
  • spending_public_key.x: the x-coordinate of the spending key that is been assigned to this account via this note.

The commitment to an account note

A, denoted
cm(A)
, is a pedersen commitment of
A
:
Cm(A)=A.accountaliasidh20+A.accountpublickey.xh21+A.spendingpublickey.xh22

(The start from 20 is according to the constant ACCOUNT_NOTE_HASH_INDEX )
The Account Nullifier
nf(A)
of an account note
A
is a pedersen hash of

  • 1 - (the account circuit proof id)
  • A.account_alias_id

Note encryption and decryption

Details on this are found here

State

Aztec 2.0's state is recorded via three Merkle trees:

  • The Note Tree: The Merkle tree of note commitments to all notes ever created in Aztec
  • The Nullifier Tree: The Merkle tree of all spent notes destroyed in Aztec
  • The RootRoot Tree: The Merkle tree of all old note tree roots

Summary of Circuits

The five circuits in Aztec 2.0 are:

  1. JoinSplit Circuit
  2. Account Circuit
  3. Rollup Circuit
  4. Escape-Hatch Circuit
  5. Root Rollup Circuit

The Inner Circuits: 1, 2 & 3
Validated by ZK Proofs over "Outer Circuits"

The Outer Circuits: 4 & 5
Validated by Mainnet Verifier

1. JoinSplit Circuit

◈ Circuit Description

This circuit allows notes to be spent.

The circuit takes in two input notes, and two new output notes, and updates the Note Tree and Nullifier Tree accordingly.

◈ Circuit Inputs: Summary

The inputs for the join-split circuit are:

JoinSplit Inputs=(Public Inputs,Private Inputs)Fp13×Fp28

Where the field

Fp is from the BN254 specification.

◈ Public Inputs: Detail

  1. proof_id
  2. public_input
  3. public_output
  4. public_asset_id
  5. output_nc_1_x (nc is short for note commitment)
  6. output_nc_1_y
  7. output_nc_2_x
  8. output_nc_2_y
  9. nullifier_1
  10. nullifier_2
  11. input_owner
  12. output_owner
  13. data_tree_root

◈ Private Inputs: Detail

  1. input_note_1.val
  2. input_note_1.secret
  3. input_note_1.account_id
  4. input_note_1.asset_id
  5. input_note_2.val
  6. input_note_2.secret
  7. input_note_2.account_id
  8. input_note_2.asset_id
  9. index_1
  10. index_2
  11. input_note_2.asset_id
  12. output_note_1.val
  13. output_note_1.secret
  14. output_note_1.account_id
  15. output_note_1.asset_id
  16. output_note_1.nonce
  17. output_note_2.val
  18. output_note_2.secret
  19. output_note_2.account_id
  20. output_note_2.asset_id
  21. output_note_2.nonce
  22. account_note.account_id
  23. account_note.npk (npk=nullifier public key)
  24. account_note.spk (spk=spending public key)
  25. index_ac
  26. note_num
  27. nk (nullifier private key)
  28. signature

◈ Index of Functions

In the Pseudocode to follow, we use the following function names:

  • NC Note commitment function, which is assumed to be
    • Collision-resistant
    • Field-friendly, which means the output value only depends on the inputs as field elements, and doesn’t change e.g. when input changes from a to a+r as bit string.
  • CompressNC Note Commitment Compressor takes a note commitment (an elliptic curve point) and compresses by just taking the x coordinate
  • NF Nullifier Function, which we assume can be modeled as a random oracle, and only depends on
    nk mod r
  • AC Account Note Commitment, which is assumed to be collision resistant
  • Update Merkle Update Function inserts a set of compressed note commitments into the note tree and validates the correctness of the associated merkle root update

◈ Circuit Logic (Pseudocode)

1. Range Checks

for i = 1,2
  {
    let input_note_i =
      (
        input_note_i.val,
        input_note_i.secret,
        input_note_i.account_id,
        input_note_i.asset_id,
        input_note_i.nonce
      )
      
      
    check range
      (input_note_i.val, NOTE_VALUE_BIT_LENGTH))
      == true
      
    check range
      (input_note_i.asset_id, NUM_ASSETS_BIT_LENGTH)
      == true
      
    check
      input_note_i.account_id = account_note.account_id`
  }  

2. Check inputs notes are valid

for i = 1,2
{
  compute nc_i = NC(input_note_i)
    
    check membership
      (CompressNC(nc_i,) index_i, data_tree_root)
      == (note_num >= i)
}

3. Check Nullifiers Correctly Computed

for i = 1,2
  {
    check nullifier_i = NF(nc_i, index_i, nk)
  }

4. Verify Account Ownership

let account_note =
  (
    account_note.npk,
    account_note.spk,
    account_note.account_id
  )
  
let ac = AC(account_note)

check membership(ac, index_ac, data_tree_root)
check NPK(nk)=account_note.npk

let output_note_nc_i = 
  (
    output_note_nc_i_x,
    output_note_nc_i_y
  )

let message =
  (
    nc_1, nc_2, output_note_nc_1,
    output_note_nc_2, output_owner
  )

check CHECKSIG
  (
    message,
    signature,
    account_note.spk
  )

5. Check Notes Above Max Output Notes Do Not Carry Value

if (note_num < 2) 
  { 
    validate input_note_2.value == 0
  }
  
if (num_num < 1)
  {
    validate input_note_1.value == 0
  }

6. Check Notes In = Notes Out

let total_in_value =
  public_input +
  input_note_1.value +
  input_note_2.value
  
let total_out_value =
  public_output +
  output_note_1.value +
  output_note_2.value

check
  total_in_value == total_out_value

7. Asset Type Checks

check
  input_note_1.asset_id == input_note_2.asset_id
  
check
  output_note_1.asset_id == input_note_2.asset_id
  
check
  output_note_2.asset_id == output_note_1.asset_id
  
check
  public_asset_id == input_note_1.asset_id
  ⟺
  (public_input != 0 || public_output != 0)

2. Account Circuit

◈ Circuit Description

The Account Circuit enables the transfer of keys that control notes.

Unlike the Rollup Circuit, which always adds nullifiers to the tree, the Account Circuit conditionally adds nullifiers to the tree.

Gibberish Nullifiers

This condition is emulated via the production of Gibberish Nullifiers where we do not wish to add a nullifier to the nullifier set. In doing so, we must ensure that:

  1. Different circuits cannot produce identical nullifiers
  2. Gibberish nullfiers are distinct from real nullifiers

We achieve outcome 1. by including the proof_id in each nullifier computation.

Ensuring outcome 2. is harder. The circuit must have a flag variable, is_nullifier_fake, that we use to modify the input data being hashed.

Account Circuit: Worked Example

  1. Alice generates a grumpkin key pair (account_key)
  2. Alice can receive funds prior to registering an alias at account_value_id = (account_public_key, 0)
  3. On registration of the alias 'alice', the account_id = (alice, 0) is nullified, and new spending keys are associated with (alice, 1)
  4. Alice transfers received funds at (account_public_key, 0), to (account_public_key, 1)
  5. Alice registers additional spending keys to (alice, 1)
  6. If a spending key becomes compromised, Alice nullifies account_id = (alice, 1), associating new spending keys with (alice, 2)
  7. Alice transfers funds at (account_public_key, 1), to (account_public_key, 2)

◈ Circuit Inputs: Summary

The inputs for the account circuit are:

Account Inputs=(Public Inputs,Private Inputs)Fp13×Fp25

As previously, the field

Fp is from the BN254 specification.

◈ Public Inputs: Detail

Recall that all inner circuits must have the same number of public inputs as they will be used homogenously by the rollup circuit.

However, we repurpose and rename some inputs for to describe the inner circuit. We denote the renaming of a given input with the notation [old name] --> [new name]

  1. proof_id
  2. public_input --> acccount_pubkey_x
  3. public_output --> account_pubkey_y
  4. public_asset_id --> account_id
  5. output_nc_1_x (nc is short for note commitment)
  6. output_nc_1_y
  7. output_nc_2_x
  8. output_nc_2_y
  9. nullifier_1
  10. nullifier_2
  11. input_owner
  12. output_owner
  13. data_tree_root

◈ Private Inputs: Detail

  1. input_note_1.val
  2. input_note_1.secret
  3. input_note_1.account_id
  4. input_note_1.asset_id
  5. input_note_2.val
  6. input_note_2.secret
  7. input_note_2.account_id
  8. index_1
  9. index_2
  10. input_note_2.asset_id
  11. output_note_1.val
  12. output_note_1.secret
  13. output_note_1.account_id
  14. output_note_1.asset_id
  15. output_note_2.val
  16. output_note_2.secret
  17. output_note_2.account_id
  18. output_note_2.asset_id
  19. account_note.account_id
  20. account_note.npk (npk=nullifier public key)
  21. account_note.spk (spk=spending public key)
  22. index_ac
  23. note_num
  24. nk (nullifier private key)
  25. signature

◈ Index of Functions

None

◈ Circuit Logic (Pseudocode)

Computed vars:

  • alias_hash = account_id.slice(0, 28)
  • nonce = account_id.slice(28, 4)
  • output_nonce = migrate + nonce
  • output_account_id = alias_hash + (output_nonce * 2^224)
  • assert_account_exists = nonce != 0
  • signer = nonce == 0 ? account_public_key : signing_public_key
  • message = pedersen(account_public_key, account_id, spending_public_key_1.x, spending_public_key_2.x)
  • account_note_data = pedersen(account_id, account_public_key.x, signer.x)
  • is_nullifier_fake = migrate == 0

Computed public inputs:

  • output_note_1_x/y = pedersen(output_account_id, account_public_key.x, account_public_key.y, spending_public_key_1.x, spending_public_key_1.y)
  • output_note_2_x/y = pedersen(output_account_id, account_public_key.x, account_public_key.y, spending_public_key_2.x, spending_public_key_2.y)
  • nullifier_1 = pedersen(proof_id + (is_nullifier_fake * 2^250), account_id, !migrate * gibberish)
  • nullifier_2 = pedersen(proof_id + (1 * 2^250), gibberish)

Circuit constraints:

  • migrate == 1 || migrate == 0
  • verify_signature(message, signer, signature) == 1
  • membership_check(account_note_data, account_note_index, account_note_path, data_tree_root) == assert_account_exists

3. Rollup circuit

◈ Circuit Description

The rollup circuit aggregates proofs from a defined set of ‘inner’ circuits.

Each inner circuit has 13 public inputs. The rollup circuit will execute several defined subroutines on the public inputs.

◈ Public Inputs: Detail

There are

27+12×rollup_size public inputs, in three sections:

  1. Rollup Proof Data: 11 elements from
    Fp
    that define the rollup block information (described below)
  2. Rolled-Up Transactions Data: Inner-circuit public inputs (
    12×rollup_size
    inputs;
    12
    inputs per rolled up transaction)
  3. Recursive Proof Data:
    4
    elements from
    Fq
    , represented as
    16
    elements from
    Fp
    , whose values are
    <268
    ; see here for explanation.

All are field elements. The first 11 public inputs are the following:

  1. rollup_id
  2. rollup_size
  3. data_start_index
  4. old_data_root
  5. new_data_root
  6. old_null_root
  7. new_null_root
  8. old_data_root_root
  9. new_data_root_root
  10. total_tx_fee
  11. num_txs

◈ Private Inputs: Detail

The following inputs are private to reduce proof size:

  1. The recursive proof output of each inner proof (4
    Fq
    elements represented as 16
    Fp
    elements, see above)
  2. The remaining 2 public inputs of each inner-circuit proof (the transaction fee and a claimed root of the data tree)

◈ Index of Functions

  • Extract Extraction Function extracts 14 public inputs from a proof, validates the result matches the rollup’s inner public inputs
  • Aggregate Proof Aggregation Function for ultimate batch verification outside the circuit, given a verification key and (optional, defined by 4th input parameter) a previous output of Aggregate. Returns a BN254 point pair
  • NonMembershipUpdate Nullifier Update Function checks a nullifier is not in a nullifier set given its root, then inserts the nullifier and validates the correctness of the associated merkle root update
  • BatchUpdate Batch Update Function inserts a set of compressed note commitments into the note tree and validates the corretness of the associated merkle root update
    Update - inserts a single leaf into the root tree and validates the corretness of the associated merkle root update

◈ Circuit Logic (Pseudocode)

  1. Let Q_0 = [0, 0]
  2. Validate num_inputs == N
  3. For i = 1, ..., num_inputs
    1. Let pub_inputs = Extract(PI_i)
    2. Let vk = vks[proof_id_i]
    3. Let Q_i = Aggregate(PI_i, pub_inputs, vk, Q_{i-1}, (i > 1))
    4. Let
      leaf2i
      = CompressNC(output_nc_1_x_i, output_nc_1_y_i)
    5. Let
      leaf2i+1
      = CompressNC(output_nc_2_x_i, output_nc_2_y_i)
    6. Validate NonMembershipUpdate(
      null_root2i
      ,
      null_root2i+1
      , nullifier_1_i)
    7. Validate NonMembershipUpdate(
      null_root2i+1
      ,
      null_root2i+2
      , nullifier_2_i)
    8. Validate Membership(old_data_roots_root, data_tree_root_index_i, data_tree_root_i)
  4. Validate [P1, P2] = Q_{num_inputs}
  5. Validate BatchUpdate(old_data_root, new_data_root, data_start_index, leaf_1, ..., leaf_{2 * num_inputs})
  6. Validate old_null_root = null_root_1
  7. Validate new_null_root = null_root_{2 * num_inputs + 1}

4. Escape-Hatch circuit

◈ Circuit Description

This is an outer circuit, allowing the user to withdraw funds directly from the network without requiring a relayer service to roll up the transaction. It is a temporary safeguard until the node service is decentralised.

The escape hatch circuit consists of a JoinSplit circuit, combined with checks usually done in the rollup circuit. Namely, that the nullifiers and data tree root are valid.

The rollup smart contract will only accept escape hatch proofs for a two-hour window every twenty-four hours, to prevent race conditions between rollup proofs and escape hatch proofs.

◈ Public Inputs:

A set of public inputs joinsplit_public to the Joinsplit circuit. Including in particular ``

  1. proof_id
  2. public_input
  3. public_output
  4. public_asset_id
  5. output_nc_1_x (nc is short for note commitment)
  6. output_nc_1_y
  7. output_nc_2_x
  8. output_nc_2_y
  9. nullifier_1
  10. nullifier_2
  11. input_owner
  12. output_owner
  13. data_tree_root

The following additional public inputs
rollup_id,data_start_index,old_data_root, new_data_root, old_null_root, new_null_root,old_data_roots_root,new_data_roots_root

◈ Private Inputs: Detail

  1. A set joinsplit_private of private inputs to the joinsplit circuit.

◈ Index of Functions

None

◈ Circuit Logic (Pseudocode)

  1. Check the joinsplit circuit logic on joinsplit_public,joinsplit_private
  2. Check the rollup circuit logic except proof aggregation and verification key correctness (cause the escape hatch always uses the joinsplit verification key).
    In more detail:
    1. Let leaf_1 = CompressNC(output_nc_1_x, output_nc_1_y)
    2. Let leaf_2 = CompressNC(output_nc_2_x, output_nc_2_y)
    3. Validate NonMembershipUpdate(old_null_root, new_null_root, {nullifier_1,nullifier_2})
    4. Validate leaf_1,leaf_2 are in old_data_root, and their addition results in new_data_root
    5. Validate Membership(old_data_roots_root, new_data_roots_root,data_tree_root, rollup_id)
  3. Validate BatchUpdate(old_data_root, new_data_root, data_start_index, $\text{leaf}_{1}, ..., \text{leaf}_{2 * \text{num_inputs}}$)

5. Root Rollup circuit

◈ Circuit Description

This circuit rolls up other rollup proofs.

It is defined by a parameter rollup_num, of inner rollups. Let's also denote

M:=rollup_num for convenience.

◈ Circuit Inputs: Summary

The inputs for the root rollup circuit are:

Rool Rollup Inputs=(Public Inputs,Private Inputs)Fp27+M(1232)×Fp27M

As previously, the field

Fp is from the BN254 specification.

◈ Public Inputs

  1. For
    i=1,..,M
    1. A set
      PIi
      of public inputs of the roll-up circuit's inner-circuit proofs.
  2. A pair of points
    QM+1
    (given as 16 field elements as described in the rollup circuit)
  3. rollup_id (The location where new_root_M will be inserted in the roots tree)
  4. rollup_size
  5. data_start_index
  6. old_data_root
  7. new_data_root
  8. old_null_root
  9. new_null_root
  10. old_root_root
  11. new_root_root

◈ Private Inputs

  1. The recursive proof output of each inner rollup proof (4
    Fq
    elements represented as 16
    Fp
    elements, see above)
  2. The remaining public inputs of each rollup proof

◈ Circuit Logic (Pseudocode)

  1. For
    i=2,..,M+1
    , check that
    Qi=aggregate(PIi1,πi1,vk,Qi1,(i>1))
  2. For
    i=2,..,M
    , check that new_data_root
    i1
    =old_data_root
    i
    .
  3. Validate Update(old_data_roots_root, new_data_roots_root, rollup_id, new_data_root_M)

where

vk is the verification key of the rollup circuit.