PaperlayerView exact revision on arXiv

Source-linked AI summary

A scalable verification solution for blockchains

Jason Teutsch, Christian Reitwießner

arXiv:1908.04756v1cs.CRecon.TH

TL;DR

TrueBit addresses the limited verification bandwidth of Bitcoin and Ethereum by combining financial incentives with an interactive dispute-resolution game. It outsources computationally intensive tasks while retaining trustless correctness, but its security and capacity depend on economic assumptions and protocol parameters.

  • Problem

    Bitcoin and Ethereum’s miners offer only typical-smartphone-scale processing and verification capacity, creating a bottleneck for more complex or higher-volume transactions.

  • Method

    TrueBit combines an incentive layer with an interactive verification game that recursively resolves disputes over outsourced computations.

  • Results

    TrueBit supports secure outsourced computation and is designed to enable decentralized mining pools, scalable transaction throughput, and trustless transfers between blockchains.

  • Takeaways & Limitations

    TrueBit makes secure computing affordable by outsourcing most computation while reducing redundant verification work across Ethereum nodes.

  • Takeaways & Limitations

    Forced errors are TrueBit’s Achilles’ heel because their large prizes invite opportunistic attacks, requiring randomness and consistent verification.

Abstract

from arXiv · show

Bitcoin and Ethereum, whose miners arguably collectively comprise the most powerful computational resource in the history of mankind, offer no more power for processing and verifying transactions than a typical smart phone. The system described herein bypasses this bottleneck and brings scalable computation to Ethereum. Our new system consists of a financial incentive layer atop a dispute resolution layer where the latter takes form of a versatile "verification game." In addition to secure outsourced computation, immediate applications include decentralized mining pools whose operator is an Ethereum smart contract, a cryptocurrency with scalable transaction throughput, and a trustless means for transferring currency between disjoint cryptocurrency systems.

1 Securing computations with economics

Nakamoto consensus securely maintains public ledgers and basic computations, but miners’ limited verification bandwidth creates a bottleneck for more complex or higher-volume transactions. TrueBit addresses this bottleneck with economic incentives and dispute resolution, enabling outsourced computation and several scalable blockchain applications.

  • Bitcoin and Ethereum miners collectively provide enormous computational resources, yet transaction verification offers no more processing power than a typical smartphone.Increasing transaction volume or complexity risks invalid transactions because of the Verifier’s Dilemma.
  • TrueBit amplifies Ethereum’s consensus computer by outsourcing most computation to a handful of entities while reducing redundant node computations.The system is designed to make secure computing affordable and, in theory, support any computation task through trustless smart contracts.
  • TrueBit combines a worldwide computation market with financial incentives intended to guarantee correctness of returned solutions.Anyone can post a computational task, and anyone else can receive a reward for completing it.
  • TrueBit is presented as a foundation for trustless mining pools, cross-blockchain currency transfers, higher-throughput blockchains, and smart-contract access to incentivized peer-to-peer storage.These applications include Ethereum smart contracts managing mining pools and transfers such as dogecoin to Ethereum and back.

2 How TrueBit works

TrueBit makes computationally intensive Ethereum tasks accessible to anonymous participants through rewards, deposits, challenges, and an interactive verification game. Its design improves efficiency and adaptability but depends on economic assumptions and faces security and complexity constraints.

  • Incentives: TrueBit’s incentive design must reward both participation and correct verification, because checking rewards alone do not ensure substantive inspection.Bug bounties also fail to attract participation when Verifiers see little chance of finding an error.
  • Verification game: The verification game recursively narrows disputed computations across rounds while Ethereum enforces the game’s rules.This dispute-resolution structure reduces reliance on miners to resolve contested results.
  • System properties: TrueBit lets anonymous parties act as Task Givers, Solvers, or Verifiers without relying on participant reputation.Participants enter by posting deposits and may be hired for computational tasks.
  • System properties: TrueBit combines financial incentives with blockchain transparency, allowing its interpreter to remain open for inspection and community updates.The system is intended to avoid reliance on traditional cloud trust and support democratic interpreter changes.
  • System properties: The protocol emphasizes efficiency, simplicity, adaptability, and keyless entry, while avoiding deep proof systems and exotic cryptographic assumptions.The verification game introduces extra work, but the authors expect appeals to occur rarely because wrong answers and bogus challenges incur high penalties.
  • Model assumptions: TrueBit assumes Ethereum correctly performs very small computations and that participants act rationally according to expected compensation.Under these assumptions, the system seeks to amplify reliable small computations into larger outsourced tasks.
  • Attacker model: Forced errors create an attack surface because their large prizes may attract opportunistic participants seeking rewards without performing intended verification.The protocol therefore requires forced-error occurrences to appear random and seeks consistent verification for every task.

