I can press reveal to make sure the prover is being honest in this simulation, but how would I know that in the real protocol? By the edges alone I can't tell whether or not it's randomly assigning different colors.
The part not shown well here is that before your choice, you would receive a "commitment" for each vertex color in the graph for each iteration. The commitment allows the prover to provide a coloring that can't be changed after the round starts, but also where only the values for the chosen edge will have their commitment "opened".
If each round gets you an edge with different colors for each vertex, you can be confident it was able to 3-color the graph. You have the commitments, so the prover can't change the colors based on your requested edge, so if they didn't color it correctly you know there's some probability of getting one of the edge(s) where it had to give both vertices the same color. You can never be 100% sure it didn't lie and then get lucky each round, but you can do enough rounds to reach whatever probability of that makes you satisfied that it's honest.
There's a bunch of committment schemes: https://en.wikipedia.org/wiki/Commitment_scheme , but a simple (although I'm not sure it's ideal) one would be to hash a random value concatenated with the message, transmit the hash as your commitment to that message, and to reveal it send the random value and message so the verifier can confirm the hash comes out the same.
The "message" would have to be each vertex's color, separately, rather than the entire graph's coloring at once. Then when the verifier requests the edge for this round, the prover reveals those the commitments for the two vertices on that edge and only those two.
Since the prover doesn't know which edge will be selected and has to commit one color to each vertex, inspecting one random edge per round is enough. They either committed to a 3-coloring and any edge is valid, or they didn't and there's at least one edge we could pick to reject them. The rest of the graph doesn't need to be revealed for us to either gain confidence that they have a coloring or know for certain they do not.
Interesting! Thanks especially for the link to the Wikipedia page.
So in the demo, the black (uncolored) shape _kind of_ represents the commitment. Although as you pointed out, it doesn't explain how it is verified! Instead of a black shape, it would be a shape made out of hash values that are meaningless until the random number for any one of them is revealed. And the protocol is to only reveal one of them each time?
Exactly, the only difference is that two commitments would be revealed, since each vertex color is committed, if we let them commit to edges instead it would be much easier to lie!
This demonstration is utter nonsense, because it's musing a critical step. By the automorphism of color permutations, all possible non-trivial reaponses are equivalent and prove nothing.
What's missing is that the prover has to send you something like a salted hash of every edge coloring (called a "cryptographic commitment") in advance, so that you can verify that the revealed coloring matches what was already committed.
But since the number of distinct single edge colorings is tiny (6), you could crack the hash easily, so you need a fancier commitment protocol than just a hash, perhaps some sort of mutually trusted hashing oracle that only lets you send one query per proof.
With the second graph, Turbo mode often gets up to 60% or 70% confidence before detecting an issue. That seems odd, since I'd expect most edges in a graph to be colorable and only a few to have issues, so I'd "expect" most graphs to look fine up to that level. Is this an issue with the confidence equation and prior, or is it just expected that nobody would stop until they hit 99%+ confidence?
In other words, perhaps I'm just asking for the answer to Exercise 2!
I suppose if you choose edges at random, then it's as likely to fail early as it is to fail late. So if you get to 70% confidence, that does seem reasonable to believe it's probably 3-colorable (but still with a big chance that it is not).
One thing I do not understand and would like to learn more about is zero-knowledge proofs is that their soundness seems to rest on the data-generating mechanism. Suppose you had an adversary Alice who claims to possess a constructive proof that graph-isomorphism [1] is in P. Secretly, she has proven that graph-isomorphism is NP-complete, but only for a vanishingly small family of graphs, and almost all random graphs are polynomial-time distinguishable. Unless you had prior knowledge of these pathological cases, you never consider sampling graphs from that class, and for every triplet G, K, H, you do propose, Alice will almost surely distinguish the isomorphic pair in polynomial time, despite her claimed proof being incorrect. How would you design a ZKP to test her assertion?
One difference seems to be in the size of the domain. In the interactive example, you know the possible edges to begin with, and selecting them is straightforward. The confidence is calculated based on that. For graph isomorphism, you would have little confidence that you can pull from the full set of graphs, and so you would have a hard time building confidence.
If there is a way around that, I'm genuinely curious as well.
That’s a great question. One idea would be for Alice to generate a machine-checkable proof of her claim (e.g. in Coq or something). Instead of playing the typical game where she distinguishes graphs, we just do a secure two-party computation to check the proof, where Alice’s public input is the claim, and her private input is the proof.
You may be interested in Mahaney's Theorem (https://en.m.wikipedia.org/wiki/Mahaney%27s_theorem), which 'answers' a special case of this: If by vanishingly small you mean polynomial size, and you also assume Alice has an algorithm that can distinguish the two subclasses of graph isomorphism, then P=NP if Alice has these facts. By 'distinguish', I specifically mean that Alice has a polynomial time algorithm that will tell you, for an input of graph isomorphism, is it part of a subclass of graph isomorphism which is NP-complete, and which has polynomial size.
This is useful information, thank you for sharing this theorem! I am still skeptical about the soundness of the verifier's challenge generating mechanism. Assuming P!=NP and the challenge is drawn uniformly from the full space, I am still not convinced that the prover does not have access to a backdoor which makes the challenge "easier" on average than the challenger realizes.
Even if challenge instances are superpolynomial in the worst case, empirically, we know from SAT solving competitions that a very small fraction of randomly sampled k-SAT instances are truly hard and most are in P. It is nontrivial to design a challenge whose average case is superpolynomial, and there are many open questions in the field of average-case complexity [1].
I would be very skeptical that the challenge generator is not somehow poisoned. Even if the prover did not collude with the protocol designer to poison it directly, if she can infer any information about the internal state of the verifier from the instances he proposes, she may be able to solve future challenges much more easily than would be possible by random chance.
As expected, since the confidence level is determined by the number of times the protocol is executed, not which edges are chosen. Each time you select an edge you are opening a brand new commitment to the (claimed) coloring of the graph, so even if you choose the same edge every time you are actually checking different commitments.
Oddly, YouTube recommended me a Numberphile video about this a couple of days ago - "Zero Knowledge Proof (Avi Wigderson)" from Feb 2021. Covers the same kind of ground although extended to "you can turn any proof into a 3 colour graph and use that in your zero knowledge proof" areas (in which I am completely bereft of knowledge.)
24 comments
[ 13.9 ms ] story [ 824 ms ] threadIf each round gets you an edge with different colors for each vertex, you can be confident it was able to 3-color the graph. You have the commitments, so the prover can't change the colors based on your requested edge, so if they didn't color it correctly you know there's some probability of getting one of the edge(s) where it had to give both vertices the same color. You can never be 100% sure it didn't lie and then get lucky each round, but you can do enough rounds to reach whatever probability of that makes you satisfied that it's honest.
Since the prover doesn't know which edge will be selected and has to commit one color to each vertex, inspecting one random edge per round is enough. They either committed to a 3-coloring and any edge is valid, or they didn't and there's at least one edge we could pick to reject them. The rest of the graph doesn't need to be revealed for us to either gain confidence that they have a coloring or know for certain they do not.
So in the demo, the black (uncolored) shape _kind of_ represents the commitment. Although as you pointed out, it doesn't explain how it is verified! Instead of a black shape, it would be a shape made out of hash values that are meaningless until the random number for any one of them is revealed. And the protocol is to only reveal one of them each time?
But since the number of distinct single edge colorings is tiny (6), you could crack the hash easily, so you need a fancier commitment protocol than just a hash, perhaps some sort of mutually trusted hashing oracle that only lets you send one query per proof.
In other words, perhaps I'm just asking for the answer to Exercise 2!
[1]: https://www.scottaaronson.com/papers/philos.pdf#page=37
If there is a way around that, I'm genuinely curious as well.
Even if challenge instances are superpolynomial in the worst case, empirically, we know from SAT solving competitions that a very small fraction of randomly sampled k-SAT instances are truly hard and most are in P. It is nontrivial to design a challenge whose average case is superpolynomial, and there are many open questions in the field of average-case complexity [1].
I would be very skeptical that the challenge generator is not somehow poisoned. Even if the prover did not collude with the protocol designer to poison it directly, if she can infer any information about the internal state of the verifier from the instances he proposes, she may be able to solve future challenges much more easily than would be possible by random chance.
[1]: https://arxiv.org/pdf/cs/0606037.pdf
https://www.youtube.com/watch?v=5ovdoxnfFVc