30 行代码实现零知识证明
A quick look at zero-knowledge proofs
别被加密货币的标签吓跑，零知识证明其实与图论紧密相关。我和 Chris 决定抛开复杂的加密概念，直接从 Goldreich 等人的原始论文出发，用 Python 实现了经典的图 3-染色问题验证协议。通过随机置换颜色、哈希加盐（nonce）以及多轮交互式验证，我们仅用 30 行代码就构建了一个无需泄露具体解法却能证明其存在的系统。这个过程不仅揭示了零知识证明的数学之美，还展示了如何在不依赖区块链的情况下，利用基础算法解决 NP 完全问题的验证难题。
如果我说有一种版本的零知识证明与加密货币毫无关系，它涉及图论理论，而且只需要 30 行代码就能实现，你会不会觉得很有趣？
HN 评论区
36- _alphageek
我不觉得 ZKP（零知识证明）或可编程密码学像其他一些评论者说的那样毫无用处。但我确实记得，当初了解到它的性能如此糟糕（专用服务器除外）时，感到非常惊讶，因为人们谈论在其上构建应用的方式让人误以为它已经成熟。在性能问题解决之前，它基本上还是一项理论技术。最近这种情况有改变吗？这不是个修辞问句。
- jackb4040
很棒的文章。我会保存下来，用来向别人解释 ZKP。
一个小修正：
random.randrange(100) 会产生 300 种可能的承诺（3 种颜色对应 100 个随机数）。验证者看到几个被揭示的边之后，就能推算出颜色方案，并暴力破解所有 300 种组合，从而实际上解开了每一个承诺。
如果使用 128 位随机性，例如 secrets.token_bytes(16)，就可以缓解这个问题。
另外，我会用 sha256 代替 hash。Python 的 hash 不被认为是安全的，因为它缺乏适当的抗碰撞性。
- Cider9986
完全没人提到 ZKP 依赖于服务器信任客户端。
ZKP 对大多数安全场景不可行的唯一原因，就是它依赖于你信任客户端向你发送关于数据的真实信息。
在传统安全模式中，用户发送输入，服务器负责验证。
我注意到，当人们提起 ZKP 时几乎从不提及这一点——它基本上只适用于没有权威服务器的点对点场景，或者当该服务器信任“节点”（即客户端）时。