4 ms·

Zero-knowledge proofs, encoding Sudoku and Mario speedruns without semantic leak

160 points by pixelpoet 2y ago

pixelpoet 2y ago
Supplementary material for their video at https://www.youtube.com/watch?v=Otvcbw6k4eo https://www.youtube.com/watch?v=Otvcbw6k4eo
CJefferson 2y ago
This is really interesting! I also like how it shows the 'power' of NP-completeness. Explaining zero-knowledge proofs for colouring is fairly easy. Explaining how to go from 3-SAT to colouring is some nice pictures. Explaining how to go from Sudoku to 3-SAT is 5 minutes work (assuming you understand both 3-SAT and Sudoku already). Together, these things let you do zero-knowledge proofs for Sudoku with no more work, and by a similar process, zero-knowledge proofs for any problem in P.
- pixelpoet 2y ago
  Agreed, it covers a remarkable amount of ground in kind of far-out (to me) computer science topics in an accessible way; I love teaching and have to say, the exposition is excellent. These guys seem really young too, very impressive. I'd definitely recommend watching the video before reading the blog post, ideally!
- eru 2y ago
  Also for any problem in NP! That's useful in practice, because producing zero knowledge proofs is sooo slow. But getting non-deterministic 'hints' can speed up many computations. Crucially, the hints are arbitrary data and do not have to be computed inside the computation-to-be-proven. The most cliche example is probably verifying that a number is compound: you could either run a complicated test, or you could just 'guess' the prime factors and verify your guess via multiplication. Slightly more practical: you can sort in O(n log n) deterministic time. But that's easily beaten by Bogosort: you 'guess' a permutation, apply it to your data, and check if it's sorted. Not only does that finish in O(n) if you 'guess' right, the constant factors are also much better than for a standard sorting algorithm. Of course, your zero-knowledge computation manages to 'guess' the right permutation right away, because it gets a hint from a deterministic computer outside the 'zero-knowledge box' running the classic O(n log n) algorithm. That's still an advantage over running the O(n log n) algorithm directly, because proving computation is so expensive.
behnamoh 2y ago
Can someone explain why we care so much about graphs in various branches of science? Like, why model the problems mentioned in the video as graphs that need to be colored?
- teraflop 2y ago
  It's not so much that we want to model problems as graphs, it's that many problems and situations naturally correspond to graphs. Anything with a collection of objects, where some subset of pairs of objects are "related" to each other, is a graph. In mathematical terms, graphs are essentially the same as binary relations on a set (a generalization of functions). And any time you can think of something as a graph, you can benefit from the wealth of available mathematical and computational tools that apply to all graphs.
  - eru 2y ago
    Graphs are also really simple structures mathematically. After all, an (undirected) graph is nothing more than a ground set and a collection of its two-element subsets. It's the same reason why groups crop up so often: groups are also really simple structures, so it's really easy to satisfy their axioms 'by accident'. Same for numbers in general.
    - whatshisface 2y ago
      I don't think that's a full explanation for groups, because groups other than the free or permutation groups are rather "unlikely," in the sense that they're much smaller.
      - eru 2y ago
        Oh, I mean they crop up in lots and lots of applications, because their structure is so simple to satisfy. Not that they would crop up, if you somehow randomly generated mathematical structure. The real world, and especially the part of the real world that people engage with, seems to have a lot of simple structures.
jstanley 2y ago
> For a clause like x_1 OR x_2 OR x_3, we think of it as “the only forbidden combination is x_1 = \text{FALSE},\; x_2 = \text{FALSE},\; x_3 = \text{FALSE}.” Our task is to construct a gadget that eliminates this one forbidden combination while allowing all others. Here’s how: if both x_1 and x_2 are false (represented as the edge being colored red-blue), the node labeled x_1 OR x_2 must be blue. Similarly, the node labeled x_1 OR x_2 OR x_3 must be blue. You can verify that any other combination is acceptable. I didn't follow this. I also looked at the graph and found that the node labeled "x1 OR x2 OR x3" is in fact connected to a blue node, so it can't be blue? I didn't manage to work out how the clause gadget is meant to work so I can't tell if the graph is wrong or the explanation. > Our zero-knowledge proof was interactive—a back-and-forth conversation between the prover and the verifier. I think possibly the section containing your zero knowledge proof got edited out by accident?
- CJefferson 2y ago
  The graph explanation is saying: The 'x1 or x2 or x3' node can't be blue (as you say, it's connected to a blue node!) It doesn't take too long to convince yourself that if we coloured the right-hand node of x1, x2 and x3 all blue, there is no valid colouring of the 'clause 1' bit of the graph where the 'x1 or x2 or x3' node is not blue -- which means there is no colouring of the whole graph. On the other hand, if I make at least one of the right-hand nodes of x1, x2 or x3 red, then I can colour the 'clause 1' bit of the graph such that the 'x1 or x2 or x3' node isn't blue, so all is fine! They are trying to explain that this graph correctly represents the SAT problem, because it has a valid colouring if and only if the SAT problem has a solution -- and we do this by checking the clauses one at a time.
  - jstanley 2y ago
    Thanks.
