Outsourcing computation: the minimal refereed mechanism

DOI10.1007/978-3-030-35389-6_19zbMATH Open1435.68100arXiv1910.14269OpenAlexW2990374137MaRDI QIDQ777972FDOQ777972

Biaoshuai Tao, Yuqing Kong, Chris Peikert, Grant Schoenebeck

Publication date: 30 June 2020

Abstract: We consider a setting where a verifier with limited computation power delegates a resource intensive computation task---which requires a $TimesS$ computation tableau---to two provers where the provers are rational in that each prover maximizes their own payoff---taking into account losses incurred by the cost of computation. We design a mechanism called the Minimal Refereed Mechanism (MRM) such that if the verifier has $O(logS+logT)$ time and $O(logS+logT)$ space computation power, then both provers will provide a honest result without the verifier putting any effort to verify the results. The amount of computation required for the provers (and thus the cost) is a multiplicative $logS$-factor more than the computation itself, making this schema efficient especially for low-space computations.

Full work available at URL: https://arxiv.org/abs/1910.14269

Recommendations

• Rational proofs with multiple provers
• Refereed delegation of computation
• Efficient rational proofs with strong utility-gap guarantees
• Sequentially composable rational proofs
• Fair and rational delegation computation protocol

zbMATH Keywords

outsourcingPrisoner's dilemmaMerkle hash treeminimal refereed mechanism

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Other nonclassical models of computation (68Q09) Mechanism design theory (91B03)

Cites Work

• Strictly Proper Scoring Rules, Prediction, and Estimation
• Algorithmic rationality: game theory with costly computation
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• The Knowledge Complexity of Interactive Proof Systems
• Non-interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers
• Introduction to modern cryptography.
• Algebraic methods for interactive proof systems
• IP = PSPACE
• Title not available (Why is that?)
• From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again
• Title not available (Why is that?)
• Refereed delegation of computation
• Rational Sumchecks
• Rational arguments
• Delegating Computation
• How to delegate computations publicly
• Succinct delegation for low-space non-deterministic computation
• Constant-round interactive proofs for delegating computation
• Rational proofs

This page was built for publication: Outsourcing computation: the minimal refereed mechanism

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q777972)