Home

Awesome

RollupNC (Rollup non-custodial)

SNARKs can generate succinct proofs for large computations, which are much faster and computationally easier to verify than they are to compute. This provides a way to "compress" expensive operations by computing them off-chain in a SNARK, and then only verifying the proof on-chain.

RollupNC is an implementation of rollup in which the relayer does not publish transaction data to the main chain, but only publishes the new Merkle root at every update. This provides gas savings but not data availability guarantees: we assume the operator will always provide data to users so they can update their leaf.

NB: it is trivial to change this implementation back to the original rollup, since it simply involves switching the private circuit inputs to public.

<!-- toc --> <!-- tocstop -->

Building this repo

  1. Install node version 10.16.0, possibly using nvm
  2. Install truffle and ganache-cli bash $ npm install -g truffle ganache-cli
  3. Install submodules: use git submodule update --init --recursive to clone circomlib submodule
  4. Install npm modules (npm i) in both root directory and circomlib submodule
  5. Check out this circom intro

Spec

Parameters

Data structures

EdDSA

eddsa_prvKey: string //"biginteger"

class eddsa_pubKey = {
  X: string // "biginteger",
  Y: string // "biginteger"
}

class eddsa_signature = {
  R8: string[2] // "biginteger",
  S: string // "biginteger"
}

Account

class Account = {
  pubKey: eddsa_pubKey,
  balance: integer,
  nonce: integer,
  token_type: integer
}

account_leaf = hash([pubKey, balance, nonce, token_type])

The Accounts Merkle tree has depth bal_depth and 2^bal_depth accounts as its leaves. The first leaf (index 0) is reserved as the zero_leaf. Transactions made to the zero_leaf are considered withdraws. The second leaf (index 1) is reserved as a known operator leaf. This account can be used to make zero transactions when we need to pad inputs to the circuit.

For convenience, we also cache the empty accounts tree when initialising rollupNC.

zeroCache = string[bal_depth] //"biginteger"

Transaction

class Transaction = {
  from: eddsa_pubKey,
  fromIndex: integer,
  to: eddsa_pubKey,
  amount: integer,
  nonce: integer,
  token_type: integer
}

TODO: implement atomic swaps and fees fields in Transfer object

tx_leaf = hash([from_pubKey, to_pubKey, amount, nonce, token_type])

For each SNARK, we construct a Transactions Merkle tree, whose leaves are the transactions processed by the SNARK.

User

The user sends deposit and withdraw transactions directly to the smart contract, and all other normal transactions to the off-chain coordinator.

Deposits

  1. User calls deposit(eddsa_pubkey, amount, tokenType) on smart contract. The deposit() function:
deposits_array = []
deposits_array = [A] // Alice deposits, pushed to deposits_array
deposits_array = [A, B] // Bob deposits, pushed to deposits_array

deposits_array = [hash(A, B)] // Bob hashes Alice's deposit and his own
deposits_array = [hash(A, B), C] // Charlie deposits, pushed to deposits_array
deposits_array = [hash(A, B), C, D] // Daenerys deposits
deposits_array = [hash(A, B), hash(C, D)] // Daenerys hashes Charlie's deposit and her own
deposits_array = [hash(hash(A, B), hash(C, D))] // Daenerys hashes H(A,B) and H(C,D)

Notice that the number of times a user has to hash deposits_array is equal to the number of times her deposit_queue_number can be divided by 2. Also, the first element of deposits_array is the root of the tallest perfect deposit subtree at any given point.

  1. Coordinator inserts deposit root into balance tree at deposit_root.height

Transactions

  1. User constructs Transaction object

  2. User hashes Transaction object Use multiHash in https://github.com/iden3/circomlib/blob/master/src/mimc7.js#L47.

txHash = multiHash([from, to, amount, nonce, token_type]) //"biginteger"
  1. User signs hash of Transaction object Use signMiMC in https://github.com/iden3/circomlib/blob/master/src/eddsa.js#L53.
signature = signMiMC(prvKey, txHash)

Withdraw

  1. User submits proof of inclusion of withdraw tx on-chain Merkle proof of a transaction in a tx tree, made from user's EdDSA account to the zero address

  2. User EdDSA signs message specifying recipient's Ethereum address

  3. User submits SNARK proof of EdDSA signature to smart contract

Prover

The prover collects transactions from users and puts them through a SNARK circuit, which outputs a SNARK proof. She then submits the SNARK proof to the smart contract to update the Accounts tree root on-chain.

Public inputs and output

What the circuit is actually doing

The circuit is a giant for loop that performs a few validity checks on each transaction and updates the Accounts tree if the transaction is valid. It takes in the original root of the Accounts tree and a list of transactions, and outputs a legally updated root of the Accounts tree.

Let's go through the first iteration of the for loop:

Note: there is a special transaction where the receiver is the zero_leaf. We consider these to be withdraw transactions and do not change the balance and nonce of the zero_leaf.

Inputs to SNARK circuit

Parameters

Private inputs (organised by purpose)

General
Transaction information
Transaction checks
Account existence checks