1
$\begingroup$

I understand how the Kate Polynomial Commitment Scheme Evaluation Proof works however, I don't understand what is the purpose of it?

In general, in a commitment scheme, Peggy commits to message & sends the commitment to Victor. The purpose of a commitment scheme is two fold

  • Once Peggy commits to a message, then she cannot change it. At a later stage, when the commitment is opened, Victor can check if the commitment matches the message.

  • When Peggy sends the commitment to Victor, Victor cannot actually see the message till the opening is done.

In the Kate PCS, the message is encoded as a polynomial. After Peggy sends the commitment of the polynomial to Victor. The Opening is going to be when Peggy reveals the polynomial & Victor checks that the commitment matches.

However, the Kate PCS also has an Evaluation Proof - i.e.assuming the polynomial is $f(x)$, then after the commitment is sent to Victor, Victor can ask Peggy to evaluate the polynomial at a value $u$ & prove the evaluation. i.e. if $f(u) = v$, then the evaluation proof proves to Victor that the polynomial originally committed to by Peggy indeed evaluates to $v$ at $u$.

I understood how Kate PCS does this, however I don't understand what's the purpose of this? Of what practical use it for Victor to know the evaluation of the polynomial at one value? I think Kate is used zkSNARKS - but how exactly? In zkSNARKS, the polynomial represents the trace of the transaction. zkSNARKS are non-interactive, so who decides the $u$ at which the polynomial is evaluated & how exactly does it help in verifying the transaction without knowing the transaction. In zkSNARKS, is the evaluation proof of each polynomial which is committed provided at one value $u$ or at multiple values? Though I understand Kate PCS, I am unable to understand at a higher level how it's used in zkSNARKs.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

The evaluation proofs make the Polynomial Commitment (PC) scheme a powerful cryptographic primitive. Below, I'll give two important applications of the evaluation proofs of PC schemes. For more fascinating applications (zero-knowledge sets, credentials, and content extraction signatures), see the KZG paper.

  • Verifiable secret sharing (VSS). In the simplest form of secret sharing, i.e., Shamir's secret sharing, the dealer interpolates a polynomial $f\in\mathbb{F}^{t}_p[x]$, where $f(0)=s$ the secret, and distributes the shares $f(i)$ to party $\mathcal{P}_i$. If at least $t+1$ parties contribute their shares, they can recover the original polynomial, hence the secret value $f(0)$. Additionally, we would like to defend the protocol against malicious dealers (think of MPC applications). For instance, the dealer might send inconsistent shares to the parties. Polynomial commitment schemes and evaluation proofs allow us to build efficient VSS schemes. Imagine that the dealer also sends a commitment $C$ to $f$ and evaluation proofs to each party $\mathcal{P}_i$, proving that indeed $f(i)=z_i$, i.e., the distributed share $f(i)$ is consistent with the committed polynomial.
  • Polynomial-Interactive Oracle Proofs (IOP). In polynomial IOPs the computation is encoded in a polynomial. Typically, the model of computation is arithmetic circuits that consist of numerous addition and multiplication gates. The polynomial encodes the inputs and outputs of each and every gate and also the final result of the computation. The prover commits to this polynomial and sends this commitment to the verifier. Since we want an efficient verifier, the verifier does not have time to check that the computation itself was carried out correctly at each and every step. Instead, the verifier just asks the prover for evaluation proofs. Depending on which poly-IOP we are talking about, in some evaluation proofs the verifier asks for evaluations at random points (Naturally, these protocols can be made non-interactive via the Fiat-Shamir heuristic). The intuition is that if the prover can prove correctly the evaluation proof at a random point, then the prover has the correct polynomial via the Schwartz-Zippel lemma. But there are also evaluation proofs that are asked at designated points, for example, the point that represents the end result of the computation. A really great introduction to the PLONK zkSNARK is this lecture by Dan Boneh, here. Highly suggested!
Improve this answer
$\endgroup$
9
  • $\begingroup$ The intuition is that if the prover can prove correctly the evaluation proof at a random point, then the prover has the correct polynomial via the Schwartz-Zippel lemma - from the SZ lemma, you can prove 2 things - one is if some polynomial is a zero polynomial & if polynomial f(x) is same as polynomial g(x) (by check if f-g is the zero polynomial). But can the SZ lemma also be extended to show that if the prover knows evaluation of the poly at one point, then he does know the poly? Intuitively, it seems so, but the Kate paper has no mention of the SZ lemma & it doesn't seem to use it $\endgroup$
    – user93353
    Commented Jan 21, 2023 at 20:26
  • $\begingroup$ (Cont) Let me rephrase my question. In the Kate PCS, is the point of the eval proof to show using SZ lemma that the Prover knows the polynomial? I don't see this mentioned anywhere in the paper or any other write up of the PCS. $\endgroup$
    – user93353
    Commented Jan 21, 2023 at 20:26
  • $\begingroup$ This property is called knowledge soundness: an extractor machine can indeed extract the right polynomial from the prover if it succeeds in creating a correct evaluation proof. In the original KZG paper, this property was not yet formalized. For a definition of knowledge soundness, see this paper: eprint.iacr.org/2020/081.pdf (Bottom of page 5). It can be shown that KZG indeed satisfies the notion of knowledge soundness. See Appendix B here: eprint.iacr.org/2019/1047.pdf $\endgroup$
    – István András Seres
    Commented Jan 21, 2023 at 20:55
  • $\begingroup$ If I understand you correctly, you are saying that if Prover says he knows $f(x)$ & provides proof for $f(u) = v$ which verifies correctly then the probability that the Prover actually has a different polynomial $g(x)$ instead of $f(x)$ such that $g(u) = v$ is very low assuming $u$ is randomly selectively selected from $F_p$. And this is because of the Schwartz Zippel Lemma, Because as per the SZ lemma the probability that $f(u)-g(u) = 0$ is very low for a randomly selected $u$ unless $f(x) = g(x)$. $\endgroup$
    – user93353
    Commented Jan 22, 2023 at 6:23
  • $\begingroup$ Yes, exactly! Basically, your first sentence is a rephrase of the knowledge soundness definition. $\endgroup$
    – István András Seres
    Commented Jan 22, 2023 at 9:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.