Tôi có thể chứng minh tôi đã giải Sudoku này mà không cần tiết lộ đáp án

Support us on Patreon: http://patreon.com/polylog

I can convince you that I’ve solved a sudoku without giving you any information about my solution. We discuss how to do this using what cryptographers call a zero-knowledge proof, and how the same tricks can be used for almost any other problem you can think of.

Blog post: https://vasekrozhon.wordpress.com/2025/03/17/zero-knowledge-proofs/

Code for the animations: https://github.com/polylog-cs/zero-knowledge-proofs/

Richard Hladík: Script editor, video editor, animator. Site: https://rihl.uralyx.cz/

Tomáš Sláma: Script editor, video editor, animator. Channel: https://www.youtube.com/@YTomS

Václav Rozhoň: Writer, animator, the verifier. Blog: https://vasekrozhon.wordpress.com/

Václav Volhejn: Narrator, animator, script editor, the prover. Channel: https://www.youtube.com/@vvolhejn

Thank you to our beta testers: Matěj, Honza, Filip.

Thank you to Gabor Hollbeck for helping with the video equipment.

Animations: Motion Canvas, a TypeScript library https://motioncanvas.io/

Color palette: Solarized https://ethanschoonover.com/solarized/

Music: Astrisx, Cases to Rest, Thannoid, and ZigZag Heart by Blue Dot Sessions

Mario Speedrun: https://www.youtube.com/watch?v=LmgguleEH3k

0:00 Intro

0:50 Interactive proofs

2:28 Graph coloring

3:22 A simple protocol

6:31 Building the full protocol

10:24 Commitment schemes

12:37 Reducing sudoku to coloring

14:28 General reduction

17:04 Discussion

19:09 Outro