KO | EN

GitLite

Minimalist Open Source Repository Search Engine

gitlite — search

#developer-tools #typescript #claude-code #codex #dsh #dsh-plugin #ai-agent #ai-agents #deepseek-harness #agent-skills #macos #cli

RollupNC

★ 104 Open GitHub ↗

non-custodial exchange build with rollup

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# RollupNC (Rollup non-custodial)

![](https://i.imgur.com/ZXVs8IP.png)

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](https://github.com/barryWhiteHat/roll_up) 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`.

- [Building this repo](#building-this-repo)
- [Spec](#spec)
  * [Parameters](#parameters)
  * [Data structures](#data-structures)
    + [EdDSA](#eddsa)
    + [Account](#account)
    + [Transaction](#transaction)
- [User](#user)
  * [Deposits](#deposits)
  * [Transactions](#transactions)
  * [Withdraw](#withdraw)
- [Prover](#prover)
  * [Public inputs and output](#public-inputs-and-output)
  * [What the circuit is actually doing](#what-the-circuit-is-actually-doing)
  * [Inputs to SNARK circuit](#inputs-to-snark-circuit)
    + [Parameters](#parameters-1)
  * [Private inputs (organised by purpose)](#private-inputs-organised-by-purpose)
      - [General](#general)
      - [Transaction information](#transaction-information)
      - [Transaction checks](#transaction-checks)
      - [Account existence checks](#account-existence-checks)

## Building this repo

1. Install node version 10.16.0, possibly using [nvm](https://github.com/nvm-sh/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](https://github.com/iden3/circom/blob/master/TUTORIAL.md)

## Spec

### Parameters
- `bal_depth`: depth of balance Merkle tree
- `tx_depth`: depth of transaction Merkle tree

### Data structures

#### EdDSA

```
eddsa_prvKey: string //"biginteger"
```

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

```js
class eddsa_signature = {
  R8: string[2] // "biginteger",
  S: string // "biginteger"
}
```
#### Account
```js
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 `withdraw`s. 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
```js
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:

- increments `deposit_queue_number` (global variable in smart contract)
  
  - hashes `[eddsa_pubkey, amount, nonce = 0, tokenType]` to get the `deposit_leaf` (an `account_leaf`)

- push `deposit_leaf` to `deposits_array`
  ```
  deposits_array = []
  deposits_array = [A] // Alice deposits, pushed to deposits_array
  deposits_array = [A, B] // Bob deposits, pushed to deposits_array
  ```

- hash deposit array into on-chain Merkle root, `deposit_root`
  
  ```
  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.

2. Coordinator inserts deposit root into balance tree at `deposit_root.height`

- **prove that balance tree was empty at `deposit_root.height`**: provide `deposit_proof` to smart contract, a Merkle proof showing inclusion of an empty inner node at `deposit_tree.height` (`zeroCache[deposit_tree.height]`) in the current state root

- **update balance root on-chain**: using same `deposit_proof`, update the balance root replacing the empty inner node with the first element of `deposits_array`. (NB: the first element of `deposits_array` is the root of the tallest perfect deposit subtree.)

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

```js
txHash = multiHash([from, to, amount, nonce, token_type]) //"biginteger"
```

3. User signs hash of `Transaction` object
Use `signMiMC` in https://github.com/iden3/circomlib/blob/master/src/eddsa.js#L53.

```js
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
- `tx_root`: Merkle root of a tree of transactions sent to the coordinator
- `current_state`: Merkle root of old Accounts tree 
- `out`: Merkle root of updated Accounts tree

### 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:
- transaction check
  - **transactions existence check**: check that transaction exists in the `tx_root`
  - **transactions signature check**: check that transaction is signed by sender
- sender check
  - **sender account existence check**: check that sender account exists in `current_state`
  - **balance underflow check**: check that sender has sufficient balance to send transaction
- sender update
  - **sender state update**: decrement sender `balance` and increase sender `nonce`
  - **intermediate root update #1**: update `current_state` with new sender leaf to get `intermediate_root_1`
- receiver check
  - **receiver account existence check**: check that receiver account exists in `intermediate_root_1`
- receiver update
  - **receiver state update**: increment receiver `balance`
  - **intermediate root update #2**: update `intermediate_root_1` with new receiver leaf to get `intermediate_root_2`

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
- `n`: depth of Accounts tree (`bal_depth`)
- `m`: depth of Transactions tree (`tx_depth`)

### Private inputs (organised by purpose)
##### General
- `intermediate_roots[2**(m+1) + 1]`: the roots of the Accounts tree after processing each transaction. There are `2*2^m + 1` intermediate roots because each transaction results in two updates (once to update the sender account, and then to update the receiver account), and we also include the original root at the beginning (before updating any account)

##### Transaction information
- sender and receiver addresses
  - `from_x[2**m]`: the sender address x coordinate for each transaction
  - `from_y[2**m]`: the sender address y coordinate for each transaction
  - `from_index[2**m]`: the sender leaf index in the Merkle tree
  - `to_x[2**m]`: the receiver address x coordinate for each transaction
  - `to_y[2**m]`: the receiver address y coordinate for each transaction

- signature from sender
  - `R8x[2**m]`: the x component of the R8 value of the sender's signature, for each transaction
  - `R8y[2**m]`: the y component of the R8 value of the sender's signature, for each transaction
  - `S[2**m]`: the S value of the sender's signature, for each transaction

- sender and receiver state
  - `nonce_from[2**m]`: the nonce of the sender account, for each transaction
  - `nonce_to[2**m]`: the nonce of the receiver account, for each transaction
  - `token_balance_from[2**m]`: the balance of the sender account, for each transaction
  - `token_balance_to[2**m]`: the balance of the receiver account, for each transaction

- amount and token type being transacted
  - `amount[2**m]`: amount being transferred, for each transaction 
  - `token_type_from[2**m]`: the sender account token type, for each transaction
  - `token_type_to[2**m]`: the receiver account token type, for each transaction

##### Transaction checks
- `paths2tx_root[2**m, m]`: Merkle proofs of inclusion (`m` long, since the Transactions tree has depth `m`) for the transactions (`2^m` of them)`
- `paths2tx_root_pos[2**m, m]`: a binary vector for each transfer indicating whether each node in its transfer proof is the left or right child

##### Account existence checks
- `paths2root_from[2**m, n]`: Merkle proofs of inclusion (`n` long, since the Accounts tree has depth `n`) for the sender accounts (`2^m` of them)
- `paths2root_from_pos[2**m, n]`: a binary vector for each sender account indicating whether each node in its transfer proof is the left or right child
- `paths2root_to[2**m, n]`: Merkle proofs of inclusion (`n` long, since the Accounts tree has depth `n`) for the receiver accounts (`2^m` of them)
- `paths2root_to_pos[2**m, n]`: a binary vector for each receiver account indicating whether each node in its transfer proof is the left or right child

RollupNC

Explore Similar Repositories

Was this content helpful?

Recent Feedback

Download README