zero knowledge - Scalable Transparent ARgument of Knowledge

zero knowledge（零知识）：Private input（秘密的输入）将会被隐藏，除了 Prover 以外的任何人都不知道 Private input 的内容，在知识论证的过程中也不能反推出 Private input。

Scalable（扩展性）：与 Replay Computation 的验证耗时相比，zk-STARK 生成 Proof 的时间复杂度近似于计算的复杂度 (O(n))，而 Verify Proof 的时间复杂度远小于计算的复杂度 (O(log))。

假设区块链网络中 Verifier 的 VerifyTime = Transcation 交易数量的对数的平方。当一个区块包含 10000 Transcation 时，验证者的 VerifyTime = (log₂ 10000)² ~ (13.2)² ~ 177 ms；当一个区块包含 100 0000 Transcation 时，验证者的 VerifyTime = (log₂ 1,000,000)² ~ 20² ~ 400 ms。换句话说，交易吞吐量增加 100 倍只会导致验证者的运行时间增加 2.25 倍，这将极大的节省宝贵的链上计算资源。

Transparent（透明性）：与 zk-SNARK 的算法相比，zk-STARK 算法无须 Trust Setup（可信设置）的过程。

Low Degree Testing 低度测试（通过仅对函数进行少量查询来确定给定函数是否是某个有界度的多项式的问题，可以简单理解为 Prover 使用的多项式的度数足够低，从而说明他作弊成功的概率足够低）是概率证明理论的核心工具，零知识证明又是基于概率证明理论的。

zk-SNARK Trust Setup 是使用同态加密、KCA等方法使得 Prover 只能在事先提供的加密幂值（可信设置）上进行线性计算，即加秘幂值的度数是事先确认的，所以可以保证 Prover 提供的多项式的度数在特定范围内，即保证了 LDT。

zk-STARK 使用 Commitment Scheme（承诺方案）的思路：Verifier 让 Prover 提供更多的关于多项式的取值信息，通过 FRI Protocol，Verifier 可以得到结论 “ Prover 提供的取值点绝大部分在一个低度多项式上”，即保证了 LDT。

ARgument of Knowledge（知识论证）：只有知道 Private input 的 Prover 才能生成有效的Proof。

Zero Knowledge Proof

一、零知识证明的一般过程

f ( x ) = y，函数 f 代表一个计算任务，计算的规则是 Public 的，但是计算的过程比较耗时。

Prover 使用 Private input x（秘密的输入x），执行计算过程 f 并得到输出 y。

二、零知识证明的一般目标

1、零知识（Zero knowledge）：Proof π 不能泄露有关 Private input x（秘密的输入x）的任何信息。

2、完备性（Completeness）：Prover 通过 Private input x，可以得到 Proof π ，使得 Verifier 可以验证 Proof π，从而相信 y 是正确的输出。

3、可靠性（Soundness）：在 Prover 不知道 x 的情况下通过伪造 Proof π 从而使得其他人相信，是一件概率极低的事件。换句话说：Prover 作弊被抓到的概率是很大的。

4、简洁性（Succinct）：Verify 过程不涉及大量数据传输以及 Verify 算法简单。

Prover 声明：拥有一个长度为 10^6 的整数数组 x，并且其中的每一位数都处于 [ 1 - 10 ]。

x = [ 1，10，5，8 …… 9 ]，数组内元素共计 10^6 个。潜在的零知识应用场景可以是我的活期存款是1，定期存款是10，理财是5，我想在不暴露我的实际资产的情况下向银行证明我的资产情况不高于银行反洗钱的审查条款：任何一项子资产大于10万就要反洗钱。

一、Prove

Prover 将完整数组 x 作为 Proof π 直接发送给 Verifier。

二、Verify

Verifier 逐个检查数组 x 的每个元素。

三、目标完成度

1、零知识：不满足。Prover 的所有秘密作为 Proof 都发给 Verifier 了。

2、完备性：满足。Prover 的所有秘密作为 Proof 都发给 Verifier 了，Verifier 可以验证 Proof π 的正确性。

3、可靠性：满足。除了 Prover 其他人并不知道数组 x 到底是什么组成的，伪造 10^6 个数都满足约束条件的概率比较低。

4、简洁性：不满足。Verifier 需要逐个检查数组 x 中的每个元素，计算 x 的大小和检查的大小的时间复杂度相同。

在这个协议中我们可以确定的是第三方是可信的，另外两方却面临着：

Prover 可能发送不真实的数据给可信第三方；

Verifier 总是试图从可信第三方得到的信息中推断 Prover 持有的秘密数据。

一、Prove

Prover 将完整数组 x 作为 Proof π 发送给可信第三方。

二、Verify

Verifier 向可信第三方请求 k 个元素，k 属于 [ 1 - 10^6 ]。

Verifier 逐个检查 k 个元素是否都是 [ 1 - 10 ] 的整数。

三、目标完成度

1、零知识：不满足。Verifier 请求的 k 越多，零知识暴露的越多。

2、完备性：满足。Verifier 可以验证 Proof π 的正确性。

3、可靠性：不满足。如果 Prover 并不知道零知识，他构造的数组 x 中有 k 个元素是大于 10 的，此时 Prover 被 Verifier 发现作假的概率是 k / 10^6 。k 越大，Prover 被 Verifier 发现作假的概率越大。

4、简洁性：满足。Verifier 不需要逐个检查数组 x 中的每个元素，只检查 k 个元素即可。

注：当 k = 10^6 时，zk-STARK 1 协议 退化为 zk-STARK 0 协议。zk-STARK 1 协议仍然不是我们理想中的零知识协议，此时我们需要引入一些数学工具。

对于多项式 P(x) = a0·x^0 + a1·x^1 + a2·x^2 + …… + ad·x^d

我们把多项式的最大非零次数称为多项式的度数（degree），即如果 ad =！0，则 degree( P(x) ) = d。

根据高中代数知识我们已知多项式的性质：

1、如果多项式在某一点 x0 处有 P ( x ) = 0，那么必然存在一个度数为 d-1 的多项式 P'(x) ，满足 P(x) = (x - x0) P'(x)。

2、对于任意 d+1 个不同的点集（xi ，yi），i 属于 [ 0，d ]，我们都能唯一确定的找到一个度位 d 的多项式 P(x) ，使得 d+1 个点都在 P(x) 表示函数的曲线上。这种构造多项式的方式称之为：多项式插值。

2 点确定唯一一个 1 次多项式即直线；d+1 点确定唯一一个 d 次多项式。

3、对于两个度数为 d 的多项式 P(x) 和 Q(x) ，方程 P(x) = Q(x) 最多有 d 个根，换句话说这两个多项式代表的函数在二维平面上最多有d个交点。

一、Prove

Prover 把自己持有的包含 10^6 个整数的秘密数组 x 转化为二维平面上的点坐标：(1，x1)，(2，x2)，(3，x3)，…… ( 10^6，x(10^6) )。

1、P(x) 发送给可信第三方

根据多项式性质2 通过多项式插值的方法生成多项式 P(x)，并发给可信第三方（协议至此本质上还是 zk-STARK 1）。形如：

2、Public C(x)、D(x)；计算得到 C'(x) 后发送给可信第三方

Prover 构造 C( X ) = C( P(x) ) = 0，x ∈ [ 1 - 10^6 ]。

