Join Log in
Score:1
avatar Crypto

What is a practical application of evaluating at a point in the Kate Polynomial Commitment Scheme?

et flag
user93353

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.

82
1 + 0
Score:1
István András Seres avatar Crypto
cf flag
István András Seres

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!
+ 9
et flag
user93353
`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
0
Reply
et flag
user93353
(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.
0
Reply
István András Seres avatar
cf flag
István András Seres
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: https://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: https://eprint.iacr.org/2019/1047.pdf
0
Reply
et flag
user93353
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)$.
0
Reply
István András Seres avatar
cf flag
István András Seres
Yes, exactly! Basically, your first sentence is a rephrase of the knowledge soundness definition.
0
Reply
et flag
user93353
Thank you. I am just a little bit confused about one thing - proving the soundness of the **VerifyEval** doesn't require the SZ lemma. The soundness of Kate is based on the t-Strong DH assumption -i.e. the prover cannot produce 2 different polynomials which both evaluate to true on the VerifyEval proof because of the t-Strong DH assumption in the group. So it's SDH which provides the Evaluation Proof & the SZ lemma proves that if the eval proof verifies, then the Prover does know the polynomial which is committed to. Is this right or SDH & SZ lemma two different ways of proving the same thing?
0
Reply
et flag
user93353
i.e.the SDH proves the soundness of the evaluation. And SZ lemma shows that if the prover can evaluate the polynomial at a point, then that proves that he knows the polynomial
0
Reply
István András Seres avatar
cf flag
István András Seres
The t-SDH assumption is necessary to prove the Polynomial-binding property. But knowledge soundness is a bit different. It might be the case that the prover provides correct evaluation proofs, but there is no polynomial in the prover's head when (s)he creates the proofs. For an example of such a PC scheme, see page 212 in this writeup https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf Proving the knowledge soundness of KZG requires either the algebraic group model or some knowledge assumption. See the Marlin paper's Appendix B above for details on the KZG knowledge soundness.
0
Reply
István András Seres avatar
cf flag
István András Seres
The Schwartz-Zippel lemma only comes into the picture when we talk about applications of the evaluation proofs, such as zkSNARKs, especially, poly-IOPs. It ensures that the verifier can ask for a correct evaluation proof only at a single point to test polynomial identity.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.