Proving the Existence of Differently Colored Balls through Interactive Zero-Knowledge Proofs

It's a new week, dear subscribers. A new week to properly understand Zero-Knowledge Proofs (ZKP) and what they entail. Today, let's dive into a scenario between two friends, Peggy and Victor. Victor wants to prove to Peggy that he holds two balls of different colors, but Peggy is colorblind. To us, it may seem impossible to prove this to Peggy, but to Victor, it can be done. This scenario is similar to how ZKPs work in reality: through an interactive series of events between the prover and verifier, which increases the probability of the outcome of the proof. This is known as interactive ZKP, which will be discussed further in future articles. There is also non-interactive ZKP, which is more computational. In this type of ZKP, the prover only needs to prove to the verifier once that a statement is accurate.

Today's topic is about Peggy wanting to prove to the color-blind Victor that he has two balls of different colors. He will do this through an interactive series of events known as Interactive ZKP. Let's take a closer look.

On a sunny Sunday, Peggy and Victor went out for some fun. They played table tennis with two balls, a white one and a red one. However, because Victor is colorblind, he can only see the two balls as white. Peggy kept winning even when they used both the white and red ball, but Victor became angry, thinking the white ball was faulty. He asked Peggy to change the ball. Peggy explained to him that there were a white and red ball, and that at least one of them wouldn't be faulty. Victor didn't believe him, so Peggy had to show him that the two balls were different colors.

Peggy's task is to prove to Victor (the verifier) that the two balls are different colors and nothing else. He will not reveal which one is white and which one is red.

Here's how the proof works: Peggy gives the two balls to Victor. Victor places them behind his back, brings one out, and displays it, then places it back and randomly reveals one of the two balls. Victor asks Peggy if he has switched the ball. Peggy will use his ability to see the difference in color to correctly guess whether or not Victor switched the balls with a higher than 50% probability; this means that if the two balls were the same color and indistinguishable, Peggy would only be able to guess correctly 50% of the time by chance alone. However, since Peggy can see the difference in color, his chances of guessing correctly are higher than 50%. This is a way to prove that the balls are differently colored without revealing which one is white and which one is red. By repeatedly doing this process, the probability of guessing correctly by chance decreases while the probability of guessing correctly based on the color difference increases. This will convince Victor that the balls are differently colored even though he can't see the color difference.

The above is a Zero-Knowledge proof because it exhibits the following three properties of ZKP:

1. Completeness: if this process is repeated to Victor multiple times, he becomes convinced.

2. Soundness: there's a 0% chance that Peggy guessed correctly at all times by chance alone.

3. Zero-Knowledge: Victor gains no knowledge of which ball is white or red.

In conclusion, ZKPs allow for a verifier to be convinced of a statement's accuracy without revealing any additional information, and interactive ZKPs, such as the scenario between Peggy and Victor, demonstrate this concept in a real-world example. This scenario shows how Peggy was able to prove to Victor that he had two differently colored balls without revealing which one was white and which one was red, using an interactive series of events, increasing the probability of the outcome of the proof.