# How can you convince your colour-blind friend that two balls have the same colour?

I was reading about zero-knowledge proofs. I understand how one can convince their colour-blind friend that the two chosen balls have different colours.

Now what happens if the two chosen balls have the same colour - is there a zero-knowledge proof that will convince your colour-blind friend that they are the same colour? If you follow the classic protocol then you will obtain a 50% chance of guessing correctly that the balls were swapped.

However, this does not rule out the case when the balls are different colour and you were simply lying to obtain the same 50% chance of guessing correctly. In other words, your colour-blind friend will not know whether you are lying or telling the truth.

• @YvesDaoust, of course the prover is allowed to lie. That is the very purpose of the "P" in ZKP, a protocol such that if it is followed, a verifier will not be fooled by a prover who does not know the fact but bragging that they know by lying. The protocol is designed to tell those liars. Apr 10, 2022 at 15:29
• You could show that they have the same grey scale value; which would get one part the way there. Apr 12, 2022 at 19:18

#### Summary

Suppose Victor, who is colour-blind would like Peggy, who can tell colours to convince him that two balls (the unknown pair) are the same colour. Assume Victor has another pair (the known pair) of balls that have different colours. All balls are either green or red.

Here is the zero-knowledge proof (ZKP). See later sections for the rigorous specification.

Victor will select one ball from the unknown pair and one ball from the known pair randomly and secretly. Then ask Peggy whether the selected pair are the same colour. Repeat this routine as many times as needed.

If Peggy changes his answer if and only if Victor select a different ball from the known pair, Victor gains confidence that the unknown pair are the same colour. Otherwise, the protocol ends immediately with Victor gaining no information.

#### The setup: preconditions and goals

The ingenious zero-knowledge proof (ZKP) for the case of two balls of different colors is not applicable directly to the case of two balls of the same colour. It turns out the verifier needs to bring two extra balls, at least.

Preconditions:

1. There are two people, Victor and Peggy. Victor is colour-blind. Peggy are allowed to lie in whatever way.
2. Victor has two balls, the known pair, one of which is red and one of which is green. Victor does not know which one is red, however.
3. There are two other balls, the unknown pair. Both are either red or green. Both may or may not be the same colour.
4. All balls are identical except possibly by their colour.

Goals:

1. Victor wants to be convinced of the same-colour-ness of the unknown pair if they are the same color. Victor should not be fooled into believing the same-colour-ness of the unknown pair if they are not.
2. If the unknown pair are the same colour, at the end of protocol, Victor should not have gained any information except that same-colour-ness as long as Peggy did not found Victor had violated the protocol.

#### A simple interactive ZKP that proves two balls are the same colour.

1. Victor selects a ball $$U$$ from the unknown pair and a ball $$K$$ from the known pair. Victor will keep track of $$K$$ and the known pair until the end of step 3 below.

Victor displays $$U$$ and $$K$$ in some random order to Peggy, asking "are they the same colour?" Peggy replies with either "YES" or "NO".

2. Victor selects ball $$U'$$ from the unknown pair secretly and randomly, which may or may not be $$U$$. Victor also select ball $$K'$$ from the known pair secretly and randomly, which may or may not be $$K$$. In any case, Victor knows whether $$K'$$ is $$K$$ or not.

Victor displays $$U'$$ and $$K'$$ in some random order to Peggy, asking "are they the same colour?" Peggy replies with either "YES" or "NO".

3. Note that if the unknown pair are the same colour and Peggy responds correctly, then her two replies are the same if and only if $$K'$$ is $$K$$. If that is the case, Victor becomes more likely to believe that the unknown pair are the same colour. Otherwise, Victor will claim Peggy cannot prove that the unknown pair are the same colour and stop the whole protocol.

4. Victor passes the known pair to Peggy, who passes them back after making sure they have different colours as well as shuffling them randomly secretly. If Peggy find they are the same colour instead, Peggy will claim Victor violate the protocol and stop the whole protocol.

