相关概念

计算完整性(Computational Integrity， CI)

简单来说，就是表示某次计算的输出是正确的。CI可以使我们能够信任别人提供给我们的账单或账户余额。

代数中间表达(Algebraic Intermediate Representation, AIR)

证明系统

证明系统最早起源于1985年的交互式证明(Interactive Proof，IP)模型，这个协议涉及两个实体：证明者和验证者。他们通过发送消息进行多轮交互。证明者和验证者的目标是相互冲突的：证明者想让验证者相信某个计算的完整性，而验证者是受公众委托的可疑的看门人，肩负着区分真理和虚假的任务。
就好比法院所实施的审查过程时，当一方提出索赔而对方质疑其有效性。为了使声明被真实接受，声明者（证明者）给审查员（验证者）之前询问提供的答案必须一致且有效。审查过程预计会暴露陈述与事实之间的任何不匹配，从而揭露其错误。
一般来说，如果系统从状态A更新到状态B时，并满足以下属性，我们就说证明系统解决了CI：

  • 完整性(Completeness)：如果证明者确实知道如何以有效的方式将状态从A更改为B，那么证明者将设法说服验证者接受更改。
  • 健全性(Soundness)：如果证明者不知道如何将状态从A更改为B，那么验证者将注意到交互中的不一致并拒绝其建议的状态转换。虽然还是有概率使验证者接受到无效证明，但这个概率很小，并且这个概率是一个系统安全参数，可以设置为可接受的水平，如$1/2^{128}$，这个大小几乎与连续赢5次强力球的几率相同。

简介

zk-STARK 的全称是 Zero-Knowl­edge Scal­able Trans­par­ent Ar­gue of Knowl­edge，也就是透明可拓展性零知识证明。与zk-SNARK(Zero-Knowledge Succinct Non-Interactive Argument of Knowledge)简洁非交互式零知识证明很像，但却有着很大不同，下面将来谈谈两者的相关性。

相同点

  • 都实现了对隐私输入的可靠隐藏
  • 都基于知识论证
  • 都实现了交互式与非交互式的算法

不同点

zk-STARK

  • 可拓展性(Scal­able)：stark的证明时间呈拟线性关系，验证时间呈对数关系。
  • 透明性(Trans­par­ent)：stark没有CRS(setup by Trusted party)

zk-SNARK

  • 简洁性(Succinct)：snark生成的proof足够小，生成与验证时间足够短。
  • 非交互性(Non-Interactive)：证明者生成证明过程中不需要与验证者交互。

除此之外，stark还具有抗量子攻击特性，与简洁性，但stark的简洁性只体现在验证时(验证时的时间消耗为对数阶)，而且stark的证明大小要比snark大的多，差不多是后者的数百到一千倍。
对于给定的计算，STARK 证明器的速度至少比 SNARK 和 Bulletproofs 证明器快10倍。STARK 验证器比 SNARK 验证器快至少2倍，比 Bulletproof 验证器快10倍以上。随着 StarkWare 继续优化 STARK，这些比率可能会提高。然而，STARK 证明长度比相应的 SNARK 长约100倍，比 BulletProofs 长约20倍。

算法比较

SNARK ALG

  • 多项式：$QAPinst(C): \Sigma A_i s_i * \Sigma B_i s_i - \Sigma C_i s_i = H*Z$
  • 算法思想：将证明CI statement成立问题转换成证明多项式等式成立问题，转换过程用到了算术环路和QAP方法；
  • 算法步骤：CRS生成；证明者证明；验证者验证；

多项式成立的意义

  1. 等式两边可以看做两个度为n的多项式，很容易知道，若是两个多项式不等，则两多项式的交点最多有n个。所以，加入在一个很大范围内随机选择一个点，如果两个多项式的值相等，则证明两多项式是相等的。
  2. 等式右边的多项式因子Z是目标多项式，它的零点就是右边整体多项式的零点，同样也是等式左边整体多项式的零点，而等式左边的多项式在这些零点处的取值，就转换成了一个个的算术电路里每个乘法门对应的一阶线性约束等式(R1CS)的成立，也就相当于原始计算等式成立（注：R1CS由原始计算等式分解得到）；

如何保证prover用于生成证明的$A、B、C、H$是多项式且是小于某个度数呢？

  1. 通过trusted party来保证，因为它是可信任的，因此它生成$pk$,$vk$用到的$A、B、C$等肯定是多项式并且是小于某个度的；
  2. 如果证明者作恶，那么验证者将会很大概率验证失败；
  3. 主要用到了同态加密HH和系数知识假设KCA和椭圆曲线双线性配对等数学知识；

STARK ALG

多项式：$Compose \ polynomial \ \psi: Q(x) = \psi (x) * T(x)$

  • 算法思想：将证明CI statement成立问题转化成证明多项式小于某个度的问题。
  • 算法步骤：算术化；低度测试；

多项式成立的意义

与snark类似，T为目标多项式，其零点已知且公开，也是等式左侧多项式Q的零点，多项式Q在每一个零点的取值都对应了一个执行轨迹(execute trace, 与snark中的R1CS对应)的成立。因此多项式相等，也就是执行轨迹正确，也就说明原始CI成立。

多项式小于某个度意味着什么？

与snark类似，两者都把CI statement转换成了证明多项式等式成立的问题。在整个过程中，可能存在攻击者特意生成满足验证等式的一些点，这些点并不是真正的多项式上的点，但是根据这些点生成的证据也能通过验证者验证。不同的是，snark通过trusted party和同态加密等方法，而stark则是使用帝都测试等数学方法。当且仅当多项式真正的小于某个度时，多项式的相等才是真实意义上的相等，说明生成轨迹多项式的execute trace 是正确的，即原始CI成立。

参考文章

https://medium.com/starkware/stark-math-the-journey-begins-51bd2b063c71
https://www.8btc.com/article/512859
https://snowolf0620.xyz/index.php/zkp/561.html