Verifiable delegated computation (focus on SNARKS)

[nicola]

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

• TinyRAM explained
• SNARKS explained

Classics (from 0 to Zero-Knowledge)

• Micali's CS Proofs
• [GMR89] The Knowledge Complexity of Interactive Proof-Systems
• [BFM88] Non-interactive zero-knowledge and its applications
• [NY90] Public-Key Cryptosystems Provably-Secure against
  Chosen-Ciphertext Attacks
• [BDMP91] Non-interactive Zero Knowledge
• [FLS99] Multiple Non-Interactive Zero Knowledge Proofs under general assumptions

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
• ⭐️ 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 Incentive-based verifiable delegated computation #27)
• Succinct Non-Interactive Arguments via Linear Interactive Proofs
  • efficient non-interactive arguments for NP
  • however, based on non-standard assumptions

SNARK now

• M. Walfish's review of the field
  • Review of the recent work until 2015
• SNARKS and Discrete Log
• ADSNARKS (full)
• Composable SNARKS
• Commit-and-prove

SNARK alternative

• See Incentive-based proofs Incentive-based verifiable delegated computation #27

Other Resources

• The evolution of a proof
• SCIPR Lab Publications
• Snarks for layman person
• Madars introduces Libsnark
• Great review in the Section 1 Introduction
• Stackoverflow on NIZK
• Shafi on Zero Knowledge Proofs
• Silvio on Proofs, Secrets, and Computation

Applications

• SNARKs and their practical applications
• Hawk: privacy-preserving smart contracts
• Learn Libsnark

[nicola]

Adding SNARKs and their practical applications

[nicola]

Adding Madars introduces Libsnark

[nicola]

Adding classics:

• [GMR89] The Knowledge Complexity of Interactive Proof-Systems
• [BFM88] Non-interactive zero-knowledge and its applications
• [NY90] Public-Key Cryptosystems Provably-Secure against
  Chosen-Ciphertext Attacks
• [BDMP91] Non-interactive Zero Knowledge
• [FLS99] Multiple Non-Interactive Zero Knowledge Proofs under general assumptions

[nicola]

@madars please feel free to add some key material that I should read!

[nicola]

adding

• ⭐️ Goldreich's overview of proof systems

[nicola]

adding

• TinyRAM explained
• SNARKS explained