Verifiable delegated computation (focus on SNARKS)

nicola commented 7 years ago

Background

random oracle: black-box that to every query gives a random response (uniform from its domain), same query == same response. (Note: church-turing thesis said computable functions have finite description, random oracles don't)
NP: is the class of problems for which efficiently verifiable proofs of "yes" instances exist
co-NP: is the class of problems for which efficiently verifiable proofs of "no" instances exist
interactive proof: conversation between a prover and a verifier that ends with the verifier either accepting or rejecting
zero knowledge IP: cheating verifier does not learn anything more
proof of knowledge IP: cheating prover cannot convince a honest verifier to accept unless it knows some secret

General background

Classics (from 0 to Zero-Knowledge)

Pre-SNARKS

[ ] ⭐️ Shamir's IP=PSPACE
- it is possible for a prover to convince the verifier about any language in PSPACE, in particular any language computable in poly time!
- not enough for practical delegation: round-complexity, prover efficiency
[ ] ⭐️ Kilian's Interactive Arguments
- four round interactive arguments for all languages in NP
- zero-knowledge arguments can have very low communication complexity
[x] ⭐️ Micali's CS Proofs
- using random oracles & non interactive protocol in NP
- "computational guarantee": proofs for false statements may exist and are expensive to find.
- Given a random oracle, every computation has a short certificate proving its correctness, any program NP-complete is checkable in polynomial time.
- easy to find: comparable to the time to decide a statement
- easy to verify: polylog time shorter to verify
[ ] ⭐️ Delegating computation reliably
- delegation with sub-linear verification are not achievable with respect to the standard notion of soundness
- relaxed models to make sublinear verification time!
[ ] ⭐️ [GMW91] Proofs that Yield Nothing But Their Validity (All Languages in NP Have Zero-Knowledge Proof Systems)
- all languages in NP have zero-knowledge proofs
[ ] ⭐️ [BCC88] Minimum disclosure Proofs of knowledge
- all languages in NP have zero-knowledge arguments with perfect zero knowledge
[ ] ⭐️ [Fiat-Shamir86] How to Prove Yourself: Practical Solutions to Identification and Signature Problems
- Non-interactive flipping of a coin: hash function will produce random looking output and therefore be a suitable replacement for the verifier
- Non-interactive only in the random oracle model
[ ] ⭐️ Goldreich's overview of proof systems

SNARKS t=0

Standard assumptions problem:
- quasi-linear solutions: don't work in practice, e.g. a database is too big
- substituting this step -> sublinear verification! (See rational sumchecks https://github.com/nicola/decentralized-research/issues/27)
[ ] Succinct Non-Interactive Arguments via Linear Interactive Proofs
- efficient non-interactive arguments for NP
- however, based on non-standard assumptions