type
status
date
slug
summary
tags
category
icon
password
Sub-item
Last edited time
Oct 28, 2023 10:41 AM
Parent item
领域
【背景知识】
- Prover。
提供一个不泄露任何额外信息的陈述的人。
- Verifier。
如果陈述是正确的， 他可以证明陈述是对的， 否则能发现陈述是错的。
- 多项式的特性。
2个阶数为的多项式，他们相交的点最多只有个，换句话说，一个阶的多项式最多只有个根(也叫解)。这意味着，有2个多项式，如果在一个足够大的范围内，选取一个值，计算得到相同的值的概率几乎为0。例如范围是,那么相同的概率是。可以得到结论：任何多项式在任意点的计算结果都可以作为其唯一身份的标识。
【提出问题】
Prover有一个多项式：，他想向别人证明自己拥有这样的一个3阶多项式，其中有2个解是：。
但他不想透露这个多项式的任何其他信息（这些信息是指这个多项式的“知识”：多项式系数）。
定义：
- t表示target，目标多项式， 因为Prover已经公布了2个解， 所以verifier是知道这个目标多项式的。
- ， h表示harmless 无关的任意多项式， verifier无需这个多项式是什么。
那么
- 要证明的多项式可以写成：，可以简写为。 p表示polynomial，多项式。
一个Verifier说，我随便给一个x值，例如，计算目标多项式。把告诉Prover，Prover计算出2个值, 和，把2和6个告诉Verifier。
Verifier根据这2个值计算，可以证明Prover有这个多项式，他有2个解：1和2。
虽然满足要求的多项式可以通过上面的验证，但是Prover使用不满足要求的多项式也可能骗过Verifier。
- Verifier无法确定Prover有没有具有2个解为1和2的多项式，由于Prover知道值和的多项式，根据r=3，他计算，然后随便找2个值，例如7和14，或者随机的任意多项式，给Verifier， Verifier也能验证通过，但无法证明Prover具有符合要求的多项式。
- Prover即使具有2个解为1和2的多项式，Verifier也无法确定这个多项式是不是3阶。例如的4阶多项式，他也能给出满足这个要求的结果。
【解决问题】
问题的原因是verifier暴露了原始值，使得Prover能够根据原始值任意构造数据。
解决办法是：
- Verifier不能泄露值和值给Prover。
- 限制Prover计算的值和的值的方法，Prover必须按照多项式的格式计算值，并且要和相关。
使用同态加密对随机取值进行加密， 保证不泄露原始值就能计算
因为Verifier把值直接给了Prover，Prover根据值可以构造任意满足要求的多项式，甚至不是多项式。
那么，如果不给出原值，那么Prover就不知道的原值，那么他也就不能任意构造的值和的值来欺骗Verifier。
同态加密可以使用加密值的情况下计算加密多项式的值。
例如同态加密， 可以计算。使用模的原因是：g是公开的，如果不取模，那么原始值很容易被猜出来，取模后，就很难推出原始值了。
原始值 | 同态加密 |
加法： | 乘法： |
减法： | 除法： |
乘法： | 幂运算： |
n*x | |
除法： | ㅤ |
原始值相乘， 不等于加密值相乘。
由于使用用同态加密的值，Prover无法直接计算得到同态加密的等值，因此Verifier需要给出所有r的幂的加密值，这样Prover才能根据多项式展开公式计算加密多项式的值。
第一步，对值及其所有阶数的幂值进行同态加密。Verifier给出同态加密值：，，，发送给Prover；
第二步，Prover计算，，，推导方法很简单，把加密值代入多项式即可，把和发给Verifier；
第三步，Verifier根据与自己选的值，计算；
第四步，Verifier计算是否等于，如果相等，表示验证通过。
上面过程没有泄露值和值，那么Prover要造假给出满足要求的值就比较困难了。但这并不意味着Prover就无法找到满足等式的值，因此，还要使用一种方法，能够限定Prover计算的值的格式一定是的格式。
使用变换保证Prover使用Verifier给出的同态加密值来计算
α-变换是指A有2个值，这2个值的关系是求幂的关系：，B拿到a之后，只能同时进行再次求幂的操作，再把计算后的值返回给A，只有在B正确求幂的情况下，A才可以验证通过，B如果进行任何其他操作，都会导致验证失败。这样就可以证明B只进行了求幂的操作。
α-变换就是对同态加密值进行DSA非对称加密. DSA加密公式是： ，其中（E，N）称为公钥。α-变换就可以理解为B使用A的公钥对A的明文进行加密， A使用私钥进行解密验证， 解密后和明文一致，表示B是使用的A提供的公钥加密的。
第一步，Verifier除了提供值及其所有阶数的幂值的同态加密值之外，还提供对其进行α变换之后的加密值：，，，。
第二步，Prover使用变换后的加密值分别计算加密多项式：和，和。
第三步，Verifier先验证变换，再验证加密多项式，如果验证通过，表示Prover肯定使用了Verifier提供加密幂值计算的。
进一步可以优化的地方是，如果这个多项式没有某些次幂，那么Verifier可以不提供对应的加密幂值。
【新的问题】
上述方法保证了Prover无法”作弊“，约束了Prover的行为，但是Prover知道的多项式和的参数还有缺陷，理论上他是一个取值范围很广的值，但实际上这个范围可能很有限，如果阶数比较小，系数范围比较小，那么很可能被暴力破解 比如，那么和只相差一个的幂，那么Verrifier就能推断出Prover的的知识了。所以需要一个协议，即使系数是1，阶数是1的多项式，零知识协议也能保证其安全性，保证Verifier除了验证之外，也无法获取额外的Prover的额外知识。
【零知识证明】
为了防止Verifier暴力破解或偶的多项式的知识，要限制Verifier从Prover提供的数据中：，，提取到多项式的知识。为了防止Verifier提取知识，Prover对计算结果进行一次变换，，，，因为验证时的式子两边都有δ变换，所有变换后不影响Verifier的验证。这样可以保证多项式的阶数和系数等知识不被泄露，防止被暴力破解。这种方式称为无成本的零知识。
变换同变换一样，对结果进行一次非对称加密。
【非交互式】
上面整个过程是一个交互式的零知识方案。存在以下几个问题：
- Verifier和Prover可以串通，Verifier可以告知随机数r和变换系数α，Prover就能伪造证明
- Verifier自己构造参数，伪造证明
- Verifier需要一直保存和， 有泄露风险。注意：这里的s就是上文的r。
Prover需要和每个Verifier做交互来证明一个陈述，那他如果想众多参与者同时或者永久确信，这种方式就比较低效。
因此需要一个可以被重复利用、公开可信、又不会被滥用的秘密参数。就是把和进行加密，这样Prover无法通过任何途径获取这些值，从而伪造假的证明，同时，任何Verifier也可以拿着加密的参数，随时进行验证，而无需每次构造验证用的参数。
注意到上面Verfier验证中，, 是对加密值的t次幂的计算，而同态加密不支持2个加密值相乘（相乘的结果是原值的相加的同态值），如果t被加密了，那么无法计算了，α的计算也有类似的情况，这里先解决这个问题。
这里要用到双线性映射：
其中属于生成元为g的有限循环乘法交换群的2个成员。是2个加密值。双线性映射的作用是把2个值（一次只能2个）确定性地映射到第三个地址空间上，并且不可逆（类似hash的计算）。映射出来的值是原始值的乘积的加密值，遵守同态加密的属性：
有了双线性映射，就可以设置安全且公开可复用的参数了。
第一步，让一个诚实的参与者生成秘密的s和α，并算出，，，，，，.....，，......。这些参数组成CRS（common reference string）。任何Verifier和Prover都可以用它来构造非交互式的零知识证明协议。
把CRS分层2组，
- verification key。，，也就是t和α的加密值。
- proving key（evluation key）。，，，，.....，，也就是需要发送给Prover的一组值。
Verifier根据verification key，就可以处理从Prover那里得到的加密多项式的值：，，:
- 验证：
- 验证多项式的限制：
信任第一个参与者
所有使用CRS的用户必须信任生成CRS的人。除此之外， 也可以由多用户参与共同生成CRS：
Alice生成和，然后公布他的CRS：。
Bob生成和，通过同态乘法结合Alice的CRS，变成自己的CRS：。
Cacnl生成和，通过同态乘法结合Bob的CRS：。
只要有一个是诚实的，就没有办法伪造证明。但是如果其中某一个参与者没有使用前一个的数据，而是自己随机生成数据替换之前的数据，那么前面的参与者就没有意义了。这里可以使用双线性映射来验证。
【多项式的SNARK】
为了简介起见， 定义： 表示一组数：。
完整过程如下
第一步，setup。
- 挑选随机数。
- 计算CRS： 。
第二步，proving。
- 分配系数。。得到多项式。
- 求多项式：。
- 代入，计算。
- 代入，计算。
- 选择随机数δ。
- 构造随机化证明。。
第三步，verification。
- 得到。
- 验证多项式约束：。
- 验证多项式系数：。
【程序构造成多项式】
Prover声称知道2个数的乘积， Verifier如何验证？
运算的证明
把运算的操作数使用多项式表示，那么计算结果也是多项式代入值后计算的结果。
如果x在取值a时， 满足：L(x) * R(x) = O(x)，那么：L(a) * R(a) - O(a) = 0。表示这个多项式有一个根：a， 也就是说有一个目标多项式是
。
定义：，这样就可以把乘法运算转换为多项式的证明。但是多项式中含有加密值的乘法和减法，在求多项式h(x)时，是不能计算加密值乘法的， 减法的成本也很高。需要把多项式换一个方式：，在双线性映射中就是。
接下来计算多项式的SNARK。
第一步，setup。步骤不变
第二步，proving。
- 分配系数给3个多项式。
- 求多项式：。
- 代入，计算。
- 代入，计算。
- 选择随机数δ。
- 构造随机化证明。。
第三步，verification。
- 得到。
- 验证多项式约束：。
- 验证多项式系数：。
多个运算
比如说。可以拆分成2个乘法：
1：。
2：。
一个操作数是在一个多项式上的一个点的取值，如果上面2个式子的左操作数是在同一个多项式上的取值，右操作数是在另一个统一多项式的取值， 比如在
多项式上取2个坐标和，在上取值和，那么在上的取值为和。
，， 表示多项式具有2个根。
进一步地，如果是，都可以转换成多个基本乘法运算的式子组合，那么只要能够找到满足条件的多项式，就可以用多项式来证明了。
多项式插值
为了构造操作数 和 输出多项式，我们需要一种方法来用给定的一组点去构造一个能经过所有这些点的弯曲 多项式，这叫插值。最简单的方法可以算出这个多项式，是一组未知方程：就是解方程组。需要阶数为n的方程， 给出n+1个点，就能解出多项式的系数。
解决证明多个计算多项式的问题，我们就可以一次证明多个运算（如上百万个甚至更多）了，但是这个方案还有一个关键的缺点：如果证明中执行的“程序”在不同运进行
怎么约束呢？Verifier需要限制Prover只能修改比例而不是单个系数。方法是通过变换把l(x)进行加密，使得Prover无法看到l(x)的原始多项式。
接下来计算多项式的SNARK。
第一步，setup。
- 使用对应的系数构造相应的操作符多项式：选择
- 选择随机数 α 和 s
- 使用加密的和它的”转换“: 来设置 proving key；
- 设置 verification key：；
第二步，proving。
- 对进行比例换换，系数为。
第三步，verification。
- 验证比例：。
这样Prover就无法修改单个系数了。
算术电路中一个 input wire 或者 output wire可能同时会作为多个门的输入wire，如何确保约束这些公用wire的问题。
上面讨论的是所有左操作数是同一个变量的情况。如果是多个变量，需要把操作数多项式分成操作数的变量多项式。例如：
定义2个变量多项式：。
这样操作符多项式就可以用变量多项式的组合进行表示：。
接下来计算多项式的SNARK。
通过这样的约束，Prover不能修改系数来改变变量多项式，也不能通过和其他多项式相加或相乘来改变， 这样就无法通过变换的验证。
除了变量系数之外，还有静态系数。