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?
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?
https://en.wikipedia.org/wiki/PCP_theorem
This is where zkSNARKS help since they generate a non-interactive + succinct proof.
To the best that anyone knows, for a generalized chess board of size WxW, to demonstrate that a checkmate can be forced in at most N moves, you'd need a candidate set of almost every possible sequence of N moves. You can prune some sequences, but not enough to bring the size of the candidate set down to something that can be verified in polynomial time.
Chess, depending on how you generalize it, belongs to EXPTIME.
"Prove it!" - Me
"aec070645fe53ee3b3763059376134f058cc337247c978add178b6ccdfb0019f" - God
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.
IP is _known_ to be _equal_ to PSPACE
Thanks for your correction.
In the case where you prove existence, it's easy as just knowing the object is a proof. Here it's not really a proof of existence, it's more complex.
The only proof acceptable here would be the whole tree starting from this point. This seems too complex to use in a zero knowledge proof