3 Dispute resolution layer

TrueBit uses an interactive verification game with limited-power Judges to resolve disputes over outsourced computations while avoiding the Verifier’s Dilemma. The protocol narrows disputes recursively and keeps Judges’ work small relative to the computation.

  • 3.1 Bottleneck: The Verifier’s Dilemma: Ethereum’s redundant verification burden creates a Verifier’s Dilemma because rational miners may skip substantial checks and leave invalid transactions unverified.Miners risk either falling behind or mining on an invalid chain when verification becomes costly.
  • 3.2 Solution: The verification game: TrueBit assigns disputed computations to a Solver and Challenger, while bounded-power Judges rule on whether the output is correct.Ethereum miners collectively serve as Judges and record their decisions on the blockchain.
  • 3.2 Solution: The verification game: Each verification-game round narrows the disputed computation to a smaller subset until the final challenge is sufficiently trivial to verify.The protocol applies recursive narrowing to identify the disputed computation step.
  • 3.3 Detailed protocol: TrueBit combines parametrized binary search with probabilistic Merkle trees to reduce interaction rounds and blockchain space demands.Merkle roots commit to computation data while enabling paths to be checked selectively.
  • 3.4 Runtime and security analysis: Judges perform small amounts of work compared with the task, mostly recording data across transactions, thereby avoiding the Verifier’s Dilemma.The protocol distributes Judges’ work over many blockchain transactions.
  • 3.4 Runtime and security analysis: TrueBit’s secure computation capacity is bounded by parameters such as σ, the jackpot size, and the Challenger’s ability to participate in long verification games.Posting complete machine states could remove a stated security risk but would make the protocol more expensive.

4 Incentive layer

TrueBit’s incentive layer pays participants for correct computation and verification while using forced errors, deposits, taxes, and unpredictable randomness to discourage manipulation. These mechanisms impose costs and constrain secure task complexity.

  • 4 Incentive layer: TrueBit pays Verifiers through error-finding rewards that amortize the cost of checking tasks where no bugs are found.Rewards must compensate verification work even when a checked solution is correct.
  • 4.1 Protocol overview: A TrueBit contract announces a task, selects a Solver by lottery, and reveals either a correct or forced-incorrect solution depending on the protocol state.The Solver prepares both solution types before the relevant forced-error outcome is revealed.
  • 4.1 Protocol overview: Verifiers receive jackpot payouts for correctly identifying forced errors, which motivates them to check tasks despite forced errors being rare and unpredictable.Verifiers learn the random bits only after deciding whether to challenge.
  • 4.1 Protocol overview: The jackpot payout bounds secure computation complexity because Verifier compensation must cover checking costs multiplied by the forced-error rate.The paper sets forced errors to occur on average once every thousand tasks.
  • 4.2 Taxes: Task Givers pay Solver, Verifier, Referee, and Judge costs through a verification tax, while the jackpot payout is capped at one third of repository funds.An initial repository is intended to become self-sustaining through taxes.
  • 4.2 Taxes: The estimated verification tax is 500% – 5000% of the task’s execution cost, reflecting participation incentives and security tradeoffs.Higher Solver deposits may absorb part of this burden.
  • 4.3 Deposits: Solver and Verifier deposits fund verification-game costs and deter collusion, bogus solutions, random guessing, and other attacks.Deposits must exceed the expected jackpot payout plus the cost of playing a verification game.
  • 4.3 Deposits: Deposit values remain context-dependent: a small Solver deposit relative to a controlled payout can let an adversary submit bogus answers to delay a time-sensitive contract.The paper leaves appropriate minimum deposits for such situations to the Task Giver.

