Skip to content

Instantly share code, notes, and snippets.

@Haseeb-Qureshi
Created October 10, 2018 19:51
Show Gist options
  • Save Haseeb-Qureshi/f552fdbbb649ed4bbfeb681beb4091e1 to your computer and use it in GitHub Desktop.
Save Haseeb-Qureshi/f552fdbbb649ed4bbfeb681beb4091e1 to your computer and use it in GitHub Desktop.
Transaprent Succinct Arguments @ CESC

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).
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment