2
$\begingroup$

I would like to know if I am understanding this correctly. Zero-knowledge proofs need a prover, verifier and witness.

So if we have a blockchain where person A pays person B 100 dollars. In blockchain, is person A the prover? It proves to the other nodes (the verifiers) that person A has 100 dollars. A witness applies a hash function to the verifier..

Am I understanding this wrong?

$\endgroup$
3
$\begingroup$

I think you are mixing concepts.

In an interactive proof system, you have two communicating entities: the prover and the verifier, where the prover tries to convince the verifier about the validity of some statment.

The witness you mention is not another entity. To understand that, we need to know what kind of problems make sense to be dealt with in a proof system, which are the problems in the so called Non-deterministic Polynomial Time class, or $NP$ for short. Imagine all problems (not only those in $NP$) as being described by a string $x$. A problem $x \in NP$ has the additional property that, it can actually be efficiently verified to belong in $NP$ when you are given a value $w$ related to this $x$. More interestingly, if you are not given this $w$, it is (conjectured) to be hard to decide whether or not problem $x \in NP$. This is why these $w$'s are typically called witnesses.

Now, getting back to proof systems, it makes sense that they deal with problems where the prover needs to prove something that is not trivial to obtain. This is where witnesses (and $NP$ problems) come in. So, in order for the proof system to be meaningful, we restrict to $NP$ problems where the verifier cannot do the computation unless she interacts with the prover, who knows a valid witness for $x$.

Summarizing, the prover needs to have a witness in order to convince the verifier of the validity of the ($NP$) statement being dealt with.

A proof system being zero-knowledge further requires that the verifier does not gain any knowledge beyond the validity of the statment. Specifically, that she does not gain any information about the witness being used by the prover.

Note that I have introduced interactive proof systems. But there are non-interactive proof systems too. Actually, these are the ones you most probably want to use in a blockchain. As the name implies, in an interactive proof system, the prover needs to be active during the proof process and several communication rounds take place. But in a blockchain, assuming this would be doable is probably very unrealistic: blockchains are of a highly decentralized nature and you cannot expect the prover to be active at all times (even more assuming that blockchains are expected to last "forever"). In a non-interactive proof system, the prover just "creates" the proof and sends it to the verifier, who can verify the proof without further interaction.

Finally, then, getting back to your payment example: "The prover needs to use a witness in order to demonstrate to the other nodes (the verifiers) that she owns 100 dollars". How is this witness used depends on the nature of the proof and would most certainly not be just a hash function (although using hash functions is one step of a common approach to convert interactive proofs into non-interactive ones which, as I said, would be needed in a blockchain).

Note: I have been extremely vague (and possibly incorrect if we are being strict) when introducing the related concepts, specially in the definition of the complexity class $NP$. If you are interested in precise definitions, I urge you to lookup some more formal source. You can begin with Wikipedia and the links therein, or any textbook on computational complexity theory, or the original works on knowledge and interactive proof systems by Goldwasser, Micali and Rackoff.

$\endgroup$
  • $\begingroup$ thank you for the links. so if i understood the links, the witness is just the extra part which is the cryptography proof of the computation. $\endgroup$ – Lilz Jul 25 '18 at 18:58
  • $\begingroup$ as described 'a valid execution of the computation' $\endgroup$ – Lilz Jul 25 '18 at 18:58
  • $\begingroup$ The witness is the extra information that the prover has (but the verifier does not) and she uses to convince the verifier of the correctness of the statement. $\endgroup$ – Ginswich Jul 25 '18 at 20:54
  • $\begingroup$ ah okay so for instance "witness (for example the address she wants to spend from, the preimage of a hash function or the path to a certain Merkle-tree node)." blog.ethereum.org/2016/12/05/zksnarks-in-a-nutshell thanks understood $\endgroup$ – Lilz Jul 25 '18 at 21:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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