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:

order anonymity. (But we keep in mind that the proof here should be zk-snark supportable in the future)
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.
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.

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)

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.
Direct heist by transfer to hacker's address.
The venue operates in restricted custody mode, operator will not mine such transaction.
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.
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.
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.
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.
Censorship of orders: Remains research: https://github.com/omisego/research/issues/81
Frontrunning: Remains research, some ideas here: Frontrunning Ideas doc

Attacks by dishonest user

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

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 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 where we have the ability and flexibility to define our own transaction and output type for DEX.

Transaction output type

Normal tx output: an output of normal payment UTXO transaction.
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.
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

Checks the signature of the owner of normal output

Predicates for ODEX output to be used in Batch Settlement tx

Checks the signature of exchange

Predicates for ODEX output to be used in Withdrawal tx

Checks the inclusion proof of withdrawal notification
Checks the validity of withdrawal notification

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

inputs are using output of normal tx output type
output are of special type for ODEX
sum of inputs >= sum of outputs
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

inputs are using output with special ODEX type
whole tx signed by exchange (checks by predicate)
utxo_pos from all orders are used as input. No mismatch.
order has the correct signature singing the order from utxo_pos owner.
data of input is valid for the order and fit the settlement price.
data of output is valid for the order and fit the settlement price. (for partial fill, need to consider both remaining output + settled output.)
for the partial filled order, there would be a order signed by exchange for the remaining round.
all outputs are of special type for ODEX
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

all inputs are of same owner.
output is type of normal output.
output information is correct.
signed by either user or exchange. (It's fine to be signed by exchange because there is withdraw notification tx with user signature already)
all the input must have valid withdraw notification accordingly (checks by predicate)
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

inputs and outputs are empty
should have the correct signature of the owner of utxo_pos want to withdraw from.
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

start standard exit for a tx output
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

Submit in-flight exit.
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
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

Submit in-flight exit
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.
Respond with the proof data according to the challenged rule and run the verification.

In-Flight Exit (IFE) Game - Piggyback

Submit in-flight exit
Starts piggyback
Challenge piggyback used. It can be used in the following txs:
- Another batch trade tx
- Withdrawal tx

Funding Tx

Standard Exit (SE) Game

start standard exit for a tx output
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

Submit in-flight exit. Verify tx correctness while submission. (see Correctness of Funding Tx)
Challenge non canonical (Same as normal tx)
Respond (same as normal tx)

In-Flight Exit (IFE) Game - Piggyback

Submit in-flight exit. Verify tx correctness while submission. (see Correctness of Funding Tx)
Starts piggyback
Challenge piggyback used by predicate.

Withdrawal Tx

Standard Exit (SE) Game

start standard exit for a tx output
challenge output already spent.

In-Flight Exit (IFE) Game - MoreVp canonicality

Submit in-flight exit. Verify tx correctness while submission. (see Correctness of Withdrawal Tx)
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…)
Respond:
- prove that the IFE tx is included in a block that is older than competing tx.

In-Flight Exit (IFE) Game - Piggyback

Submit in-flight exit. Verify tx correctness while submission. (see Correctness of Withdrawal Tx)
Starts piggyback
Challenge piggyback used.

FAQ

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.
Do we support partial fill limit order? Yes.
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.
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

boolafish

2019/04/16 05:46:55

Curious, does operator must handle settlement tx in the order of "round number"? or it is fine? (Edited)

2019/04/16 05:47:17

price: nil | number Is "nil" for market order? (Edited)

2019/04/16 05:49:42

If we want to be explicit, I think we can use "settlement rate" here instead. settlement rate: (tokenA, tokenB, ratio) (Edited)

2019/04/16 05:57:20

In general, I think it would be nice if we have info of order <> output. This can be helpful if a trader has multiple orders (perhaps with slightly different price) and be settled in same round. Without that data, we need to identify the output via address, then we limit the possible usage of this settlement (Edited)

Piotr Żelazko

2019/04/16 23:13:25

Do we really have to post another transaction that would be the withdrawal? Can't the "notification" be treated as frozen UTXO until "clearance" period passes or a trade appears? (Edited)

2019/04/18 06:43:39

BTW, can user start exit with the output directly? Case 1: only venue can start the exit. Now, though a bad venue cannot steal money, but can lock all the users' money. Case2: If user can start exit themselves, this has the same issue as withdraw here. What do we do? (Edited)

2019/04/18 06:54:51

> Direct heist by exiting money to Ethereum via standardExit. Instead of challenge it, we can make such type of output always exit to the user instead of exchange. (Edited)

2019/04/18 06:58:04

> in-flight withdraw. Both input and output are of owner of the real user. Not matter what wins, it's sort of promised to withdraw to the real user. (Edited)