Outsourcing Computation: the Minimal Refereed Mechanism
This addresses the challenge of secure and efficient computation delegation in settings with limited verifier resources, though it is incremental in improving efficiency for low-space computations.
The paper tackles the problem of outsourcing computation to rational provers by designing the Minimal Refereed Mechanism, which ensures honest results without verification effort from the verifier, requiring only O(log S + log T) time and space for the verifier and a multiplicative log S-factor more computation for the provers.
We consider a setting where a verifier with limited computation power delegates a resource intensive computation task---which requires a $T\times S$ 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(\log S + \log T)$ time and $O(\log S + \log T)$ 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 $\log S$-factor more than the computation itself, making this schema efficient especially for low-space computations.