Zero K proof that a chess position contains a checkmate

AI Thread Summary
The discussion revolves around building a zero-knowledge proof (ZKP) to demonstrate that a specific chess position contains at least one checkmate without revealing the checkmate itself. The RISC Zero zkVM is highlighted as a tool that can create such proofs, with an example provided in a GitHub repository that utilizes the shakmaty crate to validate checkmate conditions. The author seeks a detailed understanding of the process, particularly how to convert a chess position represented in FEN notation into a graph suitable for a three-coloring algorithm. This transformation is crucial for proving the existence of a checkmate. The author notes that while using shakmaty can assert the presence of a checkmate, the RISC0 framework offers a more comprehensive zero-knowledge setup, which is currently beyond their understanding.
fluidistic
Gold Member
Messages
3,929
Reaction score
272
Hi people,
It's been years I wanted to post this question here. I would like to build a zero knowledge proof that a given chess position contains at least one checkmate. I know that anything provable admits a zero k proof. I know about https://crypto.stackexchange.com/questions/110939/zero-knowledge-proof-applied-to-a-chess-position and .
I know it's been done already (see https://github.com/risc0/risc0/tree/main/examples/chess):
This code demonstrates a minimal example of how to use the RISC Zero zkVM to make ZK proofs about chess.


The demo uses the shakmaty crate to prove that a chess position has a checkmate without revealing what that checkmate is.
But I would like to understand exactly how to do so, every single step. There are other ways to accomplish it. I think I should be able to transform the problem into a graph/map with 3 colors scheme. I.e. if I can convince the Verifier that I can color the map with 3 colors such that no 2 colors are adjacent, then the proof would be complete. The hard part I don't know how to do is to apply an algorithm to transform a given FEN (or chess position) into such a graph. For example, this position
Code:
6Q1/8/8/8/8/8/5K2/7k w - - 0 1
contains 4 ways to checkmate in 1.
 
Computer science news on Phys.org
You need to feed the FEN into a chess engine, and get it to tell you what all of the legal moves are and what the resulting positions are.
 
pasmith said:
You need to feed the FEN into a chess engine, and get it to tell you what all of the legal moves are and what the resulting positions are.
Not exactly. I could use shakmaty (not even a,chess engine) like risc0 does, to assert whether the FEN contains a checkmate. You don't even need to invoke the command to check all legal moves. However risc0 does more than this, for it is designed to be a real 0k setup. It's over my,head for now.
 
This week, I saw a documentary done by the French called Les sacrifiés de l'IA, which was presented by a Canadian show Enquête. If you understand French I recommend it. Very eye-opening. I found a similar documentary in English called The Human Cost of AI: Data workers in the Global South. There is also an interview with Milagros Miceli (appearing in both documentaries) on Youtube: I also found a powerpoint presentation by the economist Uma Rani (appearing in the French documentary), AI...

Similar threads

Replies
25
Views
4K
Replies
77
Views
12K
3
Replies
105
Views
14K
4
Replies
175
Views
25K
Replies
28
Views
6K
Replies
13
Views
3K
Replies
10
Views
5K
Back
Top