区块链技术博客
www.b2bchain.cn

区块链技术ZKSwap 解读零知识证明最新进展:RedShift 红移算法

第17395篇区块链技术文章区块链技术ZKSwap 解读零知识证明最新进展:RedShift 红移算法

它不需要信任设置,也不依赖于任何数学问题。具有量子电阻的Zkp算法效率更高,复杂度更低

写在前面

随着区块链技术的发展,Zkp(zero knowledge proof)技术越来越多地应用于隐私和二层扩展领域,技术也在不断更新。从需要不同信任设置的zkp(如groth16),到需要一个信任设置来支持更新的zkp(如plonk),再到不需要信任设置的zkp(如stark),zkp算法逐渐走向去中心化,从依赖经典NP问题到不依赖任何数学问题,zkp算法逐渐向反量子化方向发展

当然,我们希望zkp算法不需要建立信任,不依赖任何数学问题,具有量子抵抗能力,也能有更好的效率和更低的复杂度(Stark的证明太大)。是红移。

REDSHIFT

ZKSwap 解读零知识证明最新进展:RedShift 红移算法

因此,只要读者对plonk算法有深入的了解,我相信理解红移算法会相对简单。Zkswap团队之前对plonk算法做了深入的分析。在零知识证明算法的plonk电路中,分析了plonk算法中电路的详细设计,包括语句->电路->详细阐述了plonk算法中“置换检查”的原理和意义。本文对plonk协议的零知识证明算法进行了详细的分析,其中多项式承诺起着重要的作用:为了保证算法的简洁性和保密性,零知识证明算法的第一步是算法化,它将问题证明者想要证明的问题转化为多项式方程的形式。如果多项式方程为真,则表示原问题的关系为真。证明多项式方程是否成立相对简单。根据Schwartz-Zippel定理,可以推断n的最高阶的两个多项式的交点至多为n

但是,上述方法存在一定的疑问,“如何保证校验器提供的值是某一点的多项式值,而不是专门选定的保证校验通过的值,而且这个值不是多项式计算出来的?”为了解决这一问题,在经典snark算法中,采用了KCa算法来保证在vgod的ZK snarks序列中可以看到具体的原理。在plonk算法中,引入了多项式承诺的概念。具体的原理可以在零知识证明算法的plonk协议中提及,简言之,该算法使验证者在不暴露多项式的情况下,相信多项式在某一点上的值就是证明者所声称的值。两种算法都能解决上述问题,但通信复杂度较小,因此更简洁

红移算法的协议部分将在下面详细介绍。如上所述,该算法与plonk算法非常相似,因此本文只对不同部分进行了详细的介绍,为了方便读者理解,将相似部分划出,如下图所示:

ZKSwap 解读零知识证明最新进展:RedShift 红移算法

协议的步骤1-6体现在算法设计中对于plonk算法,本文重点分析了plonk算法中的第7步,为了使验证者相信多项式等式关系已经建立,验证者随机选择一个点,然后验证者提供各种多项式的承诺(包括setup poly、consistent poly和witness)poly),因此,作为plonk算法的子协议,plonk算法自然需要信任设置,依赖于redshift协议中的离散对数问题,多项式的承诺是基于Merkel树的(简而言之,所有多项式在域H中的值都被计算出来并作为Merkel树的叶节点,最后的根就是承诺(commitment)。如果证明者想证明一个多项式在某一点上的值,只需根据这些值插值一个特定的多项式,然后用原多项式做商,证明商也是一个多项式(阶数是有限的)

当然,为了保护隐私,我们需要隐藏原始多项式,类似于上述协议中的第一步。在实际设计中,为了方便fri协议的操作,我们经常设计原多项式d=2^n+K(其中K=log(n))的阶数。也许读者一直在想上面提到的FRI协议是如何工作的。Zkswap解释了fri(stark系列)的具体原理,如果您感兴趣,可以点击以下链接阅读:

协议

1。零知识证明算法zk-stark的理解
2。零知识证明算法zk-stark的理解——优化
3。零知识证明算法zk-stark的理解——低阶测试
4。了解零知识证明算法的zk stark——fri协议

源链接:zks.org网站你知道吗

协议的 1-6 步骤在 PLONK 的算法设计里都有体现,这里着重分析一下后续的第 7 步骤。

在 PLONK 算法里,prover 为了使 verifier 相信多项式等式关系的成立,由 verifier 随机选取了一个点,然后 prover 提供各种多项式(包括 setup poly、constriant ploy、witness poly)的 commitment,由于使用的 Kate commitment 算法需要一次 Trust Setup 并依赖于离散对数难题,因此作为 PLONK 算法里的子协议,PLONK 算法自然也需要 Trust Setup 且依赖于离散对数难题。

在 REDSHIFT 协议里,多项式的 commitment 是基于默克尔树的(简单讲,计算多项式在域 H 上的所有值,并当作默克尔树的叶子节点,最终形成的根,即为 commitment)。若 prover 想证明多项式在某一个或某些点的值,证明方只需要根据这些值插值出具体的多项式,然后和原始的多项式做商并且证明得到商也是个多项式(阶是有限制的)即可。

当然为了保护隐私,需要对原始多项式做隐匿处理,类似于上图协议中的第一步。在实际设计中,为了方便 FRI 协议的运行,往往设计原始多项式的阶 d = 2^n + k (其中 k = log(n))。可能读者一直在疑惑前面一直提到的 FRI 协议具体是怎么运行的,ZKSwap 曾对 FRI 的具体原理进行过解读(STARK 系列),感兴趣的可点击链接进行阅读:

1.《理解零知识证明算法之 ZK-STARK》
2.《理解零知识证明算法之 ZK-STARK — Arithmetization》
3.《深入理解零知识证明算法之 ZK-STARK — Low Degree Testing》
4.《深入理解零知识证明算法之 ZK-STARK — FRI 协议》

来源链接:zks.org

区块链技术ZKSwap 解读零知识证明最新进展:RedShift 红移算法 由www.b2bchain.cn 提供
文章整理自网络,只为个人学习与分享使用
链接地址https://www.b2bchain.cn/17395.html

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 区块链技术ZKSwap 解读零知识证明最新进展:RedShift 红移算法
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们