30 行代码实现零知识证明

A quick look at zero-knowledge proofs

别被加密货币的标签吓跑，零知识证明其实与图论紧密相关。我和 Chris 决定抛开复杂的加密概念，直接从 Goldreich 等人的原始论文出发，用 Python 实现了经典的图 3-染色问题验证协议。通过随机置换颜色、哈希加盐（nonce）以及多轮交互式验证，我们仅用 30 行代码就构建了一个无需泄露具体解法却能证明其存在的系统。这个过程不仅揭示了零知识证明的数学之美，还展示了如何在不依赖区块链的情况下，利用基础算法解决 NP 完全问题的验证难题。