STARKs 和 SNARKs 到底有什么异同点
区块链中的可扩展性问题，特别是以太坊，出现了两个无处不在的概念：SNARKs和STARKs。几乎每个区块链项目都依赖于某种形式的证明系统，如果初学者对这个零知识证明领域还不熟悉，并计划了解其中的概念和想法，很快就会感到压力倍增，因为这个领域正在不断发展。
zkSNARKs 和 zkSTARKs
ZK - SNARKs是一种密码学协议，旨在生成零知识证明，以验证信息的真实性，而不泄露实际的数据。
该缩写反映了其核心属性，如下：
(1). 零知识：这意味着验证者除了真假之外，对该陈述没有其他知识。
(2). 简明：ZK - SNARK证明足够紧凑，以便Bob可以快速验证。
(3). 非交互式：与早期的零知识证明系统不同，早期的系统需要提供者和验证者之间多次消息交换，SNARK是非交互式的，只需要最初的证明提交。
(4). 论证：SNARK是一个“计算上可靠”的陈述，它满足严格的标准，使得制作欺诈性证明变得非常困难。
(5). 知识：基于SNARK的证明不能通过访问底层数据或证人来生成，确保敏感信息的保密性。
ZK - SNARK协议通常涉及两个关键参与者：
证明者，即声明某条件为真，并给出证明的一方。
验证者，负责验证证明者主张的有效性。
主张中提到的信息通常被称为“证据”（witness）。为了在不暴露这些敏感信息的情况下证明主张的真实性，Alice使用ZK-SNARK机制生成能够使Bob相信主张准确性的证明。
ZK-SNARK的一个实际应用可以在身份验证领域中看到。例如，个人可以声称自己是欧洲公民，而不需披露个人详细信息如护照号码。
另一方面，ZK-STARKs是Zero-Knowledge Scalable Transparent Argument of Knowledge的缩写，与ZK-SNARKs共同目标在于提供一种验证陈述真实性的方法，而不披露有关陈述本身的任何细节。
除了细微的区别外，STARKs表现出与SNARKs许多相同特征。基于STARK的有效性证明是使用保密信息创建的，该信息对验证者来说是隐藏的。类似地，STARK可以用于验证交易的准确性，同时保持交易输入不公开。
那么，这两个概念之间的主要区别是什么？将ZK-STARKs与众不同的主要区别在于其可扩展性和透明性特征：
ZK-STARK之所以称为透明（transaprent），是因为它在操作时不需要涉及公共参考字符串（CRS）的值得信赖的设置。相反，STARK协议利用公开可验证的随机性来建立提供者和验证者之间的交互。
ZK-STARK的可扩展性是一个值得注意的特点，因为无论是证明还是验证的复杂性，都与所涉及的计算复杂性几乎呈线性关系。相比之下，ZK-SNARKs在涉及底层计算的证明和验证复杂性方面呈线性扩展。
在实际操作中，这意味着当处理大量计算任务时，ZK-SNARKs需要更多的时间来生成和验证证明。因此，ZK-STARKs更适用于处理大量交易的应用。
多项式承诺
当涉及到零知识算法（如SNARKs和STARKs）时，人们总会遇到一个基本的密码学概念，即多项式承诺。
承诺是一个公开的值，以两种关键的方式与原始消息安全地关联起来，即计算绑定和隐藏：
承诺者负责创建承诺，将其与消息绑定在一起，同时确保消息保持隐藏。
承诺者最终必须揭示这个承诺，并将消息传递给验证者，使验证者能够确认承诺和消息之间的对应关系。
在多项式承诺的背景下，可以将其视为对特定多项式P的承诺。承诺者有能力证明多项式在特定点z的值满足方程P(z) = a，而不泄露实际的多项式P。
存在各种方案来实现多项式承诺，其中我们重点介绍了KZG（基于配对和椭圆曲线）和FRI（基于哈希函数）。
总的来说，KZG方案在简洁性方面表现出色，它的证明大小和验证时间都保持着O(1)的恒定复杂度，这意味着随着电路规模的扩大，证明的大小不会相应增加。
另一方面，在FRI的背景下，证明的大小与电路的规模紧密相关。随着电路规模的增长，证明的大小也会增加。准确地说，证明和验证时间都遵循O(log^2(d))的复杂度，其中'd'表示电路的大小。
然而，在考虑安全方面时，与FRI相比，KZG方案表现出一定的弱点。这种弱点源于KZG方案中对第三方可信设置的要求，这可能引入潜在的漏洞。
SNARKs: 优点和缺点
利用ZK-SNARKs有三个主要优势，即高吞吐量、紧凑的有效性证明大小和增强安全性。
ZK-SNARKs通过减少以太坊基层的计算负担显著提高吞吐量。由ZK-SNARKs赋能的Rollups可以将每秒交易数（TPS）提升到数千个。此外，ZK-SNARKs通常比它们验证的交易数据要小得多。这种减少缓解了基础区块链的拥塞问题，导致更实惠的gas费用和加快的交易。
SNARK证明的微小大小简化了在主链上的验证。在以太坊上，这意味着验证链下交易的gas费用降低，从而最终降低了用户的Rollup成本。
ZK Rollups由于使用了ZK-SNARKs中固有的最先进的加密安全机制，因此享有更高的安全性声誉。
ZK-SNARK证明遵循计算上的可靠性框架，使欺骗验证者和从事恶意活动变得极为困难。此外，ZK-SNARKs的非交互性确保证明可以被任何一方无需信任地验证，进一步增强了它们的安全性。
另一方面，使用ZK-SNARKs也存在三个主要缺点：需要可信设置、容易受到量子计算攻击的漏洞以及对专用硬件的依赖。
实施ZK-SNARK协议需要创建一个称为公共参数的通用公共参考字符串（CRS）。这些公共参数有助于证明者和验证者之间的安全通信。然而，如果恶意行为者获得了公共参数，他们可能会伪造虚假的有效性证明。一些项目试图通过采用多方计算（MPC），即涉及多个个体生成公共参数来解决这个问题。然而，这种方法要求用户对涉及方的诚信放心，这是一个挑战，因为区块链技术旨在减少对可信机构的依赖。
ZK-SNARK依赖于椭圆曲线密码学（ECC）来加密用于生成有效性证明的信息。虽然ECC目前提供了合理水平的安全性，但量子计算的进展对其安全模型构成潜在威胁。
使用ZK-SNARKs生成有效性证明是一个计算密集型的过程，需要证明者投资于专用硬件。考虑到这些机器的有限可访问性，人们对ZK-SNARK证明过程的集中化问题产生了担忧，因为只有少数人能够负担得起这样的硬件。
STARKs: 优点和缺点
使用ZK-STARK的主要优势包括：无需可信设置、可扩展性、最大吞吐量和强大的安全性保证。
ZK-STARK不需要可信设置，而是依赖公共随机性，从而增强了基于STARK的协议的安全性，并减少了用户对外部实体的信任需求。
与SNARK相比，STARK具有显著的可扩展性优势。特别是，即使底层计算的复杂性呈指数增长，ZK-STARK仍能在大规模上实现更快的计算和验证。
与SNARK类似，STARK通过促进安全且可验证的链外计算，有助于区块链的可扩展性。当单个STARK证明提交到L1链时，它可以验证主链外进行的数千笔交易的完整性。因此，一些知名的ZK Rollup项目采用ZK-STARK以确保链外计算的可信性。
与ZK-SNARK使用的椭圆曲线方案相比，ZK-STARK采用了抗碰撞哈希进行加密。这种加密选择被认为对潜在的量子计算攻击具有弹性，从而增强了ZK-STARK与SNARK中使用的椭圆曲线的安全性。
缺点方面主要有两点：较大的证明大小和较低的采用率。
尽管STARK具有提供更快证明的优势，但与基于SNARK的证明相比，STARK的证明大小较大。这增加了在以太坊上验证STARK证明的燃气费用，使其使用成本更高。
SNARK是在区块链系统中实际应用零知识技术的先驱，使其在市场上占有较大份额。大多数ZK Rollup解决方案利用ZK-SNARK，而基于SNARK的ZK证明的生态系统和工具更加广泛。
虽然ZK-STARK也得到了以太坊基金会等有影响力实体的支持，但其采用率并未达到相同水平。因此，开发人员在使用STARK构建ZK项目时可能会遇到更少的资源、支持和工具。
总结
零知识证明的演进，特别是ZK-SNARKs和ZK-STARKs，标志着隐私保护和可扩展性技术的重要里程碑。正如ZK rollups的日益普及所示，这些密码学技术显然将在推动以太坊等区块链平台的可扩展性方面发挥关键作用。
以其高效和紧凑而闻名的ZK-SNARKs，提供了密码安全和计算效率的令人印象深刻的结合。它们能够简洁地证明交易的有效性，而不泄露敏感数据，已经成为各种应用的首选，尤其是在DeFi领域。
另一方面，具有透明度和量子抵抗性的ZK-STARKs提供了一种引人注目的替代方案。虽然它们可能需要比ZK-SNARKs更多的计算资源，但不能忽视它们解决区块链技术长期安全问题的潜力。ZK-STARKs承诺在量子计算进展的情况下，为隐私和可扩展性提供稳固的基础。
在可扩展性问题上，ZK-SNARKs和ZK-STARKs都将发挥重要作用。选择取决于具体的用例、权衡和不断发展的安全需求。此外，递归SNARKs的出现进一步丰富了可扩展性解决方案的工具包，为研究和开发提供了新的途径。
作者: Ramsès Fernàndez-València
翻译： 杨赟博
来源：https://medium.com/@ramsesfv/starks-vs-snarks-d2e09c4e6069
分享仅供学习参考，若有不当，请联系我们处理
END
2.笔记分享｜组队学习密码学（5）— 密码数学基础：初等数论
推荐4.论文分享｜基于Vector OLE构造的恶意安全的PSI协议（VOLE-PSI）