Transaprent Succinct Arguments @ CESC

snargs.md

Transparent Succinct Arguments

Alessandro Chiesa (UC Berkeley, Starkware, Zcash)

What are succinct arguments?

• Proofs of computational integrity
• Game between prover and verifier
• Prover knows an input to a F(x) that would make it return y
• Prover could trivially prove this by providing x
  • This convinces the verifier for sure!
  • Being able to convince the verifier of a true claim is the property of completeness
    • Trivially, verifier could always answer "yes"
  • But this is not good enough...
  • The verifier should not be fooled by an unsatisfactory x, in such cases the verifier should reject the proof.
  • This property is called soundness.
    • Trivially, verifier could always answer "no"
  • We want both properties!
• Sending x explicitly satisfies completeness and soundness, but is pretty trivial.

Why not just send x?

• x could be really big! Say an entire database.
• Verifier also has to re-execute the computation natively, even if F(x) is extremely slow.
• In blockchains, lots of good examples where computations are expensive, such as block / transaction verification.
• Succinct proofs achieve these goals efficiently.
  • Proof is small, time to check is faster than re-computing F(x)
  • Formally: the number of bits in the proof of <= poly(log(T))
  • Time to check the proof is <= poly(log(T))
• First constructed in the early 90s by Silvio Micali

Argument vs proof?

• What's the difference between a succinct argument and a succinct proof?
• We have to make compromises somewhere: we will say that an argument relaxes the soundness condition. I.e., an argument relies on some computational hardness assumption.
  • With this relaxation (which can be proven to be necessary), then we can achieve our goal of succinct proofs.

What has been happening over the last 10-20 years in succinct arguments

• SNARK = succinct, non-interactive argument of knowledge
• Generating proof tends to be expensive, but proof size is small and verification time is fast
• Many beautiful and efficient constructions have been created in the last few years
• Zcash today uses some ZK-SNARKs under the hood
• Last year, STARKWare explores scalability also brought about by SNARKs
• For this talk, will ignore the zero-knowledge aspect of these succinct proofs. The efficiency is the important part, not the privacy.
• In order to accomplish these goals, you need some trusted setup.
  • Set of numbers / strings used to interpret what a proof means when you check it.
  • When you think about deploying this kind of cryptographic primitive in P2P systems, the question arises: who produces these system parameters?

What are transparent succinct arguments?

• Who samples the parameters?
• We could decide that some person or small group of people to sample the parameters: but it's possible that an individual can cheat.
  • For many known constructions of SNARKs, if you know the secret randomness that was involved to produce the parameters, you can use that randomness to forge false proofs.
  • Impossible to prove deletion of that randomness.
• Seems implausible to find someone in a P2P system who can be trusted to sample this randomness.
• In the real world, what we've done is find strong mitigations: bring together a group of people to construct a cryptographic ceremony, such that if at least one of the participants is honest, then the parameters that are generated are securely sampled.
  • Uses multi-party computation (MPC). Secure as long as not all actors are corrupted.
  • Practically speaking, can bring in many people with different ideological perspectives, such that they're unlikely to collude.
  • The major drawback here is operational cost of organizing something like this.

Transparent SNARGs

• In SNARGs, the system parameters have no structure
  • Only rely on sufficient amounts of public randomness
• Qualitatively, much harder to corrupt
  • E.g., take pi and read enough of its digits to derive some randomness
  • Merely relying on public randomness is a pretty good compromise in practice
• If we believe that these kinds of proofs are going to play a big role in the future of these P2P systems, we need to develop good constructions of transparent proofs
• These types of constructions are not deployed yet, but thanks to recent developments in academia, we should see deployments starting 2019

Where do transparent SNARGs come from?

Probabilistically checkable proofs

• In the 90s @ UC Berkeley, several graduate students came up with the idea of probabilistically checkable proofs
• Prover:
  • "I know of an x such that F(x) = y"
  • Imagine the prover encodes x in some way (poly(T) sized proof)
• Verifier:
  • Instead of checking the entire proof, the verifier only checks the statement by sampling certain subsets of the proof.
  • The verifier produces some number of queries: a smallish number, like 3.
  • It gets back the answers based on the proof, and based on those queries (constant number of them), decides to accept or reject the proof.
• Turns out that every computation is such that you can construct a proof of this form.
  • This proof is not small: it has size poly(T).
  • This proof contains a lot of redundancy
• Transparent SNARGs are a way to build on these probabilistically checkable proofs to build cryptographically checkable proofs
• These probabilistically checkable proofs already sound like SNARGs... are they?
  • They are not succinct (large proofs), so no.

From PCP (probabilistically checkable proof) to SNARG

• Main cryptographic tool is a random oracle (i.e., a hash function)
• Side note: only lightweight crypto is needed to construct SNARGs. Kind of surprising.
• Prover:
  • Runs the PCP prover algorithm internally, and commits to the proof using a Merkle Tree.
  • Then hashes the root of the Merkle Tree, and presents that to the verifier.
  • Then uses the hash of the Merkle root to query the PCP itself. (Queries are not manipulable assuming secure hash function.)
  • To reveal the entire proof, can provide leaf values and authentication path, plus query results.
• Verifier:
  • Sees that the queries are consistent with the root, verifies that the random queries were derived from the Merkle tree root, and that the queries themselves were satisfied.
• Makes the entire protocol non-interactive.
• Is the proof in fact succinct?
  • Authentication path is small:

    • queries (constant) * log(PCP)

    • PCP is poly(T)
    • total size = polylog(T)
• Only assumption is random oracle model
  • If we can agree on a hash function that's secure, then we're good to go
  • Much better than multi-party computation for trusted setup

PCP-based SNARGs

• Good:
  • Black-box use of light-weight crypto (any hash function)
  • Plausibly post-quantum (no fancy crypto)
  • Transparent setup (just hash function)
• Bad:
  • Random oracle model is a strong assumption
    • Eh, no one cares in the real world
  • 1990s-2010s, PCPs were galactic algorithms
    • I.e., they have very large constants. They are "efficient" in the CS sense, but it sucks.
  • By today:
    • Just "very expensive"

A new generation of transparent SNARGs

• Can achieve must better efficiency while preserving other good properties!
• Will be constructing PCPs in a bigger design space
• Will now allow the prover and verifier to have a "longer conversation" (abstraction, it's still non-interactive)
• Verifier:
  • Sends randomness
• Prover:
  • Sends over PCPs
• Do this a few times
• Verifier:
  • Then submits queries and decides on correctness

From IOPs to SNARG

• Prover:
  • Creates the first PCP, does the whole jig and generates the proof
  • Uses the hash of that first proof to generate the next PCP, do the whole jig
  • Send the whole set of proofs + roots to the verifier
• Verifier:
  • Check all the proofs and that they were chained together
• Much faster than PCPs!
• Asymptotic improvements lead to concrete, practical improvements, and vice versa
  • Have now improved IOP-based transparent SNARGs
• Two years ago, we had long proofs in the 10s of MB
• We now have proofs for arbitrary computations that are ~200 KB
  • Each of these improvements, from 10MB -> 1MB -> 0.5MB -> 0.2MB (today) are directly attributable to specific theoretical insights
• Getting lower all the time... may be able to get down to 10KB with further theoretical work

Takeaways

• PCPs are no longer totally inefficient
  • Proofs have become much shorter
• Public-key cryptography still gives us much better proof length
  • 128 bytes with trapdoor setup
  • 2KB with transparent setup (bulletproofs)
• Transparent SNARGs obtained from IOPs give you fully succinct verification and only use lightweight crypto (just hash functions).