4 ms·

Does 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 pro

Does 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?

elcomet 5y ago
To write a zkp you first need to have a proof. How would your proof look like here ? 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
Kranar 5y ago
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.
- tooltower 5y ago
  > IP is currently believed to be a subset of PSPACE. IP is _known_ to be _equal_ to PSPACE
  - Kranar 5y ago
    Well there you go, Wikipedia confirms that IP = PSPACE, and furthermore that if some assumptions hold about one-way functions, then zero knowledge IP = IP = PSPACE. Thanks for your correction. https://en.wikipedia.org/wiki/IP_(complexity) https://en.wikipedia.org/wiki/IP_(complexity)
aan1092j 5y ago
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 https://en.wikipedia.org/wiki/PCP_theorem This is where zkSNARKS help since they generate a non-interactive + succinct proof.
- omegalulw 5y ago
  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.
  - kevinwang 5y ago
    Isn't this just an ordinary proof, not a zero knowledge proof? And why would you say this is infeasible for large n? NP doesn't mean that verification is hard, it means that verification is easy, no?
- kevinwang 5y ago
  How do you verify a checkmate in polytime? I'd think a candidate sequence of p1,p2 moves isn't a certificate, since it says nothing about whether the losing player still gets checkmated if they make some different moves.
- Kranar 5y ago
  Giving a candidate set of moves that results in a checkmate does not prove that said checkmate was forced. I can provide a candidate set of moves that results in a checkmate after 3 moves (the classic Blitzkrieg), and certainly you can verify that in polynomial time, but that does not mean that it's possible to force a checkmate in 3 moves. 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.
api 5y ago
"I am the Lord thy God!" - God "Prove it!" - Me "aec070645fe53ee3b3763059376134f058cc337247c978add178b6ccdfb0019f" - God
baby 5y ago
Intuitively I would encode the rules of the game, then the program would let you perform N moves (where N is hardcoded in the circuit, or is a public input but then the circuit must allow for N or more moves) and check at the end that there's a checkmate.
deleted 5y ago
[deleted]

elcomet 5y ago

To write a zkp you first need to have a proof. How would your proof look like here ? 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

Kranar 5y ago

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.

tooltower 5y ago
> IP is currently believed to be a subset of PSPACE. IP is _known_ to be _equal_ to PSPACE
- Kranar 5y ago
  Well there you go, Wikipedia confirms that IP = PSPACE, and furthermore that if some assumptions hold about one-way functions, then zero knowledge IP = IP = PSPACE. Thanks for your correction. https://en.wikipedia.org/wiki/IP_(complexity) https://en.wikipedia.org/wiki/IP_(complexity)

aan1092j 5y ago

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 https://en.wikipedia.org/wiki/PCP_theorem This is where zkSNARKS help since they generate a non-interactive + succinct proof.

omegalulw 5y ago
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.
- kevinwang 5y ago
  Isn't this just an ordinary proof, not a zero knowledge proof? And why would you say this is infeasible for large n? NP doesn't mean that verification is hard, it means that verification is easy, no?
kevinwang 5y ago
How do you verify a checkmate in polytime? I'd think a candidate sequence of p1,p2 moves isn't a certificate, since it says nothing about whether the losing player still gets checkmated if they make some different moves.
Kranar 5y ago
Giving a candidate set of moves that results in a checkmate does not prove that said checkmate was forced. I can provide a candidate set of moves that results in a checkmate after 3 moves (the classic Blitzkrieg), and certainly you can verify that in polynomial time, but that does not mean that it's possible to force a checkmate in 3 moves. 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.

api 5y ago

"I am the Lord thy God!" - God "Prove it!" - Me "aec070645fe53ee3b3763059376134f058cc337247c978add178b6ccdfb0019f" - God

baby 5y ago

Intuitively I would encode the rules of the game, then the program would let you perform N moves (where N is hardcoded in the circuit, or is a public input but then the circuit must allow for N or more moves) and check at the end that there's a checkmate.

deleted 5y ago

[deleted]