STARK，作为新一代的SNARK技术，在速度上有着显著优势，更重要的是，它具备以下显著优势：1. 无需依赖可信任的设置；2. 具有抵御量子攻击的能力。
然而，STARK并非完美无缺。其证明量（proof size）大约在40-50KB之间，相较于SNARK的288 bytes，体积显得过大，相差了数个数量级。此外，这篇论文自发布以来已近两年，在密码学领域，其应用仍需时间的检验。
STARK的“S”不仅代表简洁（Succinct），还代表可扩展性（Scalable），而“T”则代表透明性（Transparency）。可扩展性易于理解，而透明性则是指利用公开透明的算法，无需依赖可信任的设置来存放秘密参数。SNARK与STARK均基于多项式验证的零知识技术。它们之间的差别主要在于信息隐藏的方式、验证的简洁性以及如何实现非互动性。
接下来，让我们简要了解SNARK是如何运作的。假设Alice有一个多项式P(x)，Bob有一个秘密s，Alice不知道s，Bob也不知道P(x)，在此情况下，Bob可以验证P(s)。通过同态隐藏（Homomorphic Hiding）将Bob的秘密s转换为H(s)，然后利用QAP/Pinocchio协议实现简洁验证，并将H(s)放入CRS（Common Reference String），以解决非互动性问题。
在零知识证明中，首先需要将“问题”转化为可以运算的多项式。本节将介绍如何将问题转化为多项式，具体的转换细节将不予详述。
问题→限制条件→多项式：SNARK和STARK都利用高维多项式进行验证。例如，如果多项式为x³ + 3x² + 3 = 0，那么其解很容易被破解；如果多项式为x²⁰⁰⁰⁰⁰ + x¹⁹⁹⁹⁹⁹ + ...，则破解难度将大大增加。
首先，将想要验证的问题转换为多项式。以Collatz Conjecture为例，Collatz Conjecture是指，对于任何正整数，按照以下两个规则操作：1. 如果数字是偶数，则除以2；2. 如果数字是奇数，则乘以3再加1（3n+1）。经过上述操作，最终结果会变为1。目前尚未证明这个猜想一定成立，但也未找到反例。
例如，数字52经过以下步骤最终变为1：52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1。将这些运算过程的结果记录下来，形成执行轨迹（Execution Trace），如52 → 26 → ... → 1。接着，将执行轨迹转换为多项式（具体转换方法将在后续文章中介绍）。
接下来，将这四个限制条件的多项式合并为一个，这个最终的多项式就被称为合成多项式（composition polynomial），它是后续验证所需的多项式。
正如之前提到的，SNARK和STARK都使用高维多项式进行验证。接下来，我们将介绍STARK如何通过哪些方式实现零知识交换、透明性和可扩展性。
修改多项式维度：这一步是为了后续验证做准备。在验证过程中，使用了一种技巧，即通过将多项式以2的次方递减至常数项（D, D/2, D/4, ...，1）来降低验证的复杂度。因此，需要先将多项式修改为2^n维度。
假设上述的每个限制多项式（不是合成多项式）为Cj(x)，维度为Dj，D >= Dj，且D = 2^n。为了达到D维度，需要乘以一个维度（D - Dj）的多项式。因此，最终的合成多项式如下：
其中的αj、βj由验证者提供，因此最终的多项式是由证明者和验证者共同组成的。
本节的重点是将多项式修改为D维度，若觉得多项式过于复杂，可以忽略。
FRI（Fast RS IOPP）：FRI的全称是“Fast RS IOPP”（RS = “Reed-Solomon”，IOPP = “Interactive Oracle Proofs of Proximity”）。通过FRI可以简洁地验证多项式。在介绍FRI之前，先来讨论如何证明你知道多项式f(x)。
RS 纠删码：纠删码的概念是将原始数据扩展，使得部分数据既可以进行验证，又可以容错。其方式是将数据组成多项式，通过验证多项式来验证数据是否正确。例如，有d个点可以组成d-1维的多项式y = f(x)，通过验证f(z1) != y，来确定z1是否是正确数据。
回到上述问题，如何证明知道多项式？最直接的方式就是直接代入点求解。通过纠删码的方式，假设有d+1个点，根据Lagrange插值法，可以得到一个d维的多项式h(x)。如果两个多项式在（某个范围内）任意d点上都相同（f(z) = h(z)，z = z1, z2, ...，zd），则可以证明我知道f(x)。然而，我们面对的是高维度的多项式，d是1、2百万，这样的测试太没有效率，也不可行。FRI解决了这个问题，验证次数由百万次降至数十次。
降低复杂度：假设最终的合成多项式为f(x)，通过将原本的1元多项式改为2元多项式，可以降低多项式的维度。假设f(x) = 1744 * x¹⁸⁵⁴²³，加入第二变数y，使y = x¹⁰⁰⁰，因此多项式可改写为g(x, y) = 1744 * x⁴²³ * y¹⁸⁵。通过这种方式，将维度从10万降低至1千，通过这种技巧大幅降低多项式的维度。在FRI的当前实现中，将维度对半降低y = x²（f(x) = g(x, x²)）。
此外，还有另一个技巧，将一个多项式拆成两个较小的多项式，将偶数次方和奇数次方分开，如下：
f(x) = g(x²) + xh(x²)
例如：
f(x) = a₀ + a₁x + a₂x² + a₃x³ + a₄x⁴ + a₅x⁵
g(x²) = a₀ + a₂x² + a₄x⁴
h(x²) = a₁x + a₃x² + a₅x⁴
通过这两个方法，可以将高维度的多项式拆解，重复地将维度对半再对半，以此类推至常数项。FRI协议在流程上包含两个阶段——“提交”和“查询”。
提交阶段：提交阶段类似于上述过程，将多项式拆解后，由验证者提供一随机数，组成新的多项式，再继续对多项式拆解，一直重复。
f(x) = f₀(x) = g₀(x²) + x * h₀(x²) → f₁(x) = g₀(x) + α₀ * h₀(x)，α₀（验证者提供）→ f₂(x) = g₁(x) + α₁ * h₁(x)，α₁（验证者提供）→ ...
查询阶段：这个阶段要验证证明者所提交的多项式f₀(x)、f₁(x)、f₂(x)、...是否正确。这里运用了一个技巧，即代入任意数z及-z（这代表在选域的时候，需满足L² = {x²：x ∈ L}，这里不再赘述）。因此，可以得到以下结果：
f₀(z) = g₀(z²) + z * h₀(z²)
f₀(-z) = g₀(z²) - z * h₀(z²)
通过两者相加、相减，可以得到g₀(z²)、h₀(z²)，进而计算出f₁(z²)，再推导出f₁(x)，以此类推验证证明者传来的多项式。
Interactive Oracle Proofs (IOPs)：通过FRI（RS纠删码、IOPs），将验证次数由数百万降至20-30次（log2(d)），实现了简洁验证。尽管我们解决了复杂度问题，但仍然存在互动性问题。
与SNARK比较：SNARK在验证方面利用了QAP和Pinocchio协议。
非互动性：通过Micali建构（Micali construction）这个概念来解释如何实现非互动验证。Micali建构包括两部分：PCPs（Probabilistically Checkable Proof）和杂凑函数。PCPs是一个随机抽样检查的证明系统。简单来说，证明者产出一个大资料量的证明（long proof），通过随机抽样来验证这个大资料量的证明。过程大约是这样的：证明者产出证明...
标签: 数字货币
