零知识证明学习（五）— zkSNARKs（构造多项式）

zkSNARK-密码学基础

本节接着上一节继续讲

零知识

因为验证者可能从证明者发送的信息抽取关于多项式 p ( x ) p(x) p(x)的更多信息，让我们考虑证明者提供的信息： g p , g p ′ , g h g^p,g^{p'},g^h gp,gp′,gh。主要做的验证： g p = ( g h ) t ( s ) , ( g p ) α = g p ′ g^p = (g^h)^{t(s)},(g^p)^{\alpha}=g^{p'} gp=(gh)t(s),(gp)α=gp′。这个问题是我们怎么进行有效的验证，信息还不被抽取呢？一个问答是：我们使用一个随机数 δ \delta δ偏移这些值，例如： ( g p ) δ (g^p)^{\delta} (gp)δ。现在，为了抽取这个知识，需要找到这个随机数，然而这是不可能。我们展示一下详细的偏移过程，证明者抽取随机数 δ \delta δ，并做为证明值的幂次： ( g p ( s ) ) δ , ( g h ( s ) ) δ , ( g α p ( s ) ) δ (g^{p(s)})^{\delta},(g^{h(s)})^{\delta},(g^{\alpha p(s)})^{\delta} (gp(s))δ,(gh(s))δ,(gαp(s))δ，发送给验证者核验： ( g p ) δ = ( ( g h ) δ ) t ( s ) , ( ( g p ) δ ) a l p h a = ( g p ′ ) δ (g^p)^{\delta}=((g^h)^{\delta})^{t(s)},((g^p)^{\delta})^{alpha}=(g^{p'})^{\delta} (gp)δ=((gh)δ)t(s),((gp)δ)alpha=(gp′)δ。

非交互性

从上述方案来看，我们设计的是一个交互式零知识证明方案。为什么是这种情况呢？因为证明只对原始的验证者有效，没有人(其他验证者)可以信任相同的证明，因为:

验证者可能与证明者勾结，揭露那些允许伪造证明的秘密参数 s , α s,\alpha s,α验证者自己也可以出于同样的原因生成假证明验证者一定要存储 α , t ( s ) \alpha ,t(s) α,t(s)，直到相关证明被验证，这就使得额外的攻击可能会泄露秘密参数

因此，为了证明一个陈述(在这种情况下是多项式的知识)，需要与每个验证者进行单独的交互。而交互式证明系统也有它的用例，例如当一个证明者只想说服一个专门的验证者，这样证明就不能被重复用来向其他人证明相同的陈述，当一个人需要同时(例如，在像区块链这样的分布式系统中)或永久地说服许多人时，它是非常低效的。证明者将被要求一直保持在线，并对每个验证程序执行相同的计算。因此，我们需要秘密参数是可重用的，公开的，值得信任的和不可滥用的。我们需要如何安全的保护产生的参数 ( t ( s ) , α ) (t(s), \alpha) (t(s),α)，我们可以用验证者在发送给证明者之前加密 s s s的相同方式加密它们。然而，我们使用的同态加密不支持两个加密值的相乘，这对于 t ( s ) t(s) t(s)和 h h h的加密相乘以及 p p p和 α α α的加密相乘的验证检查都是必需的，因此，引出下述方法。

加密值乘法（Multiplication of Encrypted Values）

密码配对(双线性映射)是一种数学结构,表示为一个函数 e ( g ∗ , g ∗ ) e(g^*,g^*) e(g∗,g∗)，考虑到两个加密的输入(例如： g a , g b g^a,g^b ga,gb)从一组数据允许它们映射确定性乘积表示的一组不同的输出的数字,例如： e ( g a , g b ) = e ( g , g ) a b e(g^a,g^b)=e(g,g)^{ab} e(ga,gb)=e(g,g)ab。

由于源数集和输出数集是不同的，因此配对的结果不能作为另一个配对 *** 作的输入。我们可以将输出集(也称为目标集)视为来自另一个世界。因此，我们不能将结果乘以另一个加密的值，根据名称本身的建议，我们一次只能将两个加密的值相乘。在某种意义上，它类似于一个哈希函数，它将所有可能的输入值映射到可能输出值集合中的一个元素，而且它不是简单的可逆的。

双线性映射函数 e ( g ∗ , g ∗ ) e(g^*,g^*) e(g∗,g∗)的一个基本的(技术上不正确的)数学类比是，有一种方法可以交换每个输入的底数和指数，这样底数 g g g在转换为指数的过程中被修改，例如， g a → a g g^a \to a^g ga→ag。然后将交换后的两个输入相乘，使原始的a和b值在相同的指数下相乘， e ( g a , g b ) = a g ⋅ b g = ( a b ) g e(g^a,g^b)=a^g \cdot b^g=(ab)^g e(ga,gb)=ag⋅bg=(ab)g。因此，由于在交换过程中使用另一个配对中的结果 ( a b ) g (ab)^g (ab)g(例如， e ( ( a b ) g , g c ) e((ab)^g,g^c) e((ab)g,gc))将不会产生所需的加密乘法 a b c abc abc，因为基数会被更改。

配对的核心性质可以用方程来表示： e ( g a , g b ) = e ( g b , g a ) = e ( g a b , g 1 ) = e ( g 1 , g a ) b = e ( g 1 , g 1 ) a b = . . . e(g^a,g^b)=e(g^b,g^a)=e(g^{ab},g^1)=e(g^1,g^a)^b=e(g^1,g^1)^{ab}=... e(ga,gb)=e(gb,ga)=e(gab,g1)=e(g1,ga)b=e(g1,g1)ab=...

从技术上讲，配对的结果是原始值在目标集的不同生成器 g g g下的加密,，例如， e ( g a , g b ) = g a b e(g^a,g^b)=g^{ab} e(ga,gb)=gab。因此它具有同态加密的性质，例如可以将多对的加密产物叠加在一起： e ( g a , g b ) ⋅ e ( g c , g d ) = g a b ⋅ g c d = g a b + c d = e ( g , g ) a b + c d e(g^a,g^b) \cdot e(g^c,g^d)=g^{ab} \cdot g^{cd} =g^{ab+cd}=e(g,g)^{ab+cd} e(ga,gb)⋅e(gc,gd)=gab⋅gcd=gab+cd=e(g,g)ab+cd.

注意:密码配对是利用椭圆曲线来实现这些属性的，因此从现在开始，标记 g n g^n gn将表示曲线上的一个生成器点，它自己加n次，而不是我们在前几节使用的乘法组生成器。

可信方设置

有了密码配对，我们现在就可以设置安全的公共和可重用参数了。让我们假设我们信任一个诚实的一方来产生秘密 s s s和 α α α。一旦 α α α和 s s s的所有必要幂和相应的α-移位被加密( g α , g s i , g α s i g^{\alpha},g^{s^i},g^{\alpha s^i} gα,gsi,gαsi)，必须删除原始值。这些参数通常被称为通用引用字符串（ ∗ c o m m o n r e f e r e n c e s t r i n g , C R S *common reference string,CRS ∗commonreferencestring,CRS）。 C R S CRS CRS生成后，任何证明者和验证者都可以使用它来进行非交互的零知识证明协议。虽然不重要，但优化版本的 C R S CRS CRS将包括目标多项式 g t ( s ) g^{t(s)} gt(s)的加密计算。

一般 C R S CRS CRS被划分为两组（对于 i ∈ [ 0 , d ] i \in [0,d] i∈[0,d]）:

证明者计算密钥： ( g s i , g α s i ) (g^{s^i},g^{\alpha s^i}) (gsi,gαsi)验证者计算密钥： ( g t ( s ) , g α ) (g^{t(s)},g^{\alpha}) (gt(s),gα)

由于能够将加密值相乘，验证者可以检查协议最后一步中的多项式:

有验证密钥验证者过程从证明者收到加密多项式结果 g p , g h , g p ′ g^p,g^h,g^{p'} gp,gh,gp′ 检查 p = t ⋅ h p=t \cdot h p=t⋅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)\Longrightarrow e(g,g)^p=e(g,g)^{t \cdot h} e(gp,g1)=e(gt,gh)⟹e(g,g)p=e(g,g)t⋅h检查多项式限制： e ( g p , g α ) = e ( g p ′ , g ) e(g^p,g^{\alpha})=e(g^{p'},g) e(gp,gα)=e(gp′,g) 多方里挑出一个

虽然可信设置是有效的，对于 C R S CRS CRS的多个用户它不是有效的，因为 C R S CRS CRS的多个用户将不得不信任一个并删除的 α α α和 s s s，因为目前没有办法证明。因此，有必要尽量减少或消除这种信任。否则，不诚实的一方就能伪造证明而不被发现。实现这一目标的一种方法是由多方生成一个复合 C R S CRS CRS，这样各方都不知道这个秘密。这里有一个方法，让我们考虑三个参与者Alice, Bob和Carol，它们对应的指标是A, B和C，对于 i ∈ [ 1 , d ] i \in [1,d] i∈[1,d]：

Alice随机抽取 s A s_A sA​和 α A \alpha _A αA​，并发布她的 C R S CRS CRS： ( g s A i , g α A , g α A s A i ) (g^{s_{A}^{i}},g^{\alpha _A},g^{\alpha _As_{A}^{i}}) (gsAi​,gαA​,gαA​sAi​)Bob随机抽取 s B s_B sB​和 α B \alpha _B αB​，并通过同态乘法对Alice的 C R S CRS CRS进行增宽: ( ( g s A i ) s B i , ( g α A ) α B , ( g α A s A i ) α B s B i ) = ( g ( s A s B ) i , g α A α B , g α A α B ( s A s B ) i ) ((g^{s_{A}^{i}})^{s_{B}^{i}},(g^{\alpha _A})^{\alpha _B},(g^{\alpha _As_{A}^{i}})^{\alpha _Bs_{B}^{i}})=(g^{(s_As_B)^i},g^{\alpha _A \alpha_B},g^{\alpha _A \alpha _B(s_As_B)^i}) ((gsAi​)sBi​,(gαA​)αB​,(gαA​sAi​)αB​sBi​)=(g(sA​sB​)i,gαA​αB​,gαA​αB​(sA​sB​)i)。发布Alice-Bob的两方 C R S CRS CRS： ( g s A B i , g α A B , g α A B s A B i ) (g^{s_{AB}^{i}},g^{\alpha _{AB}},g^{\alpha _{AB} s_{AB}^{i}}) (gsABi​,gαAB​,gαAB​sABi​)所以Carol随机抽取 s C s_C sC​和 α C \alpha _C αC​：

并公开Alice-Bob-Carol的 C R S CRS CRS： ( g s A B C i , g α A B C , g α A B C s A B C i ) (g^{s_{ABC}^{i}},g^{\alpha _{ABC} },g^{\alpha _{ABC}s_{ABC}^{i} }) (gsABCi​,gαABC​,gαABC​sABCi​)

作为这样的协议的结果，我们有复合 s i = s A i s B i s C i s^{i}=s_{A}^{i}s_{B}^{i}s_{C}^{i} si=sAi​sBi​sCi​和 α = α A α B α C \alpha =\alpha _{A}\alpha _{B}\alpha_{C} α=αA​αB​αC​，以及没有参与者知道其他参与者的秘密参数，除非他们串通。事实上，为了学习 s s s和 α α α，一个人必须与其他所有参与者勾结。因此，即使有一个人是诚实的，伪造证明也是不可行的。

基于上述方案可能会产生疑问，如何验证参与者对每一个 C R S CRS CRS值的一致性，因为攻击者可以抽样多个不同的 s 1 、 s 2 … … s_1、s_2…… s1​、s2​……和 α 1 ， α 2 ， … ， α_1， α_2，…， α1​，α2​，…，并将它们随机用于 s s s的不同幂次(或提供随机数字作为一个增强的公共引用字符串)，使 C R S CRS CRS无效和不可用。幸运的是，因为我们可以使用配对将加密的值相乘，所以我们能够执行一致性检查，从第一个参数开始，并确保每一个都从它派生。每一个由参加者发表的 C R S CRS CRS可按下列方式查阅:

我们取 s s s的1次幂作为正则值，并对每一次幂进行一致性检验: e ( ( g s i , g ) ) = e ( ( g s 1 , g s i − 1 ) ) ∣ i ∈ ( { 2 , . . . , d ) } e(( g^{s^{i} },g) ) =e(( g^{s^{1} } ,g^{s^{i-1} }))|_{i \in ( \{ 2,...,d ) \} } e((gsi,g))=e((gs1,gsi−1))∣i∈({2,...,d)}​ 幂次为2： e ( ( g s 2 , g ) ) = e ( ( g s 1 , g s 1 ) ⇒ e ( ( g , g ) ) s 2 = e ( ( g , g ) ) s 1 + 1 e(( g^{s^{2} } ,g ))=e(( g^{s^{1} } ,g^{s^{1} })\Rightarrow e(( g,g ))^{s^{2} } =e(( g,g ))^{s^{1+1} } e((gs2,g))=e((gs1,gs1)⇒e((g,g))s2=e((g,g))s1+1幂次为3： e ( ( g s 3 , g ) ) = e ( ( g s 1 , g s 2 ) ) ⇒ e ( ( g , g ) ) s 3 = e ( ( g , g ) ) s 1 + 2 e(( g^{s^{3} } ,g ))=e(( g^{s^{1} } ,g^{s^{2} } ))\Rightarrow e(( g,g ))^{s^{3} } =e(( g,g ))^{s^{1+2} } e((gs3,g))=e((gs1,gs2))⇒e((g,g))s3=e((g,g))s1+2 现在我们检查如果是 α \alpha α偏移值也是正确的： e ( ( g s i , g α ) ) = e ( ( g α s i , g ) ) ∣ i ∈ [ d ] e(( g^{s^{i} } ,g^{\alpha })) =e(( g^{\alpha s^{i} } ,g ))\mid _{i \in [d]} e((gsi,gα))=e((gαsi,g))∣i∈[d]​

注意，当我们验证每个参与者与他们的秘密参数是一致的时候，使用以前发布的 C R S CRS CRS的需求并不是对下一个参与者强制的(在我们的示例中是Bob和Carol)。因此，如果敌手是链中的最后一个，他可以忽略之前的 C R S CRS CRS，从头构造有效参数，就好像他是链中的第一个，因此是唯一知道秘密 s s s和 α α α的人。

我们可以通过额外要求除第一个参与者外的每个参与者加密并发布他的秘密参数来解决这个问题，例如，Bob也发布： ( ( g s B i , g α B , g α B s B i ) ) ∣ i ∈ [ d ] (( g^{s_{B}^{i} },g^{\alpha _{B} } ,g^{\alpha _{B}s_{B}^{i} })) \mid _{i \in [d]} ((gsBi​,gαB​,gαB​sBi​))∣i∈[d]​，这允许验证Bob的 C R S CRS CRS是Alice的参数的固有倍数，对于 i ∈ 1 , 2 , . . , d i \in 1,2,..,d i∈1,2,..,d：

e ( ( g s A B i , g ) ) = e ( ( g s A i , g s B i ) ) e(( g^{s_{AB}^{i} } ,g )) =e(( g^{s_{A}^{i}} ,g^{s_{B}^{i} })) e((gsABi​,g))=e((gsAi​,gsBi​)) e ( ( g α A B , g ) ) = e ( ( g α A , g α B ) ) e(( g^{\alpha _{AB} } ,g)) =e(( g^{\alpha _{A} } ,g^{\alpha _{B} })) e((gαAB​,g))=e((gαA​,gαB​)) e ( ( g α A B s A B i , g ) ) = e ( ( g α A s A i , g α B s B i ) ) e(( g^{\alpha _{AB}s_{AB}^{i} } ,g) ) =e(( g^{\alpha _{A}s_{A}^{i} } ,g^{\alpha _{B}s_{B}^{i} } )) e((gαAB​sABi​,g))=e((gαA​sAi​,gαB​sBi​))

同样，Carol必须证明她的 C R S CRS CRS是Alice-Bob的$ CRS$正倍数。

这是一个robust的 C R S CRS CRS设置方案，它不完全依赖于任何一方。事实上，如果只有一方是诚实的，删除并从不共享其秘密参数，即使所有其他方都勾结了，这就足够了。因此， C R S CRS CRS设置中不相关的参与者越多，虚假证明的可能性就越小，如果有竞争对手参与，这种可能性就可以忽略不计。该方案允许涉及其他对设置的易读性有疑问的不可信方，因为验证步骤确保他们不会破坏(这也包括 α α α和 s s s的使用)最终的通用引用字符串。

链接

[1]零知识证明学习（四）— zkSNARKs（引入密码学）