5. Repeat step 2 to 4 as many times as necessary until Victor is convinced that the unknown pair are the same colour.

#### Can Victor just run step 1 repeatedly?

Someone might wonder, can Victor just repeat step 1 with secret and random selections each time, gather the results so that he will know whether the unknown pair have the same colour as one of the balls in the known pair?

That scheme implies that Victor at the end of a successful run of the protocol knows that the colour of the unknown pair is the same as a particular ball in the known pair, a ball that Victor that identify. This is information beyond the same-colour-ness of the unknown pair, even though Victor still does not know the actual colour of the unknown pair. For example, Victor can confidently present three balls of the same color, which is a task that he could not do with certainty had he not known that extra piece of information.

In general, had Victor been able to track the balls selected from the known pair across the whole protocol, he would be able to associate the colour of the unknown pair with one particular ball in the known pair.

These three steps and especially step 4 are designed to prevent leak of knowledge, even if Victor tries to gain extra knowledge without violating the protocol in any way that can be detected by Peggy.

#### There are many other solutions

This answer shows a brilliant simpler solution, assuming the availability of two identical boxes in addition to the required known pairs of balls.

• Updated my answer with more explanation. Step 3, 4, 5 are designed to ensure zero-knowledge. Step 2 alone does not contain any information at all to $V$, unless $V$ keeps track of $B$ and $C$ all along (disregarding step 5), which will lead to leak of extra information. Apr 11, 2022 at 7:38
• I'm confused here. Peggy can see whether $C$ and $C'$ are the same, by seeing their color, right? If so, then in the case $B_1$ and $B_2$ are different, Peggy can tailor their answer to match the situation where $B_1$ and $B_2$ are the same, i.e., by intentionally lying half of the time. Victor won't be able to distinguish whether "$B_1=B_2$ and Peggy simply can't tell" or "$B_1 \neq B_2$ but Peggy is lying". The answer in that Puzzling seems to be able to resolve this (but I'm not sure whether that's truly zero-knowledge, please help me on this) Apr 12, 2022 at 4:28
• @justhalf I was puzzled about that, too. I think the resolution is this: each time Victor is going to show Peggy some balls, he randomly chooses whether to put the B or the C ball on the left. This way Peggy can't reliably tell whether C and C' are the same, because she's not sure which two to compare. Apr 12, 2022 at 5:04
• @justhalf, thanks for pointing out an ambiguity that I did not realize. I should have written something like "Victor shuffles $B$ and $C$ randomly secretly and then displays them to Peggy." and ""Victor shuffles $B'$ and $C'$ randomly secretly and then displays them to Peggy." Apr 12, 2022 at 6:28
• With one additional assumption you can make it a lot easier "Assume both boxes are identical except for their content". Then just use the ZKP method for different balls on the boxes themselves
– Ivo
Apr 12, 2022 at 13:41

## Zero Knowledge

You can't prove the balls are the same if you only have two balls with no means of testing the difference.

This is essentially asking for proof of philosophical zombies (the idea that two physically identical objects are different in some undefinable way, while being identical in every definable way).

Scenario 1: you have a red and green ball. I lie every time, claiming they're the same color.

Scenario 2: you have two red balls. I tell the truth every time, claiming they're the same color.

You don't know the colors, and my claim is the same in both cases, so you can't determine whether my statement is true or false.

## Partial Knowledge

Any method you can use to differentiate the balls defeats the zero knowledge portion, but that might be acceptable in some cases. If you modify the conditions to include a known pair of balls that doesn't match, that gives you extra knowledge (the pair doesn't match) by definition. However, no additional knowledge is gained during each test, so it's zero knowledge given the context of additional starting knowledge.

