ZK Whiteboard Study Group

Module 2: Building a SNARK, pt 1/2

A casual “office hours” series to reinforce learning from the ZK Whiteboard series

Recommendation: Populate these slides with your questions, answers and insights are you watch the lecture videos!

​

We’ll use this for discussion during the study group itself.

​

Note: Slides are editable by all.

Module Summary

1. Functional commitment schemes
2. Interactive Oracle Proofs

Two components: Commitments & IOPs

Q&A

• …

​

Insights:

• A common paradigm that comes up a lot
• Cryptographic object within the Commitment scheme
• And IOP is an information theoretic object
• [Nico] we’ve been playing around with what kind of IOP you run with. Need to test if f = 0 in different ways.

Paste slide here

Link to video at this slide

Commitments

Q&A

• Q1 [Arro] If m=message- is this different from w in the previous slides?
• Q2 [Arro] what is r?
• Q3 [Arro] SNARKs can be binding, not necessarily hiding. zkSNARK must be hiding.
• Q4 [venky]
• Q5 [Paul] if there was a hash collision would we lose the binding property [nico]: Yes.

​

Insights:

• I think the commit function is computationally secure, not statistically (or information-theoretically) secure. That is probably why the SNARK is not a proof but an argument, since proof of knowledge soundness is computational.
• [Nico] a commitment is a generalization. You can commit to anything, not just a w. You can commit
• [Nico] r is something that is compatible with m (if m is int then r is ints, if m is point then r is points).
• [Nico] opening means revealing whole or part of the message.
• [Nico] IOP can provide Zero Knowledge.
• [Nico] Can you 2 different rs to hide message.
• [Nico] collision resistance vs pre-image resistance. Related. Depends on what adversary is given (find a collision for any 2 vs find a collision given 1) Binding is stronger than pre-image resistance property. Pre-image resist is hiding. Collision resist is binding.
• [Nico] hash does not preserve structure. However with KZG we are able to do computations on encrypted values.

Paste slide here

Link to video at this slide

Committing to a Value

Q&A

• (Arro) How do you combine M and R [Nico] we concatenate them as bits.
• (Paul) What goes wrong if we were to do this without the random value r? [Nico] you lose the hiding property. Because everytime you commit to the same message you get the same commitment.
• (Derek) How is r chosen and by who? [Nico] You keep r secret at first. Then when you are ready to open you provide r.

​

Insights:

• I think the binding property arises from the fact that H is collision-resistant. I also think the random number “r” assists in the hiding property.
• [Nico] M is the set of all messages and R is the set of all randomness and MxR are all combinations of M and R.
• [Nico] A hash is a way to commit but its not the only way.
• [Nico] Pre-image resist is hiding. Collision resist is binding.

Paste slide here

Link to video at this slide

Committing to a Function

Q&A

• Q1 [arro]Does this describe an interactive commitment scheme –> interactive proof? Or is this always the way it is done? [Nico] V holds P accountable to the commitment. Back and forth comes from nature of commitment: P gives com to V in order to be held accountable later.
• Q2 [arro] order is counter-intuitive. How is proof built?

​

Insights:

• [Hickup]: Wasn’t clear to me initially, but the prover does not need to submit the function ƒ; it will be proven that ƒ is used, through proof π.
• [Nico] Family of functions is now your domain of Messages. All f that take an element of X and map it onto an element of Y.
• [Paul] V does not get to know what f is. [Nico] “opening” in this context gives you one evaluation of f.
• [Li] if V doesn’t need to ask anything than this is non-interactive.
• [Nico] proof pi. If you want to use FRI you have a lot of back and forth between V & P.

​

Paste slide here

Link to video at this slide

Committing to a Function: Syntax

Q&A

• [Arro]Is the “setup” here the equivalent step as the “trusted setup”? [Nico] for KZG yes, it will be the trusted setup.
• [v9] gap between f and arithmetic circuit. [Nico] in IOP you transform proof of knowledge of w to commitment of polynomial.
• [Arro] how does this relate to succinctness? [Nico] succ is desirable but we don’t assert anything about succ on this slide. For Bulletproofs, V does as much work as the size of the polynomial. Starks use FRI as PCS. FRI eval is interactive. Number of rounds is O(log |C|). Translate from # of rounds to size of proof. We will get to Fiat–Shamir transformation.
• [Arro]Is eval basically “verify” from the previous slides?

​

​

Insights:

• [Nico] “eval” is the protocol that may or may not be interactive. Defined by 2 algos: Proover and Verifier.
• [Arro]

Paste slide here

Link to video at this slide

Examples of Functional Commitments

Q&A

• [abishek] multilinear polynomial means multivariate polynomial [dbrans] multilinear = multivariate with power at most 1 for each variable. [Nico] “multlinear” you see many variables but they never have powers. max degree 1 for each variable.
• [arro] what is a linear function?

​

Insights:

• [hickuphh3] one is generalizations of the other.
• [Li] They are equivalent but transformation from linear to multilinear is easier.
• [Nico] “linear function” should be “linear combination of functions”. Imagine 2 vectors and you want to take the dot product of the vectors.
• [Nico] “univariate” means one variable (e.g. x).

​

Paste slide here

Link to video at this slide

Polynomial Commitment Schemes (PCS)

Q&A

• …

​

Insights:

