Outsourcing computation: the minimal refereed mechanism

DOI10.1007/978-3-030-35389-6_19MaRDI QIDQ777972zbMATH OpenOpenAlexFDO

Authors Yuqing Kong, Chris Peikert, Grant Schoenebeck, Biaoshuai Tao

Publication date 30 June 2020

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 5485522 (Why is no real title available?)
• scientific article; zbMATH DE number 1559566 (Why is no real title available?)
• Algebraic methods for interactive proof systems
• Algorithmic rationality: game theory with costly computation
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Constant-round interactive proofs for delegating computation
• Delegating computation: interactive proofs for muggles
• From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again
• How to delegate computations publicly
• IP = PSPACE
• Introduction to modern cryptography.
• Non-interactive verifiable computing: outsourcing computation to untrusted workers
• Rational arguments: single round delegation with sublinear verification
• Rational proofs
• Rational sumchecks
• Refereed delegation of computation
• Strictly Proper Scoring Rules, Prediction, and Estimation
• Succinct delegation for low-space non-deterministic computation
• The Knowledge Complexity of Interactive Proof Systems

Cited in

(2)

• Optimal contracts for outsourced computation
• Verifiable crowd computing: coping with bounded rationality

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)