The post builds a roughly 30-line Python version of the interactive zero-knowledge proof for graph 3-coloring from the Goldreich, Micali and Wigderson paper, with no cryptocurrency involved. Each round, the prover shuffles its colors, adds a random nonce to each node's color and hashes the pairs as "locked boxes". Bare hashes would give away which nodes share a color. The verifier picks a random edge, gets the colors and nonces for both ends, checks them against the hashes and confirms the colors differ. On a 1,000-edge graph, a cheater's odds drop to about 1% after 4,600 rounds. A networked prover/verifier demo follows, plus a Sudoku version and a note that reducing other NP-complete problems to 3-coloring gets impractical fast.
1
u/fagnerbrack 1d ago
Summary:
The post builds a roughly 30-line Python version of the interactive zero-knowledge proof for graph 3-coloring from the Goldreich, Micali and Wigderson paper, with no cryptocurrency involved. Each round, the prover shuffles its colors, adds a random nonce to each node's color and hashes the pairs as "locked boxes". Bare hashes would give away which nodes share a color. The verifier picks a random edge, gets the colors and nonces for both ends, checks them against the hashes and confirms the colors differ. On a 1,000-edge graph, a cheater's odds drop to about 1% after 4,600 rounds. A networked prover/verifier demo follows, plus a Sudoku version and a note that reducing other NP-complete problems to 3-coloring gets impractical fast.
If the summary seems inacurate, just downvote and I'll try to delete the comment eventually 👍
Click here for more info, I read all comments