Understanding Zero-knowledge proofs through illustrated examples
blog.goodaudience.com
Understanding Zero-knowledge proofs through illustrated examples
1–10 of 86 posts
Re: Understanding Zero-knowledge proofs through illustrated examples
#2It's kind of mind-blowing that the universe allows us to do this at all: Convincingly prove that you have a solution to a puzzle without revealing anything about the solution itself.
On the sudoku example, I built out a playable version of zero-knowledge sudoku a few months ago: https://github.com/nalinbhardwaj/snarky-sudoku
It doesn't use the same strategy as the article, but the underlying idea of non-interactive SNARK based proof is the same (just using the more general circom circuit library to compile the constraints into a ZK-SNARK).
Re: Understanding Zero-knowledge proofs through illustrated examples
#3This is partially tangential, but they have misidentified Wanda as Waldo in the original image. In some of the books, there are multiple Waldo characters to be found on the pages. In this image, Waldo is elsewhere.
Doesn't detract from the main ideas and shouldn't be too hard to fix.
Re: Understanding Zero-knowledge proofs through illustrated examples
#4In addition to Nalin's great sudoku example elsewhere, here's a couple of my repos that use SNARKS:
1) Some experiments/learnings https://github.com/JofArnold/zkp-learning-in-public
2) A blockchain-based Dungeon crawler built for a hackathon that uses a SNARK (Circom, snarkjs) to validate that the user hasn't cheated when getting to the end of the maze https://github.com/Derked/FantasyCampaign
Re: Understanding Zero-knowledge proofs through illustrated examples
#5This is partially tangential, but they have misidentified Wanda as Waldo in the original image. In some of the books, there are multiple Waldo characters to be found on the pages. In this image, Waldo is elsewhere. Doesn't detract from the main ideas and shouldn't be too hard to fix.
Nice one, let's call it intentional deeper meaning saying you shouldn't roll your own zero-proof knowledge crypto implementation.
Re: Understanding Zero-knowledge proofs through illustrated examples
#6A while back I came up with a third ZK Where's Waldo protocol [1] that avoids the need to watermark the page or search Alice for contraband, and also has the (usually desirable) property that it's only convincing to Bob.
You instead have Bob randomly choose whether Alice must a) pull off the screen, revealing the original page, or b) punch a hole through to Waldo, but not both. Then you can do any number of rounds of this, with Alice putting the page in a random position each time.
It's only convincing to Bob because bystanders (or rather, anyone not part of the random number generation for which challenge to use) can't rule out the possibility that they conspired to have Bob always pick the challenge that a faker Alice could solve. (Show the original page when the uses the real one, punch a hole when she uses a fake page.)
[1] https://news.ycombinator.com/item?id=15323790
Edit: That original comment gives the "magic formula" for coming up with such ZKPs as well.
Re: Understanding Zero-knowledge proofs through illustrated examples
#7Does anyone know if all provable things are zero-knowledge provable?
As an example: given a chess position, would you be able to construct a zero-knowledge proof that you can force checkmate in N moves or less without revealing anything about the particular moves involved?
If so, what would such a proof look like?
Re: Understanding Zero-knowledge proofs through illustrated examples
#8Does anyone know if all provable things are zero-knowledge provable? As an example: given a chess position, would you be able to construct a zero-knowledge proof that you can force checkmate in N moves or less without revealing anything about the particular moves involved? If so, what would such a proof look like?
The main type of zero-knowledge proofs are a subset (potentially proper subset) of interactive proofs. All problems that have an interactive proof form a complexity class called IP, and IP is currently believed to be a subset of PSPACE.
So no, not all provable statements are zero-knowledge provable if by zero-knowledge proof you mean an interactive proof where no information is transferred.
Of course it's possible that in the future, other types of zero knowledge proofs will be formulated that are not interactive proofs. For example there are zk-SNARKs that are non-interactive and zero knowledge, but they form a subset of IP and in fact are a subset of NP problems.
Re: Understanding Zero-knowledge proofs through illustrated examples
#9Does anyone know if all provable things are zero-knowledge provable? As an example: given a chess position, would you be able to construct a zero-knowledge proof that you can force checkmate in N moves or less without revealing anything about the particular moves involved? If so, what would such a proof look like?
For problems in NP (i.e. for which a solution can be verified in polynomial time), we can construct a Zero Knowledge Proof by reducing it to 3SAT, then constructing a PCP (Probabilistically checkable proof).
T̶h̶e̶ ̶p̶r̶o̶b̶l̶e̶m̶ ̶o̶f̶ ̶d̶e̶t̶e̶r̶m̶i̶n̶i̶n̶g̶ ̶w̶h̶e̶t̶h̶e̶r̶ ̶y̶o̶u̶ ̶c̶a̶n̶ ̶f̶o̶r̶c̶e̶ ̶a̶ ̶c̶h̶e̶c̶k̶m̶a̶t̶e̶ ̶i̶n̶ ̶N̶ ̶m̶o̶v̶e̶s̶ ̶i̶s̶ ̶i̶n̶ ̶N̶P̶,̶ ̶s̶i̶n̶c̶e̶ ̶g̶i̶v̶e̶n̶ ̶a̶ ̶c̶a̶n̶d̶i̶d̶a̶t̶e̶ ̶s̶e̶t̶ ̶o̶f̶ ̶m̶o̶v̶e̶s̶,̶ ̶i̶t̶ ̶c̶a̶n̶ ̶b̶e̶ ̶v̶e̶r̶i̶f̶i̶e̶d̶ ̶i̶n̶ ̶p̶o̶l̶y̶n̶o̶m̶i̶a̶l̶ ̶t̶i̶m̶e̶.̶
The main challenge is the time taken to construct the proof
https://en.wikipedia.org/wiki/PCP_theorem
This is where zkSNARKS help since they generate a non-interactive + succinct proof.
Re: Understanding Zero-knowledge proofs through illustrated examples
#10Does anyone know if all provable things are zero-knowledge provable? As an example: given a chess position, would you be able to construct a zero-knowledge proof that you can force checkmate in N moves or less without revealing anything about the particular moves involved? If so, what would such a proof look like?
For problems in NP (i.e. for which a solution can be verified in polynomial time), we can construct a Zero Knowledge Proof by reducing it to 3SAT, then constructing a PCP (Probabilistically checkable proof). T̶h̶e̶ ̶p̶r̶o̶b̶l̶e̶m̶ ̶o̶f̶ ̶d̶e̶t̶e̶r̶m̶i̶n̶i̶n̶g̶ ̶w̶h̶e̶t̶h̶e̶r̶ ̶y̶o̶u̶ ̶c̶a̶n̶ ̶f̶o̶r̶c̶e̶ ̶a̶ ̶c̶h̶e̶c̶k̶m̶a̶t̶e̶ ̶i̶n̶ ̶N̶ ̶m̶o̶v̶e̶s̶ ̶i̶s̶ ̶i̶n̶ ̶N̶P̶,̶ ̶s̶i̶n̶c̶e̶ ̶g̶i̶v̶e̶n̶ ̶a̶ ̶c̶a̶n̶d̶i̶d̶a̶t̶e̶ ̶…
A simple answer to OPs question should be "Yes". Given a finite number of moves, the state space is finite and thus, e.g. using naive min-max, you can verify if you can force a checkmate. In practice this is infeasible for any large N as this is NP as you noted.