1
$\begingroup$

I know next to nothing about cryptography. From what I have understood, anything that is provable can be done so using a zero knowledge proof (the result seems to be known from the 1980's or so, by S. Micali & al.)

Starting from a given chess position, I want to use zero knowledge proof for a Prover to convince a Verifier that the position contains at least a checkmate in one move. It is assumed that the Verifier doesn't calculate this from the known position.

Chess positions can be simplified to FEN chess notation. Here is a chess position 6Q1/8/8/8/8/8/5K2/7k w - - 0 1 that contains 4 ways to checkmate Black's king within 1 move, so it satisfies the criterion.

From what I understand, I should now transform the problem into a 3 colors map problem. If I can do so and reduce the problem to "if this map can be colored with 3 colors such that no colors are adjacent, then there is at least one checkmate in the given FEN". From there, I understand that the zero knowledge proof would be completed, as the Verifier could ask the Prover to reveal adjacent colors over and over (and the Prover would reset the choice of the coloring between each time).

How can I do this? How can I transform the FEN chess notation into a map, or a graph that would satisfy the conversion problem?

$\endgroup$
32
  • 1
    $\begingroup$ @kodlu I'm not sure why there is so much focus on the FEN. I mentioned it, but it isn't even necessary. It's just one way, of many, to encode a chess position. It's not part of the main question which is simply "how do I prove this chess position contains at least one checkmate, without revealing anything about the move?". There are more efficient ways to encode a chess position (bitboards) and less efficients (PGN), than FEN. I put a FEN here just as an example. $\endgroup$ Commented Mar 2 at 15:53
  • 2
    $\begingroup$ I don't know anything about chess, so I'll just leave a comment here. The 3-colorability proof system isn't probably what you want to use in a practical implementation. Instead, you can think of the game as a program storing a sequence of states encoded in FEN (whatever this is) and each move to the program creates a new state assuming it is legal. Therefore, what you want to prove here is that give some state, you know a move for the appropriate player that will lead to a state that counts a check make (whatever this means). $\endgroup$ Commented Mar 2 at 20:05
  • 2
    $\begingroup$ So just to clarify again, you can think of this as a program or circuit that takes as input, a state, a move, the new state and outputs whether the move is legal and the state is check mate. Once you describe that program, you can implement it using for example the Halo2 proof system $\endgroup$ Commented Mar 2 at 20:08
  • 2
    $\begingroup$ It's an interesting question, but in the example you gave, I couldn't understand what is the purpose of proving whether a chess state has at least one checkmate in a single move. As a prover, what I have to prove to verifier is not whether the state contains mate in a move or not, but that I know that move. So what needs to be proven as an argument here is "there is checkmate in one move and I know it." $\endgroup$
    – NB_1907
    Commented Mar 4 at 0:56
  • 1
    $\begingroup$ Compare it to factorization problem. The fact that you can prove that the given number is not prime and can be factorized does not mean that you know how to factorize this number. $\endgroup$
    – mentallurg
    Commented Mar 4 at 3:29

1 Answer 1

0
$\begingroup$

The question asks for Prover to prove to Verifier a property (exists chessmate in 1 move) about a chess position# they BOTH know. This is not what a Zero Knowledge Proof is designed to solve.

A standard kind of Zero Knowledge Proof aims at proving to Verifier that a property applies (or not) to the position known by Prover, without revealing anything else about that position to Verifier (here: without the Verifier gettign any clue about the position, beyond that it belongs to the set of positions with chessmate in 1 move). That is possible at least in principle. Basically we codify the finite set of operations to determine if the proposition stands or not, and give a ZKP proof of that.

If indeed we assume the position is known by Verifier, perhaps we really want that Prover demonstrates that they know a move that chessmates, without revealing anything about that move. I think that's possible in principle too: Prover gives a zero-knowledge commitment to the move, and a zero-knowledge proof that the committed value chessmates.

In both cases the details are beyond my current expertise, and I can't tell what size the proof would be, nor how hard it's to compute and verify.


Update: My statement above was misunderstood. It's that three things are possible in zero knowledge:

  1. For a position they know, Verifier gets convinced of the value (true or false) of the proposition "exists chessmate in 1 move". No communication with Prover is necessary, all that's needed is Verifier applying a finite set of rules. No crypto is involved. No data in the protocol trivially implies that the protocol is zero knowledge.
  2. For a position they do not necessarily know, Verifier gets convinced of the value (true or false) of that same proposition. They do not learn anything else about the position. This requires communication with Prover. But that's not what the question is about, thus I did not explore ramifications according to if we assume Prover is honest, or a third party knowing the position verifies that Prover is honest, or Verifier gets convinced that Prover is honest (e.g. because Prover committed the position in zero knowledge).
  3. For a position they know, Verifier gets convinced that Prover knows a moves that checksmates. They do not learn anything about which move Prover is thinking about, if there are several.

Update 2: We can also read the question as: For a position they know, Verifier gets convinced that Prover ran an agreed-upon algorithm that determined that "exists chessmate in 1 move". This can be seen as a special case of 2, in the ramification where Verifier gets convinced that Prover is honest, but with reduced work and communication because Verifier knows the position. Since the position is known in advance, that knowledge can not leak, thus as far as I can tell any protocol convincing the Verifier is zero-knowledge (and, like in 1, not one making good use of ZKP). The method of 1 (run the algorithm on verifier side) remains better on every count.


# "position" is in a notation that includes everything needed to decide the valid next moves (including w.r.t. castling and en-passant). Should we generalize to "Chessmate in $n>1$ moves", we may further assume the position was never reached before, and neutralize the 50-moves rule, so that there can't be ambiguity about if a line of play results in a draw.

$\endgroup$
9
  • $\begingroup$ Every provable statement that admits a proof, also admits a 0k proof. Therefore, I believe your 1st paragraph is wrong. The rest of your answer is based on a different problem, or case. $\endgroup$ Commented Mar 4 at 16:30
  • $\begingroup$ @untreated_paramediensis_karnik: I'm not stating that for a given position it can't be proven in zero knowledge that exists chessmate in 1 move. On the contrary: the verifier knowing the position can unambiguously find the status of the proposition "exists chessmate in 1 move" by applying a finite set of rules to the position, without any communication with the Prover, thus in zero-knowledge. It's just that the framework of zero-knowledge proof is of no help here, because the verifier knows the position. Perhaps read after "If indeed we assume" / #3 for what you really are asking. $\endgroup$
    – fgrieu
    Commented Mar 4 at 17:16
  • $\begingroup$ you are making a fallacy in assuming that the verifier can himself verify if there is a checkmate if he knows the position. He may not know the rules of chess. And even if he knew chess, he could still make a mistake. However he will be convinced by a 0k proof. He won't be shown which move(s) the prover has found. $\endgroup$ Commented Mar 4 at 18:06
  • $\begingroup$ @untreated_paramediensis_karnik: it's indeed possible to assume Verifier does not want to apply the rules of chess themselve, only get convinced that Prover applied them. I (now) discuss that in Update 2. Basically it's a proof that some computation was performed. But I do not see what "zero knowledge" means in that context (zero knowledge <=> Verifier learns nothing beyond the proposition proven). Also Verifier will have much more work (thus opportunity of error) than applying the rules of chess, or will need to trust Prover or a third party. $\endgroup$
    – fgrieu
    Commented Mar 4 at 18:52
  • $\begingroup$ The verifier doesn't learn anything about the checkmate move. He can get convinced by asking the prover to reveal adjacent node colors on a graph for example. $\endgroup$ Commented Mar 4 at 19:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.