7
$\begingroup$

I've seen people making lots of distinctions while reading papers about zero-knowledge.
I've seen the term "Argument of Knowledge" that seems to be used as a weaker "Proof of Knowledge": what I understood is that if you talk about the normal soundness property you talk about "arguments", whilst if you talk about the validity property (from Proofs of Knowledge) then you talk about "proofs". Is it correct?

But what confuses me the most, is that I've seen the term "witness" and "proof" used both differently and to express the same concept. I know what a witness is (basically, the secret of the Prover), but i've also heard the phrases:
"P doesn't know a witness, but he knows a proof"
"generating the witness AND generating the proof"
"in Zk-SNARKS, succinctness: the size of the proof is much smaller than the size of the witness".

"Verifying the proof is much faster than directly checking the statement, even given the witness."
This last phrase is really chaotic to me.

So do they differ? If so, what's the difference between "proof" and "statement"?
English isn't my native language, that could be the problem, but please can you clarify all of these terms for me?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

First, it's important to understand that not everyone uses terminology correctly or in the same way. So, you won't find full consistency everywhere. Having said that, I believe that in this case it is quite clear. A witness is a very specific type of proof. Specifically, it is what we call an NP proof that $x\in L$. ($\mathcal NP$ as a complexity class can be looked at in many ways. The "best" way conceptually, in my opinion, is as a class of languages for which statements have efficient written proofs. That is, there exists a (deterministic) polynomial-time verification machine $V$ such that $x\in L$ if and only if there exists a $w$ such that $V(x,w)=1$. However, there are many other ways of proving statements. First, there are statements that we prove that are not in $\mathcal NP$. Second, we may be proving an NP-statement, but we want other properties - like zero knowledge. In such a case, we use an interactive proof. The prover may use the witness, but doesn't send it. Finally, there may be cases (like in a SNARK) where the proof may be shorter than the original NP witness, and we may want proofs where the time that it takes to verify the proof is shorter than the time to run $V(x,w)$ and verify it in the classic NP way, and so on. I hope this makes it clear.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thank you very much Yehuda, yes this helps a lot. I thought that a witness was some secret that allowed a Prover to generate a proof always in a efficient way, if you have it, and i think its "kinda" correct (maybe not always efficient) right? But also the witness can be seen as a proof itself, but an NP one, right? Than the question that comes naturally is: how is it possible that in contexts like SNARKs a proof is shorter and faster than a witness, if the witness is a NP deterministic proof? What can be faster than that? $\endgroup$
    – Andrea Farneti
    Commented Nov 3, 2021 at 12:29
  • $\begingroup$ I mean, i guess to verify a proof P you still need to run V(x, p) like you would run V(x, w), right? And the witness is much powerful than a proof, so how can it be faster? That's my only doubt $\endgroup$
    – Andrea Farneti
    Commented Nov 3, 2021 at 12:38
  • $\begingroup$ Think about P working harder to provide something that is easier for V. Also, unlike NP-proofs, we allow the verifier to sometimes make a mistake (with low probability), and we also allow it to be probabilistic. These things help a lot. $\endgroup$
    – Yehuda Lindell
    Commented Nov 3, 2021 at 13:57
  • $\begingroup$ Ok, so let me know if I understood well because its hard to see the full image: in a interactive protocol, a Witness for it is a proof that will always be accepted from the Verifier, so if you have a Witness you can always prove that x is in L with probability 1, but isn't necessairly really efficient. If you have a proof, instead, you can prove that x is in L with a certain (pretty high) probability. This way, a proof can be faster than a witness. Is this the correct way to view the difference between proof and witness? $\endgroup$
    – Andrea Farneti
    Commented Nov 3, 2021 at 15:10
  • $\begingroup$ Yes. The only thing I would say differently is in the second half where I would refer to a "proof system" involving a prover and verifier. This is different from a witness which provides the analog of a written proof. $\endgroup$
    – Yehuda Lindell
    Commented Nov 3, 2021 at 15:53
3
$\begingroup$

About a couple of side-topics

I believe we speak about "Argument" when a "Proof" of soundness depends on computational assumptions: so Arguments' soundness is weaker than Proofs' one, but often strong enough considering that current applications of cryptography always rely on computational hardness; and the counterpart is that, for example, NP Arguments can be ZK is a stronger way than NP Proofs (Statistically ZK vs Computationally ZK).

"of Knowledge" suffix is used (for both Proofs or Arguments) when the prover holds information that can be extracted efficiently via a "special setup" (special in an analogous way the Simulator is special).

Or try to think it in this way: "soundness flavour" and "knowing something (or not)" are two orthogonal properties, so you could have a "cartesian product" of combinations:

  1. ZK Proof
  2. ZK Argument
  3. ZK Proof of Knowledge
  4. ZK Argument of Knowledge (the "ARK" in ZK-SNARK)

1 and 3 have stronger(*) soundness, 2 and 4 only computational; for 3 and 4 an Extractor exist (that's the recognized way to prove Knowledge) which can efficiently get the information the prover holds (and it doesn't break ZK property in an analogous way the Simulator doesn't break soundness... halting/rewinding and all that stuff..)

so an Argument, which is weaker than a proof from a soundness perspective, can have a stronger Zero Knowledge level of security (statistical) than a proof (computational)? I mean, ok... but how come? Can't see why that would be possible.

If you get the point that "soundness" and "knowledge" are two distinct properties, you would also get that a third distinct property is "zero-knowledgeness", which could depend on former in a way that's not what you are expecting.

I'm only a geek and an avid reader, so I guess you could easily receive many better explanations than mine, however I want to suggest you chapter 4 of Oded Goldreich's Foundations of Cryptography Vol.1 ...really insightful...

(*) not only on statistical "level", in Proofs soundness is proved by logical derivation from context and axioms, so the common "classical/standard" demonstrations

Improve this answer
$\endgroup$
4
  • $\begingroup$ Ok so, basically when you talk about the soundness property on a computational level you use the term Argument, whilst if you define a Knowledge Extractor and prove that a witness exists, you talk about proofs... Or maybe you talk about proofs even without Knowledge Extractors but just the soundness property on a statistical level of security? Other than that, so an Argument, which is weaker than a proof from a soundness perspective, can have a stronger Zero Knowledge level of security (statistical) than a proof (computational)? I mean, ok... but how come? Can't see why that would be possible. $\endgroup$
    – Andrea Farneti
    Commented Nov 3, 2021 at 12:50
  • $\begingroup$ I have tried to answer with a comment, but I needed more space so I edited my previous answer $\endgroup$
    – baro77
    Commented Nov 3, 2021 at 16:15
  • $\begingroup$ Thank you so much, I gave best answer to Yehuda cause that response was the main thing I needed to clear my mind but even yours has been super helpful. Didn't know well the difference between argument and proof before but now I do, so many different terms to learn to really understand Zero Knowledge... I gave you an upvote! $\endgroup$
    – Andrea Farneti
    Commented Nov 4, 2021 at 1:24
  • $\begingroup$ You did the right thing! :) Yehuda is not only prominent in the industry, also belongs to a group of professionals/Professors who donate part of their time here in the community: so offering pills of their teaching activity out of official channel of university classes, as well: not common and praiseworthy, helping to spread quality knowledge. So my thanks to him and others (now I remember @GeoffroyCouteau , but for sure missing many others too). Regarding me, I'm only learning like you, and trying to answer helps me consolidate concepts: thanks for the upvote! $\endgroup$
    – baro77
    Commented Nov 4, 2021 at 14:04

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.