deleted 2y ago
[deleted]
jkaptur 2y ago
I didn't quite follow how you can actually prove that you've solved a sudoku via reduction to graph coloring. If I understand correctly, an important part of the graph coloring protocol is that the prover permutes the colors between each round (otherwise the verifier can just iteratively learn the color of every node). But all sudoku puzzles have the same graph structure - a puzzle instance is a partial assignment of colors to nodes. So can't a verifier can gain knowledge about the prover's solution by asking for edges that correspond to known values? (I found a different ZKP protocol for sudoku, but I don't think it relates to the graph coloring protocol: https://www.wisdom.weizmann.ac.il/~naor/PAPERS/SUDOKU_DEMO/ https://www.wisdom.weizmann.ac.il/~naor/PAPERS/SUDOKU_DEMO/)
- tdb7893 2y ago
  I haven't read this particular blog but the solution I remember seeing is you randomly swap the colors each edge verification so each is independent. All the edges are numbers that are required to be different so when you verify they are different you gain no information.
  - jkaptur 2y ago
    How does the verifier gain confidence that the prover has solved a particular instance of a sudoku puzzle?
    - heinrich5991 2y ago
      They can ask whether the pre-filled fields have the correct equal/unequal relationship by testing two of them at a time.
- benediktwerner 2y ago
  The way the conversion is done here, different sudokus produce different graphs. Besides the regular sudoku graph structure, there are nine additional nodes, each corresponding to one number. They are all connected to each other to ensure they must be different and each one is connected to each cell where the corresponding number is present as a clue from the start. This way, the graph doesn't need any pre-coloring to still encode the sudoku including the given clues.
crtasm 2y ago
Neither Sudoku or Mario are mentioned, .. oh there's a linked video - got it.

160 points by pixelpoet 2y ago

Supplementary material for their video at https://www.youtube.com/watch?v=Otvcbw6k4eo https://www.youtube.com/watch?v=Otvcbw6k4eo

CJefferson 2y ago

This is really interesting! I also like how it shows the 'power' of NP-completeness. Explaining zero-knowledge proofs for colouring is fairly easy. Explaining how to go from 3-SAT to colouring is some nice pictures. Explaining how to go from Sudoku to 3-SAT is 5 minutes work (assuming you understand both 3-SAT and Sudoku already). Together, these things let you do zero-knowledge proofs for Sudoku with no more work, and by a similar process, zero-knowledge proofs for any problem in P.

pixelpoet 2y ago
Agreed, it covers a remarkable amount of ground in kind of far-out (to me) computer science topics in an accessible way; I love teaching and have to say, the exposition is excellent. These guys seem really young too, very impressive. I'd definitely recommend watching the video before reading the blog post, ideally!
eru 2y ago
Also for any problem in NP! That's useful in practice, because producing zero knowledge proofs is sooo slow. But getting non-deterministic 'hints' can speed up many computations. Crucially, the hints are arbitrary data and do not have to be computed inside the computation-to-be-proven. The most cliche example is probably verifying that a number is compound: you could either run a complicated test, or you could just 'guess' the prime factors and verify your guess via multiplication. Slightly more practical: you can sort in O(n log n) deterministic time. But that's easily beaten by Bogosort: you 'guess' a permutation, apply it to your data, and check if it's sorted. Not only does that finish in O(n) if you 'guess' right, the constant factors are also much better than for a standard sorting algorithm. Of course, your zero-knowledge computation manages to 'guess' the right permutation right away, because it gets a hint from a deterministic computer outside the 'zero-knowledge box' running the classic O(n log n) algorithm. That's still an advantage over running the O(n log n) algorithm directly, because proving computation is so expensive.

behnamoh 2y ago

Can someone explain why we care so much about graphs in various branches of science? Like, why model the problems mentioned in the video as graphs that need to be colored?

teraflop 2y ago
It's not so much that we want to model problems as graphs, it's that many problems and situations naturally correspond to graphs. Anything with a collection of objects, where some subset of pairs of objects are "related" to each other, is a graph. In mathematical terms, graphs are essentially the same as binary relations on a set (a generalization of functions). And any time you can think of something as a graph, you can benefit from the wealth of available mathematical and computational tools that apply to all graphs.
- eru 2y ago
  Graphs are also really simple structures mathematically. After all, an (undirected) graph is nothing more than a ground set and a collection of its two-element subsets. It's the same reason why groups crop up so often: groups are also really simple structures, so it's really easy to satisfy their axioms 'by accident'. Same for numbers in general.
  - whatshisface 2y ago
    I don't think that's a full explanation for groups, because groups other than the free or permutation groups are rather "unlikely," in the sense that they're much smaller.
    - eru 2y ago
      Oh, I mean they crop up in lots and lots of applications, because their structure is so simple to satisfy. Not that they would crop up, if you somehow randomly generated mathematical structure. The real world, and especially the part of the real world that people engage with, seems to have a lot of simple structures.

jstanley 2y ago

> For a clause like x_1 OR x_2 OR x_3, we think of it as “the only forbidden combination is x_1 = \text{FALSE},\; x_2 = \text{FALSE},\; x_3 = \text{FALSE}.” Our task is to construct a gadget that eliminates this one forbidden combination while allowing all others. Here’s how: if both x_1 and x_2 are false (represented as the edge being colored red-blue), the node labeled x_1 OR x_2 must be blue. Similarly, the node labeled x_1 OR x_2 OR x_3 must be blue. You can verify that any other combination is acceptable. I didn't follow this. I also looked at the graph and found that the node labeled "x1 OR x2 OR x3" is in fact connected to a blue node, so it can't be blue? I didn't manage to work out how the clause gadget is meant to work so I can't tell if the graph is wrong or the explanation. > Our zero-knowledge proof was interactive—a back-and-forth conversation between the prover and the verifier. I think possibly the section containing your zero knowledge proof got edited out by accident?

CJefferson 2y ago
The graph explanation is saying: The 'x1 or x2 or x3' node can't be blue (as you say, it's connected to a blue node!) It doesn't take too long to convince yourself that if we coloured the right-hand node of x1, x2 and x3 all blue, there is no valid colouring of the 'clause 1' bit of the graph where the 'x1 or x2 or x3' node is not blue -- which means there is no colouring of the whole graph. On the other hand, if I make at least one of the right-hand nodes of x1, x2 or x3 red, then I can colour the 'clause 1' bit of the graph such that the 'x1 or x2 or x3' node isn't blue, so all is fine! They are trying to explain that this graph correctly represents the SAT problem, because it has a valid colouring if and only if the SAT problem has a solution -- and we do this by checking the clauses one at a time.
- jstanley 2y ago
  Thanks.

