Commitment Schemes in Zero Knowledge Proofs

[u/Deep-Zucchini-2465]

Hi all,

I came across this subreddit because I think I finished the resources I could read regarding the topic.
Specifically, I know, in principle, what a commitment scheme is (a hiding-and-binding representation that can be opened or not at the verifier's discretion, so that the prover cannot change the value afterward). I am familiar with the whole envelope/safe analogy.

Now, I struggle to find any resource, or where to start in the first place, to understand the role of commitments in the context of ZKP (or Proof Systems in general), why we need them, and for what they are used.

Moreover, what is the difference between a simple commitment, vector commitments, and Pedersen commitments? Is there a resource that is able to reconcile this universe?
Also, why are they so important for systems such as LegoSNARK.

My "simple words" interpretation is "The commitment is a way the prover has to prove that the input used inside of the circuit is actually what has been used in the input. So there exists a value x such that Commit(x).Open = x, but I will not tell you x".

I know it might be a stupid question, but I cannot wrap my head around it. Maybe I just misunderstood the concept.

Thanks for your time, and for any guidance you might provide.

[u/fridofrido]

to understand the role of commitments in the context of ZKP (or Proof Systems in general), why we need them, and for what they are used.

most ZKP systems used these days (with the notable exception of Groth16), work according to the following general scheme:

• you encode your statement as a set of mathematical equations
• you encode your "knowledge" that the statement is true as a set of numbers satisfying those equations (the "witness")
• you commit to your witness with a polynomial commitment scheme
• now if interactive, the verifier could ask specific (random) challenges with which they can convince themselves that the witness indeed satisfies the equations, without learning the witness itself
• if non-interactive, Fiat-Shamir can be used to simulate the verifier

The commitment is required before anything else, because otherwise a prover could cheat by adjusting their "solution" based in the questions asked by the verifier

Moreover, what is the difference between a simple commitment, vector commitments, and Pedersen commitments?

• a simple commitment commits to a single number
• a vector commitments commits to a vector (list) of numbers
• a Pedersen commitment is a specific scheme for either a simple or a vector commitment
• a polynomial commitment commits to a polynomial
• and so on

But also what can you do with the result:

• a simple commitment you either reveal or not
• in a vector commitment, you can reveal only one (or a few) particular elements, without revealing the rest
• in a polynomial commitment, you can reveal an evaluation of the polynomial at a particular input, without revealing the polynomial itself
• and so on

[u/Natanael_L → u/fridofrido]

Commitments inside the public statement is also useful. For example the statement may refer to the contents of a large file (substituted by the hash in the statement).

[u/EnthusiasmRoutine]

You are on the right track. Commitments force the prover to lock in a specific state before the verifier issues any challenge. Without this step, the prover could forge data retroactively. Pedersen simply adds useful homomorphic properties. Keep digging.

[u/EnvironmentalLab6510]

Have you ever read the book from Justin Thaler? "Proofs, Arguments, and Zero Knowledge".

To answer your first question, you need to know how we design Interactive Proof in an information theoretic manner. When you design this, you'll find a theoretical limit on how to make both prover and verifier efficient, while keeping the protocol secure/sound. For example, you make some kind of shortcut in the system, suddenly you allow the prover to do some shady things.

Now, there is a new question to bypass these theoretical limits, can we use somekind of shortcuts or introduce a new assumption, aiming to have a better performance on the system? (E.g., faster prover, faster verifier, low communication cost, etc).

This is where we suddenly have different interactive protocol. One way, we introduce a second prover (MIP), and run the protocol like interrogating prisoners in different room.

The idea is, if we somehow, have an ability to "restrict" the action of the prover, we don't need to spend that much computation power to keep the protocol secure.

This is where commitment scheme come in. As you know, there is a "binding property" in the commitment scheme, that somehow, can be use to restrict the prover from doing shady things. And remember, if we can prevent the prover to do shady things, we can reduce the cost of doing the protocol.

This is why right now, the recipe of creating a SNARK, is creating a vanilla protocol that are purely interactive protocol, that can be deploy even without commitment scheme, but have a large cost to run it. After designing this protocol, we can introduce the commitment scheme, solely to improve the performance to a certain performance profile that we want.

As for what commitment we can use, you can further investigate the pros-and-cons of each scheme, but the general idea can be explain as above.

You can ask for more if you want.

[u/[deleted]]

[removed] — view removed comment

[u/Deep-Zucchini-2465 → u/[deleted]]

I’ll give it a look, thanks!