# 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

    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

    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

    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)

    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

    txRoot(string,unique,indexable,PrimaryKey),
    toIndexArray (JSON array),
    txHashArray (JSON array),
    proof (JSON object)

what's contained in the proof:

    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)

    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

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

    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)

    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:

    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`

    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

    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

    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)

   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`

    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

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)

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()
    }
}

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?
    }

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

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

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