5 Defenses

TrueBit’s defenses use deposits, incentives, verification participation, and randomized strategies to resist Sybil attacks, collusion, and bogus solutions. The analysis also identifies boundaries where external economic incentives or task-giver resources matter.

  • Security basis: TrueBit’s security relies on at least one Verifier checking each task, while its incentive layer defends against shortcuts that divert rewards from actual verification.The analysis assumes network and attacker conditions from Sections 2.2 and 2.3.
  • Pairwise Sybil attacks: Deposits deter Sybil identities, and pairwise cooperation among Task Givers, Solvers, and Verifiers does not generally provide a cheating advantage.Judges and Referees are treated separately under the paper’s assumptions.
  • Pairwise Sybil attacks: Block withholding is one-sided: miners may lock jackpot funds, but they almost never release them, making block hashes a safe randomness source.A Solver lacks incentive to bias randomness against forced errors, and miners have little control over their own block hashes.
  • Pairwise Sybil attacks: Task Giver–Solver collusion loses money because taxes and payments to participating parties exceed the expected jackpot gains from manufactured forced errors.The Task Giver cannot predict the private random bits when creating the task.
  • Pairwise Sybil attacks: A Solver–Verifier pair is deterred because the Solver’s burned deposit exceeds the Verifier’s income, although external temporal constraints may require larger deposits.The paper states that the Task Giver must set the necessary deposits in such cases.
  • Pairwise Sybil attacks: Independent Verifiers remain incentivized during forced errors because the tax rate and jackpot payout support additional checking even when the Solver challenges himself.The Solver cannot claim the same jackpot repeatedly, preserving other Verifiers’ motivation.
  • External threats: TrueBit cannot use penalties to deter every bogus-solution attack because, as a closed system, it cannot estimate the solution’s true economic impact on Ethereum.This is an explicit scope boundary for the penalty-based defense.

6 Implementation

TrueBit standardizes task execution through the Google Lanai architecture so participants can simulate a fixed machine consistently. Its on-chain interpreter is reserved for disputes, while ordinary execution uses native languages and hardware.

  • Execution architecture: TrueBit accepts C, C++, or Rust tasks only after conversion to the Google Lanai architecture, ensuring consistent simulation and fair adjudication by Judges.The fixed architecture is required by the verification-game framework.
  • Execution architecture: TrueBit’s Solidity interpreter runs tasks on-chain only during disputes; otherwise Solvers and Verifiers execute native implementations on regular hardware.Private optimization is possible when tasks do not require the Lanai interpreter.

7 Applications

TrueBit separates transaction selection from verification, enabling complex computations and several blockchain applications without overburdening miners. Its applications include decentralized mining pools, scalable throughput, cross-chain currency transfer, and externally stored data.

  • 7.1 Practical decentralized pooled mining: TrueBit can support smart contract-based mining pools for any Nakamoto consensus cryptocurrency by checking proof-of-work computations beyond Ethereum’s gasLimit capacity.The text cites Zcash proof-of-work verification as appearing to exceed Ethereum’s gasLimit by a factor of 50.
  • 7.2 Dogecoin–Ethereum bridge: TrueBit can build a two-way Dogecoin–Ethereum peg that transfers dogecoins between blockchains without a third-party exchange and adds smart contract functionality to Dogecoin.TrueBit contracts can check Dogecoin’s Scrypt-based proof-of-work, supporting confirmation of transfers under the described scripting extension.
  • 7 Applications: TrueBit decouples transaction selection from validity verification, allowing off-chain Solvers and Verifiers to handle correctness while miners select transactions.Judges and Referees assist the verification protocol, enabling complex transactions to reach the blockchain without overburdening miners.
  • 7.3 Scalable transaction throughput: Separating verification from mining can increase blockchain transaction throughput without facing the Verifier’s Dilemma.The application decouples verification for miners into a separate protocol.
  • 7.4 Towards a big data system: TrueBit can use massive external datasets when their Merkle root is stored on-chain and the data is publicly and permanently available elsewhere.Ethereum’s blockchain alone is too expensive for storing even moderate amounts of data directly; Solvers and Verifiers require access to the full dataset.
  • 7.4 Towards a big data system: In practice, TrueBit’s verification game becomes inefficient for big-data tasks, motivating specialized verification games for particular task classes.The paper states that computation security degrades as tasks reach the level of big data.

