TrueBit

A verification and storage solution for blockchains

Jason Teutsch
University of Alabama-Birmingham

Loi Luu
National University of Singapore

Christian Reitwiessner
Ethereum

Supported by Wanxiang Blockchain Labs

Problem: the blockchain bottleneck

Ethereum’s incentive structure severely restricts the amount of computation work that smart contracts can accurately enforce. Each miner must not only verify but remember the state of every single smart contract on the blockchain. These redundant demands not only waste network resources but also limit the scope of potential smart contract applications. While honest Ethereum miners must verify every smart contract, only the miner who adds a new block containing the given smart contract receives compensation for their verification efforts. Smart contracts whose verifications require non-trivial computational efforts will fail to execute correctly as rational miners, who may choose to deviate from the suggested protocol, stop donating their limited resources to thankless verification tasks. In short, Ethereum lacks a verification mechanism.

Solution: the verification game

We propose to build a system which correctly enforces computationally-intensive smart contracts. Its core will consist of a user-friendly contract interface where a user can request a solution to a computational task or puzzle, and anyone can solve it in exchange for a reward. When a challenging party detects an incorrect solver submission, the smart contract initiates an interactive verification game between the solver and challenger. At the end of this game, either the cheating solver will be discovered and punished, or the challenger will pay for the resources consumed by the false alarm. The system functions correctly with minimal resources: only one honest challenger has to verify each solution.

The entire Ethereum community rules on whether a given challenge is justified. It performs only a trivial checking task which enforces that both parties follow the rules of the verification game. In this way, the primary computational burden moves off-chain while expensive smart contracts handle the light work of enforcing protocol rules.

Our verification game protocol will empower users to both outsource arbitrary computations in a decentralized manner and receive back correct solutions. For computational puzzles that are solvable in time n^t , where ε>0, we aim to devise a probabilistic verification game protocol that requires at most t/ε rounds of interaction, writes O(n^ε) bits on the blockchain each round, and needs only poly log n time for community-wide verification.

Finally, one can view our protocol as a decompression tool. Suppose you wanted to write a smart contract which requires access to Ethereum’s proof-of-work. Rather than storing the entire 16 MB proof-of-work cache on the blockchain, which would be expensive, you could instead store on the blockchain a small generating seed for the cache. The verification game would then enable the smart contract to efficiently verify bits of the cache. In general, one could perform arbitrary computations on data that is stored in an authenticated way (like in swarm or ipfs) without having to store the data itself on the blockchain. Only the computing and verifying nodes need to have access to the full data.

Show your support

Clapping shows how much you appreciated Christian’s story.