truebitfoundation/dispute-resolution-layer

[DEPRECATED] Generic dispute resolution layer for Truebit verification games

dispute-resolution-layer's Issues

Test performStepVerification on lowest steps (0 - 1)

Create test where it tests the steps 0 and 1, and then calls performStepVerification

Develop client + tests for verification game

The client needs to be able to be used as a module by other client software (think big picture Truebit client).

Simply JS code that interacts with the deployed VerificationGame contracts + tests

Contracts don't implement interfaces :(

BasicVerificationGame should implement IDisputeResolutionLayer explicitly
SimpleAdderVM should implement IComputationLayer explicitly

Batch query/response

@mrsmkl had the suggestion to do
Add methods to do batch queries responses

function query(bytes32 gameId, uint[] steps)
function respond(bytes32 gameId, uint[] steps, bytes32[] hashes)

Then a mini verification game takes place here

[WIP] Dispute Resolution Interface Spec

Summary - Standard for interfacing with Truebit Verification Games.

Rationale - Truebit will serve as critical infrastructure for a wide variety of dapps. Internally in Truebit we are already seeing different ideas and implementations being developed. At the core of these services is the verification game. We currently have two implementations of verification games that don't use a common interface. Defining a standard interface for verification games will make it easier to test, upgrade, and develop these different Truebit implementations.

Core Functionality -

1. Create a new verification game session
2. Ask solver for computation state at step n
3. Respond to verifier with computation state at step n
4. Trigger a timeout if either the verifier or solver does not make their turn in time
5. Perform final verification by computing one step onchain

Initial Spec -

newGame(uint task_id, address solver, address challenger, bytes input, bytes32 outputHash, uint numSteps) returns(uint game_id)

query(uint game_id, uint stepNumber)

respond(uint game_id, bytes32 hash)

timeout(uint game_id)

performFinalVerification(uint sessionId, uint claimId, bytes preValue, bytes postValue, bytes proof)

Rationale for name performFinalVerification:

• perform is an action
• final as in the final step to be run onchain
• verification, using the merkle proof to verify the results of the computation

Current Verification Game Implementations -
scrypt-interactive: https://github.com/TrueBitFoundation/scrypt-interactive/blob/master/contracts/Verifier.sol
webasm-solidity: https://github.com/TrueBitFoundation/webasm-solidity/blob/master/contracts/interactive2.sol

The above specification works cleanly with the scrypt-interactive repo mostly because that was inspiration for the spec. webasm-solidity could mostly work with some name changes. The biggest challenge with integrating is with the respond (postPhases) portion. As it passes an array of 13 32 byte values, instead of a single bytes32. However, it is not impossible to integrate with the above spec:

• Values of array could be stored on chain before respond is called
• Only pass the hash of the 13 values of proofs
• Interface is used as a base class with users overloading the respond method

TODO:
PR with tests and example of interface

Fix awkward double query at finalStep

See basic_verification_game.js query to highStep for an example of this. Solution would be to able to run the test without using the second query.

The issue is because performStepVerification needs lowStep + 1 == highStep. If one doesn't query again, then lowStep doesn't get set.

highStep, lowStep get changed by query/response.

So the fix will belong in the logic in the query method

Client Block Reorg tolerance

The client needs to be able to gracefully handle a block reorg

Solutions delay client by a couple blocks (blockstream)

Move Ordered Merkle Tree to Open Zeppelin

Right now it uses a linked list approach, need a more complex data structure for better performance

Test performStepVerification on intermediate steps

Do test case where game ends on some step between (initialStep+1..finalStep-1)

Dynamic Byte array for IComputationLayer

Right now computation layer specifies a 3 element array, this should be changed to a dynamic array. However, these are new Solidity features

ethereum/solidity#3270

Define dispute resolution layer interface

The goal of this is to have a formal standard that can interop with as many Truebit use cases as possible

Example use cases:

• Generic Truebit (WASM)
• scrypt-interactive
• proof of steak (less strict verification games)

Client Caching Solution + Shutdown Tolerance

Client needs a caching solution that can also be used to quickly restart a client after a shutdown

State channels (Timeout Fraud Problem)

The query/response mechanism seems like a good place for the use of state channels. However, the current issue is the data availability problem around the timeout mechanism.

Ex: Using a state channel verifier makes a query, solver sends a response. Verifier claims solver never sent a response within the time frame (5 blocks). Solver has chance to prove they are indeed still playing. This fraud proof mechanism happens on-chain. Incentives dictate verifier pulls this trick every single query/response round because they want to see the solver lose. Then each round ends up being on-chain anyways.

Summary - In order to use state channels for query/response need to solve timeout fraud problem.

Research efficiency of different merkle trees

There are multiple ways to merklize a list of bytes, the branches can use different patterns. These patterns have different characteristics.

The most important characteristic is the length of the proof (basically search properties). We need to be able to always submit short proofs (Olog(n))

Setup Travis

Need to setup travis so I stop pushing buggy code

Fix performStepVerification

The test in basic_verification_game.js where it calls performStepVerification fails because the postState is not merklizing properly.

Implement SimpleHasherVM

Simple substitute the addition operation with keccak256.

This could be useful for verifying arbitrary merkle root computations