You have a red ball, a green ball, and an unknown ball (that's guaranteed to be red or green). You already know red and green are different (proven by the Wikipedia method), and now you have a third ball. By keeping track of the balls' positions out of my sight, then asking whether the balls match or not, you can determine whether I'm lying or not.

• If I claim red and green are the same, or that red and red or green and green are different, I can't be trusted to know the difference, end test.
• If I consistently say red and green are different, I'm telling the truth.

There are two scenarios: unknown is red, or unknown is green. First, presume unknown is red.

• Lie: If I claim unknown and green are the same, then you can sometimes show me red and green, and sometimes show me unknown and green. Because I don't know which case is happening (because unknown isn't green), I'll get it wrong about half the time.
• Truth: If I claim unknown and red are the same, you can sometimes show me green and red, and sometimes show me unknown and red. Because I'm consistently able to differentiate green from red, while claiming unknown is red, you can know unknown isn't green (or I would have gotten it wrong half the time).

Second, presume unknown is green, then switch the above tests.

• Truth: If I claim unknown and green are the same, you'll show me red and green or unknown and green and I'll consistently get it right.
• Lie: If I claim unknown and red are the same, you'll show me green and red or unknown and red and I'll get it wrong half the time.

In these cases, you don't know which is red and which is green, but you can build collections of red and green balls and determine which collection a new ball belongs to. Of course, if I constantly lie, you can't get any useful information out of me, but you know I'm lying.

Zero Extra Knowledge: To prevent building collections of red and green balls, you can randomly shuffle the known red and green ball after finishing the protocol. Now, you know the unknown ball matches the known ball I claimed it matched, but you can't use that information to match the unknown ball to any particular unknown ball from a previous or future test.

## Multiple Discrete Colors

The above won't work with an unknown number of colors. However, it will work for a finite number of discrete colors if you have one of each color already. Essentially, you do tests for each color. For all but one color, I'll easily tell the ball never matches. But for one color, I'll claim they match. I can lie when they clearly don't match, but I can't consistently lie when they do match, as above.

For each color, X:

• Compare unknown to colorX. If I claim they're different, move to next X.
• If I claim unknown matches colorX do a test with each other color, Y.
• Do the test as we did with red and green above, but now with colorX and colorY. If I'm telling the truth, my statements will always be correct.
• If I'm lying (i.e., colorX and unknown don't actually match), there will be a particular colorY that does match unknown, and I won't consistently tell them apart.

Again, you can't determine what color a normal person would use to describe each ball, but you can determine which group to put a new ball in. By shuffling the known balls after the protocol, you can prevent building collections of balls, since you don't know which ball from this test matches the unknown ball in a previous or future test.

## Matching the Initial Question Better

The question posits a scenario where I hand you a pair of balls and claim they're the same. Other answers use an independent pair of non-matched balls to test the pair I handed you, and those answers are probably better for general use. However, I went with the idea of using only three balls total, so I'll expand that here since the four-ball solutions already exist.

I'll hand you three balls, call them A, B, and C, and tell you A and B match, while C doesn't. There is still a requirement that you somehow know each ball must be red or green.

• 1,. You use the standard Wikipedia protocol to prove that C doesn't match A (shuffle A and C and if I get it right consistently I can clearly differentiate between them).

• 2a. EITHER use my protocol to prove that B matches A. If it matches A, I was right.

• 2b. OR use the standard protocol to prove that C also doesn't match B. Because C doesn't match A or B, A must match B. If C doesn't match B, I was right.

This is still not zero knowledge in the context of the original question, because you've learned not only that A matches B, but that A and B don't match C. However, I think it's the minimal amount of extra knowledge you can gain while proving A matches B.

This can still be expanded for many colors.

• I hand you balls A, B, [$$C_1$$, $$C_2$$, ... $$C_n$$].
• For each pair in [B, [$$C$$]] you prove that pair is distinct using the Wikipedia method.
• Then you prove that A doesn't match anything but B.

Again, there's the requirement you somehow know there can only be (n+1) ball colors.

## Conclusion

I don't know if any of the above is actually useful in a real-world application, but I think it's a sufficient answer to your question. None of the given answers are truly zero knowledge, but do allow for zero extra knowledge given the modified constraints.

