The Color Blind Table Tennis Club

The Color Blind Table Tennis Club

Understanding Zero Knowledge Proof

In the Color Blind Table Tennis Club they have green and orange table tennis balls, but they think they all look the same.

A man walks in the club and says:

– «You know those actually have different colors?»

All the Club members are like:

– «Pft...Yeaah right!»

And so the game is on.

Marking the Balls

So a first approach could be asking Mr. Knowitall to write G on green balls and O on orange balls.

The diligent members of the CBTTC would then shuffle them in a sack and proceed like this:

  1. Pick a random ball from the sack
  2. Make sure Mr. Knowitall can't see the mark on it
  3. Ask him to tell them what color it is
  4. Check if the mark matches with the color he says

The more balls they pick from the sack and the more colors he gets right, the more they convince themselves he can actually tell them apart.

Key Concepts

In this first example, we can already see some key concept behind Zero Knowledge Proof:

  1. The goal is to prove to someone else that you have some knowledge or skill they don't have.
  2. It's based on a sequence of tests. The more tests the subject passes, the higher the chance it actually possesses the claimed skill or knowledge.
  3. The key of the proof lays in the testers' hands because they're the ones that need to take care the subject doesn't see the marks, that the balls are randomly picked from the sack etc.

You Shared Too Much!

With the above method the man would possibly have to mark every single ball in the CBTTC in order to convince the members he can really tell them apart by their color.

So after the guy leaves, them CBTCC members will remain with their marked balls and will be able to tell them apart by the marks on them. This means the man actually passed down (part of) his knowledge to them.

They still can't tell new balls apart, but those old marked ones? Piece of cake!

Make it Zero Knowledge

So let's try this other method instead!

  1. A random member of the club asks the man to give him a green and an orange ball which he holds in separate hands.
  2. The club member hides the balls behind his back and decides whether to switch them or keep them in the same hand.
  3. The club member reveals the newly positioned balls in his hands.
  4. Each time the man has to say if the balls were switched or kept in the same hand.

The more the man keeps guessing, the more the club member that is testing him convinces himself that he can actually tell the balls apart.

This time thought, when the man leaves, the club members will be left with two apparently identical balls and won't have acquired any knowledge from the process.

Zero Knowledge Proof

So with this last method, we had an actual example of a fully fledged Zero Knowledge Proof, with all its key aspects:

  1. It's a proof of possessing some knowledge or skill.
  2. It's done with a sequence of tests.
  3. The more successful tests, the higher is the chance that the subject actually possesses the claimed knowledge or skill.
  4. The key of the proof is actually in the tester's hands as he has to convince himself that the subject couldn't possibly guess the outcome in any other non-genuine way.
  5. Other third parties assisting the test, don't have any way to make sure the two actors involved (the subject and the tester) aren't actually playing a set-up farce.
  6. The test ends when the tester feels positive about the subject genuinity.
  7. When the test is over, nor the tester nor the assisting third parties have gained any additional knowledge over the matter.

Let this sink in for a moment... basically Zero Knowledge Proof is:

A way someone else has to convince himself (but not others) that you actually possess a knowledge you claim to possess, without you giving out any of that knowledge to him (or anyone else).

Next Steps

So know that we have an high-level grasp of what Zero Knowledge Proof is, we can ask ourselves what may be the possible applications of this!

I'll cover practical uses of Zero Knowledge Proof and other ZKP extensions in a future article, so stay tuned!