一文详解zk-STARK：运作原理、优缺点和用例

zk-STARK是一种零知识证明系统，表示一个声明是有效的，而不透露任何关于声明本身的信息，被设计为比ZK-SNARK更透明和可扩展，同时仍保持相同的安全性和隐私。更重要的是，zk-STARK不需要进行初始化可信设置。

什么是zk-STARK

zk-STARK（Zero-Knowledge Scalable Transparent Argument of Knowledge，零知识可扩展透明知识论证）在Eli Ben-Sasson、Iddo Bentov、Yinon Horesh和Michael Riabzev于2018年发表的一篇论文中作为SNARK的替代方案引入。

正如论文中所述，STARK（更广泛地说，ZKP）可以为社会带来很大的好处：

“人们的个人信息，例如医疗和法医数据需要保持私有，这是一种人的尊严。但是，旨在保护隐私的面具也可能被委托数据的机构滥用以掩盖谎言和欺骗，从而不公正地伤害公民并削弱对中央机构的信任。

零知识证明系统是一种巧妙的加密解决方案，可以解决个人隐私和机构完整性之间的紧张关系，可以在不损害前者的情况下加强后者。”

zk-STARKS的工作原理

假设现在有一个公开的函数f，一个私有输入x，以及一个公开输入y。在不透露x是什么的情况下，想要证明有一个x能够满足条件f(x)=y。

为了使这个证明具有一定的简洁性，相比于通过计算f本身，我们希望找出一种更快的方式进行验证。

通常来说，简洁地证明计算相关的事情十分困难。如果有一个很复杂的计算，只要将其中任意一位bit(从0改成1)，就能使得计算产生一个完全不同的结果。很难看出如何才能通过一些手段判定其正确性，如果随机采样一个计算轨迹，非常容易就会错过那些比较作恶的节点。

不过，通过一些相当复杂的数学运算，是可以做到的。

有一些数据，将这些数据编码为一条线，从这条线上选出四个点，这四个点中的任意两个都可以重画这条线。

即使你对这些数据做出极微小的改变，保证这四个点的至少三个，可以将这些数据编码为一个1,000,000次多项式，然后在这个多项式上选出2,000,000个点，任意一个1,000,001个点都会恢复原始数据，继而恢复其他点，原始数据的任何一点偏离都会改变至少1,000,000个点。

举个简单的例子来说明：有一个多项式P，对于从1到1百万之间的所有x，P(x)是一个整数且0<=P(x)<=9。把它从数学上转化一下，C(x)为一个约束检查多项式，如果0<=x<=9，C(x)=0。构造C(x)有一个简单的方式:x*(x-1)*(x-2)*…*(x-9)。

这时，问题变成了：证明你知道P，对于从1到1,000,000的所有x，都有C(P(x))=0。让Z(x)=(x-1)*(x-2)*…(x-1000000)，对于从1到1,000,000的所有x，任何等于零的多项式都是Z(x)的一个乘积。

因此，问题可以被再次转化：对于所有的x，证明你知道P和D,满足C(P(x))=Z(x)*D(x)，然后除以Z(x)来得到D(x)。

如何证明

可以把证明过程想象成证明者和验证者之间一个三步的交流过程:

1. 证明者发送一些信息
2. 验证者发送一些请求
3. 证明者再发送一些信息证明者提交（生成一个Merkle树并且将根哈希发送给验证者）从1到10亿之间的所有x，P(x)和D(x)的值。这包含了1百万个点，而0<=P(x)<=9且9.99亿个是状况外的点。

假设验证者已经知道了Z(x)在所有这些点上的值，在获得提交（Merkle根）后，验证者在1和10亿之间随机选择16个x的值，并要求证明者提供这些值上P(x)和D(x)的Merkle分支。

证明者提供这些值，验证者检查两个要件：

1. 分支与之前提供的Merkle根相匹配
2. C(P(x))在所有16种情况下都等于Z(x)*D(x)

如果一个恶意证明者提供了一个坏的P(x)，他们被发现的最小概率是1-10^-32，该方案与计算哈希冲突一样难以欺骗。

zk-STARKs的优缺点

优先

无需可信设置

zk-STARK不需要可信设置即可运行，而是依赖于公共随机性。这减少了用户的信任假设并提高了基于STARK 的协议的安全性。

可扩展的属性

与SNARK相比，STARK的计算和验证速度更快。更重要的是，即使底层计算的复杂性呈指数级增长，zk-STARKs的证明和验证时间仍然很短。

最大吞吐量

与SNARKs一样，STARKs可以通过启用安全且可验证的链下计算来扩展区块链。提交到L1 链的单个STARK 证明可以验证在主链外进行的数千笔交易。

更高的安全保障

zk-STARKs使用抗碰撞哈希（collision-resistant hashes）进行加密，而不是ZK-SNARKs中使用的椭圆曲线方案（elliptic curve schemes）。

这被认为可以抵抗量子计算攻击，使其比SNARK中使用的椭圆曲线更安全。

缺点

更大的证明尺寸

虽然STARKs提供了更快的证明，但缺点是这些证明与基于SNARK的证明相比更大。这使得STARK 证明在以太坊上的验证成本更高，因为计算更大的证明会产生更高的gas 费用。

采用率较低

SNARKs是零知识技术在区块链中的第一个实际应用，这就是为什么它们比STARKs拥有更多的市场份额。大多数ZK rollups使用zk-SNARKs，基于SNARK的ZK 证明的开发者生态系统和工具更大。

尽管zk-STARKs也有知名的支持者，包括以太坊基金会，但他们的采用率较低。因此，开发人员可能会发现使用STARKs构建ZK项目的支持和工具较少。

zk-STARKs用例

以下是使用zk-STARKs的项目。

StarkNet

作为以太坊上的L2 网络运行的通用ZK rollup。StarkNet 允许去中心化应用程序（dApps） 实现无限的可扩展性，而不会损害以太坊的去中心化和安全性。

dYdX

基于以太坊的ZK rollup 项目（兼作去中心化交易所）为加密货币用户和交易者提供快速且低成本的交易、借贷。dYdX 使用STARK 证明作为其安全机制的一部分，保证用户的资金安全。

Polygon Miden

具有EVM 兼容性的基于STARK 的ZK rollup。虽然仍在生产中，但Polygon Miden将成为第一个与EVM兼容的zk-STARK 协议，并允许开发人员迁移以太坊原生dApp以享受L2网络上的可扩展性。