Restricted custody proof spec
==

## Status
This doc is very out of date.

## TODOs:
- [ ] how can we define this priority in batch settlement message??? Also, do we really need this? (See Batch settlement message section)
- [ ] Update with MVP & privacy funding
- [ ] If we would like to do order decoupling with UTXO, update this doc too
- [ ] Review the whole things again

## Overview
Funds are deposited to the venue. Venue collects orders from traders and executes them in batches. Each batch is a single price auction for all orders. All users funds are protected by "Restricted Custody" design where either venue of operator is honest, those funds are safe.

It would be running on a plasma chain that support M(ore)VP protocol, as where normal payment transactions would be running with MoreVP and DEX settlement transactions with MVP protocol.

Out of scope in this spec:
1. order anonymity. (But we keep in mind that the proof here should be zk-snark supportable in the future)
1. Whether the settlement price is reflecting the venue's matching algorithm correctly.
- We need more input to know what's the best algo.
- Also, it seems like to verify this means we need keep looping through all orders on the order book (not only the orders for the settlement), this is impratical to do it on ethereum for in-flight exit.
1. Continuos trading support

## Concepts

### Funding
An user can use a special funding transaction to provide funds to the exchange. The funding transaction would transfer a normal transaction output to a DEX specific output. In the DEX specific output, it would explicit the exchange and the real owner address. Thus, owner address would be the target address when doing exit. However, exchange address would be verified when doing trade settlement transaction.

There are some other possible ways to do the funding with less info leakage. However, as a DEX MVP, let's start with the simpliest solution. (For other funding designs, see: https://github.com/omisego/research/issues/71)

### Order Submission
An user can submit order after the funding is done. The order should specify a UTXO that the order is going to use. The UTXO must be an output of funding transaction, or the output of settlement transaction.

After user submit the order to exchange, exchange should provide a unique order id signed by the exchange. User would need such order id to cancel the order.

We support two types of orders at this moment: market order and limit order.

#### Market Order
Below is an example data needed for a market order:

{
    token_to_buy: [:token],
    amount_to_buy: [:amount],
    utxo_pos: [:pos],
    signature: [:sig],
}

#### Limit Order
Below is an example data needed for a limit order:

{
    token_to_buy: [:token],
    amount_to_buy: [:amount],
    price: [:price]
    utxo_pos: [:pos],
    signature: [:sig],
}

### Order Cancelation
An order can be canceled by the user to send a order cancelation message with order id to venue. Venue should sign the message and now the order should be considered canceled.

Since we want the cancelation to be "immediate", we are not introducing any protection from plasma chain. In other words, a possible attack here is that a dishonest exchange can still put your order into a settlement transaction even though such order is "canceled".

As a compensation, if an canceled order ever exists in a settlement tx, user can slash an exchange bond on root chain by disclosing the order cancelation message singed by venue and the proof of inclusion of the order in a settlement tx. As our exchanges are not anonymous, this means it become obvious the exchange if rogoue and people should stop using such exchange.