• Thank you, this is really good. I am particularly impressed that you handled the case with multiple colors. Do you mean "finite number of colors" rather than "discrete number of color"? Apr 11, 2022 at 6:43
• You may be interested in my puzzle based on this question. We still don't have a good solution to the bonus part. puzzling.stackexchange.com/questions/115671/two-secret-numbers Apr 11, 2022 at 7:32
• This is not a zero knowledge proof protocol, since it will associate an unknown ball with a particular group of balls with the same color. Apr 11, 2022 at 8:19
• @JohnL.: I feel like that's what I wrote in the answer. Since an actual zero knowledge protocol isn't possible, I expanded it with partial knowledge protocol that might or might not be useful. Apr 11, 2022 at 22:26
• @FirstNameLastName: That answer is essentially John L's answer to this question. In the exact context of this question, neither is zero knowledge, because you learn of two balls/papers that are different, which you didn't know before. If you expand the conditions such that we already have this knowledge, those answers become zero knowledge protocols. I've expanded my answer to also become zero extra knowledge in that context by shuffling the extra balls between tests. Apr 12, 2022 at 21:14

This seems like a simpler-to-explain variant of John L.'s answer.

Victor has four boxes: one contains two red balls (RR), one contains two green balls (GG), one contains RG, and one contains the two unknown balls.

Victor repeatedly shows Peggy one of the boxes at random, and asks her if the balls in it have the same color.

A sufficiently long series of experiments in which Peggy produces correct answers to the first three boxes and a consistent answer "yes" to the fourth box will convince Victor that she is telling the truth and that the answer for the fourth box is "yes".

With the following assumptions it should be easy (which are actually weaker assumptions than the accepted answer I think)

1. All balls are only 1 of 2 colors
2. In addition to the 2 balls (pair 1) that need to be proven to be equal you have 2 additional balls (pair 2), one of each color.

If necessary, first prove to him that the additional balls are in fact different color, using the known ZKP method to do that.

Then simply use that same ZKP method on the pairs of balls. Pair 1 and pair 2 can only be distinguished if pair 1 has the same color balls.

• Upvoted. Note this protocol made it easy for Victor to steal information. He can show a pair of balls, one from the target pair and one from the additional pair, tracking the one from the additional pair. A simple remedy is to require Victor to put each pair in an unbreakable box. The boxes are indistinguishable by themselves. Apr 12, 2022 at 15:44
• @JohnL.: Actually we only need Peggy to put the main balls into an unbreakable box. This then allows Victor to provide the two test balls, that Peggy can agree to use after looking at them. One might wonder whether this is meaningful, as Victor needs to ensure that the main balls' colours are a subset of the test balls' colours, but how can he do this, being colour-blind? Well, here is a 'practical' application: Victor made many balls himself, painting each either red or green, but put all into one bin and lost track of their colours. Now he wants to sell them in pairs of the same colour... Apr 12, 2022 at 18:01
• Peggy is the customer. The protocol is: { (1) P openly picks two pairs from the bin and seals each pair in a transparent bag, before passing them to V. (2) P 'proves' that one pair is same-colour and the other pair is different-colour (via the shuffle-behind-back method). (3) V lets P pick one pair to unseal and pass back. (4) P then 'proves' that this unsealed pair is different-colour. (5) V passes that pair to P, and P openly puts it back into the bin and then covers and shakes the bin. (6) V passes the still-sealed pair to P. } At the end, V is sure that P ends up with a same-colour pair. Apr 12, 2022 at 18:22
• This is zero-knowledge if Peggy is the n-th customer and Victor had made at least (2n+1) balls of each colour. We do need two identical sealable transparent bags provided by P (and that only P can unseal), but P only needs to seal one pair, to be certain that V can't steal information by rearranging the pairs. V can seal the other one. @JohnL: I hope I didn't miss any detail! =) Apr 12, 2022 at 18:36
• @user21820 You also have to assume that a red-green pair cannot be distinguished from a green-red pair. Otherwise, P can pick RG and GR, can distinguish between the two, can prove that one is a different pair and ends up with a different pair at the end. Apr 13, 2022 at 17:28

