zk-斯塔克是什么？

Question

zk-斯塔克是一种证明零知识的证明系统，与zk-SNARK不同，它不再依赖于“有毒废物”参数被初始化的可信设置。

用外行人的话说，zk的基本构件是什么--斯塔克，它们是如何工作的？

Answer 1

斯塔克是一种透明的零知识证明系统。换句话说，验证者和验证者不需要使用第三个生成的参数来分别生成证明和验证索赔的有效性。相反，zk系统缺乏安全性(这些方案基于通用引用字符串(CRSs))。

让有一个数据中心来回答用户的查询。在这个术语中，这个数据中心不仅要降低对每个查询执行协议的复杂性，而且要在第三方的攻击下安全(通过使用主密钥来泄露信息和损害隐私)。

假设有100万个DNA剖面，数据中心作为一个验证者只想为所有的文件提供一个证明，以使验证者信服。一个疯狂的解决方案似乎是数据中心为每个配置文件提供了一个证明，但它不是有效的(即双重效率)。对于里德-所罗门(RS)纠错码，验证器能够获得与所有DNA剖面相对应的编码功能。对于每个RS码，RS[F, S, \rho]是f: S\to F的函数族，这些函数是对度小于\rho|S|的多项式的求值。准确地说，编码的输出是一个多项式，如果验证者将每个DNA剖面作为输入，则输出等于零(即一个低次多项式的根)。重要的一点是，验证者永远不知道其他配置文件的任何信息。

但是，正如您所知道的，这还不足以让验证者检查声称的函数是好的还是坏的！我的意思是关于施瓦兹-Zipple引理，两个不同的多项式与度d最多有d交点，所以函数f对于999.999的DNA剖面并不是唯一的。此外，验证者需要检查所有的轮廓，以确定函数的有效性(即是一个低次多项式)。STARK白皮书作者所讨论的方法是FRI (快速傅里叶变换里德所罗门交互邻近测试)方案。这是一种解决低贴近度测试问题的方法.该方案试图一步一步地减少S集合中的元素数，通过检查低次多项式而不是原来的结构，使验证者信服。(为了提供更好的可靠性，多项式度选择的次数小于剖面数，例如，为100万个DNA剖面提供10.000度的多项式)

该方案基于交互式甲骨文证明(IOP)系统，验证者选择随机数，验证者为其提供相应的甲骨文访问权限。最后，经过几轮验证，验证者可以判断验证程序声明的正确性。也可以提供非交互式IOP。

临界点是验证者想要产生一个与电路可满足性问题相对应的邻近测试问题的算术化。换句话说，验证者和验证者同意一个电路来分别证明和检查它的执行的有效性。这个术语是基于一些技术来解决这个问题的对数复杂性，而不是NP -完全(3 3SAT是一个NP问题)。我只是在这里提到这些技巧，如果你需要知道更多，发送评论。

电路可满足性\to代数约束满足问题(CSP)、\to 3 3SAT、\to 3-着色问题、\to de-Bruijn图求解3个着色问题等。

有关更多信息：https://www.starkware.co/ https://vitalik.ca/

Answer 2

NP-完备计算完整性关系的知识系统论证中的zkSTARK满足以下性质：

1. 零知识
2. 非互动性
3. 渐近最优效率(多对数证明大小、验证器时间和拟线性证明时间)
4. 透明度(设置中的所有随机性都是公开的)

虽然确切结构的细节是复杂的，但总体思路是构建一个交互式论证系统，在这个系统中，验证者可以自由地以概率方式查询验证者的消息，而不是完整地阅读它们。这种类型的协议称为交互式甲骨文证明(IOP)。如果所有验证者的查询都是从统一分布生成的，那么IOP就可以使用Fiat-Shamir启发式实现非交互。zkSTARK的主要创新之处在于：(1)将计算完整性降为关于Reed-所罗门码的某些语句；(2)为前面提到的语句构造一个非常有效的IOP。