零知识证明 - 从puzzle解题深入ZK-STARK

STARK零知识证明系统的理解采用github page分享给感兴趣的小伙伴：

https://trapdoor-tech.github.io/zkstark-book/

一切从zkHack的puzzle说起。解题的过程也是ZK-STARK的学习过程。

零知识证明 - zkHack mini挑战赛第一名

这篇文章记录一下团队解题的思路以及学习STARK的过程。方便更多的小伙伴学习零知识证明相关技术。

0 - 预习

zkHack mini的第二道题目相对比较复杂，解题之前需要先详细阅读题目给出的参考资料。

[StarkDEX Deep Dive: the STARK Core Engine]

https://medium.com/starkware/starkdex-deep-dive-the-stark-core-engine-497942d0f0ab

中文翻译：

https://trapdoor-tech.github.io/zkstark-book/StarkDEX-Deep-Dive-the-STARK-Core-Engine.html

这份参考资料比较详细地解释了STARK的证明系统。trace以及约束多项式承诺，构建DEEP多项式，FRI低阶证明等等。即使看懂了这些，解题还是一头雾水，无从下手。别急，一点点的理清楚。

1 - AIR算术化

https://trapdoor-tech.github.io/zkstark-book/AIR/air.html

先从电路的搭建开始，STARK证明系统采用的是AIR算术化方法。Puzzle的电路设计没有问题。不过，通过打印证明的参数，发现证明采用的参数对应的安全等级太低只有2。既然电路没有问题，这个安全等级是个突破口。

2 - 再看STARK证明系统

https://trapdoor-tech.github.io/zkstark-book/chapter_1.html

深入理解STARK的证明系统，了解STARK证明的原理以及安全等级的推算。

3 - 深入理解STARK证明系统的安全性

https://trapdoor-tech.github.io/zkstark-book/chapter_3.html

在深入理解STARK的安全性的同时，查看了不少相关论文。

4 - Cairo虚拟机以及语言

https://trapdoor-tech.github.io/zkstark-book/chapter_2.html

如果直接用AIR编写电路，容易出错。对于大规模电路也不现实。Cario虚拟机是一个方案，方便开发者开发相关电路。

5 - Cairo开发流程

https://trapdoor-tech.github.io/zkstark-book/Cairo_example/frame.html

使用Cairo语言开发电路可以参考这些流程。

其实，在第3步的时候，Trapdoor Tech团队已经成功的解开了Puzzle。对解题的源代码感兴趣的小伙伴，可以查看公开的解题源代码：

https://github.com/Trapdoor-Tech/zkhack-can-you-turn-up-the-heat-winterfell.git

https://github.com/Trapdoor-Tech/zkhack-M1-can-you-turn-up-the-heat.git

对零知识证明技术感兴趣的小伙伴，欢迎交流讨论 :)

本文首发于：https://mp.weixin.qq.com/s/9MkDahDq2mJulzQpYvDFEA