Sequential Composition of Rational Proofs
summary
Defines sequential composability so honest computation remains the best long-term strategy, shows existing rational proofs fail for repeated volunteer tasks because a random prover can out-earn an honest one (the original threshold protocol has reward gap 1/n^2, requiring scaling by ~n^3). Gives two remedies: a batch-and-check k scheme that recomputes one of k results (needs large k and a no-state input distribution), and an interactive PCP-like protocol for log-depth arithmetic circuits with probability of survival 1-2^-d, which works for FFT-style circuits under the stated cost and distribution assumptions.
AI-written summary · about
chapters (14)
- 0:00Intro
- 0:25Model
- 1:28Motivation
- 2:32Rational Proofs
- 3:19Interactive Proofs
- 4:38Uniform Verification
- 5:53Threshold Protocols
- 9:05Reward Gap
- 12:14Lazy Proofer
- 18:47PCP Model
- 23:57PCP Protocol
- 26:09Regular Circle
- 28:54Mixed Strategy
- 29:57Summary
related talks
27mProofs of proofs: incremental verifiability from recursion and accumulation
51mDistributed Zero-Knowledge Proofs and Applications to Secure Computation
41mGKR based Zero-Knowledge Proofs
51mWhy you shouldn't trust me
20mSNARKs from the sum-check protocol
44mIOP based Zero-Knowledge Proofs
01h 06mCompiled Nonlocal Games: From CHSH to BQP Verification
26mzk-SHARKs: Combining Succinct Verification and Public Coin Setup