Interesting! In fact, the following condition from the Wikipedia page: if the statement is false, no cheating prover can convince the honest verifier that it is true, except with some small probability. - makes the things complicated, while the prover can pretend they do not distinguish between the balls.

I think that there are much better solutions to this question than the following mere sketch.

A quite artificial almost-ZKP I have on my mind is as follows. Let us have the two pencils, red and green, such that they are undistinguishable to the verifier, having the colours exactly as the green and red balls (this assumption is greatly artificial, but I do not know how to do better). The prover can convince the verifier that the pencils are really different using the Wikipedia technique. Then they iterate the following step. The verifier marks the two balls by letters using the both pencils in such a way that the marks done with the same pencil are equal on the both balls, but their distribution varies. Say, he marks the first ball with $$A$$ by the red pencil, and with $$B$$ by the green pencil, and the second ball is marked with $$B$$ by the red pencil, and with $$A$$ by the green. So, the sets of the letters are the same: $$\{A,B\}$$. Then the prover must name the two letters forming the set. If the balls have the equal color, then they always succeed in the naming, because the marks done by the pencil with the other color are distinguishable. If the balls have different colors, then the marks done in the corresponding colors are not visible by the prover, and they would not see one of the two given letters.

Besides the assumption of the existence of such pencils, this proof has another flaw, but I do not know whether it is relevant to ZKP. The verifier cannot know which one of the pencils is red and which is green, but in the case the balls have different colours, the verifier can retrieve the information that some ball is the same colour as the given pencil if the prover always names (or at least tries to name) the marks done on the balls. The possible solution is: if the prover cannot name the two distinct letters, they simply reject to guess. Since the prover want to prove that the balls are of the same colour, and does not want to reveal any additional information, it is unreasonable to them to make the false guesses.

Another possible solution (though, somewhat not complete) is inspired by John's L remark about usage of the additional balls. Let us suppose the common knowledge that the balls are taken from a box containing balls of $$n$$ possible colours. Then the prover can take $$n-1$$ other balls from the box (all having distinct colours different from the colour of the two chosen balls) and prove to the reviewer that the colours of these $$n-1$$ balls are all different and that they are different from the colour of the both chosen balls. Then by pigeonhole principle the reviewer will be convinced that the chosen balls must have the same colour. But additionally the reviewer get the knowledge that the $$n-1$$ balls taken from the box by the prover have different colours, and some information leak happens there. I wonder if there is a way to fix it.

• Very interesting answer. It has some assumptions though. You are assuming that the ball colours are red and green, but they could be blue and yellow. Also you are marking the first ball with red and the second ball with green. If the the first ball is red and the second ball is green then they wouldn't see any of the marks. Apr 10, 2022 at 23:42
• @DmitryKamenetsky, yes, I assume the reviewer knows in advance that the pencils are the same colours as can be the balls, and that's the limitation I mentioned. And if the prover provides red and green pencils, but the balls are blue and yellow, then yes, the prover can cheat the reviewer. Under the assumption of the same colour set, it seems that the marking is sound. Every ball is marked by both pencils, thus the prover sees exactly one mark on every ball (the one done by the pencil with the opposite colour). Apr 11, 2022 at 0:18
• If the balls are of the same colour, then the prover will see the whole set of the marks. If they are of the different colours, then the prover will see the same marks on the both balls. For example, reviewer marks ball 1 with A by red and with B by green, and ball 2 with A by green and with B by red. If ball 1 is red and ball 2 is green, then the prover can see both letters B, and if the ball 1 is green and ball 2 is red, then the prover sees both A. Apr 11, 2022 at 0:18

Take two balls A and B of the same color (both red or both green), then take a third ball C of opposite color.

Give all three balls to your color-blind friend and convince them that A and C have different colors, then convince them that B and C have different colors using the known method. During this process, the friend should keep track of all three balls, so in the end, they will still know which ball is A, B and C.

