学校网站建设管理,网站收录上万没有流量,优秀网站设计分析,网站基本功能全称为 Zero-Knowledge Succinct Non-Interactive Argument of Knowledge#xff0c;简洁非交互式零知识证明#xff0c;简洁性使得运行该协议时#xff0c;即便 statement 非常大#xff0c;它的 proof 大小也仅有几百个bytes#xff0c;并且验证一个 proof 的时间可以达…全称为 Zero-Knowledge Succinct Non-Interactive Argument of Knowledge简洁非交互式零知识证明简洁性使得运行该协议时即便 statement 非常大它的 proof 大小也仅有几百个bytes并且验证一个 proof 的时间可以达到毫秒级别。这是一个通用的零知识证明协议可以用作各种证明如范围证明。核心方法是通过R1CSQAP等方法将计算难题变为多项式将计算结果正确性巧妙转化为了多项式的有特殊解的问题生成对应proof然后再运用多项式证明方法来完成证明与验证。
Non-Interactive Argument of Knowledge of a Polynomial
注意 计算和参数选取是在域内即有模运算
一般多项式的证明
场景如下Verifier 有一个多项式 f ( x ) f(x) f(x)Prover 向 Verifer 证明他知道这一个多项式。假设 Prover 知道的多项式为 p ( x ) p(x) p(x)那么现在要证明的就是 f ( x ) p ( x ) f(x)p(x) f(x)p(x)如果这两个多项式的阶数最高为 d d d那么两个多项式代表的曲线将最多有 d d d个交点当 Verifier 随机在一个很大的范围内取一个值 s s s的时候那么 s s s和 d d d相同的概率会非常低所以有以下协议
Verifier 在大范围里随机选择一个值 s s s并且在本地计算 f ( s ) f(s) f(s)然后把 s s s发送给 ProverProver 计算 p ( s ) p(s) p(s)然后发送给VerifierVerifier 验证 f ( s ) ? p ( s ) f(s)\overset{?}p(s) f(s)?p(s)
证明多项式的根
有些多项式是可以分解多个多项式的乘积的如假设 p ( x ) ( x − a ) ( x − b ) ( x − c ) p(x)(x-a)(x-b)(x-c) p(x)(x−a)(x−b)(x−c)那么假设 Prover 有一个多项式 p ( x ) p(x) p(x)现在他想证明他的多项式持有一部分根部分多项式也就是证明他的多项式 p ( x ) t ( x ) h ( x ) p(x)t(x)h(x) p(x)t(x)h(x)中包含 t ( x ) t(x) t(x)假设为 ( x − a ) ( x − b ) (x-a)(x-b) (x−a)(x−b)而此时的 t ( x ) t(x) t(x)称为目标多项式是公开的要注意 Prover 是不能透露原多项式的。那么有以下协议
Verifier 在大范围内随机取值 s s s计算 t t ( s ) t t(s) tt(s)然后将 s s s发送给 ProverProer 计算 h ( x ) p ( x ) t ( x ) h( x) \frac {p(x)}{t(x)} h(x)t(x)p(x), h ( s ) h(s) h(s), p ( s ) p(s) p(s)然后发送后两个给 VerifierVerfier 验证 p ( s ) ? t ( s ) h ( s ) p(s)\overset{?}t(s)h(s) p(s)?t(s)h(s)
显而易见以上变量都局限为整数如果 p p p确实能够整除 t t t那么等式一定是成立的如果不能那么式子将存在余式有极大的概率不是整数。当然此协议仍然有很大漏洞比如 Prover 可能完全不知道 p ( x ) p(x) p(x)但知道公开的 t ( x ) t(x) t(x)所以可以完全捏造出 h ( x ) h(x) h(x)满足条件。
同态加密
显然我们不能在协议里进行明文的传输但又需要密文的计算所以需要一个满足加密和计算两种特性的算法。同态加密算法 E ( x ) E(x) E(x)如 E ( a x b y ) g a x b y g a x ⋅ g b y ( g x ) a ⋅ ( g y ) b E ( x ) a ⋅ E ( y ) b . E(a xb y)g^{a xb y}g^{a x} \cdot g^{b y}\left(g^{x}\right)^{a} \cdot\left(g^{y}\right)^{b}E(x)^{a} \cdot E(y)^{b} . E(axby)gaxbygax⋅gby(gx)a⋅(gy)bE(x)a⋅E(y)b. g g g是生成元这里基于离散对数难题和 CDH 假设即给定 g a , g b g^a,g^b ga,gb得到 g a b g^{ab} gab很困难。显然这是仅仅满足同态加法的同态加密不支持密文相乘。那么该算法不支持乘法仅有一个 s s s的情况下该怎么同态计算多项式呢显然是不行的于是想办法把同态乘法转变为同态加法注意到多项式 P ( x ) P(x) P(x)可以看作是一组系数和未知数的线性结合也就是计算出 s s s的各个幂次这需要固定好多项式的阶数 d d d相当于限制了多项式的阶数这样提前计算出 s 1 , … , s d s^1,\dots,s^d s1,…,sd然后计算出多项式的每个部分相加即可。具体使用如下
Verifier 在大范围里随机选择一个 s s s先计算好 s s s的幂次 s 1 , … , s d s^1,\dots,s^d s1,…,sd接着计算 t ( s ) t(s) t(s)最后 E ( 1 ) , E ( s ) , … , E ( s d ) E(1),E(s),\dots,E(s^d) E(1),E(s),…,E(sd)并发给 ProverProver 收到数据后计算 h ( x ) p ( x ) t ( x ) h( x) \frac {p(x)}{t(x)} h(x)t(x)p(x)然后配合多项式的系数计算 E ( p ( s ) ) E(p(s)) E(p(s)) E ( h ( s ) ) E(h(s)) E(h(s))并发送给VerifierVerifier 进行验证 E ( p ( s ) ) ? E ( t ( s ) ) E ( h ( s ) ) E(p(s))\overset{?}E(t(s))E(h(s)) E(p(s))?E(t(s))E(h(s))即 g p ( s ) ( g h ( s ) ) t ( s ) g^{p(s)} (g^{h(s)})^{t(s)} gp(s)(gh(s))t(s) ** KCAThe Knowledge of Coefficient Test and Assumption**
上面的协议的还是有很大漏洞比如 Prover 在计算多项式的时候没有采用多项式的格式常数系数和未知数的线性组合而是使用了另外的方法算法找到一个满足 z p ( z h ) t ( s ) z_p (z_h)^{t(s)} zp(zh)t(s)的两个值 z p , z h z_p,z_h zp,zh去替代掉 g p ( s ) , g h ( s ) g^{p(s)},g^{h(s)} gp(s),gh(s)也就是根本没用多项式直接仿造了满足条件的结果。这里就需要对 Prover 进行限制让他必须使用满足条件的多项式限定为常数也限定了指数不能随意改变指数。所以KCA也可以叫做KEA(Knowledge of exponent)思路如下定义一对元素 ( a , b α ⋅ a ) (a,b \alpha \cdot a) (a,bα⋅a)称为一个 α \alpha α-对, α ⋅ a \alpha \cdot a α⋅a表示 α \alpha α个 a a a相加也就是 a α a^\alpha aα那么一个KC流程如下具体如下
首先Verifier会随机选择一个非零的 α \alpha α计算 b α ⋅ a b \alpha \cdot a bα⋅a定义这是一个 α − s h i f t \alpha -shift α−shift。Verifier 发送这个 challenge pair ( a , b ) (a,b) (a,b)给 Prover。这时候 Prover 会 respond 一对不一样但具有相同性质的 pair ( a ′ , b ′ ) (a,b) (a′,b′)它应当是 α − s h i f t \alpha -shift α−shift如果收到的是一个 α − s h i f t \alpha -shift α−shift那么Verifier 接受这个response
注意这是满足DL问题的 Prover 是很难找到一个 α \alpha α那么她该如何构造新的 α − s h i f t \alpha -shift α−shift呢一个显而易见的方式是Prover 选择一个常数系数 γ \gamma γ直接构造 ( a ′ , b ′ ) γ ( a , b ) (a,b) \gamma(a,b) (a′,b′)γ(a,b)。假设 Verifier 发送的不是一个而是是 d d d组 α − s h i f t \alpha -shift α−shift那么 Prover 也将选择一组系数 c 1 , … , c d c_1,\dots,c_d c1,…,cdrespond 一个 ( a ′ , b ′ ) ( ∑ i 1 d c i a i , ∑ i 1 d c i b i ) (a,b) (\sum_{i1}^d c_ia_i,\sum_{i1}^d c_ib_i) (a′,b′)(∑i1dciai,∑i1dcibi)显然该对也是满足 α − s h i f t \alpha -shift α−shift。如果把 Verifier 发的内容优化一下就构成了KCA。 Blind Evaluation of Polynomials Verifiable Protocol
完整的多项式盲验证协议。解决整个问题需要满足的两个性质
**Blindness**也就是 Prover 不能获取到 s s s同样 Verifier 也不能拿到 p ( x ) p(x) p(x)同态。**Verifiability**也就是得确保 Prover 发的 E ( p ( x ) ) E(p(x)) E(p(x))确实是用某个多项式 p ( x ) p(x) p(x)计算的而不是完全不相关的数据KCA
那么使用KCA对前面协议进行优化如下
Verifier 随机选择 α \alpha α非0和 s s s然后计算 t ( s ) t(s) t(s)接着构造 α − s h i f t \alpha -shift α−shift ( g , g α ) , ( g s , g α ⋅ s ) , … , ( g s d , g α ⋅ s d ) (g,g^{\alpha}),(g^s,g^{\alpha \cdot s} ),\dots,(g^{s^d},g^{\alpha \cdot s^d}) (g,gα),(gs,gα⋅s),…,(gsd,gα⋅sd)Prover 则使用多项式 p ( x ) p(x) p(x)的系数 c 1 , … , c d c_1,\dots,c_d c1,…,cd然后计算 E ( h ( s ) ) E(h(s)) E(h(s))以及 ( E ( p ( s ) ) , E ( α p ( s ) ) ) ( g ∑ i 1 d c i s i , g ∑ i 1 d c i α ⋅ s d ) (E(p(s)),E(\alpha p(s))) (g^{\sum_{i1}^d c_is^i},g^{\sum_{i1}^d c_i\alpha \cdot s^d}) (E(p(s)),E(αp(s)))(g∑i1dcisi,g∑i1dciα⋅sd)发送给VerifierVerifier进行验证 E ( p ( s ) ) ? E ( α p ( s ) ) E(p(s))\overset ?E(\alpha p(s)) E(p(s))?E(αp(s))和 E ( p ( s ) ) ? E ( t ( s ) ) E ( h ( s ) ) E(p(s))\overset{?}E(t(s))E(h(s)) E(p(s))?E(t(s))E(h(s))即可
该方案也可以解决前面的问题即Prover 不能随意构造满足类似 z p ( z h ) t ( s ) z_p (z_h)^{t(s)} zp(zh)t(s)的 h ( s ) h(s) h(s)这样会很容易不满足 α − s h i f t \alpha -shift α−shift的限制条件。 Parings and bilinear map
前面的协议基本实现了诚实两方之间的交互方案相关的 proof 仅仅在两方之间有效无法重复使用但在实际运用中存在这恶意的多方的情况这显然不符合实际。所以需要让一些秘密参数变得可重复使用甚至公开而且足够可信以防止滥用。首先考虑将 Verifier 生成的 ( t ( s ) , α ) (t(s),\alpha) (t(s),α)进行加密保护防止泄露。如果采用前面的同态加密那么在后面的乘法计算中就会涉及到同态的乘法 但是前面用的同态算法不支持同态乘法。那么必须用到类似乘法的时候应该怎么办呢这时候就引入了椭圆双曲线映射。Parings 是能够将一个集合里的两个加密输入确定性的映射到另一个集合里的一个输出的一种乘法表示函数。即 e : G × G → G T e: \mathbb{G} \times \mathbb{G} \rightarrow \mathbb{G}_T e:G×G→GT满足以下性质 e ( g 1 a , g 2 b ) e ( g 1 , g 2 ) a b e ( g 1 a b , g 2 ) e ( g 1 , g 2 a b ) \begin{aligned}e(\mathrm{g_1^a,g_2^b})\mathrm{e(g_1,g_2)^{ab}e(g_1^{ab},g_2)e(g_1,g_2^{ab})}\end{aligned} e(g1a,g2b)e(g1,g2)abe(g1ab,g2)e(g1,g2ab) e ( g 1 a , g 2 b ) e ( g 1 c , g 2 d ) e ( g 1 , g 2 ) a b c d \begin{aligned} e(\mathrm{g_1^a,g_2^b})e(\mathrm{g_1^c,g_2^d})\mathrm{e(g_1,g_2)^{abcd}}\end{aligned} e(g1a,g2b)e(g1c,g2d)e(g1,g2)abcd 其意义在于将某个群中的一对元素映射到一个新的群当且仅当两个原像对应指数的积相同其像也相同。并且该函数要求是可计算的即不需要用暴力搜索等方式它能够验证一对加密后的数据的乘积是否和另一对相同虽然算不出这个乘积 接下来将协议的计算放到满足Parings的椭圆曲线群上来。 Multiple Parties Composite Common Reference String
首先引入一个可信的第三方来随机生成 s s s和 α \alpha α并且计算出CRSCommon Reference String共证明和验证两部分都是公开的 i ∈ { 0 , … , d } i \in \{0,\dots,d\} i∈{0,…,d}接着需要删除掉 s s s和 α \alpha α。
Proving Key E ( s i ) , E ( α s i ) g s i , g α s i E(s^i),E(\alpha s^i) g^{s^i},g^{\alpha s^i} E(si),E(αsi)gsi,gαsiVerification Key E ( t ( s ) ) , E ( α ) g t ( s ) , g α E(t(s)),E(\alpha) g^{t(s)},g^{\alpha} E(t(s)),E(α)gt(s),gα
接着基于CRS让 Prover 和 Verifier 仅仅通过CRS就能完成协议。继续优化协议如下下面简化 p p ( s ) , t , h pp(s),t,h pp(s),t,h也类似
对于 Prover 来说公开的CRS中已经包含了第一步的内容接下来是利用 Proving Key 来计算出 E ( h ( s ) ) E(h(s)) E(h(s))和 ( E ( p ( s ) ) , E ( α p ( s ) ) ) (E(p(s)),E(\alpha p(s))) (E(p(s)),E(αp(s)))对于Verifier来说是利用CRS中的 Verfication来进行验证 p ′ α p p \alpha p p′αp 首先验证 p t ⋅ h pt \cdot h pt⋅h即 e ( g p , g 1 ) e ( g t , g h ) e ( g , g ) p e ( g , g ) t ⋅ h e(g^p,g^1) e(g^t,g^h) e(g,g)^p e(g,g)^{t \cdot h} e(gp,g1)e(gt,gh)e(g,g)pe(g,g)t⋅h然后验证 α − s h i f t \alpha -shift α−shift即 e ( g p , g α ) e ( g p ′ , g ) e(g^p,g^\alpha) e(g^{p},g) e(gp,gα)e(gp′,g)
注意这里也暴露出两个问题
Proving Key 中的 E ( α ) E(\alpha) E(α)是公开的也就是对于 Prover 来说 他是可以打破多项式的限制条件的。引入了一个可信第三方但更复杂的现实中不能保证第三方不存在恶意比如不销毁 trusted setup 的随机秘密这一旦暴露会导致任何人都可以伪造证明。
于是 ZKSNARK 引入了多方联合的setup每个人用自己的私钥 ( α , s ) (\alpha,s) (α,s)和前一个人生成的 CRS 作为输入生成一个新的 CRS只要保证有一个人销毁了私钥就能保证最终的CRS是安全的。具体实现如下假设有三方 Alice,Bob,Carol 参与仅需要使用同态乘法让每个人的私钥相加即可同理参与方 Carol 公开后也可以进行验证。
完整的简短非交互式的多项式证明方案
这里用 { g s i } i ∈ [ d ] \{g^{s^i}\}_{i\in[d]} {gsi}i∈[d]代表 s 1 , … , s d s^1,\dots,s^d s1,…,sd首先确定好目标多项式 t ( x ) t(x) t(x)和 prover 的多项式的阶数 d d dprover 需要证明他持有的多项式里含有 t ( x ) t(x) t(x)。具体如下 参考
浅谈零知识证明背景与起源zcash官方科普Exploring Elliptic Curve PairingsQuadratic Arithmetic Programs: from Zero to HeroWhy and how zk-SNARK worksZKSNARK介绍李威翰,张宗洋,周子博等.简洁非交互零知识证明综述[J].密码学报,2022,9(03):379-447.DOI:10.13868/j.cnki.jcr.000525.