当 P(x) ∈ [ 1 - 10 ] 时，C( P(x) ) = 0，根据多项式性质1 我们得到：C( X ) = (X - 1)( X - 2)……(X-10)。

C(X) 描述了 Prover 持有的秘密数据内部的一种约束关系，因此我们将 C(X) 和 D(X) 称之为约束多项式（Constraint Polynomial）。

当 x ∈ [ 1 - 10^6 ] 时，C( P(x) ) = 0，根据多项式性质1 我们得到：C( P(x) ) = (x - 1)( x - 2)……(x-10^6) · C'(x)。令 D(x) = (x - 1)( x - 2)……(x - 10^6)，则 C( P(x) ) = D(x) · C'(x)。

二、Degree

我们提前计算各多项式的 degree（一会分析 Prover 作假概率时会用到）：

degree( P(x) ) = 10^6 - 1

比如2点确定一条直线 ax+b ：度=2-1

degree( C(X) ) = 10

degree( C(P(x)) ) = degree( C(x) ) · degree( P(x) ) = 10^7 - 10

比如C(x)=x^3，P(x)=x^2，则C(P(x))=(x^2)^3=x^(2 · 3)

degree( D(x) ) = 10^6

degree( C'(x) ) = degree( C(P(x)) ) - degree( D(x) ) = 10^7 - 10 - 10^6

比如P(x)=x^6，D(x)=x^2，则C'(x)=C( P(x) ) / D(x)=x^6 / x^2=x^(6-2)

三、Verify

1、Verifier 产生 random r，r ∈ ( 10^6 - 10^9 ]，并将 r 发送给可信第三方。

2、可信第三方在之前已经得到了 Prover 发来的 P(x) 和 C'(x)，代入 r 计算得到 P(r) 和 C'(r)，然后返回给 Verifier。

3、Verifier 已知 Public C(x)、D(x)，因此可以计算等式 C( P(r) ) = D(r) · C'(r)是否成立，从而完成对 Prover 秘密的验证。

四、目标完成度

1、零知识：不满足。zk-STARK 2 协议执行过程中，Verifier 得到的唯一有效信息是多项式 P(x) 在随机值 r 处的取值 ，由于 r ∈ ( 10^6 - 10^9 ) ，所以保证了 Verifier 不可能知道 Prover 持有的数组中任何一个元素的具体值。看似完美是不是？

实际上多项式 P(x) 本质上是由 Prover 持有的秘密数据唯一确定的，这个多项式上的任意一点必然包含了关于这个多项式的一部分信息，也就是关于 Prover 持有的秘密的部分信息。作恶的 Verifier 可以自己生成任意的 10^6 个 1 - 10之间的整数，然后同样用插值法生成多项式 P'(x)，然后 Verifier 只需要检查多项式在 r 处的取值 P'(r)：

（1）如果 P'(r) != P(r)，则 Verifier 就知道了 Prover 持有的秘密和自己随机生成的不同。

（2）如果 P'(r) = P(r)，则 Verifier 就知道了 Prover 的秘密（即便这种概率很低）。下一个协议将主要改进这个问题。

2、完备性：满足。Verifier 可以验证 Proof π = [ P(r) + C'(r) ] 的正确性。

3、可靠性：*满足。

degree( C(P(x)) ) = 10^7 - 10

根据多项式性质3 ，当 C(P(x)) = D(x) · C'(x) 时，最多有 10^7 - 10 个根，即二维平面中的若干个点。如果 Prover 不知道数组 x，就很难构造出和 C(P(x)) 一模一样的多项式，Prover 瞎编出 10^7 - 10 个点，恰巧和 Verifier random r ∈ ( 10^6 - 10^9 ] 的范围重合的概率为 10^7 - 10 / 10^9 - 10^6 = 0.01001 ，即 Prover 蒙对的概率是 1.001%，亦即 Verifier 通过一次验证就能发现 Prover 作假的概率是 98.999%。

请注意：这个低概率的前提是 degree( C(P(x)) ) 相比于全域 r 的选取范围，即 P(x) 是低度的（Low Degree）。在下面的 zk-STARK 6 我们将再次讨论这个重要问题。

对于任意的问题，我们都能用这样的思路，把“秘密”通过插值的方式编码到一个低阶多项式P(x) 中，然后用一个“约束多项式” C(x) 来描述秘密数据内部的约束关系。

4、简洁性：满足。Verifier 只需要检查一个点，因此验证的计算复杂度是很小的。

对于作恶的总想破解秘密的 Verifier 来说，zk-STARK 2 不是零知识的，因此此次 Prover 使用秘密（10^6 个点）插值生成 P(x) 之前，特意在秘密（10^6 个点）中多加入 k 个混淆点，然后再插值生成 P(x) 。此时：

1、零知识：可以满足了。由于 Prover 在秘密中加入了 k 个混淆点，所以 Prover 生成的多项式 P(x) 就不再由 Prover 持有的秘密数组唯一确定。即便 Verifier 自己生成任意的 10^6 个 1 - 10之间的整数，然后同样用插值法生成多项式 P'(x) ，然后比对 P'(r) = P(r)，Verifier 仍然不能确定这就是 Prover 的秘密，所以零知识得到了满足。

2、完备性：不变，所以满足。

3、可靠性：满足。degree( P(x) ) = 10^6 - 1 + k，与指数 10^6 相比，增加的度数 k 较小，所以不影响协议的可靠性。

4、简洁性：不变，所以满足。

至此，交互式的 zk-STARK 3 基本完成，我们整理如下：

一、Prove

Prover 把自己持有的包含 10^6 个整数的秘密数组 x 转化为二维平面上的点坐标：(1，x1)，(2，x2)，(3，x3)，…… ( 10^6，x(10^6) )，并加入混淆点 (a，b)，(c，d)……(x，y)。

1、Prover P(x) 通过多项式插值的方法将上面混淆过的点生成多项式 P(x)，并发送给可信第三方。

2、Prover 构造 Public C(x)、D(x)，计算得到 C'(x) 后发送给可信第三方

Prover 构造 C( X ) = C( P(x) ) = 0，x ∈ [ 1 - 10^6 ]。

当 P(x) ∈ [ 1 - 10 ] 时，C( P(x) ) = 0，根据多项式性质1 我们得到：C( X ) = (X - 1)( X - 2)……(X-10)。

C(X) 描述了 Prover 持有的秘密数据内部的一种约束关系，因此我们将 C(X) 和 D(X) 称之为约束多项式（Constraint Polynomial）。

当 x ∈ [ 1 - 10^6 ] 时，C( P(x) ) = 0，根据多项式性质1 我们得到：C( P(x) ) = (x - 1)( x - 2)……(x-10^6) · C'(x)。令 D(x) = (x - 1)( x - 2)……(x - 10^6)，则 C( P(x) ) = D(x) · C'(x)。

二、Verify

1、Verifier 产生 random r，r ∈ ( 10^6 - 10^9 ]，并将 r 发送给可信第三方。

2、可信第三方在之前已经得到了 Prover 发来的 P(x) 和 C'(x)，代入 r 计算得到 P(r) 和 C'(r)，然后返回给 Verifier。

3、Verifier 已知 Public C(x)、D(x)，因此可以计算等式 C( P(r) ) = D(r) · C'(r)是否成立，从而完成对 Prover 秘密的验证。

总体思路是利用承诺方案（Commitment Scheme）替换掉原来协议里的可信第三方，构造新的协议具体如下：

一、Prove

Prover 把自己持有的包含 10^6 个整数的秘密数组 x 转化为二维平面上的点坐标：(1，x1)，(2，x2)，(3，x3)，…… ( 10^6，x(10^6) )，并加入混淆点 (a，b)，(c，d)……(x，y)。

1、Prover P(x) 通过多项式插值的方法将上面混淆过的点生成多项式 P(x)，此时不再发送给可信第三方。

2、Prover 构造 Public C(x)、D(x)。

3、根据 C( P(x) ) = D(x) · C'(x) 计算得到 C'(x) 后，也不再发送给可信第三方。

4、Prover 对多项式 P(x)、C'(x) 在 x ∈ [ 1 - 10^9 ] 的所有取值计算得到 P(x)、C'(x) 的 10^9个计算结果做承诺：将 10^9 个计算结果生成 2 棵 Merkle Tree，计算出 Merkle Tree Root1 和 Root2，最后将 Merkle Tree Root1 和 Root2 发送给 Verifier。

Merkle Tree Leaf1 = [ (P(x1)、P(x2))，(P(x3)、P(x4))……(P(r)、P(r+1))……(P(x 10^9-1)、P(x10^9)) ]

Merkle Tree Leaf2 = [ (C'(x1)、C'(x2))，(C'(x3)、C'(x4))……(C'(r)、C'(r+1))……(C'(x 10^9-1)、C'(x10^9)) ]

二、Verify

1、Verifier random r，然后向 Prover 请求多项式 P(x)、C'(x) 在 r 处的取值：P(r)、C'(r)，以及对应的 Merkle Path。

注：Verifier random r 是交互式的关键节点，也是后续修改为非交互式协议的地方。

2、Prover 返回给 Verifier Proof π = [ P(r)，Merkle Path1，C'(r)，Merkle Path2，Root1，Root2 ] 。

3、Verifier 检查：

（1）根据 P(r)、C'(r) 和两条 Merkle Path 计算得到 Root'1 和 Root'2，与 Root1 和 Root2 比对进行验证。如果 Root'1 = Root1、Root'2 = Root2，则证明 P(r)、C'(r) 就是 Prover 事先承诺的值，Prover 在协议过程中没有恶意篡改，即 Prover 此时是可信的（等价于可信第三方）。

（2）根据 Public C(x)和D(x)，以及刚刚验证通过的验证 P(r)、C'(r)，Verifier 验证 C( P(r) ) = D(r) · C'(r) 是否成立。

现存协议的交互中最重要的一环在于 Verify 选择的随机值 r 发送给 Prover。最直接改变协议的为非交互的办法是：把生成随机值 r 的工作交给 Prover 来完成。

这个办法的问题是 Prover 如何让 Verifier 相信他选择的 r 是随机选择的，而不是 Prover 选择了一个特殊值从而欺骗 Verifier。所以我们需要设计一种让 Prover 生成随机值 r，并且让Verifier 相信这个 r 值是足够随机的方案：

Prover 在生成随机数的时候，使用他之前生成的Merkle Tree Root 作为随机数种子（seed）搭配一种 CRH 函数（抗碰撞哈希）即可生成随机数 r：

1、由于Merkle Tree Root 是公开的，因此 Verifier 可以检查 Prover 生成的随机值 r 是否使用了正确的随机数种子 Root。

2、CRH 函数保证了从随机数种子 Root 到随机数 r 的过程是单向的，也就是说 Prover 不能够先选好随机数 r，然后反推出随机数种子 Root。

这样我们就实现了从交互式协议到交互式协议的转换，这样的构造方法叫做：Fiat-Shamir heuristic

最新协议更新为：

一、Prove

1、Prover 把自己持有的包含 10^6 个整数的秘密数组 x 转化为二维平面上的点坐标：(1，x1)，(2，x2)，(3，x3)，…… ( 10^6，x(10^6) )，并加入混淆点 (a，b)，(c，d)……(x，y)。

2、Prover P(x) 通过多项式插值的方法将上面混淆过的点生成多项式 P(x)。

3、Prover 构造 Public 的约束多项式：C(x) = (X - 1)( X - 2)……(X-10)

4、Prover 构造 Public 的多项式：D(x) = (x - 1)( x - 2)……(x - 10^6)。

5、Prover 根据 C( P(x) ) = D(x) · C'(x) 计算得到 C'(x) 。

6、Prover 对多项式 P(x)、C'(x) 在 x ∈ [ 1 - 10^9 ] 的所有取值计算得到 P(x)、C'(x) 的 10^9个计算结果做承诺：将 10^9 个计算结果生成 2 棵 Merkle Tree，计算出 Merkle Tree Root1 和 Root2。

7、Prover 利用 Root1 和 Root2 作为随机种子，使用 CRH 函数计算得到随机值 r，并根据随机值 r 计算得到 P(r)、C'(r) 对应的 Merkle Path。

8、最后 Prover 将 Proof π = [ P(r)，Merkle Path1，C'(r)，Merkle Path2，Root1，Root2 ]发送给 Verifier。

二、Verify

Verifier 检查：

（1）根据 P(r)、C'(r) 和两条 Merkle Path 计算得到 Root'1 和 Root'2，与 Public Root1 和 Root2 比对进行验证。如果 Root'1 = Root1、Root'2 = Root2，则证明 P(r)、C'(r) 就是 Prover 事先承诺的值，Prover 在协议过程中没有恶意篡改。

（2）根据 Public C(x)和D(x)，以及刚刚验证通过的验证 P(r)、C'(r)，Verifier 验证 C( P(r) ) = D(r) · C'(r) 是否成立。

为了提高协议的可靠性，我们可以设置多个检查点，即 Prover 生成 Proof 时选取多个随机值 r ，Verifier 在检查的时候也一次性检查多个，这个改动不会影响协议的非交互性，却可以有效地提高可靠性。

在 zk-STARK 2 的 “四、目标完成度” “3、可靠性” 章节，我们计算了Prover 蒙对的概率很低的前提是 P(x) 是低度的（Low Degree）。低阶多项式是 zk-STARK 协议可靠性来源的核心前提，但是我们刚才推导协议的过程中并没有明确如何保证多项式 P(x) 是低度的。

在 zk-STARK 1-3 中由于有可信第三方的存在，所以第三方可以直接检查多项式 P(x) 的度数足够低。在 zk-STARK 4-5 中不存在可信第三方，所以协议的可靠性就没了基于数学概率的足够保障：

比如在 zk-STARK 5 中 Prover 不使用自己持有的包含 10^6 个整数的秘密数组 x 生成多项式 P(x)，而是使用 10^9 个点生成多项式 P(x)，这样相当于在 10^9 个点的范围内选取 10^9 个点，即 Prover 蒙对的概率接近 100%，协议的可靠性就彻底丧失了。

那么如何保证 Prover 生成的多项式 P(x) 和计算出的 C'(x) 的度数在符合要求的范围内呢，也就是如何才能通过检查 Prover 提供的多项式的取值点，来知道这些点对应的多项式的度数是否小于某个阈值呢？

这个问题又被称作 Low Degree Testing（低度测试）问题：LDT 是指通过仅对函数进行少量 Query 来确定给定函数是否是某个有界度的多项式的问题。

LDT 已经研究了二十多年，是概率证明理论的核心工具，也是零知识证明协议中最复杂的问题。最终版 zk-STARK 中使用 FRI Protocol（Fast Reed-solomon Interactive oracle proofs of proximity）进行了 LDT。

LDT 目前来看主要有两个方向的解决思路：

一、使用同态加密、KCA等方法，使得 Prover 只能够在事先提供的加密幂值（可信设置）上进行线性计算。由于加秘幂值的阶数是事先确认的，所以可以保证 Prover 提供的多项式的度数在特定范围内。

这种方法需要为每种特定的计算执行 Trust Setup 可信设置的操作，发展为zk-SNARKs 类型的零知识证明协议。

二、使用承诺方案的思路，Verifier 可以让 Prover 提供更多的关于多项式的取值信息，通过设计好的协议（比如 FRI Protocol），可以得到结论：Prover 提供的取值点大部分在一个低阶多项式上。

这种方法不需要 Trust Setup 可信设置，称之为 Transparent 透明性，发展为zk-STARKs 类型的零知识证明协议。

关于 Low Degree Testing，具体可以参见 STARK 论文作者 Eli Ben Sasson 的科普文章：

https://medium.com/starkware/low-degree-testing-f7614f5172db

一、其他ZKP系统

1、hPKC：Homomorphic Public-Key Cryptography 同态公钥密码，如Pinocchio和libSNARK。

2、DLP：Discrete Logarithm Problem 离散对数问题，如BulletProofs。

3、IP：Interactive Proofs 交互式证明，如Hyrax。

4、MPC：Secure Multi-Party Computation 多方安全计算，如ZKBoo、Ligero。

5、IVC：Incrementally Verifiable Computation 增量可验证计算，如hPKC-based IVC。

二、测试指标

测试均基于同一个硬件服务器，基于同样的DPM（DNA Profile Match）问题。使用 Arithmetic circuit complexity（算术电路复杂度）作为标准测量场。测试的所有 ZKP 系统均为算术化之后的运算，将计算完整性(CI)语句简化为相关的有限域上的低次多项式系统，测试算数电路的参数：

数据库中有 n 条数据

电路深度 = 62·n

电路宽度 = 81

秘密复杂度 = 40·n bytes

乘法复杂度 = 1467·62·n ≈ (2^16.4)·n

三、测试结论

ZK-STARK 是测量的所有电路尺寸中生成证明最快的，特别是与广泛采用的 libSNARK 相比较，速度快了近 10 倍。

在小电路情况下 Ligero 和 ZKBoo 的通信时间更短，验证更快。在深度较小的电路的情况下，Hyrax的通信时间更短，验证更快。

在同一固定电路上多次重复的计算，BulletProofs, Pinocchio, libSNARK 的通信时间更短，验证更快。

但是对于一般的大规模计算，ZK-STARK 的验证时间和通信复杂性优于其他透明系统。换句话说，对 ZK-STARK 的实践表明：对于实际相关的具体计算( 如DPM )，已经充分体现了完全可伸缩性和透明性的优势，并表明 zk-STARK 系统类型对于构建可伸缩性解决方案很有用， 例如用于分布式的加密货币。

zk-STARK 论文的作者 Eli Ben Sasson 创建了 StarkWare 区块链项目，并担任项目的 Co-Founder 联合创始人兼 President 总裁。

一、StarkWare 简介

项目官网：https://starkware.co/

项目简介：STARK证明的先驱（以色列项目方），为区块链带来可扩展性、安全性和隐私性。（可扩展性解决方案：在cloud中运行的off-chain prover生成的加密证明，然后由on-chain smart-contract进行验证）。

二、StarkWare 资方

2021年11月16日，Series C 5000万刀，项目估值达到20亿刀，Sequoia Capital、Paradigm、Three Arrows Capital、Alameda Research、Founders Fund。

2021年3月24日，Series B 7500万刀，Paradigm、Three Arrows Capital、Founders Fund、DCVC、Wing VC。

2018年11月29日，Series A 3000 万刀，Paradigm领投、Intel Capital、Sequoia、Atomico、DCVC、Wing、Consensys、Coinbase Ventures、Multicoin Capital、Collaborative Fund、Scalar Capital、Semantic Ventures。

三、StarkWare 产品一：StarkNet（https://starknet.io/）

StarkNet 是一个无需许可的去中心化 ZK-Rollup，支持独立部署智能合约。 任何开发人员都可以在无需许可的情况下编写和部署他们的智能合约。 StarkNet 还支持可组合性。

它作为以太坊上的 L2 网络运行，使任何 dApp 能够实现其计算的无限规模，而不会影响以太坊的可组合性和安全性。

四、StarkWare 产品二：StarkEx

StarkEx 是经过许可的、定制的，位于以太坊主网上的L2可扩展性引擎，以满足应用程序的特定需求。于2020年6月在以太坊主网launched。

StarkEx 的工作流程：

1、Operator 在 off-chain 将用户 Tx 进行 batch，然后 Sent batch to StarkEx Service

2、StarkEx Service 校验 batch ，将相关 balance 更新

3、StarkEx Service 生成：可以证明 batch 中交易合法性的 STARK proof，然后send proof on-chain即上链

4、on-chain Verifier smart contract 收到STARK proof，验证通过后提交 new balance state 上链存储。

五、Cairo 语言

Cairo 是富有表现力和高性能的 ZKP 编程语言。

Cairo 是StarkNet 合约的原生语言，可充分优化 StarkNet 的扩展潜力。

Cairo 同时允许 StarkEx 支持任何业务逻辑。

StarkWare正在开发从 Solidity 和其他编程语言到 Cairo 的转译器，这些转译器将允许在 StarkNet 上快速部署。

六、项目里程碑

2018年: STARK 白皮书发布，获得以太坊基金会 Grant。

2019年: 第一个 Demo 发布 (扩大以太坊效率200倍)，StarkEx Alpha 发布测试网, 第二个 Demo 发布 (扩大以太坊效率700倍)。

2020年: DeversiFi (StarkEx 1.0) 发布主网，VeeDo (基于Stark的VDF) 发布主网，StarkEx Rollup 发布主网，ethSTARK发布，Cairo (图灵完备的针对STARK语言) 以及其 PlayGround 发布，Ziggy STARK (后量子安全的安全签名) 发布，StarkEx 2.0 发布主网。

2021年: StarkNet 发布，dYdX 与 Immutable X (均为StarkWare的客户) 项目发布主网。

七、StarkWare 业绩

DiversiFi 的支付 TPS 可以达到 18k。

Immutable 的 NFT 铸造费用仅需 0.2 美分。

dYdX 的交易费用缩减到了1/50，秒级确认,，费率几乎为 0，带来了极佳的用户体验。

截止到2022年2月3日，DeversiFi、dYdX、Immutable、Sorare 通过StarkEx平台实现了TVL 11亿刀，10.2万笔Tx，交易额累计3780亿刀。DYOR

================================

================================

欢迎大佬们的探讨指正～

您可以在这里找到作者 twitter：@ethan_ifdao

zero knowledge - Scalable Transparent ARgument of Knowledge

zero knowledge（零知识）：Private input（秘密的输入）将会被隐藏，除了 Prover 以外的任何人都不知道 Private input 的内容，在知识论证的过程中也不能反推出 Private input。

Scalable（扩展性）：与 Replay Computation 的验证耗时相比，zk-STARK 生成 Proof 的时间复杂度近似于计算的复杂度 (O(n))，而 Verify Proof 的时间复杂度远小于计算的复杂度 (O(log))。

假设区块链网络中 Verifier 的 VerifyTime = Transcation 交易数量的对数的平方。当一个区块包含 10000 Transcation 时，验证者的 VerifyTime = (log₂ 10000)² ~ (13.2)² ~ 177 ms；当一个区块包含 100 0000 Transcation 时，验证者的 VerifyTime = (log₂ 1,000,000)² ~ 20² ~ 400 ms。换句话说，交易吞吐量增加 100 倍只会导致验证者的运行时间增加 2.25 倍，这将极大的节省宝贵的链上计算资源。

Transparent（透明性）：与 zk-SNARK 的算法相比，zk-STARK 算法无须 Trust Setup（可信设置）的过程。

Low Degree Testing 低度测试（通过仅对函数进行少量查询来确定给定函数是否是某个有界度的多项式的问题，可以简单理解为 Prover 使用的多项式的度数足够低，从而说明他作弊成功的概率足够低）是概率证明理论的核心工具，零知识证明又是基于概率证明理论的。

zk-SNARK Trust Setup 是使用同态加密、KCA等方法使得 Prover 只能在事先提供的加密幂值（可信设置）上进行线性计算，即加秘幂值的度数是事先确认的，所以可以保证 Prover 提供的多项式的度数在特定范围内，即保证了 LDT。

zk-STARK 使用 Commitment Scheme（承诺方案）的思路：Verifier 让 Prover 提供更多的关于多项式的取值信息，通过 FRI Protocol，Verifier 可以得到结论 “ Prover 提供的取值点绝大部分在一个低度多项式上”，即保证了 LDT。

ARgument of Knowledge（知识论证）：只有知道 Private input 的 Prover 才能生成有效的Proof。

Zero Knowledge Proof

一、零知识证明的一般过程

f ( x ) = y，函数 f 代表一个计算任务，计算的规则是 Public 的，但是计算的过程比较耗时。

Prover 使用 Private input x（秘密的输入x），执行计算过程 f 并得到输出 y。

二、零知识证明的一般目标

1、零知识（Zero knowledge）：Proof π 不能泄露有关 Private input x（秘密的输入x）的任何信息。

2、完备性（Completeness）：Prover 通过 Private input x，可以得到 Proof π ，使得 Verifier 可以验证 Proof π，从而相信 y 是正确的输出。

3、可靠性（Soundness）：在 Prover 不知道 x 的情况下通过伪造 Proof π 从而使得其他人相信，是一件概率极低的事件。换句话说：Prover 作弊被抓到的概率是很大的。

4、简洁性（Succinct）：Verify 过程不涉及大量数据传输以及 Verify 算法简单。

Prover 声明：拥有一个长度为 10^6 的整数数组 x，并且其中的每一位数都处于 [ 1 - 10 ]。

x = [ 1，10，5，8 …… 9 ]，数组内元素共计 10^6 个。潜在的零知识应用场景可以是我的活期存款是1，定期存款是10，理财是5，我想在不暴露我的实际资产的情况下向银行证明我的资产情况不高于银行反洗钱的审查条款：任何一项子资产大于10万就要反洗钱。

一、Prove

Prover 将完整数组 x 作为 Proof π 直接发送给 Verifier。

二、Verify

Verifier 逐个检查数组 x 的每个元素。

三、目标完成度

1、零知识：不满足。Prover 的所有秘密作为 Proof 都发给 Verifier 了。

2、完备性：满足。Prover 的所有秘密作为 Proof 都发给 Verifier 了，Verifier 可以验证 Proof π 的正确性。

3、可靠性：满足。除了 Prover 其他人并不知道数组 x 到底是什么组成的，伪造 10^6 个数都满足约束条件的概率比较低。

4、简洁性：不满足。Verifier 需要逐个检查数组 x 中的每个元素，计算 x 的大小和检查的大小的时间复杂度相同。

在这个协议中我们可以确定的是第三方是可信的，另外两方却面临着：

Prover 可能发送不真实的数据给可信第三方；

Verifier 总是试图从可信第三方得到的信息中推断 Prover 持有的秘密数据。

一、Prove

Prover 将完整数组 x 作为 Proof π 发送给可信第三方。

二、Verify

Verifier 向可信第三方请求 k 个元素，k 属于 [ 1 - 10^6 ]。

Verifier 逐个检查 k 个元素是否都是 [ 1 - 10 ] 的整数。

三、目标完成度

1、零知识：不满足。Verifier 请求的 k 越多，零知识暴露的越多。

2、完备性：满足。Verifier 可以验证 Proof π 的正确性。

3、可靠性：不满足。如果 Prover 并不知道零知识，他构造的数组 x 中有 k 个元素是大于 10 的，此时 Prover 被 Verifier 发现作假的概率是 k / 10^6 。k 越大，Prover 被 Verifier 发现作假的概率越大。

4、简洁性：满足。Verifier 不需要逐个检查数组 x 中的每个元素，只检查 k 个元素即可。

注：当 k = 10^6 时，zk-STARK 1 协议 退化为 zk-STARK 0 协议。zk-STARK 1 协议仍然不是我们理想中的零知识协议，此时我们需要引入一些数学工具。

对于多项式 P(x) = a0·x^0 + a1·x^1 + a2·x^2 + …… + ad·x^d

我们把多项式的最大非零次数称为多项式的度数（degree），即如果 ad =！0，则 degree( P(x) ) = d。

根据高中代数知识我们已知多项式的性质：

1、如果多项式在某一点 x0 处有 P ( x ) = 0，那么必然存在一个度数为 d-1 的多项式 P'(x) ，满足 P(x) = (x - x0) P'(x)。

2、对于任意 d+1 个不同的点集（xi ，yi），i 属于 [ 0，d ]，我们都能唯一确定的找到一个度位 d 的多项式 P(x) ，使得 d+1 个点都在 P(x) 表示函数的曲线上。这种构造多项式的方式称之为：多项式插值。

2 点确定唯一一个 1 次多项式即直线；d+1 点确定唯一一个 d 次多项式。

3、对于两个度数为 d 的多项式 P(x) 和 Q(x) ，方程 P(x) = Q(x) 最多有 d 个根，换句话说这两个多项式代表的函数在二维平面上最多有d个交点。

一、Prove

Prover 把自己持有的包含 10^6 个整数的秘密数组 x 转化为二维平面上的点坐标：(1，x1)，(2，x2)，(3，x3)，…… ( 10^6，x(10^6) )。

1、P(x) 发送给可信第三方

根据多项式性质2 通过多项式插值的方法生成多项式 P(x)，并发给可信第三方（协议至此本质上还是 zk-STARK 1）。形如：

2、Public C(x)、D(x)；计算得到 C'(x) 后发送给可信第三方

Prover 构造 C( X ) = C( P(x) ) = 0，x ∈ [ 1 - 10^6 ]。

当 P(x) ∈ [ 1 - 10 ] 时，C( P(x) ) = 0，根据多项式性质1 我们得到：C( X ) = (X - 1)( X - 2)……(X-10)。

C(X) 描述了 Prover 持有的秘密数据内部的一种约束关系，因此我们将 C(X) 和 D(X) 称之为约束多项式（Constraint Polynomial）。

当 x ∈ [ 1 - 10^6 ] 时，C( P(x) ) = 0，根据多项式性质1 我们得到：C( P(x) ) = (x - 1)( x - 2)……(x-10^6) · C'(x)。令 D(x) = (x - 1)( x - 2)……(x - 10^6)，则 C( P(x) ) = D(x) · C'(x)。

二、Degree

我们提前计算各多项式的 degree（一会分析 Prover 作假概率时会用到）：

degree( P(x) ) = 10^6 - 1

比如2点确定一条直线 ax+b ：度=2-1

degree( C(X) ) = 10

degree( C(P(x)) ) = degree( C(x) ) · degree( P(x) ) = 10^7 - 10

比如C(x)=x^3，P(x)=x^2，则C(P(x))=(x^2)^3=x^(2 · 3)

degree( D(x) ) = 10^6

degree( C'(x) ) = degree( C(P(x)) ) - degree( D(x) ) = 10^7 - 10 - 10^6

比如P(x)=x^6，D(x)=x^2，则C'(x)=C( P(x) ) / D(x)=x^6 / x^2=x^(6-2)

三、Verify

1、Verifier 产生 random r，r ∈ ( 10^6 - 10^9 ]，并将 r 发送给可信第三方。

2、可信第三方在之前已经得到了 Prover 发来的 P(x) 和 C'(x)，代入 r 计算得到 P(r) 和 C'(r)，然后返回给 Verifier。

3、Verifier 已知 Public C(x)、D(x)，因此可以计算等式 C( P(r) ) = D(r) · C'(r)是否成立，从而完成对 Prover 秘密的验证。

四、目标完成度

1、零知识：不满足。zk-STARK 2 协议执行过程中，Verifier 得到的唯一有效信息是多项式 P(x) 在随机值 r 处的取值 ，由于 r ∈ ( 10^6 - 10^9 ) ，所以保证了 Verifier 不可能知道 Prover 持有的数组中任何一个元素的具体值。看似完美是不是？

实际上多项式 P(x) 本质上是由 Prover 持有的秘密数据唯一确定的，这个多项式上的任意一点必然包含了关于这个多项式的一部分信息，也就是关于 Prover 持有的秘密的部分信息。作恶的 Verifier 可以自己生成任意的 10^6 个 1 - 10之间的整数，然后同样用插值法生成多项式 P'(x)，然后 Verifier 只需要检查多项式在 r 处的取值 P'(r)：

（1）如果 P'(r) != P(r)，则 Verifier 就知道了 Prover 持有的秘密和自己随机生成的不同。

（2）如果 P'(r) = P(r)，则 Verifier 就知道了 Prover 的秘密（即便这种概率很低）。下一个协议将主要改进这个问题。

2、完备性：满足。Verifier 可以验证 Proof π = [ P(r) + C'(r) ] 的正确性。

3、可靠性：*满足。

degree( C(P(x)) ) = 10^7 - 10

根据多项式性质3 ，当 C(P(x)) = D(x) · C'(x) 时，最多有 10^7 - 10 个根，即二维平面中的若干个点。如果 Prover 不知道数组 x，就很难构造出和 C(P(x)) 一模一样的多项式，Prover 瞎编出 10^7 - 10 个点，恰巧和 Verifier random r ∈ ( 10^6 - 10^9 ] 的范围重合的概率为 10^7 - 10 / 10^9 - 10^6 = 0.01001 ，即 Prover 蒙对的概率是 1.001%，亦即 Verifier 通过一次验证就能发现 Prover 作假的概率是 98.999%。

请注意：这个低概率的前提是 degree( C(P(x)) ) 相比于全域 r 的选取范围，即 P(x) 是低度的（Low Degree）。在下面的 zk-STARK 6 我们将再次讨论这个重要问题。

对于任意的问题，我们都能用这样的思路，把“秘密”通过插值的方式编码到一个低阶多项式P(x) 中，然后用一个“约束多项式” C(x) 来描述秘密数据内部的约束关系。

4、简洁性：满足。Verifier 只需要检查一个点，因此验证的计算复杂度是很小的。

对于作恶的总想破解秘密的 Verifier 来说，zk-STARK 2 不是零知识的，因此此次 Prover 使用秘密（10^6 个点）插值生成 P(x) 之前，特意在秘密（10^6 个点）中多加入 k 个混淆点，然后再插值生成 P(x) 。此时：

1、零知识：可以满足了。由于 Prover 在秘密中加入了 k 个混淆点，所以 Prover 生成的多项式 P(x) 就不再由 Prover 持有的秘密数组唯一确定。即便 Verifier 自己生成任意的 10^6 个 1 - 10之间的整数，然后同样用插值法生成多项式 P'(x) ，然后比对 P'(r) = P(r)，Verifier 仍然不能确定这就是 Prover 的秘密，所以零知识得到了满足。

2、完备性：不变，所以满足。

3、可靠性：满足。degree( P(x) ) = 10^6 - 1 + k，与指数 10^6 相比，增加的度数 k 较小，所以不影响协议的可靠性。

4、简洁性：不变，所以满足。

至此，交互式的 zk-STARK 3 基本完成，我们整理如下：

一、Prove

Prover 把自己持有的包含 10^6 个整数的秘密数组 x 转化为二维平面上的点坐标：(1，x1)，(2，x2)，(3，x3)，…… ( 10^6，x(10^6) )，并加入混淆点 (a，b)，(c，d)……(x，y)。

1、Prover P(x) 通过多项式插值的方法将上面混淆过的点生成多项式 P(x)，并发送给可信第三方。

2、Prover 构造 Public C(x)、D(x)，计算得到 C'(x) 后发送给可信第三方

Prover 构造 C( X ) = C( P(x) ) = 0，x ∈ [ 1 - 10^6 ]。

当 P(x) ∈ [ 1 - 10 ] 时，C( P(x) ) = 0，根据多项式性质1 我们得到：C( X ) = (X - 1)( X - 2)……(X-10)。

C(X) 描述了 Prover 持有的秘密数据内部的一种约束关系，因此我们将 C(X) 和 D(X) 称之为约束多项式（Constraint Polynomial）。

当 x ∈ [ 1 - 10^6 ] 时，C( P(x) ) = 0，根据多项式性质1 我们得到：C( P(x) ) = (x - 1)( x - 2)……(x-10^6) · C'(x)。令 D(x) = (x - 1)( x - 2)……(x - 10^6)，则 C( P(x) ) = D(x) · C'(x)。

二、Verify

1、Verifier 产生 random r，r ∈ ( 10^6 - 10^9 ]，并将 r 发送给可信第三方。

2、可信第三方在之前已经得到了 Prover 发来的 P(x) 和 C'(x)，代入 r 计算得到 P(r) 和 C'(r)，然后返回给 Verifier。

3、Verifier 已知 Public C(x)、D(x)，因此可以计算等式 C( P(r) ) = D(r) · C'(r)是否成立，从而完成对 Prover 秘密的验证。

总体思路是利用承诺方案（Commitment Scheme）替换掉原来协议里的可信第三方，构造新的协议具体如下：

一、Prove

Prover 把自己持有的包含 10^6 个整数的秘密数组 x 转化为二维平面上的点坐标：(1，x1)，(2，x2)，(3，x3)，…… ( 10^6，x(10^6) )，并加入混淆点 (a，b)，(c，d)……(x，y)。

1、Prover P(x) 通过多项式插值的方法将上面混淆过的点生成多项式 P(x)，此时不再发送给可信第三方。

2、Prover 构造 Public C(x)、D(x)。

3、根据 C( P(x) ) = D(x) · C'(x) 计算得到 C'(x) 后，也不再发送给可信第三方。

4、Prover 对多项式 P(x)、C'(x) 在 x ∈ [ 1 - 10^9 ] 的所有取值计算得到 P(x)、C'(x) 的 10^9个计算结果做承诺：将 10^9 个计算结果生成 2 棵 Merkle Tree，计算出 Merkle Tree Root1 和 Root2，最后将 Merkle Tree Root1 和 Root2 发送给 Verifier。

Merkle Tree Leaf1 = [ (P(x1)、P(x2))，(P(x3)、P(x4))……(P(r)、P(r+1))……(P(x 10^9-1)、P(x10^9)) ]

Merkle Tree Leaf2 = [ (C'(x1)、C'(x2))，(C'(x3)、C'(x4))……(C'(r)、C'(r+1))……(C'(x 10^9-1)、C'(x10^9)) ]

二、Verify

1、Verifier random r，然后向 Prover 请求多项式 P(x)、C'(x) 在 r 处的取值：P(r)、C'(r)，以及对应的 Merkle Path。

注：Verifier random r 是交互式的关键节点，也是后续修改为非交互式协议的地方。

2、Prover 返回给 Verifier Proof π = [ P(r)，Merkle Path1，C'(r)，Merkle Path2，Root1，Root2 ] 。

3、Verifier 检查：

（1）根据 P(r)、C'(r) 和两条 Merkle Path 计算得到 Root'1 和 Root'2，与 Root1 和 Root2 比对进行验证。如果 Root'1 = Root1、Root'2 = Root2，则证明 P(r)、C'(r) 就是 Prover 事先承诺的值，Prover 在协议过程中没有恶意篡改，即 Prover 此时是可信的（等价于可信第三方）。

（2）根据 Public C(x)和D(x)，以及刚刚验证通过的验证 P(r)、C'(r)，Verifier 验证 C( P(r) ) = D(r) · C'(r) 是否成立。

现存协议的交互中最重要的一环在于 Verify 选择的随机值 r 发送给 Prover。最直接改变协议的为非交互的办法是：把生成随机值 r 的工作交给 Prover 来完成。

这个办法的问题是 Prover 如何让 Verifier 相信他选择的 r 是随机选择的，而不是 Prover 选择了一个特殊值从而欺骗 Verifier。所以我们需要设计一种让 Prover 生成随机值 r，并且让Verifier 相信这个 r 值是足够随机的方案：

Prover 在生成随机数的时候，使用他之前生成的Merkle Tree Root 作为随机数种子（seed）搭配一种 CRH 函数（抗碰撞哈希）即可生成随机数 r：

1、由于Merkle Tree Root 是公开的，因此 Verifier 可以检查 Prover 生成的随机值 r 是否使用了正确的随机数种子 Root。

2、CRH 函数保证了从随机数种子 Root 到随机数 r 的过程是单向的，也就是说 Prover 不能够先选好随机数 r，然后反推出随机数种子 Root。

这样我们就实现了从交互式协议到交互式协议的转换，这样的构造方法叫做：Fiat-Shamir heuristic

最新协议更新为：

一、Prove

1、Prover 把自己持有的包含 10^6 个整数的秘密数组 x 转化为二维平面上的点坐标：(1，x1)，(2，x2)，(3，x3)，…… ( 10^6，x(10^6) )，并加入混淆点 (a，b)，(c，d)……(x，y)。

2、Prover P(x) 通过多项式插值的方法将上面混淆过的点生成多项式 P(x)。

3、Prover 构造 Public 的约束多项式：C(x) = (X - 1)( X - 2)……(X-10)

4、Prover 构造 Public 的多项式：D(x) = (x - 1)( x - 2)……(x - 10^6)。

5、Prover 根据 C( P(x) ) = D(x) · C'(x) 计算得到 C'(x) 。

6、Prover 对多项式 P(x)、C'(x) 在 x ∈ [ 1 - 10^9 ] 的所有取值计算得到 P(x)、C'(x) 的 10^9个计算结果做承诺：将 10^9 个计算结果生成 2 棵 Merkle Tree，计算出 Merkle Tree Root1 和 Root2。

7、Prover 利用 Root1 和 Root2 作为随机种子，使用 CRH 函数计算得到随机值 r，并根据随机值 r 计算得到 P(r)、C'(r) 对应的 Merkle Path。

8、最后 Prover 将 Proof π = [ P(r)，Merkle Path1，C'(r)，Merkle Path2，Root1，Root2 ]发送给 Verifier。

二、Verify

Verifier 检查：

（1）根据 P(r)、C'(r) 和两条 Merkle Path 计算得到 Root'1 和 Root'2，与 Public Root1 和 Root2 比对进行验证。如果 Root'1 = Root1、Root'2 = Root2，则证明 P(r)、C'(r) 就是 Prover 事先承诺的值，Prover 在协议过程中没有恶意篡改。

（2）根据 Public C(x)和D(x)，以及刚刚验证通过的验证 P(r)、C'(r)，Verifier 验证 C( P(r) ) = D(r) · C'(r) 是否成立。

为了提高协议的可靠性，我们可以设置多个检查点，即 Prover 生成 Proof 时选取多个随机值 r ，Verifier 在检查的时候也一次性检查多个，这个改动不会影响协议的非交互性，却可以有效地提高可靠性。

在 zk-STARK 2 的 “四、目标完成度” “3、可靠性” 章节，我们计算了Prover 蒙对的概率很低的前提是 P(x) 是低度的（Low Degree）。低阶多项式是 zk-STARK 协议可靠性来源的核心前提，但是我们刚才推导协议的过程中并没有明确如何保证多项式 P(x) 是低度的。

在 zk-STARK 1-3 中由于有可信第三方的存在，所以第三方可以直接检查多项式 P(x) 的度数足够低。在 zk-STARK 4-5 中不存在可信第三方，所以协议的可靠性就没了基于数学概率的足够保障：

比如在 zk-STARK 5 中 Prover 不使用自己持有的包含 10^6 个整数的秘密数组 x 生成多项式 P(x)，而是使用 10^9 个点生成多项式 P(x)，这样相当于在 10^9 个点的范围内选取 10^9 个点，即 Prover 蒙对的概率接近 100%，协议的可靠性就彻底丧失了。

那么如何保证 Prover 生成的多项式 P(x) 和计算出的 C'(x) 的度数在符合要求的范围内呢，也就是如何才能通过检查 Prover 提供的多项式的取值点，来知道这些点对应的多项式的度数是否小于某个阈值呢？

这个问题又被称作 Low Degree Testing（低度测试）问题：LDT 是指通过仅对函数进行少量 Query 来确定给定函数是否是某个有界度的多项式的问题。

LDT 已经研究了二十多年，是概率证明理论的核心工具，也是零知识证明协议中最复杂的问题。最终版 zk-STARK 中使用 FRI Protocol（Fast Reed-solomon Interactive oracle proofs of proximity）进行了 LDT。

LDT 目前来看主要有两个方向的解决思路：

一、使用同态加密、KCA等方法，使得 Prover 只能够在事先提供的加密幂值（可信设置）上进行线性计算。由于加秘幂值的阶数是事先确认的，所以可以保证 Prover 提供的多项式的度数在特定范围内。

这种方法需要为每种特定的计算执行 Trust Setup 可信设置的操作，发展为zk-SNARKs 类型的零知识证明协议。

二、使用承诺方案的思路，Verifier 可以让 Prover 提供更多的关于多项式的取值信息，通过设计好的协议（比如 FRI Protocol），可以得到结论：Prover 提供的取值点大部分在一个低阶多项式上。

这种方法不需要 Trust Setup 可信设置，称之为 Transparent 透明性，发展为zk-STARKs 类型的零知识证明协议。

关于 Low Degree Testing，具体可以参见 STARK 论文作者 Eli Ben Sasson 的科普文章：

https://medium.com/starkware/low-degree-testing-f7614f5172db

一、其他ZKP系统

1、hPKC：Homomorphic Public-Key Cryptography 同态公钥密码，如Pinocchio和libSNARK。

2、DLP：Discrete Logarithm Problem 离散对数问题，如BulletProofs。

3、IP：Interactive Proofs 交互式证明，如Hyrax。

4、MPC：Secure Multi-Party Computation 多方安全计算，如ZKBoo、Ligero。

5、IVC：Incrementally Verifiable Computation 增量可验证计算，如hPKC-based IVC。

二、测试指标

测试均基于同一个硬件服务器，基于同样的DPM（DNA Profile Match）问题。使用 Arithmetic circuit complexity（算术电路复杂度）作为标准测量场。测试的所有 ZKP 系统均为算术化之后的运算，将计算完整性(CI)语句简化为相关的有限域上的低次多项式系统，测试算数电路的参数：

数据库中有 n 条数据

电路深度 = 62·n

电路宽度 = 81

秘密复杂度 = 40·n bytes

乘法复杂度 = 1467·62·n ≈ (2^16.4)·n

三、测试结论

ZK-STARK 是测量的所有电路尺寸中生成证明最快的，特别是与广泛采用的 libSNARK 相比较，速度快了近 10 倍。

在小电路情况下 Ligero 和 ZKBoo 的通信时间更短，验证更快。在深度较小的电路的情况下，Hyrax的通信时间更短，验证更快。

在同一固定电路上多次重复的计算，BulletProofs, Pinocchio, libSNARK 的通信时间更短，验证更快。

但是对于一般的大规模计算，ZK-STARK 的验证时间和通信复杂性优于其他透明系统。换句话说，对 ZK-STARK 的实践表明：对于实际相关的具体计算( 如DPM )，已经充分体现了完全可伸缩性和透明性的优势，并表明 zk-STARK 系统类型对于构建可伸缩性解决方案很有用， 例如用于分布式的加密货币。

zk-STARK 论文的作者 Eli Ben Sasson 创建了 StarkWare 区块链项目，并担任项目的 Co-Founder 联合创始人兼 President 总裁。

一、StarkWare 简介

项目官网：https://starkware.co/

项目简介：STARK证明的先驱（以色列项目方），为区块链带来可扩展性、安全性和隐私性。（可扩展性解决方案：在cloud中运行的off-chain prover生成的加密证明，然后由on-chain smart-contract进行验证）。

二、StarkWare 资方

2021年11月16日，Series C 5000万刀，项目估值达到20亿刀，Sequoia Capital、Paradigm、Three Arrows Capital、Alameda Research、Founders Fund。

2021年3月24日，Series B 7500万刀，Paradigm、Three Arrows Capital、Founders Fund、DCVC、Wing VC。

2018年11月29日，Series A 3000 万刀，Paradigm领投、Intel Capital、Sequoia、Atomico、DCVC、Wing、Consensys、Coinbase Ventures、Multicoin Capital、Collaborative Fund、Scalar Capital、Semantic Ventures。

三、StarkWare 产品一：StarkNet（https://starknet.io/）

StarkNet 是一个无需许可的去中心化 ZK-Rollup，支持独立部署智能合约。 任何开发人员都可以在无需许可的情况下编写和部署他们的智能合约。 StarkNet 还支持可组合性。

它作为以太坊上的 L2 网络运行，使任何 dApp 能够实现其计算的无限规模，而不会影响以太坊的可组合性和安全性。

四、StarkWare 产品二：StarkEx

StarkEx 是经过许可的、定制的，位于以太坊主网上的L2可扩展性引擎，以满足应用程序的特定需求。于2020年6月在以太坊主网launched。

StarkEx 的工作流程：

1、Operator 在 off-chain 将用户 Tx 进行 batch，然后 Sent batch to StarkEx Service

2、StarkEx Service 校验 batch ，将相关 balance 更新

3、StarkEx Service 生成：可以证明 batch 中交易合法性的 STARK proof，然后send proof on-chain即上链

4、on-chain Verifier smart contract 收到STARK proof，验证通过后提交 new balance state 上链存储。

五、Cairo 语言

Cairo 是富有表现力和高性能的 ZKP 编程语言。

Cairo 是StarkNet 合约的原生语言，可充分优化 StarkNet 的扩展潜力。

Cairo 同时允许 StarkEx 支持任何业务逻辑。

StarkWare正在开发从 Solidity 和其他编程语言到 Cairo 的转译器，这些转译器将允许在 StarkNet 上快速部署。

六、项目里程碑

2018年: STARK 白皮书发布，获得以太坊基金会 Grant。

2019年: 第一个 Demo 发布 (扩大以太坊效率200倍)，StarkEx Alpha 发布测试网, 第二个 Demo 发布 (扩大以太坊效率700倍)。

2020年: DeversiFi (StarkEx 1.0) 发布主网，VeeDo (基于Stark的VDF) 发布主网，StarkEx Rollup 发布主网，ethSTARK发布，Cairo (图灵完备的针对STARK语言) 以及其 PlayGround 发布，Ziggy STARK (后量子安全的安全签名) 发布，StarkEx 2.0 发布主网。

2021年: StarkNet 发布，dYdX 与 Immutable X (均为StarkWare的客户) 项目发布主网。

七、StarkWare 业绩

DiversiFi 的支付 TPS 可以达到 18k。

Immutable 的 NFT 铸造费用仅需 0.2 美分。

dYdX 的交易费用缩减到了1/50，秒级确认,，费率几乎为 0，带来了极佳的用户体验。

截止到2022年2月3日，DeversiFi、dYdX、Immutable、Sorare 通过StarkEx平台实现了TVL 11亿刀，10.2万笔Tx，交易额累计3780亿刀。DYOR

================================

================================

欢迎大佬们的探讨指正～

您可以在这里找到作者 twitter：@ethan_ifdao