当前位置：首页 > 区块链

什么是 STARK 的证明大小？为什么比 SNARK 大？

95272周前 (09-18)区块链29

零知识证明技术是现代密码学领域的重要突破，它允许一方（证明者）向另一方（验证者）证明某个陈述是真实的，而无需透露除该陈述真实性之外的任何信息。在区块链、隐私计算、身份验证等领域，零知识证明技术正发挥着越来越重要的作用。

在众多零知识证明方案中，STARK和SNARK是两种最具代表性的技术。它们各自有着独特的优势和适用场景，而证明大小作为衡量零知识证明效率的关键指标，直接影响着这些技术在实践中的可用性和性能表现。本文将深入探讨STARK和SNARK的证明大小问题，分析为什么STARK的证明通常比SNARK大，以及这一差异背后的技术原理和实际影响。

零知识证明基础

零知识证明（Zero-Knowledge Proof, ZKP）由Goldwasser、Micali和Rackoff在1985年首次提出，是一种密码学协议，允许证明者向验证者证明某个陈述是真实的，而无需泄露除了该陈述真实性之外的任何额外信息。

零知识证明具有三个核心特性：

  1. 完备性：如果陈述为真，诚实的证明者能够说服验证者。
  2. 可靠性：如果陈述为假，欺骗的证明者无法说服验证者。
  3. 零知识性：验证者除了知道陈述为真之外，无法获得任何额外信息。

SNARK（Succinct Non-interactive Argument of Knowledge）和STARK（Scalable Transparent ARgument of Knowledge）是两种主流的零知识证明系统，它们各自采用了不同的数学构造和技术路径，导致在证明大小、验证效率、安全性等方面存在显著差异。

SNARK的证明大小

SNARK的证明大小通常非常小，通常只有几百字节。例如，Zcash使用的zk-SNARK证明大小约为228字节，而其他一些SNARK系统的证明大小甚至可以做到更小。这种极小的证明大小使得SNARK特别适合带宽受限的场景，如移动设备或物联网应用。

SNARK之所以能够实现如此小的证明大小，主要归功于其精心设计的密码学构造：

  1. 多项式承诺方案：SNARK通常依赖于多项式承诺方案，如KZG承诺或Bulletproofs，这些方案允许证明者以简洁的方式证明关于某个多项式的特定属性。

  2. 递归证明：许多SNARK系统支持递归证明，即一个证明可以验证另一个证明，这种机制可以显著减少最终证明的大小。

  3. 预定义参考字符串：大多数SNARK系统需要一个可信设置阶段，生成一个公共的参考字符串。这个参考字符串被用来生成和验证证明，允许证明者以非常紧凑的方式编码其证明。

  4. 优化的协议设计：SNARK协议通常经过高度优化，使用各种密码学技巧来最小化证明的大小，如使用椭圆曲线配对、优化编码方案等。

然而，SNARK的小证明大小也伴随着一些限制和挑战：

  1. 可信设置需求：大多数SNARK系统需要一个可信设置，这引入了安全隐患。如果参考字符串被泄露，整个系统的安全性将受到破坏。

  2. 计算复杂性：生成SNARK证明通常需要大量的计算资源，这可能限制了其在某些资源受限环境中的应用。

  3. 透明性问题：许多SNARK系统不是完全透明的，因为它们依赖于预定义的参考字符串，这可能影响用户对系统的信任。

STARK的证明大小

与SNARK相比，STARK的证明大小通常要大得多。一个典型的STARK证明大小可能在几KB到几十KB之间，比SNARK大1-2个数量级。例如，以太坊采用的STARK证明大小通常在20KB左右。

STARK的较大证明大小主要源于其不同的技术构造：

  1. 基于STARKs的证明系统：STARK基于可扩展的透明知识论证（Scalable Transparent ARguments of Knowledge），使用Merkle树和FRI（Fast Reed-Solomon IOPP）协议等工具来构建证明。

  2. 无需可信设置：STARK不需要可信设置，这是通过使用密码学学假设（如哈希函数的抗碰撞性）来实现的，这些假设被认为比SNARK依赖的椭圆曲线假设更可靠。

  3. 透明性：STARK是完全透明的，不需要任何预定义的参考字符串，这增强了系统的可审计性和可信度。

  4. 基于哈希的构造：STARK依赖于密码学安全的哈希函数，而不是复杂的椭圆曲线运算，这使得证明生成过程更加简单和透明。