The friend is only color-blind to red and green as per problem statement. So now they know that if C is red, A and B must be both green, and if C is green, A and B must be both red.

• Since the friend knows at the end A and B have a color different from that of C, which is some knowledge different from the same-color-ness of A and B, this protocol is not zero-knowledge proof. Apr 12, 2022 at 15:03
• @JohnL.: That's hardly the biggest problem! Red-green colour blindness means that many colours (including any that is a mixture of the indistinguishable red and green hues) look the same, so this proposed procedure utterly fails even if we don't care to achieve zero-knowledge! Therefore this post should be simply deleted. Apr 12, 2022 at 15:26
• @JohnL.: I've deleted my reply as well, thanks! (This will disappear too.) Apr 12, 2022 at 15:38
• @user21820 Good point! But if we allow for more indistinguishable colors than just red and green, then the accepted solution would not work either: you could trick your friend by picking $B_1$ and $B_2$ of different colors nor red nor green, and your friend would not notice that (without knowledge). Apr 12, 2022 at 16:02
• @GOTO0: The accepted answer explicitly states the assumptions. Yours doesn't. And as already pointed out, it fails to be zero-knowledge. So why keep it around? Apr 12, 2022 at 16:07

What is wrong with following (sorry for missing the obvious)?

First: (as verb) convincing someone of something may give linguistic connotation you want to potentially fool someone of something which is not the case. In ZKP wikipedia page one uses proving and one also use convincing (as adjective) in 'convincing proof'. For what follows, if permitted, I stick to proof

Next, P (prover) wants to prove to (colour-blind) V (verifier) to have the knowledge k where in this case k = 'balls have same colour'. P wants to leak no extra information to V (or to any other spectator)

What is wrong with following ... (similar to different colour): P defines following protocol to be followed by V: each time in a row, V hides balls behind the back, P closes eyes and V swaps balls or not. P looks at one ball and cooperates (after all P wants to prove something to V) by, as a perfect thinker guessing if balls were swapped or not. If balls have same color, there is no way P can always guess correctly. So P will soon one time in the row guess incorrectly. The protocol could continue and probability of P guessing correctly would converge to $$0.5$$. But, isn't a single incorrect guess a proof? Because probability to always guess correct is zero.

• If we trust that P can't lie, we can just ask P if they're the same color. The proof only matters if we don't trust P, but trust that the balls are identical in every respect except possibly color. If P can lie, P can simply flip a coin for each guess and you get the same result whether the colors are the same or not. (I think I made the same comment on your Puzzling thread answer.) Apr 11, 2022 at 22:46
• What if the colors are not the same though? P can still respond randomly, making it look like they're the same, but they're not. Since the case where the colors are the same and the case where they're different but P lies both have the same result, V can't be assured which of those two cases is occurring. Apr 11, 2022 at 23:15
• If V doesn't know they're the same, then the protocol V is using can't assume they're the same. Otherwise there's no point in having a protocol, since V would already know they're the same. So V's protocol must account for both the scenario where the balls are the same and the one where they're not. V being colorblind just prevents the solution "V looks at the balls and sees what color they are". The question could also stipulate that V can't look at the balls. Apr 11, 2022 at 23:34
• At the end of the protocol, V knows that P claims the balls are the same color. But V knew that before the protocol started. If V can trust P, P's claim is sufficient. The point is that V doesn't trust P, so V wants to come up with a way to differentiate between P lying and P telling the truth. Since the result of this protocol is the same in both cases, V can't tell which is which, so P has proven nothing except P's claim. Apr 11, 2022 at 23:50
• Bear in mind that these sorts of questions are often designed for things like cryptography. I want to know your server is legit, and you want to know my password is legit, but we can't give out all the information or everyone will have it. So the internet comes up with a protocol that keeps some information secret and allows trading other information so both parties are convinced the other party is who they claim to be. So both V and P want a protocol that prevents some random other guy from cheating in the real world, rather than actually mistrusting each other. Apr 12, 2022 at 1:15