[HN Gopher] Zero-knowledge proofs, encoding Sudoku and Mario spe...
___________________________________________________________________
Zero-knowledge proofs, encoding Sudoku and Mario speedruns without
semantic leak
Author : pixelpoet
Score : 152 points
Date : 2025-03-18 00:56 UTC (3 days ago)
(HTM) web link (vasekrozhon.wordpress.com)
(TXT) w3m dump (vasekrozhon.wordpress.com)
| pixelpoet wrote:
| Supplementary material for their video at
| https://www.youtube.com/watch?v=Otvcbw6k4eo
| CJefferson wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| 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.
| ForTheKidz wrote:
| Graphs don't really capture the entirety of hashmaps and
| other indexing concerns. Other than that yea I agree.
| magicalhippo wrote:
| GP was talking about modelling your problem. A hashmap is
| seldom a good model for a given problem. Typically they're
| "just" an implementation detail.
|
| For example, in some cases it can be useful to consider
| triangles in a 3D model as cyclic graphs of vertices. The
| edges of the triangle correspond to the edges in the graph.
|
| However I can't think of any case where it's useful to
| think of a triangle as a hashmap.
| jon_richards wrote:
| There is a huge category of computer science problems that can
| be solved with the same algorithm (and a conversion). Graph
| coloring is probably the easiest of those problems to explain.
| Ar-Curunir wrote:
| Because in this case we have a relatively simple ZKP for
| 3-coloring.
|
| However what you gain in the simplicity of the ZKP, you lose in
| the reduction to 3-coloring. So nowadays people use ZKPs that
| work with more realistic computation representations, like
| arithmetic circuits
| jrndcnfh wrote:
| Not sure if I grasp your question. It's like asking "why do we
| care about lists or any data structure for that matter"
|
| Graphs are just a very simple generalization of lists. And many
| problems can be easily modelled as graphs
| carra wrote:
| I'd say this was done mainly to help visualize the problems
| better, since this is a learning video. But often problems are
| converted into graphs because it is a well studied field and
| that way you can apply many theorems and traversal algorithms.
| jstanley wrote:
| > 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 wrote:
| 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 wrote:
| Thanks.
| jkaptur wrote:
| 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/)
| tdb7893 wrote:
| 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 wrote:
| How does the verifier gain confidence that the prover has
| solved a particular instance of a sudoku puzzle?
| heinrich5991 wrote:
| They can ask whether the pre-filled fields have the correct
| equal/unequal relationship by testing two of them at a
| time.
| benediktwerner wrote:
| 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.
| jkaptur wrote:
| Ah ha! Thank you for explaining.
___________________________________________________________________
(page generated 2025-03-21 23:02 UTC)