尽管STARK的证明大小较大，但它也具有一些独特的优势：

  1. 后量子安全性：STARK基于的哈希函数假设被认为能够抵抗量子计算攻击，而SNARK依赖的椭圆曲线假设在量子计算面前可能不再安全。

  2. 无需可信设置：STARK不需要可信设置，消除了SNARK中存在的安全隐患。

  3. 更好的可扩展性：STARK的验证时间通常比SNARK更快，特别是在大规模计算场景下。

  4. 更高的透明度：STARK是完全透明的，用户可以直接验证证明而不需要依赖任何预先设置的参数。

为什么STARK的证明比SNARK大

STARK的证明比SNARK大，主要源于两者在基础构造和设计理念上的根本差异：

  1. 数学构造的不同：

    • SNARK通常基于椭圆曲线上的双线性对（pairings）和多项式承诺方案，这些数学构造允许非常紧凑的编码和验证。
    • STARK基于Merkle树和FRI协议，这些构造虽然更加透明和通用，但需要更多的数据来确保安全性。

  2. 安全假设的差异：

    • SNARK依赖于较强的密码学假设，如椭圆曲线离散对数问题或q-SRDP假设，这些假设允许更高效的证明系统。
    • STARK依赖于更基础的假设，如哈希函数的抗碰撞性，这些假设虽然更可靠，但通常需要更大的证明来确保相同的安全级别。

  3. 透明性要求的影响：

    • SNARK通常需要一个可信设置阶段，生成的参考字符串可以被用来优化证明的大小。
    • STARK不需要可信设置，所有证明数据都必须在证明中明确编码，这增加了证明的大小。

  4. 证明生成和验证机制的区别：

    • SNARK的证明生成过程通常涉及复杂的密码学运算，但这些运算可以被高度压缩。
    • STARK的证明生成过程更加直接，但需要更多的中间数据来确保完整性，这导致了更大的证明大小。

  5. 错误校正和编码方式：

    • SNARK通常使用高度优化的编码方式，如使用椭圆曲线点来编码多项式系数。
    • STARK使用基于哈希的编码方式，虽然更加通用和透明，但通常需要更多的数据来达到相同的安全级别。

  6. 交互性与非交互性的处理：

    • 虽然两者都支持非交互式证明，但SNARK通过使用预定义的参考字符串来简化交互过程。
    • STARK通过使用公共随机性来源（如区块链上的哈希值）来实现非交互性，这可能导致更大的证明。

技术细节：证明大小的数学分析

为了更深入地理解为什么STARK的证明比SNARK大，我们可以从数学角度分析两种系统的证明构造。

SNARK的证明构造： SNARK的证明通常基于以下步骤：

  1. 将计算问题编码为一个多项式关系。
  2. 使用KZG或其他多项式承诺方案对多项式进行承诺。
  3. 通过一系列交互或非交互的步骤证明多项式满足特定属性。
  4. 生成一个紧凑的证明，通常基于椭圆曲线上的点。

由于椭圆曲线上的点可以被高效编码（通常只需要几十个字节），并且多项式承诺方案允许高度压缩的证明，SNARK的证明大小可以非常小。

STARK的证明构造： STARK的证明构造通常包括以下步骤：

  1. 将计算问题编码为一个执行轨迹（execution trace）。
  2. 构建Merkle树来确保轨迹的完整性。
  3. 使用FRI协议证明轨迹满足特定的约束条件。
  4. 生成一个包含Merkle路径和FRI证明的证明。

由于Merkle树和FRI协议需要包含更多的中间数据，并且每个哈希值通常需要32字节或更多，STARK的证明大小自然会更大。

证明大小对应用的影响

