当然，我们希望一个不需要Trust Setup，不依赖任何数学问题，有量子阻力的ZKP算法，也有更好的效率和更低的复杂度(STARK的证明太大)，就是红移。

写在前面

随着区块链技术的发展，ZKP(零知识证明)技术在隐私和第二层扩展领域的应用越来越多，技术不断迭代更新。从需要不同信任设置的ZKP(如Groth16)，到需要信任设置并支持更新的ZKP(如Plonk)，再到不需要信任设置的ZKP(如STARK)，ZKP算法逐渐走向去中心化。从依赖经典NP问题到不依赖任何数学问题，ZKP算法逐渐走向反量化。

当然，我们希望一个不需要Trust Setup，不依赖任何数学问题，有量子阻力的ZKP算法，也有更好的效率和更低的复杂度(STARK的证明太大)，就是红移。

REDSHIFT

《REDSHIFT: Transparent SNARKs from List Polynomial Commitment IOPs》，可以从名字推导出来，是一个基于List多项式承诺的透明SNARK算法。算法本身和PLONK最相似，唯一不同的是多项式承诺的图元不一样。下面是一个简单的表格，显示了红移和PLONK算法之间的异同，如下所示：

所以，只要读者对PLONK算法有深入的了解，再去了解红移算法，将是一件相对简单的事情。ZKSwap团队在此之前已经对PLONK算法做了深入的分析。我们分析了《零知识证明算法之 PLONK --- 电路》文章中PLONK算法中电路部分的详细设计，包括表格中的《Statement - Circuit - QAP》过程，还详细描述了PLONK算法中“置换校验”的原理和意义。零知识证明算法的协议plonk分析了PLONK的协议细节，其中多项式承诺起着重要的作用：保持算法的简单性和保密性。

我们知道，零知识证明算法的第一步是算术，即将证明者要证明的问题转化为多项式方程的形式。如果多项式方程成立，说明原问题关系成立。证明一个多项式方程关系是否成立比较简单。根据Schwartz-Zippel定理，可以推断出两个最高次为N的多项式的交点最多为N.

换句话说，如果在一个很大的域(远大于n)内随机选取一个点，如果多项式的值相等，那么这两个多项式是相同的。因此，验证者只需要随机选择一个点，证明者在这个点提供多项式的值，然后验证者就可以判断多项式方程是否有效，保证了隐私性。

然而，上述方法存在一些疑问。“如何保证证明者提供某一点的多项式的值，而不是自己特意选择的值，以保证验证通过，而且这个值不是多项式计算出来的？”为了解决这个问题，在经典snark算法中使用了KCA算法。具体原理可以在V神的zk-snarks系列中找到。在plonk算法中，引入了多项式承诺的概念，具体原理可以参考零知识证明算法的PLONK协议。

简单来说，算法的实现就是在不暴露多项式的情况下，让验证者相信多项式在某一点的值确实是证明者所主张的值。两种算法都可以解决上述问题，但从通信复杂度来说，多项式承诺更小，所以更简洁。

下面将详细介绍红移算法的协议部分。如前所述，这个算法与PLONK算法非常相似，所以本文只详细介绍不同的部分；类似的部分会标注出来让读者理解，如下图所示：

协议的步骤1-6体现在PLONK的算法设计中，所以这里重点分析下面的步骤7。

在PLONK算法中，证明者随机选择一个点，以使验证者相信多项式等式关系成立，然后证明者提供各种多项式的承诺(包括设置多项式、约束多项式、见证多项式)。由于Kate承诺算法需要一个信任设置，并且依赖于离散对数问题，因此作为PLNK算法的子协议，PLNK算法自然需要一个信任设置，并且依赖于离散对数问题。

在红移协议中，多项式的承诺是基于默克尔树的(简单来说就是计算出域h中多项式的所有值，作为默克尔树的叶节点，最终根是承诺)。如果证明者想证明某个或某几个点的多项式的值，那么证明者只需要根据这些值对具体的多项式进行插值，然后与原多项式进行商，证明商也是多项式(阶有限)。

当然，为了保护隐私，需要隐藏原始多项式，类似于上面协议中的第一步。在实际设计中，为了方便FRI协议的操作，往往会设计原多项式的阶数d=2 ^ n ^ k(其中k=log(n))。也许读者一直想知道上面提到的FRI协议是如何工作的。ZKSwap解释了FRI (STARK系列)的具体原理。感兴趣的用户可以点击链接阅读：

《理解零知识证明算法之Zk-stark》

《理解零知识证明算法之Zk-stark -- Arithmetization》

《深入理解零知识证明算法之Zk-stark -- Low Degree Testing》

《深入理解零知识证明算法之Zk-stark -- FRI协议》