Wednesday, February 21, 2024

Sumchecks and Snarks

Last summer as I lamented that my research didn't have real world implications, one of the comments mentioned the sumcheck protocol used for zero-knowledge SNARKs. I tried to figure out the connection back then but got lost in technical papers. 

With the formal verification of the sumcheck protocol announced last week I tried again this time using Google's new Gemini Ultra. Gemini gave a readable explanation. Let me try to summarize here.

Sumcheck comes from the paper where Howard Karloff, Carsten Lund, Noam Nisan and I showed that co-NP has interactive proofs. It was Carsten who first came up with the sumcheck protocol in fall of 1989. Here's a simple version:

Suppose there is a hard to compute polynomial p of low-degree d and a prover claims p(0)+p(1) = v. The prover gives a degree-d polynomial q to the verifier claiming q = p. The verifier checks q(0)+q(1) = v and picks an r from a large range. If q was actually p then p(r) = q(r). But if p(0)+p(1) \(\neq\) v then p and q are different polynomials and with high probability p(r) \(\neq\) q(r) since p and q can only agree on at most d points.

The protocol reduces checking a sum to checking a single randomly chosen location. Our first proof used the sumcheck protocol to reduce checking the permanent of a nxn matrix to a (n-1)x(n-1) matrix and then we repeat until the matrix is small enough to compute the permanent directly.

Now let's break down the properties of zkSNARK (zero-knowledge succinct non-interactive arguments of knowledge). 

  • Efficient: A prover who knows the secret input can generate the proof efficiently.
  • Zero-Knowledge: A prover can convince a verifier that they know a secret input that satisfies a statement without revealing anything else about that secret.
  • Succinct: The proof itself is extremely small and easy to verify.
  • Non-Interactive: No repeated interaction between prover and verifier is necessary. The prover generates one proof, and anyone can verify it.

Our original sumcheck protocol is not all efficient, the prover needs to solve #P-hard problems, but in SNARKs we assume the prover already knows the problem's solution.

Our protocol requires significant interaction, in particular that r is chosen after q is set. But for SNARKs since we can assume the prover is efficient, we can use r as a hash of q. It should be difficult to find a q different than p such that q(hash(q)) \(\neq\) p(hash(q)).

Our protocol is not at all zero-knowledge, if p = q then the protocol reveals p(0) and p(1). Lots more tricks needed to make it zero-knowledge and succinct but I leave that to the interested reader.

3 comments:

  1. You're so wrong on this: "my research didn't have real world implications". I mean, literally each of my talks about STARKs starts by quoting the immortal line from BFLS "a single PC can monitor the operation of a herd of super computers, working with faulty hardware..." which I'm now quoting by heart.

    It all starts with BFLS and poly-logarithmic computation. The only thing that STARKs do is get the proofs more efficient. But the concept of poly-logarithmic verification, arithmetization (LFKN), low degree testing - it's all in there.

    And this math, which you've jumpstarted, is powering all advanced scaling techniques on Ethereum.

    Even the sum-check protocol, revamped by the "proofs for muggles" paper of GKR08, is entering modern systems.

    So, "has no practical impact" cannot be further from the truth.

    ReplyDelete
    Replies
    1. Thanks. You made my day. Now if we only patented those ideas...

      Delete
  2. You shouldn’t have patented it. Schnorr patenting his signature scheme led to nobody using it until the patent expired.

    ReplyDelete