---
# System prepended metadata

title: rollupNC user/data flow

---

# rollupNC user/data flow
in this document we think through the roles of `rollupnc_coordinator` (https://github.com/vaibhavchellani/rollupnc_coordinator), how to optimise user experience, and the complexities / possible failure paths (e.g. latency, chain reorgs).

[TOC]


## Database schema 

### Accounts Table

```mysql
    index(autoincrement?,integer,unique,primaryKey), 
    _pubkeyX(string), 
    _pubkeyY(string), 
    _balance(integer), 
    _nonce(integer), 
    _tokenType(integer)
```

### Accounts Tree Table

for a Sparse Merkle Tree of fixed depth `n` we have node entries

```mysql
    depth,
    index,
    hash
```

since most of these nodes will be empty, we can optimise storage by **only storing the subtree nodes of the tallest empty subtrees**. this saves us from having to store a large number of empty leaves. each time we add a new account or batch of accounts, we should recalculate the `zeroCache` nodes we're using, as such:

- we pre-compute the `zeroCache`, i.e. the nodes of the empty tree at depths `0, ..., n`
- for `m` nonempty leaves, the smallest perfect empty subtree that is larger than the nonempty subtree has `2^k` leaves, with `2^k` being the smallest power of 2 that is larger than `m`. 
- therefore we insert the `zeroCache` node at depth `n - k` to represent an empty tree of height `k`
- we increment `k` and repeat the procedure, until we have accounted for the whole tree (i.e., `2^{ceil(log(m))} + 2^k + 2^{k+1} + ... + 2^{n-1} == 2^n`)



### Transactions Table
```mysql
    txHash(string, unique,primary)
    fromX(string),
    fromY(string),
    fromIndex(integer),
    toX(string),
    toY(String),
    toIndex(integer),
    amount(integer),
    nonce(integer),
    token_type(integer),
    R8x(string),
    R8y(string),
    S(string),
    status(integer),
    txRoot(string)
```
each tx has a status:
    0: processing
    1: awaiting transfer inclusion in proof,
    2: transfer included in proof,
    3: awaiting withdraw inclusion in proof,
    //TODO remove usage of 3 as withdraw is same as transafer to 0 and can be indetified by to address 
    4: withdraw included in proof,
    5: withdrawn on smart contract

### Deposits Table(stores all processed deposits)
```mysql
    txHash(string,unique,indexable,PrimaryKey), // of Ethereum tx
    blockNumber(integer),
    pubkeyX(string),
    pubkeyY(string),
    tokenType(integer,foreignKey),
    amount(integer)
    DepositHash(string)
```

### State Transition History Table
```mysql
    txRoot(string,unique,indexable,PrimaryKey),
    toIndexArray (JSON array),
    txHashArray (JSON array),
    proof (JSON object)
```

what's contained in the proof:
```javascript
    txRoot: stringifyBigInts(txTree.root),
    paths2txRoot: stringifyBigInts(paths2txRoot),
    paths2txRootPos: paths2txRootPos,
    currentState: stringifyBigInts(currentState),
    intermediateRoots: stringifyBigInts(intermediateRoots),
    paths2rootFrom: stringifyBigInts(paths2rootFrom),
    paths2rootFromPos: paths2rootFromPos,
    paths2rootTo: stringifyBigInts(paths2rootTo),
    paths2rootToPos: paths2rootToPos,
    fromX: stringifyBigInts(fromX),
    fromY: stringifyBigInts(fromY),
    fromIndex: fromIndex,
    toX: stringifyBigInts(toX),
    toY: stringifyBigInts(toY),
    nonceFrom: nonceFrom,
    amount: amount,
    tokenTypeFrom: tokenTypeFrom,
    R8x: stringifyBigInts(R8x),
    R8y: stringifyBigInts(R8y),
    S: stringifyBigInts(S),
    balanceFrom: balanceFrom,
    balanceTo: balanceTo,
    nonceTo: nonceTo,
    tokenTypeTo: tokenTypeTo
```

### Token Types (stores allowed token types)
```mysql
    id(unique,indexable,PrimaryKey),
    name(string,optional),
    contractAddress(string,optional)
```




## proposed division of tasks

### DB structure [YT, VC]
- [x]  make `depositsTable`
- [x]  storing trees in `accountsTable`, 
- [x]  storing trees in `transactionsTable` 
- [x]  make `stateTransition` table

### backend <-> circuit [YT]
- [ ]  add new leaves if tx recipient pubkey does not exist
- [ ]  updating leaves and inner nodes while processing txs 
- [ ]  integrating websnark 

### backend <-> contract [YT]
- [ ]  withdraw poller 
- [ ]  update withdrawn txs
- [ ]  insert deposit subtrees 

> the tasks above this comment write to the DB, the tasks below this comment only read from the DB [name=ying tong]

### backend <-> frontend (API) [VC/YT]
- [ ]  initialise `zeroCache` in memory
    - `zeroCache` is used to provide Merkle proofs
- [ ]  checking txs before passing to circuit 
    - [ ]  `checkSignature(txHash, senderPubkey, signature)`
    - [ ]  `checkTokenTypes(txTokenType, senderTokenType, receiverTokenType)`
    - [ ]  `checkAccountExistence(senderPubkey)`
    - [ ]  `checkAccountExistence(receiverPubkey)`
- [ ]  padding txs before passing to circuit [YT]
    - [x]  generate `coordinator` prvkey and pubkey at setup for empty txs
    - [ ]  figure out optimal `maxTxs` and `timeout` quantities
    - [ ]  write `getEmptyTx()` method which signs an empty transaction form the coordinator to itself (NB: coordinator’s nonce increases each time getEmptyTx() is called) 
- [ ]  displaying list of accounts for each `pubkey` (since one `pubkey` can have accounts at different tree indices)
- [ ]  displaying account state 
- [ ]  displaying an account's unwithdrawn "withdraw" txs 
- [ ]  serving withdraw tx Merkle proofs 


## DB structure

### accounts
##### `pendingDepositsTable`
- each row should have the fields: `pubkeyX, pubkeyY, index, nonce, balance, tokenType, txHash, blockHash`

##### `accountsTable`
- should store both leaf nodes and inner nodes of `AccountsTree`
    > TODO: figure out good way to store tree; can possibly use flat list as seen at https://github.com/therealyingtong/zips/blob/44978fa6092e6d14a8f0dc6b0fb8711bedf22dc1/zip-0221.rst#background

    > TODO: think about how to store `zeroCache` in `Tree` class; since most accounts will be empty we don't need to store leaf nodes, only inner nodes

### transactions
##### `mempool`

**Queuing Logic for POC**
FIFO, transactions that persist to DB first will be picked first. Later we want to pick transactions by fees and nonce. After atomic swaps we want to pick dependant transactions. 

##### `transactionsTable`
- should store both leaf nodes and inner nodes of each `TxTree`
- each tx has a status:

        0: awaiting transfer confirmation,
        1: transfer confirmed,
        2: awaiting withdraw,
        3: withdrawn 

```javascript=
class Transaction  {
    constructor(
          _fromX, _fromY, _fromIndex, 
          _toX, _toY, 
          _nonce, _amount, _tokenType, 
          _R8x, _R8y, _S
        ) {
          this.fromX = _fromX;
          this.fromY = _fromY;
          this._fromIndex;
          this.toX = _toX;
          this.toY = _toY;
          this.nonce = _nonce;
          this.amount = _amount
          this.tokenType = _tokenType;

          this.hash = this.hashTx();
          // this.txRoot ?
      
          this.R8x = _R8x;
          this.R8y = _R8y;
          this.S = _S;
          
          this.status;
    }
}
```

## scripts

### pollers 
- `depositPoller` (implemented at https://github.com/vaibhavchellani/rollupNC_coordinator/blob/master/src/events.js)
    - listens for `RequestDeposit()` events so that `pendingDepositsTable` can be updated
- `withdrawPoller`
    - listens for `Withdraw()` events 
    - update status of "withdraw" txs in `transactionsTable` can be updated from `3 (withdraw included in proof)` to `4 (withdrawn on smart contract)`

- `mempool.js`: 
    - get txs from mempool, 
    - initial validation of txs, 
    - add txs to DB

### setters
- `depositProcessor.js`: add deposit subtrees, call `processDeposits()` on smart contract
- `processor.js`: carry out state transition using txs, update accounts table, produce stateTransition object
    - `debitAndIncreaseNonce(amount)`
    - `credit(amount)`
    - `updateInnerNodes(leafHash, index, proof)`
    - add `txTree` to DB for each batch of transactions
- `prover.js`: 
    - pad txs, 
    - reformat txs and stateTransition object into circuit input, produce proof, 
    - submit proof to smart contract, 
    - update status in accounts table

- `withdrawsTable` setter
    - add `withdrawTxs` for each batch of transactions
    

### getters (API)
- `accountsTable` getter (see )
    - get `Account` (including `token, nonce, balance, hash`) for `pubkey, index`
    - get list of accounts for each user's `pubkey` (can map to multiple `index`)
    - get `proof, proofPos` for `pubkey, index`

- `transactionsTable` getter
    - get `withdrawTxs` for `pubkey, index`

### helpers
- `preprocessingCheck` (check txs in mempool before grabbing them)
    - `checkSignature(txHash, senderPubkey, signature)`
    - `checkTokenTypes(txTokenType, senderTokenType, receiverTokenType)`
    - `checkAccountExistence(senderPubkey)`
    - `checkAccountExistence(receiverPubkey)`

- `processingCheck` (used while processing txs, refer to https://github.com/rollupnc/RollupNC/blob/master/src/accountTree.js#L11) 
    - `checkTxExistence(tx, txProof)`
    - `checkAccountExistence(accountHash, accountIndex, proof)`

## user flow
### deposit

> smart contract reference: `deposit()` and `processDeposits()` on `RollupNC.sol` https://github.com/rollupnc/RollupNC/blob/master/contracts/RollupNC.sol#L100 

0. user clicks 'Deposit' on frontend, which prompts them to sign and send a `deposit()` transaction to `RollupNC.sol` using Metamask
1. user deposits on smart contract with `deposit([pubkeyX, pubkeyY], amount, tokenType)`, emitting a `RequestDeposit([pubkeyX, pubkeyY],  amount, tokenType)` event
2. poller polls `RequestDeposit` events
3. coordinator assigns each `Deposit` event (i.e. new account) an `index` (i.e. its position in the `AccountsTree`)
      - the `index` is the sum of the first empty row number in the `pendingDepositsTable` and the index of the first empty leaf in the `AccountsTree`. 
      - make sure that each deposit event is from a unique transaction
      - what to do in case of block reorgs?
> [name=Vaibhav Chellani] Process deposits only on confirmation? 6 Blocks?
4. hash each `Deposit` event using 
    ```javascript
    function hashAccount(){
        const accountHash = mimcjs.multiHash([
            // this.index.toString(),
            this.pubkeyX.toString(),
            this.pubkeyY.toString(),
            this.balance.toString(),
            this.nonce.toString(),
            this.tokenType.toString(),
        ])
        return accountHash
    }
    ```
5. format `Deposit` event into `Account` object and insert it to the `pendingDepositsTable`. on insertion, also hash the account and store its hash in the table.

    (pseudocode)
    
    ``` javascript
    function insertDeposit(_pubkeyX, _pubkeyY, _tokenType, _amount){
        const depositHash = hashAccount()
        depositsTable.insert(
            {
                index: getIndex(),
                pubkeyX: _pubkeyX,
                pubkeyY: _pubkeyY,
                balance: _amount,
                nonce: 0,
                tokenType: _tokenType,
                hash: depositHash
            }
        )
    }
    ```
6. coordinator decides to process deposits, and selects the largest power of 2 number of deposits in `pendingDepositsTable`. 
7. coordinator hashes together the selected deposits into a `DepositSubtree` using this method from the `AccountsTree` class:

```javascript
    function treeFromLeafNodes(){
        var tree = Array(this.depth);
        tree[this.depth - 1] = treeHelper.pairwiseHash(this.leafNodes)

        for (var j = this.depth - 2; j >= 0; j--){
            tree[j] = treeHelper.pairwiseHash(tree[j+1])
        }
        return tree
    }
```
8. coordinator inserts `DepositSubtree` into `AccountsTree`, thus updating its state
    > TODO: write `insertSubtree()` method in `Tree` class
9. coordinator removes the affected rows from `pendingDepositsTable`
    > TODO: find out if we can move up the remaining rows in the table? i'm not familiar with MySQL [YT]
11. coordinator gets `depositProof = getEmptyProof(subtreeHeight)`, a series of empty inner nodes leading from the subtree root position to the original `AccountsTree` root
    > TODO: write `getEmptyProof()` method in `Tree` class

    > TODO: define `emptyLeafNode` attribute in `Tree` class
12. coordinator calls `processDeposits(subtreePosition, subtreeProof)` on smart contract, which removes the `depositRoot` from the smart contract `depositQueue`, and emits a `DepositsProcessed(depositRoot)` event 
    > TODO: add `DepositsProcessed` event on smart contract

    > TODO: enable dynamic array size for hashing subtree proof on contract; currently only works for subtree of height 2 (see https://github.com/rollupnc/RollupNC/blob/master/contracts/RollupNC.sol#L146)

### transfer
0. user clicks "Transfer" in frontend and selects the account index they are sending from
    > TODO: API to display list of account indexes for each user's `pubkey`
1. user fills in `receiverPubkey`
    > TODO: figure out how users are supposed to discover each other's `pubkey` and `index`
        - or do we just assume they can coordinate that offline? 
        - we could provide a 'dummy' account for users who just want to try the demo
        
2. UI displays a list of accounts with given `receiverPubkey` (since one pubkey may have accounts at more than one index)  
    > TODO: display list of receiver account indexes given `receiverPubkey`
3. user selects a receiver account, UI takes note of the index of the selected receiver account
4. user fills in:
    - `senderPubkey` (pre-filled)
    - `senderIndex` (recall that one pubkey can map to many indices in the `AccountsTree`)
    - `receiverPubkey` (selected)
    - `amount`
    - `nonce`
    - `tokenType`
    
which is `POST`ed to backend, along with `receiverIndex` as metadata (i.e. `receiverIndex` is not hashed into the tx)

> TODO: display or pre-fill `nonce`, `tokenType` as soon as `senderIndex` is selected
    - `nonce` can be updated as soon as the `tx` is sent to the backend, i.e. before it is proven in a SNARK

> TODO: display balance as soon as `senderIndex` is selected; provide underflow warnings for excessive tx amounts

5. coordinator receives "Transfer" requests in the mempool
6. coordinator performs basic checks on each request:
    - sender exists
    - signed by sender
    - same `tokenType` of sender to receiver accounts
    > TODO: think about if we can check `nonce` and `balance` here.
        - to check `nonce` we have to order the transactions from smallest to largest `nonce`;  they should come in that order if using our frontend, but we should account for users calling our API directly
        - to check `balance` is harder, since another transaction may have credited or debited an account but not been processed yet
7. every `timeout`, coordinator grabs requests from the mempool. if no. of requests > `maxTxs`, grab `maxTxs`; else, grab all txs in mempool  
    - TODO: decide `timeout` and `maxTxs`. should be adjusted to SNARK proving time
8. coordinator removes requests from mempool
    > @VC, is this how the mempool works? i'm not sure [name=YT]
9. coordinator pads txs with empty transactions to get `txArray` of length `maxTxs`
    > TODO: write `getEmptyTx()` method which signs an empty transaction form the coordinator to itself (NB: coordinator's `nonce` increases each time `getEmptyTx()` is called)
10. coordinator hashes `txArray` to get `txTree` and adds `txTree` to `transactionsTable`
```javascript
    const txTree = new TxTree(txArray);
```
> TODO: figure out how to store `txTree`
11. check for `withdraw` transactions in `txArray`, and set their `status` to `2`; set all other normal txs to status `0`
12. coordinator processes `txTree`, in the process checking the transactions, updating the `accountsTable` and at the end returning `stateTransition` object

```javascript
    const stateTransition = accountTree.processTxArray(txTree);
```
> TODO: if receiver `pubkey` does not exist, insert a new leaf into `AccountsTree`

> TODO: adapt `rollupNC` scripts to update the leaf nodes and inner nodes of `AccountsTree` in `accountsTable` in the `processTxArray` step
    - this is already being done in memory in `rollupNC` (see https://github.com/rollupnc/RollupNC/blob/master/src/accountTree.js#L67)
    - we just have to adapt it for storage 

> TODO: do we want to store the `stateTransition` objects somewhere?

13. coordinator gets `circuitInputs` from `stateTransition` object 

```javascript
    const inputs = getCircuitInput(stateTransition);
```

14. coordinator passes `circuitInputs` to `calculateWitness()` and gets binary witness file `witnessBin` (see https://github.com/rollupnc/rollupnc_ui/blob/master/src/util/helpers/withdrawHelper.js#L54)
```javascript
   function calculateWitness(cirDef, inputs){
        circuit = new snarkjs.Circuit(cirDef);
        witness = circuit.calculateWitness(inputs);
        witnessBin = buildWitness.buildWitness(witness)
        return witnessBin
    }
```
15. coordinator passes `witnessBin` to websnark to generate `proof`
    > TODO: write some kind of backend browser to use websnark in this step? or figure out how to integrate it without browser (can ask Kobi/Jordi/Adria)
16. coordinator sends `proof` to `RollupNC.sol`; if it passes, a `UpdatedState` event is emitted
    > TODO: write security analysis for the case of unmined transaction or block reorg
17. coordinator updates `status` of included txs from `0` to `1` (for normal txs) and from `2` to `3` (for withdraw txs)

### withdraw

smart contract reference: `withdraw()` https://github.com/rollupnc/RollupNC/blob/master/contracts/RollupNC.sol#L157

0. user selects a "withdraw" transaction and enters the Ethereum adddress of `recipient`
    > TODO: provide API to GET "withdraw" transactions which have not yet been withdrawn for a certain public address 
    - note: one public address can have multiple account leaves in the `AccountsTree`
1. user clicks "Sign withdraw" on frontend, and EdDSA signs `hash(nonce, recipient)`
(implemented at https://github.com/rollupnc/rollupnc_ui/blob/master/src/components/Withdraw.vue#L204)
2. SNARK proof of EdDSA signature is generated in the browser using websnark (implemented at https://github.com/rollupnc/rollupnc_ui/blob/master/src/components/Withdraw.vue#L208)
2. user clicks 'Get Merkle proof' on frontend
1. coordinator serves Merkle proof for that transaction hash by looking it up in `transactionsTable`, using methods in https://github.com/rollupnc/RollupNC/blob/master/src/txTree.js
    > TODO: we likely have to change these methods depending on how we're storing the `TxTree`s in `transactionsTable`

```javascript
    getTxProofAndProofPos(tx){
        const txIdx = this.findTxIdx(tx.hash)
        const [proof, proofPos] = this.getProof(txIdx)
        return [proof, proofPos]
    }
```
5. browser composes an Ethereum `withdraw()` transaction and prompts user to sign it via Metamask

```javascript
withdraw(
    [pubkeyX, pubkeyY],
    [nonce, amount, tokenTypeFrom],
    [proofPos, proof],
    txRoot,
    recipient,
    proof.a,
    proof.b,
    proof.c
)
```
6. user calls `withdraw()` on `RollupNC.sol`; if it passes, a `Withdraw([pubkeyX, pubkeyY, index], recipient, txRoot, [nonce, amount, tokenType])` event is emitted
> TODO: check in `withdraw()` on smart contract that the withdraw() transaction has not been made before
7. poller listens for `Withdraw` events and updates `status` of withdraw tx from `2` to `3` in `transactionsTable`

## data types (for reference)

``` javascript
class Account {
    constructor(
        _index = 0, _pubkeyX = 0, _pubkeyY = 0, 
        _balance = 0, _nonce = 0, _tokenType  = 0,
        _prvKey = 0
    ) {
        this.index = _index; //index is not hashed in hashAccount
        this.pubkeyX = _pubkeyX;
        this.pubkeyY = _pubkeyY;
        this.balance = _balance;
        this.nonce = _nonce;
        this.tokenType = _tokenType;

        this.prvKey = _prvKey; //optional
        this.hash = this.hashAccount()
    }
}
```

``` javascript
class Transaction  {
    constructor(
          _fromX, _fromY, _fromIndex, 
          _toX, _toY, _toIndex, 
          _nonce, _amount, _tokenType, 
          _R8x, _R8y, _S
        ) {
          this.fromX = _fromX;
          this.fromY = _fromY;
          this.fromIndex = _fromIndex;
          this.toX = _toX;
          this.toY = _toY;
          this.toIndex = _toIndex; // toIndex is not hashed into the tx
          this.nonce = _nonce;
          this.amount = _amount
          this.tokenType = _tokenType;

          this.hash = this.hashTx();
      
          this.R8x = _R8x;
          this.R8y = _R8y;
          this.S = _S;
          
          // this.withdrawn?
          // this.ethRecipient?
    }
```

``` javascript
class Tree{
    constructor(
        _leafNodes
    ) {
        this.leafNodes = _leafNodes
        this.depth = treeHelper.getBase2Log(_leafNodes.length)
        this.innerNodes = this.treeFromLeafNodes()
        this.root = this.innerNodes[0][0]
    }
```

``` javascript
class AccountTree extends Tree{
    constructor(
        _accounts
    ){
        super(_accounts.map(x => x.hashAccount()))
        this.accounts = _accounts
    }
```

``` javascript
class TxTree extends Tree{
    constructor(
        _txs
    ){
        super(_txs.map(x => x.hashTx()))
        this.txs = _txs
    }
```


### Pictorial Representation 
https://drive.google.com/file/d/1LfLEX3lxwKeJayO4P5-sjk63rBNj2IyX/view