3 ms·

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

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.

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.