However, here still exists an attack where exchange does not accpept the cancelation on purpose. In this case, user should withdraw fund to force cancel an order. Since all orders are linked with UTXO, once withdrawn, it is promised that the order would not be executed. Keep in mind that withdrawal is not a immediate process, for the detail of time needed for withdrawal, please see the [withdrawals section](#Withdrawals).

### Batch Settlement
In this design, settlement is done in batch. Each batch would have its own "round number" that specifies which batch/round it is in. Also, it would have all the UTXOs for the matched orders and the outputs for the result.

The settlement output can keep the money "on exchange", which is, the output here can be like the output of funding transaction explicit both exchange and real owner address. So the output of a settlement transaction can be immediately re-used for next trade on next order without extra funding process.

We support partial-fill settlement by auto-generating an order for the remainings amounts of the order. Since the old UTXO of the order is used, the new partial-fill order would point to an output of the settlement transaciton output specially generated for the partial-fill.

The exchange would be submitting different data of batch settlement transaction to operator (in normal case) and Ethereum (when in-flight exit). This is because of the existence of Ethereum gas limit. To reduce gas, we submit compact proof of orders instead of full order data. Correctness of the order would be delegated to challenge games to pro

#### Venue to operator

##### List of fields
###### generic input
* round number
* traded pair
* list of utxo-order pairs:
* utxo
* blknum
* txindex
* oindex
* order
* signature
* token to buy
* amount to buy
* price: nil | number
* priority: timestamp
* fee
* list of settlements
* owner
* token
* amount
#### Venue to Ethereum (In-Flight Exit)
###### generic data
* list of merkle proof of utxos:
* deposit tx (single output)
* merkle proof
* predicate id: 1
###### predicate-specific data
* round number
* traded pair:
* token A
* token B
* merkle root of orders
* order structure as above
* match data, list of items sorted by price (tokenA/tokenB)
* input owner: address
* utxo

### Withdrawals
There are two path to do the withdrawals.

For happy case, trader should sign and submit the withdrawal request to venue, and then venue would sign the request and send it to operator.

However, in case of venue being rogue, we need another mechanism for the traders to do withdrawals directly on plasma chain without venue's involvement. This type of withdrawal is non-instant action: trader must first notify the venue and the operator and only after a "clearance" period the trader can actually post a transaction that reverses the deposit; provided that the deposit was not spent in any trade during the "clearance". This mechanism protects the exchange in case the withdrawn deposit takes part in a settlement which proof is being computed at the time of withdrawal.

We must introduce a special transaction type on plasma chain, which would serve as notification of withdrawal intention. In order to post a withdrawal transaction trader should include proof of having first notified the exchange.

### Fee
Since this is a batch transaction, we have the flexibility fo venue can add their own input to pay the OmiseGo network fee. Also, venue can add their own address into output of the transaction to collect fee. It is also possible to ask user use different UTXO to provide fee for venue.

However, a pratical fee pricing model would be highly dependent on each venue to design.

## Security Analysis
Whole design is under "Restricted Custody" security design. Funds are safe if operator or venue are honest.

### Attacks by a hacked venue (chain operator is honest)
1. Indirect heist via trade against market order, combined with censorship of the order book.
Solved by venue commiting to the state of order book before learning about it's contents.
3. Direct heist by transfer to hacker's address.
The venue operates in restricted custody mode, operator will not mine such transaction.
3. Direct heist by exiting money to Ethereum via standardExit.
Root chain contract would only allow DEX specified transactions to be exited to the "real owner" of the fund. Venue cannot steal money away through exit.
4. Indirect heist via trade based on non-existing orders. The venue fakes "sell this asset really cheap" order and puts itself as a counterparty.
The venue has to provide validity proofs for every batch settlement. Operator checks such settlement before including it into the chain.
5. Indirect heist via trade based on non-existing orders, exited via standardExit on Ethereum.
Venue can't use standardExit in this situation, since it requires inclusion proof and operator will not provide such.
6. Indirect heist via trade based on non-existing orders, exited via inFlightExit on Ethereum.
The InFlightExit would be challenged to ask to prove correctness of the order. As it is impossible to prove a non-existing order correct, the IFE would be successfully challenged. To get the fund back, user can send withdrawal transaction to operator.
7. Censorship of orders: Remains research: https://github.com/omisego/research/issues/81
8. Frontrunning: Remains research, some ideas here: [Frontrunning Ideas doc](https://omisego.atlassian.net/wiki/spaces/RES/pages/37552167/Front+Running+Protection+Ideas?atlOrigin=eyJpIjoiOWMyOTY4NDY3MjY3NDRhNTg4MDJmZDU0NTJhNTIyOTkiLCJwIjoiYyJ9)
### Attacks by dishonest user
1. Double-spend via simultaneus withdrawal and trade.
Assuming later usage of zkSNARKs by venues, usual "first to be mined invalidates later ones" is troublesome for the venue, since venue would have to throw away generated proofs. Such design would create a griefing attack.

So instead, we introduce a pair of messages sent by trader. First one is - "notifyAboutWithdrawal" and the second one is "withdrawal". Both should point to the same utxo and validity of "withdrawal" is conditioned on "notifyAboutWithdrawal" being included into chain at least N blocks ago.
2. Double-spend via exit from deposit transaction and trade on plasma chain.
Venue can challege the exit or piggyback by disclosing the next settlement transaction using the output.
### Attacks by operator
1. Operator produces a block that steals funds and withholds it.
* In-flight trade settlements: full tx info is delivered to every trader on every batch. The venue exits to Ethereum, traders have full visibility and do not need to challenge.
* In-flight deposits: in-flight exit with piggyback on output doable by deposit owner.
* In-flight withdrawals: This should not happen unless the security assumption of at least one of venue and operator is honest breaks. Venue would help traders exit the trade settlement when operator is fraud. And when venue is fraud, traders should get the fund back by withdraw properly with honest operator.

## Performance limitations
### possible amount of trade settlements per pair per Ethereum block
MoreVP forbids to spend utxo that was not yet confirmed (submitBlock on Ethereum and verification by watcher are required).
There is a dependency problem with settlements (https://github.com/omisego/docs/issues/22).
Lets assume that every submitBlock mines in next Ethereum block (propagation speed is infinite, gas price is infinite).
Probability that market will move in opposite direction than last time and change output will not be consumed (no dependency) is 0.5.
This gives us average trades per block at 2 (estimated value of length of sequence of coin tosses that are terminated with first tails).
### limits on the size of single trade settlement
Single trade settlement may become in-flight transaction. Thus, we need to make it processable as tx on Ethereum. We can hide order signatures and some other data and have a challenge-reveal game around that worsening time constraints of MoreVP. We still need to merkle proof every input. [Estimation](https://docs.google.com/spreadsheets/d/1TLuCvsSn5-8XhRgTaU_iU7Xhc0h4tq3VErbbcr1FMCs/edit?usp=sharing) of gas cost of such proof puts upper bound on number of orders taking part in single trade settlement at 340.

2 * 340 = **780 orders per trading pair per Ethereum block** is our very raw upper bound.

## Spec
The followings provide the sample of how can a possible transaction looks like, and what is the essential feilds or informations in the transactions. The implementation does not need to be exactly the same as this.

The following sample/example assumes we adapt the [abstraction layer design](https://omisego.atlassian.net/wiki/spaces/RES/pages/35520517/UTXO+Based+Plasma+Abstract+Layer+Design?atlOrigin=eyJpIjoiOWMyOTY4NDY3MjY3NDRhNTg4MDJmZDU0NTJhNTIyOTkiLCJwIjoiYyJ9) where we have the ability and flexibility to define our own transaction and output type for DEX.

### Transaction output type
1. Normal tx output: an output of normal payment UTXO transaction.
2. ODEX output: a special output type used in our DEX batch settlement tx. We use `ODEX_OUTPUT` to represent this in the following data sample.
3. Partial-fill output: a special output type used for partial fill, it should be bind with another order generated by venue. We use `PARTIAL_FILL_OUTPUT` to represent this in the following data sample.

#### Predicates for normal output to be used in funding tx
1. Checks the signature of the owner of normal output

#### Predicates for ODEX output to be used in Batch Settlement tx
1. Checks the signature of exchange

#### Predicates for ODEX output to be used in Withdrawal tx
1. Checks the inclusion proof of withdrawal notification
2. Checks the [validity of withdrawal notification](#Correctness-of-Withdrawal-notification-tx)

### Transaction Definition

#### Funding Tx
Below is an example transaction for user to put fund to exchange.

{
    inputs: [{utxo_pos}, {utxo_pos}...],
    outputs: [{
        type: "ODEX_OUTPUT",
        data: {
            amount: xxx,
            token: xxx,
            exchange_address: xxx,
            owner: xxx,
        }
    }, ...]
    proofData: {
        signatures: [], // signatures for the inputs
    }
}

##### Correctness of Funding Tx
1. inputs are using output of normal tx output type
1. output are of special type for ODEX
1. sum of inputs >= sum of outputs
1. have signatures of owners of input (checks by output predicate)

#### Batch Settlement Tx

{
    inputs: [{utxo_pos}, {utxo_pos},...],
    outputs: [{
        type: "ODEX_OUTPUT",
        data: {
            amount: xxx,
            token: xxx,
            exchange_address: xxx,
            owner: xxx,
        }
    },{
        type: "PARTIAL_FILL_OUTPUT",
        data: {
            amount: xxx,
            token: xxx,
            exchange_address: xxx,
            owner: xxx,
        }
    }],
    proofData: {
        settlement_price: {
            token1: xxx,
            token2: xxx,
            raito: xxx,
        },
        round_number: xxx,
        exchange_signature: xxx,
        settled_orders: [{
            order_data: {
                signature: [:user signature]
                utxo_pos: xxx,
                token: xxx,
                amount: xxx,
                price: number
                priority: timestamp,
                fee: xxx,
            },
            settle_to_output: [:output_id],
            partial_fill_generated_order: nil | {
                utxo_pos: xxx, // point to the PARTIAL_FILL_OUTPUT
                token: xxx,
                amount: xxx,
                price: number,
                priority: timestamp
                fee: xxx,
                signature: [:exchange_signature] // partial fill order is signed by exchange instead of owner!
            }
        },...],
    }
}

##### Correctness of Batch settlement tx
1. inputs are using output with special ODEX type
2. whole tx signed by exchange (checks by predicate)
3. `utxo_pos` from all orders are used as input. No mismatch.
4. order has the correct signature singing the order from `utxo_pos` owner.
5. data of input is valid for the order and fit the settlement price.
6. data of output is valid for the order and fit the settlement price. (for partial fill, need to consider both remaining output + settled output.)
7. for the partial filled order, there would be a order signed by exchange for the remaining round.
8. all outputs are of special type for ODEX
9. sum of inputs >= sum of outputs

#### Withdrawal Tx

{
    inputs: [{utxo_pos}, {utxo_pos},...],
    outputs: [{
        type: "NORMAL_OUTPUT",
        data: {
            amount: xxx,
            token: xxx,
            owner: xxx,
        }
    }],
    proofData: {
        signature: xxx, // can be user or exchange
        notification_txs: [{
            utxo_pos: xxx,
            inclusion_proof: xxx,
        }, ...]
    }
}

##### Correctness of Withdraw tx
1. all inputs are of same owner.
2. output is type of normal output.
3. output information is correct.
4. signed by either user or exchange. (It's fine to be signed by exchange because there is withdraw notification tx with user signature already)
5. all the input must have valid withdraw notification accordingly (checks by predicate)
6. sum of inputs >= sum of outputs
#### Withdrawal Notification Tx
This is the tx to show the will of a user wants to withdraw. Withdraw can be valid after certain blocks of this notification tx.

{
    inputs: [],
    outputs: [],
    proofData: {
        utxo_pos: xxx,
        message: "I want to withdraw!",
        signature: [:signature of owner of utxo_pos],
    }
}

##### Correctness of Withdrawal notification tx
1. inputs and outputs are empty
2. should have the correct signature of the owner of utxo_pos want to withdraw from.
3. utxo_pos must point to a ODEX special type output.

### Challenge Games

#### Batch settlement Tx
Same as basic MoreVp, we have two types of exit: standard exit and in-flight exit. However, for IFE to be exitable, it has to be "format-wise" correct. It was easy to verify before as it only needs to check signature + sum of input >= sum of output. But for batch settlement, it needs to check all the correctness of orders and it would be impratical. To reduce gas, we delegate the proof of "tx format-wise correctness" to challenge games instead of running verification whenever IFE starts.

##### Standard Exit (SE) Game
1. start standard exit for a tx output
1. challenge output already spent. Can possibly be spent by the following txs:
- Another batch trade tx with exchange signature.
- Withdraw tx. Need to check signature + notification of the withdraw tx.
##### In-Flight Exit (IFE) Game - MoreVp canonicality
1. Submit in-flight exit.
1. Challenge non canonical:
- disclose the competing tx.
- proof at least one tx ouput is used in both IFE tx and competing tx (use predicate to prove the usage valid). It can possibly be the following txs:
- Another batch trade tx
- Withdrawal tx
1. Respond:
- prove that the IFE tx is included in a block that is older than competing tx.

##### In-Flight Exit (IFE) Game - Tx format correctness
1. Submit in-flight exit
1. Challenge tx format not correct: Challenger can pick one rule to challenge **without the need to run the verification**. It is responder's responsibility to provide the essential data to verify. For rules to claim tx correctness, see the above section: [Correctness of Batch settlement tx](#Correctness-of-Batch-settlement-tx).
1. Respond with the proof data according to the challenged rule and run the verification.

##### In-Flight Exit (IFE) Game - Piggyback
1. Submit in-flight exit
1. Starts piggyback
1. Challenge piggyback used. It can be used in the following txs:
- Another batch trade tx
- Withdrawal tx

#### Funding Tx
##### Standard Exit (SE) Game
1. start standard exit for a tx output
2. challenge output already spent. Can possibly be spent by the following txs:
- Another batch trade tx.
- Withdraw tx.

##### In-Flight Exit (IFE) Game - MoreVp canonicality
1. Submit in-flight exit. Verify tx correctness while submission. (see [Correctness of Funding Tx](#Correctness-of-Funding-Tx))
2. Challenge non canonical (Same as normal tx)
3. Respond (same as normal tx)

##### In-Flight Exit (IFE) Game - Piggyback
1. Submit in-flight exit. Verify tx correctness while submission. (see [Correctness of Funding Tx](#Correctness-of-Funding-Tx))
1. Starts piggyback
1. Challenge piggyback used by predicate.

#### Withdrawal Tx
##### Standard Exit (SE) Game
1. start standard exit for a tx output
2. challenge output already spent.

##### In-Flight Exit (IFE) Game - MoreVp canonicality
1. Submit in-flight exit. Verify tx correctness while submission. (see [Correctness of Withdrawal Tx](#Correctness-of-Withdraw-tx))
2. Challenge non canonical:
- disclose the competing tx.
- proof at least one tx ouput is used in both IFE tx and competing tx. It can possibly be the following txs:
- batch settlement tx with exchange signature.
- Withdraw tx. Need to check signature + notification of the withdraw tx. (Don't ask me why an user would want to withdraw twice in-flight.....)
4. Respond:
- prove that the IFE tx is included in a block that is older than competing tx.

##### In-Flight Exit (IFE) Game - Piggyback
1. Submit in-flight exit. Verify tx correctness while submission. (see [Correctness of Withdrawal Tx](#Correctness-of-Withdraw-tx))
1. Starts piggyback
1. Challenge piggyback used.

## FAQ

1. For the withdrawal clearance period, is it secure enough to wait N childchain block and not N ethereum block?
- Yes. When operator is dishonest, then venue should do the in-flight exist for the trader and would not involve withdrawal. If both venue and operator are dishonest, then it exceeds restricted custody protection.

1. Do we support partial fill limit order? **Yes.**
1. Do we support partial fill market order?
- Is this really a thing? We should limit ourselves to fill-or-kill, all-or-none and immediate-or-cancel execution for market orders.
1. What is our front-running protection for single price auction?
- For a single price auction, it is by default without such issue. See more analysis [here](https://github.com/omisego/research/issues/77)