[Feature] Decentralized Dispute Resolution Mechanism

[fleupold]

The purpose of this issue is to track different ways with which we can resolve disputes about the correctness of a state transition or auction settlements.

The main aspects of a solution are:

• order hash - rolling hash of all orders that were considered in this solution
• price vector - each value denotes the price of token_i to some arbitrary reference - e.g. $
• volumes - list of buy and sell volumes for each order that is part of order hash
• surplus - the trader surplus that is generated with this solution
• newAccountRootHash - hash of all account balances after solution as been applied
• new starting order hash - Depending on #85, a new batch might start with some orders carried over from the previous batch.

Since deposit and withdrawals only contain state transitions they can be seen as a sub-problem of auction settlement and thus a suitable dispute resolution method for the latter should work for them as well.

The main points of a solution that can be challenged are:

• State Transition - balances under newAccountRootHash are not updated according to trading volumes)
• Negative Account Balance - after applying the trades some accounts end up with negative balance. This is temporary possible (e.g. if a sell order gets processed, before the balance is filled with a later buy order), but should not be true at the end of an auction settlement.
• Price Coherence - the ratio of buy and sell volume doesn't match the ratio of price of token A to price of token B in the price vector. This would mean an order is not filled at the uniform clearing price.
• Limit Price Respected - the ratio of executed buy and sell volume is at least as large as buy and sell amount specified as a limit in the original order.
• Surplus - The surplus actually generated by the solution is not the one claimed at submission time
• Conservation of Value The sum of total buy and sell volume for a given token is not 0 (tokens are not burned or minted out of nowhere)
• Order Hash The computation of the order hash (according to #85 and #86) on which this solution is based (or the starting order hash for the next batch) the is incorrect.

Each challenge can be done independent of one another and one successful challenge is enough to render a solution invalid.

The different resolution ways to implement resolution can be discussed below.

[fleupold]

On Chain Solidity Resolution

One option for dispute resolution would be to write the verification logic in solidity and deploy a smart contract that can verify each constraint on demand. A challenger would provide part of the proposed solution data as transaction calldata and choose the aspect of the solution they are challenging. In case the solution is successful the challenger receives a significant reward (taken from the solution proposer's bond)

The general logic for the different challenges could be as follows:

• State Transition
  • Provide orders, volumes, merklePaths for each account leaf as call data
  • Verify hashed order calldata matches committed order hash of solution
  • Verify hashed volume calldata matches committed volume hash of solution
  • For each volume:
  • Find the account + buy and sell token balance of the order belonging to this volume
  • verify merkle path of buy token balance to current state root
  • add buy volume to buy token balance
  • recompute state root with updated buy token leaf
  • do the same for sell token balance (but subtract sell volume)
  • Check that resulting hash is equal to newAccountRootHash of the solution.
• Negative Account Balance
  • Provide merkle proof to account balance including it's value as calldata
  • verify merkle proof results in newAccountRootHash of the solution
  • check value < 0
• Prices Coherence
  • Provide volumes, prices and orders as well as index of order that is bad as calldata
  • Verify order/volume/price calldata hash matches solution's order/volume/price hash
  • Check at index if buyVolume/sellVolume ≠ price(buyToken)/price(sellToken)
• Limit price & amount compliance
  • Provide volumes, prices and orders as well as index of order that is bad as calldata
  • Verify order/volume/price hash matches committed order/volume/price hash
  • Check at index if buyVolume/sellVolume >= order.buyAmount/order.sellAmount
  • Check at index if buyVolume >= order.buyAmount && sellVolume <= order.sellAmount
• Surplus
  • Provide volumes, prices and orders as calldata
  • Verify order/volume/price calldata hash matches solution's order/volume/price hash
  • totalSurplus = 0
  • For each order
  • totalSurplus += surplus(order)
  • check that calculated surplus matches surplus on solution
• Conservation of value
  • Provide volumes and orders as well as index of token that does not conserve value as calldata
  • Verify order/volume calldata hash matches solution's order/volume hash
  • start with balance = 0
  • For each volume
  • if volume touches order for bad token adjust balance (depending on sell or buy side)
  • check balance == 0
• Order Hash
  • Provide orders that were part of individual order hashes store on the smart contract (open slots, reserved slots, cancellations) as calldata
  • verify hashes of orders in calldata matches the hashes in smart contract
  • For each cancelled order:
  • If submitted by original order author, override order with 0s
  • hash all orders together to final hash
  • check if final hash is equal to hash submitted in solution

Some of the checks (in particular the state transition and surplus calculation) have to be split up in multiple batches in order to fit in the block gas limit. The intermediate results could either be stored on the smart contract (and would thus require multiple txs to be mined before a decision about validity can be made) or could be committed to by the solution provider when publishing a solution. The latter would allow challenging a specific batch transition in a single transaction and thus simplify the challenging mechanism.

However, we have to keep in mind that extra data sent with the solution will have to be provided in every auction (and thus increase gas costs even in the happy case) whereas data sent with challenges will only cost gas when there is a dispute (which proper economic incentives should mitigate in the first place)

Discussion

The advantages of this approach are that a challenge can be done immediately (no interactive game with the original solution provider is needed) and that its logic can be written in solidity, which is much simpler to maintain and audit than e.g. zero knowledge options. This would likely make it much simpler to bring such a feature to market.

On the other hand this kind of challenge mechanism doesn't scale very well. While we are likely able to implement all challenges for 2**24 accounts with 32 tokens and 1000 orders per batch within the block gas limit, it is unlikely that we can scale to 10 or 100 thousand orders.

Yet, it might be a good first approach to implement while the ecosystem for using zk proofs in production is still maturing.

Gas Analysis

The on_chain_verifier branch contains a rough sketch of the solidity code for each challenge and was used to collect the following gas estimations for each challenge. All prices are estimated with 20 GWEI and ETH @ $169. We are proving 2**24 accounts with 32 tokens and 1000 orders per batch, assuming that trading amounts can be represented with 32 bit wide fixed point numbers.

• challengeStateTransition: 5.3M gas ($17.91) *
• challengeNegativeBalance 0.1M gas ($0.48)
• challengeLimitPrice: 3.3M gas ($11.10)
• challengeOrderHash 5.2M gas ($17.51)
• challengePriceNonUniform 3.3M gas ($11.10)
• challengeSurplus 5.8M gas ($19.80) **
• challengeValueConservation 6.4M gas ($21.57)

* We split up the potentially 1000 state transitions into 200 batches of 5. This cost is per batch. Only one batch is needed to complete the challenge. This increases the amount of data that needs to be provided with each solution by ~500k gas ($1.60) ** We split up the surplus calculation into two batches covering 500 orders each. This cost is per batch. In our implementation both batches are needed to complete the challenge.

[fleupold]

Succinct Zero Knowledge Proofs

Instead of having an on-chain solidity verifier, the challenge logic could also be implemented in an arithmetic circuit and be proven with a succinct fraud proof (e.g. zkSnark/Stark etc). The smart contract would then only verify the validity of such a fraud proof and if valid render the submitted solution as invalid.

The zero knowledge aspect of such a proof would not be used for privacy but rather scalability. All uncompressed data (orders, volumes, prices, etc.) which has to be provided as calldata in the on-chain solidity verifier could be passed into the snark as private input and would therefore not incur any gas cost on-chain. Inside the snark, we would also prove that the private input hashes to the public commitments (which were submitted as part of the solution). Those are already stored in the smart contract and would be the public inputs to the proof:

Public inputs:

• surplus
• order/price/volume hash
• previous state root
• final state root

Private Inputs

• All orders/prices/volumes
• Balances that make previous state root

The logic for each challenge snark would be roughly the same as for the on-chain solidity version.

Discussion

The gas cost for each challenge would be constant (or logarithmic) to the problem size and thus significantly lower than for the on-chain verifier (~1M gas + 100k gas per public input). However, these proofs are only needed in the "bad case" where a significant amount of money in the form of bonds is already at risk. Therefore, gas efficiency is not the top priority as long as submitting such a challenge is possible at all within the gas limit.

An advantage of this gas efficiency however is, that we could easily scale the amount of orders or tokens that are supported in a batch and still validate the proof on-chain. This would give us a long term solution for supporting tens or hundreds of thousands of orders.

At the moment however we are limited to zkSnarks on the alt_bn128 curve and thus to a constraint system with 268 million constraints. We have not yet done a fully optimized constraint analysis of our challenge logic, but assume that we could "only" scale up to 10k accounts, 1k orders, 32 tokens. In particular the number of accounts is very small compared to the other approaches.

For Starks, proof sizes are still a problem as unlike for snarks they are not constant in size and can easily be larger than the calldata we would need to submit in the on-chain solidity. It is possible that in an upcoming hardfork the cost of calldata is reduced in order to facilitate the usage of starks. It is also possible that other elliptic curves, which would allow up to 4 billion constraints or even allow recursive snarks (leading to infinite scalability with respect to on-chain gas cost) could be added to the EVM.

A major drawback of zkSnarks in particular is the trusted setup, which is a complex multi-party computation that has not yet been successfully executed in the context of Ethereum. Even if a universal trusted setup for all possible constraint systems (e.g. SONIC) was to be created, getting a zero knowledge proof circuit into a production ready state (implementation, audits, formal verification) has yet to be proven.

We therefore expect this approach to take much longer to implement than the ones that rely on solidity.

This fact combined with the rapid development in the space and the uncertainty which technology will prevail (Snarks, Starks, Sharks, etc.) suggest we should pursue this approach once scaling is actually needed.

[fleupold]

True Bit Resolution

Truebit is a scalable verification system for blockchains. Instead of running the entirety of the challenged computation on-chain, the challenger and responder play an interactive game which resembles a binary search over all intermediate computations steps.

The challenger asks the responder for the state of their computation (or a concise commitment to it) at half of the computation steps. Upon response the challenger can now compare if this state matches the one they believe is the correct half point state. In case the state is correct, they know that the "wrong computation step" has to have happened in the second half of the computation. They therefore request the computation state at 3/4th of the steps. Otherwise they know that the wrong computation has happened in the first half and ask for the computation state at 1/4th of the steps.

This is repeated until the incorrect step has been identified (taking log(all_steps) iterations). The disputed computation step can then be verified by the smart contract and will cost only a fraction of gas the overall computation cost.

If at any point in time a party becomes irresponsive for longer than a threshold they are assumed to have lost the game.

This approach could be used to implement the challenge logic presented in the on-chain resolution approach and make it much more gas efficient and scale to problems of infinite size (since each step is still constant).

Discussion

The big downside of an interactive game like this is that it can potentially take a long time until the smart contract has achieved consensus and thus finality over which solution is correct. It requires both the solution provider as well as the challenger to stay online for potentially a long time and interact regularly. Correct selection for timeouts that balance between timely resolution but protect players from DOS attacks is a challenging subtask.

The time to resolution scales logarithmic with the computation steps and thus increases as the problem size scales up.

In general, this approach has undesirable UX implications (requirement to stay online) and makes it harder to reason about the finality of a state. It also imposes a larger attack surface for e.g. DOS attacks against one of the party playing (since repeated interaction is required).

We therefore see Truebit as a last resort and would prefer one of the other solutions.