• (Paul) I made a video with a less technical introduction to the concept of a polynomial commitment scheme for RISC Zero Study Club – link here. Also here’s Justin Drakes’ video on the topic.
• [Paul] Everything is built on finite fields. Depends on assumptions: discrete log is hard, hashes are collision resistant.
• Elliptic curve group is a collection of solutions to an equation defined over a finite-field.
• Pairings here refer to a pair of related elliptic curve groups
• All of these constructions are built on top of finite fields.

Paste slide here

Link to video at this slide

KZG PCS Setup & Commitment

Q&A

• Q1 (dbrans): It looks like G and ⍺ are both integers and is an integer. So why can’t we recover ⍺ by dividing: H_1 / H_0?
• (Paul) What’s lambda?

​

Insights:

• Revisiting slide 8 here, we walk through KZG’s setup, commit, eval.
• Shows how comf is evaluated even without knowing ⍺. comf is small, usually under 64 bytes
• Q1 (Kobi via dbrans): a generator for a cyclic group is a point and not an integer. You cannot divide points
• [Paul] Group is like a set of elements with a single operation (in this case addition) which is reversible. So no division. Field, however has +, -, * and /. Rings have two ops, only one of which is reversible.
• [bankisan] Group we can + and -. But we can’t * and /.
• [Venky] division operation does not exist.
• lambda is amount of bits of security.
• [arro] com_f is taking pp and using it to compute f(alpha) * G.

​

Paste slide here

Link to video at this slide

KZG PCS Evaluation

Q&A

• How is ⍺ used if it was destroyed?
• Why is this secure, binding and SNARK? (Extra work)
• [bankisan] u, v are public inputs and outputs? [Paul] u is the input and v is the output.

​

Insights:

• Proof is a single group element in the group G
• [Dan’s Answer] to q above: a new structure called Pairings, verifier needs G + H1, Verifier only needs these 2 elements.
• Determining q(X) can be computationally expensive
• G = cyclic group
• [paul] Pairing refers to a pair of groups.
• [bankisan] (alpha - u) * com_q can only be done in paired space?

Paste slide here

Link to video at this slide

Example:

f(x) = 3x^2 - 4x + 2

u = 2

f(2) = 12 - 8 + 2 = 6, so v = 6.

f(u) - v = 0

f(2) - 6 = 0

3x^2 - 4x + 2 - 6 = 0

(x - 2) (?) = 0

(x - 2) (?) = 3x^2 - 4x + 2 - 6

(x - 2)(3x + 2) = 3x^2 - 4x + 2 - 6

q(x) = 3x + 2

KZG PCS Generalizations

Q&A

• What is k-variate? [brian, Venky] k variables.
• [Li] Batch proofs - multi-open?

​

Insights:

• Can be used to commit to k-variate, not only univariate
• [Paul] if P wants to commit to multiple polynomials and multiple opening of polynomials at different points, P can use a single proof of constant size. “batching = compress a bunch of things sinto a single thing”

Paste slide here

Link to video at this slide

Dory PCS

Q&A

• [Arro] how much is Dory used? [Paul] KZG and FRI are the PCSs that are most used.

​

Insights:

• Dory exists as a possible replacement for KZG, has no TS but isn’t as performant

Paste slide here

Link to video at this slide

Polynomial IOP Setup

Q&A

• What does ‘s’ in f_-s stand for and how is it determined?
• Also, is S_p = S_v = (f₀, f_-1, …, f_-s)? Or is this only for S_v?

​

Insights:

• [Margulus] ‘s’ in f_-s is just an index and means there are ‘s’ commitments. ��S_p ≠ S_v , it’s only for S_v . To recall what S_p (proving key) represents, reference lecture 1 (slide 15) of our notes.

Paste slide here

Link to video at this slide

Polynomial IOP Evaluation

Q&A

• …

​

Insights:

• Nico: the boxes can be considered Oracles: it has the magic power of evaluating a polynomial instantly. Commitment fakes that. Rather than the verifier doing the work, the prover does it for them. So verifier doesn’t have to do the work. In the real world, we don’t have oracles. The prover behaves as the oracle.

Paste slide here

Link to video at this slide

Polynomial IOP Properties

Q&A

• Are we assuming that P* is computationally bounded? (Otherwise it won’t be a SNARK, correct?) (dbrans) – The succinct requirement of the SNARK constrains the size of the proof and the time to verify the proof. It does not constrain the Prover in any way.
• How does extractor for this use case look.

​

Insights:

• Nico: Extractor depends on the IOP. There is no general construction. There should be one in the Marlin and Plonk papers.
• Paul: in general, extractor has a “rewind” power that allows it to play multiple different scenarios.

Paste slide here

Link to video at this slide

The Resulting SNARK

Q&A

• …

​

Insights:

• …

Paste slide here

Link to video at this slide

HW Question 1:

Answer Key:

In this video, Dan suggests a homework exercise

​

Here is the challenge summarized:

​

1. Given a multilinear commitment schema, how would you build a polynomial commitment scheme from it? Dan notes that this can be done “directly and very efficiently”.�
2. Similarly, given a linear commitment, how would you build a multilinear commitment from it?

​

​

Additional questions & resources

• Paste your questions and resources here
• ​

Next Week

1. Watch Module 2: Building a SNARK 2/2

​

• Next assignment
1. TBD
2. Due before next study group

​

• Come with 1 discussion question for next week for the group (in case we don’t have a guest speaker)

​

• Send feedback/improvement requests to Discord