证明大小作为零知识证明系统的关键指标，直接影响着各种实际应用的性能和可用性：

  1. 带宽和存储需求：

    • 小证明（如SNARK）在带宽受限的场景中具有明显优势，如移动应用、物联网设备等。
    • 大证明（如STARK）可能需要更多的存储空间和传输带宽，这在某些应用中可能成为瓶颈。

  2. 验证效率：

    • 虽然STARK的证明更大，但其验证时间通常比SNARK更快，特别是在大规模计算场景下。
    • 证明大小与验证时间并不总是成正比，因为验证算法的效率也起着重要作用。

  3. 安全性和透明度：

    • STARK的较大证明大小换取了更高的安全性和透明度，这在需要高度可信的应用中尤为重要。
    • SNARK的小证明大小可能牺牲一定的透明度，特别是在需要可信设置的情况下。

  4. 可扩展性：

    • 在需要处理大量证明的场景中，证明大小直接影响系统的整体可扩展性。
    • STARK虽然在单个证明上较大，但其更好的验证效率可能在某些场景下提供更好的整体性能。

实际应用中的选择

在实际应用中，选择STARK还是SNARK需要根据具体需求进行权衡：

  1. 隐私保护应用：

    • 对于需要高度隐私保护的应用，如匿名交易、隐私身份验证等，如果带宽不是主要限制，STARK可能是更好的选择，因为其更高的透明度和安全性。
    • 如果带宽是主要限制，如移动设备上的隐私应用，SNARK的小证明大小可能更具优势。

  2. 区块链和分布式系统：

    • 在区块链应用中，验证效率通常比证明大小更重要，因为验证节点需要处理大量交易。
    • STARK的快速验证时间使其在区块链扩容解决方案中具有优势，尽管其证明较大。

  3. 企业级应用：

    • 在企业级应用中，安全性和透明度通常是首要考虑因素，STARK的无需可信设置和完全透明性可能更有吸引力。
    • 如果应用场景对证明大小敏感，如资源受限的环境，SNARK可能更适合。

  4. 长期安全性需求：

    • 对于需要长期安全性的应用，如存储证明、长期身份验证等，STARK的后量子安全性优势可能使其成为更可靠的选择。

未来发展趋势

随着零知识证明技术的不断发展，STARK和SNARK之间的界限可能会变得更加模糊，两者可能会相互借鉴对方的优点：

  1. 混合证明系统：

    • 未来的零知识证明系统可能会结合SNARK的小证明大小和STARK的透明性优势，创造出更高效的混合系统。
    • 例如，可以使用STARK来验证SNARK的参考字符串的生成过程，从而提高整个系统的透明度。

  2. 证明压缩技术：

    • 随着编码和压缩技术的发展，STARK的证明大小可能会进一步减小，接近SNARK的水平，同时保持其透明性和安全性优势。
    • 新的证明编码方案，如基于量子编码的技术，可能会显著减小证明大小。

  3. 硬件加速：

    • 专用硬件（如GPU、FPGA、ASIC）可能会被用来加速STARK的证明生成和验证过程，弥补其证明大小较大的劣势。
    • 硬件加速可能会使STARK在某些应用场景下比SNARK更具竞争力。

  4. 标准化和互操作性：

    • 随着零知识证明技术的标准化，不同系统之间的互操作性可能会提高，允许用户根据具体需求选择最适合的证明系统。
    • 标准化可能会促进新技术的快速发展和应用。

结论

STARK和SNARK作为两种主流的零知识证明技术，各自具有独特的优势和适用场景。STARK的证明通常比SNARK大，这主要源于两者在基础构造、安全假设、透明性要求等方面的根本差异。

虽然STARK的证明大小较大，但它提供了更高的透明度、无需可信设置和后量子安全性等优势，使其在许多应用场景中成为更可靠的选择。而SNARK的小证明大小使其在带宽受限的场景中具有明显优势。

随着技术的不断发展，STARK和SNARK之间的界限可能会变得更加模糊，两者可能会相互借鉴对方的优点，创造出更高效、更安全的零知识证明系统。在实际应用中，选择哪种技术需要根据具体需求进行权衡，包括带宽、验证效率、安全性要求、透明度需求等因素。

零知识证明技术作为现代密码学的重要突破，正在改变我们对隐私、安全和信任的理解。随着STARK和SNARK等技术的不断成熟和完善，我们有理由相信，零知识证明将在更多领域发挥重要作用，为构建更加安全、隐私和高效的数字世界提供强大的技术支持。

Copyright Your WebSite.Some Rights Reserved.

Powered By Z-BlogPHP. Theme by TOYEAN.