How to guarantee that a ZKP was generated honestly?

Question

The following extracts were taken from the Zero-Knowledge Proof page on Wikipedia:

In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that a given statement is true while the prover avoids conveying any additional information apart from the fact that the statement is indeed true. The essence of zero-knowledge proofs is that it is trivial to prove that one possesses knowledge of certain information by simply revealing it; the challenge is to prove such possession without revealing the information itself or any additional information.

If proving a statement requires that the prover possess some secret information, then the verifier will not be able to prove the statement to anyone else without possessing the secret information. The statement being proved must include the assertion that the prover has such knowledge, but without including or transmitting the knowledge itself in the assertion. Otherwise, the statement would not be proved in zero-knowledge because it provides the verifier with additional information about the statement by the end of the protocol. A zero-knowledge proof of knowledge is a special case when the statement consists only of the fact that the prover possesses the secret information.

Reference: https://en.wikipedia.org/wiki/Zero-knowledge_proof

As an example, let's assume that Alice knows that X is 123 and Y is 456, and Alice wants to prove to Bob that X is less than Y. Alice therefore must construct a proof in such a way that X and Y are not revealed to Bob.

Let's assume that the ZKP protocol in question is implemented based on the following assumptions:

• A may be derived from X
• B may be derived from Y
• X cannot be derived from A by either Alice or Bob (Alice can only derive A from X)
• Y cannot be derived from B by either Alice or Bob (Alice can only derive B from Y)

A = f(X)
B = f(Y)

A < B // true

Bob can now verify that X is indeed less than Y purely by computing A < B and without Alice ever revealing X and Y to Bob.

My question is, how does Bob guarantee that A and B are derived from X and Y (and thus, know that Alice is not being malicious) without knowing what X and Y are?

Answer 1

My question is, how does Bob guarantee that A and B are derived from X and Y (and thus, know that Alice is not being malicious) without knowing what X and Y are?

In your scenario, A and B are declared as being commitments to X and Y respectively.

You are correct that with no further information available or steps in the protocol, it is impossible for Bob to know for sure that the commitments have been produced properly. If the commitments are properly blinded to prevent brute-forcing, even if Bob knows what X and Y are, Bob still can't know if the commitments have been produced properly unless Alice wishes to offer proof.

However, there may be certain useful protocols, such as:

1. Alice declares commitments which have been certified by a third party that Bob does trust, and therefore ZKPs involving those commitments are meaningful.

2. Alice declares commitments which have not been certified by any third party, but Alice is required to open the commitments at a later stage in the protocol to reveal the values committed to. The purpose of the commitments is to provide temporary privacy, such as in a one-round auction where Alice does not want a competitor to know her bid until all bids have been placed.

3. Alice reveals a value Z, and then announces that she has split the value Z into undisclosed values X and Y. She provides commitments A and B to values X and Y respectively, and uses the additively-homomorphic property of the commitments (Pedersen commitments have this property) to demonstrate that the sum of the commitments A and B is a commitment to the value Z. This is used in confidential asset protocols where a number of units are divided between parties, and the total number of units is public but the share of ownership of units between parties needs to be private. Alice can prove that more units were given to one person than another person, without revealing how many units each of them were given.