Incentive-based verifiable delegated computation

[nicola]

Background

Definition

• Verifiable outsourced computation: designing protocols where it is impossible for a provider to cheat.
• Incentive-based verifiable computation: cheating is possible, but the provider would have no rational motivation to do so. Rational adversaries motivation is to maximize their utility function. In other words, it would be irrational for the user to behave incorrectly.
• probabilistic checkable proof, PCP: prover writes a long proof of correctness, verifier checks randomly selected positions. This assumes both have access to trusted memory storage, so that prover is committed to the proof before verifier queries it

Example

Input is n boolean inputs, output is 1 if at least k are 1

1. Prover announces m bits are equal to 1
2. Verifier runs G(b) and select a random bit and rewards the prover
3. Verifier rewards m/n

Pre Rational Proofs

• ⭐️ Incentivizing outsourced computation:
  • amortized efficiency: system may require re-executing a random sample of the computation
  • what if the penalty is not sufficient?
  • scheme may require "infinite" budget (great for non-fungible rewards)
• Delegation schemes for restricted complexity classes (quasi-linear!)
  • 🌝 Goldwasser's Delegating Computation: Interactive Proofs for Muggles
    • single round argument to verifiably delegate any bounded depth computation with quasi-linear verification
    • only polynomial work for the prove
  • 🌝 Kalai's How to delegate computation, the power of no-signaling proofs
    • single round argument for any bounded computation, standard assumption, but quasi-linear computation for any language in P

Rational Proofs t=0

• ⭐️ Rational Proofs
  • "pay-for-service" transactions for a single "stand-alone" execution
  • reward function maximized when server returns the correct value y=f(x)
  • one round trip for any problem in #P, prover is exp-time, verifier is poly-time
  • in general, low verification and communication time
• ⭐️ Super-efficient Rational Proofs
  • d-rounds, for Boolean circuits of depth d, d=O(log(n))
  • still open problem: poly-time computable functions

Rational Proofs now

• Sequentially Composable Rational Proofs (video)
  • motivation is volunteer computation
  • show that compositional property of rational proofs does not work: in time T, prover can either do more problems incorrectly or fewer correctly, they show rational proofs incentivize fast incorrect proofs
  • new scheme: reward of honest prover > reward of a prover that invest less computation cost; or, the cost for any prover is negligibly the same
• Rational arguments: single round delegation with sublinear verification
  • single-round rational arguments in sublinear time verification (circuits on log(n) depth)
  • prover is computationally bounded
• Rational Sumchecks
  • Removes quasi-linearity & prove rationality under composition from Goldwasser/Kalai
  • Single-round rational argument with sublinear verification for any language in P!
  • Relaxation on classical sumchecks:
    • better since they make sumchecks non-interactive
    • in Goldwasser/Kalai correctness could be verified with very efficient sumchecks
    • input layer where the usage of a classical one would break soundness (?)
    • verification even without reading the entire input, not possible with classical - could not guarantee soundness (?)

[jbenet]

Great notes! thanks for taking these.

[nicola]

thank you @jbenet

Adding Rational Sumchecks

[nicola]

Adding

• Rational Sumchecks
• Rational arguments: single round delegation with sublinear verification
• Kalai's How to delegate computation, the power of no-signaling proofs
• Goldwasser's Delegating Computation: Interactive Proofs for Muggles

[nicola]

• Rational Proofs with Non-Cooperative Provers