A Addendum

The addendum records later work and feedback that informed TrueBit’s development roadmap and refined the protocol.

  • A Addendum: Subsequent work and feedback informed TrueBit’s development roadmap and helped refine the protocol itself.

A.1 Security patches

The security patches address attacks that could introduce bogus computations or extract jackpot funds by changing challenge signaling, penalizing premature disclosure, and bounding payouts.

  • A.1 Security patches: TrueBit investigates attacks targeting bogus computations on the blockchain and attacks targeting jackpot-fund extraction.
  • Premature disclosure of random bits: Arbit penalizes Solvers who prematurely reveal private random bits, discards their solutions, reruns the Solver lottery, and rewards reporters.Half the Solver’s deposit is burned and the other half goes to the reporting party.
  • Incorrect secondary solution: A three-way commitment scheme challenges solution A, solution B, or both, eliminating the incorrect secondary solution vulnerability.The Verifier’s commitment is interpreted by the integer value modulo 3.
  • Security patches: Verifiers must hide which task they challenge until the protocol’s final phase to prevent Sybil identities from reducing payouts and discouraging participation.The design ensures each Verifier performs the task without distraction from other commitments.
  • Program abort: The verification game requires an explicit step bound and deterministic computation sequence so Judges can determine correctness.
  • Jackpot balloon attack: A fixed absolute jackpot bound mitigates attacks that repeatedly challenge a forced error to inflate the jackpot repository.Extra accumulated revenue becomes available only after a protocol upgrade, and actual payouts depend on task difficulty.
  • Incentivizing block withholding: Premature disclosure defenses make block-withholding attacks an expected net loss when the Solver’s penalty exceeds the expected jackpot return.

A.2 The TrueBit Virtual Machine

The TrueBit Virtual Machine makes verification-game execution practical by using a simple, deterministic architecture with off-chain state enumeration and on-chain single-step verification.

  • A.2 The TrueBit Virtual Machine: The TVM must execute identical computation steps across hardware and keep each step and state change within Ethereum’s resource limits.A computation step must fit within Ethereum’s gas limit, and a state change must fit inside one Ethereum transaction.
  • A.2 The TrueBit Virtual Machine: WebAssembly sufficiently approximates these simplicity requirements to make TVM execution practical today.The paper identifies WebAssembly’s machine independence and relative simplicity as relevant properties.
  • A.2 The TrueBit Virtual Machine: The TVM combines an off-chain interpreter that enumerates computation states with an on-chain stepper that computes the next state.
  • A.2 The TrueBit Virtual Machine: Solvers and Challengers create Merklized computation-state lists, then Judges run the first disputed step using the stepper.
  • A.2 The TrueBit Virtual Machine: Because Native WebAssembly does not fully satisfy the simplicity properties, the TVM divides each WebAssembly instruction into substeps to reduce compiler-error risk.

A.3 Additional applications

TrueBit is presented as a verification mechanism for applications spanning decentralized video, autonomous machine learning, data markets, staking, and decentralized random-number generation.

  • Video broadcasting: TrueBit ensures decentralized video transcoders perform their work correctly during Livepeer’s live-streaming process.Swarm keeps video data available during the verification period.
  • Autonomous machine learning: A TrueBit-based ArtDAO would let blockchain code access computational resources without anyone being able to terminate it.The passage identifies computer vision as a possible future blockchain-based machine-learning application.
  • Data marketplace: TrueBit enables autonomous data markets by verifying models and supporting trustless remuneration for streamed models and data.The passage connects this possibility to Open Mined and identifies verification as relevant to Ocean Protocol.
  • Staking and random numbers: 1protocol lets participants with computing resources or capital become TrueBit Solvers or Verifiers by separating security deposits from completed work.Its Arbit protocol additionally uses interactive verification to generate decentralized random numbers.
Loading 1908.04756v1…