deleted 2y ago

[deleted]

jkaptur 2y ago

I didn't quite follow how you can actually prove that you've solved a sudoku via reduction to graph coloring. If I understand correctly, an important part of the graph coloring protocol is that the prover permutes the colors between each round (otherwise the verifier can just iteratively learn the color of every node). But all sudoku puzzles have the same graph structure - a puzzle instance is a partial assignment of colors to nodes. So can't a verifier can gain knowledge about the prover's solution by asking for edges that correspond to known values? (I found a different ZKP protocol for sudoku, but I don't think it relates to the graph coloring protocol: https://www.wisdom.weizmann.ac.il/~naor/PAPERS/SUDOKU_DEMO/ https://www.wisdom.weizmann.ac.il/~naor/PAPERS/SUDOKU_DEMO/)

tdb7893 2y ago
I haven't read this particular blog but the solution I remember seeing is you randomly swap the colors each edge verification so each is independent. All the edges are numbers that are required to be different so when you verify they are different you gain no information.
- jkaptur 2y ago
  How does the verifier gain confidence that the prover has solved a particular instance of a sudoku puzzle?
  - heinrich5991 2y ago
    They can ask whether the pre-filled fields have the correct equal/unequal relationship by testing two of them at a time.
benediktwerner 2y ago
The way the conversion is done here, different sudokus produce different graphs. Besides the regular sudoku graph structure, there are nine additional nodes, each corresponding to one number. They are all connected to each other to ensure they must be different and each one is connected to each cell where the corresponding number is present as a clue from the start. This way, the graph doesn't need any pre-coloring to still encode the sudoku including the given clues.

crtasm 2y ago

Neither Sudoku or Mario are mentioned, .. oh there's a linked video - got it.