精华内容
下载资源
问答
  • 零知识证明

    2018-10-29 14:12:02
  • 理解为什么以及如何基于多项式构造零知识证明,这篇文章讲的比较清楚。虽然文章只讲到了皮诺曹协议,但是足够理解基于多项式构造零知识证明的本质。想深入零知识证明的小伙伴都建议看看。 ...以下是我对这篇文章的理解...

    理解为什么以及如何基于多项式构造零知识证明,这篇文章讲的比较清楚。虽然文章只讲到了皮诺曹协议,但是足够理解基于多项式构造零知识证明的本质。想深入零知识证明的小伙伴都建议看看。

    http://petkus.info/papers/WhyAndHowZkSnarkWorks.pdf

    以下是我对这篇文章的理解和总结。原文由浅入深地从一个个简单版本,慢慢推导出实用的证明协议。

    协议0 - 直观版本

    随机抽查,随机提供样本,对照结果。这种协议,需要通过设定随机抽查的次数,确定安全系数。

    协议1 - 从多项式的系数证明开始

    最简单的d阶多项式,可以随机选择一个点x,让prover通过多项式计算生成y,verifier可以查看y是否正确。不同的多项式,最多有d个相交的点(相等的点)。

    如果x/y的取值范围很大(设为n),在不知道原始多项式的情况下,能正确给出证明的概率比较低:d/n。多项式,能在一次交互,就能获取比较好的安全系数(如果n远大于d的话,将近100%)。比版本0,优秀不少。

    这种协议还是比较简单和原始。证明建立在双方还是相互信任的基础上。本质上,prover并没有证明他/她知道多项式。证明本身并不能推出他/她知道一个确定的多项式。知道一个值,并不代表知道一个多项式。而且,如果多项式的值范围不大的话,证明者可以随机选择一个值撞概率。

    协议2 - 基于多项式因式分解改进

    假设一个多项式可以分解成:p(x) = t(x)h(x)。t(x)是目标多项式,是由p(x)的部分解组成的多项式:t(x)=(xx0)(xx1)...(xxd1)t(x) = (x-x_0)(x-x_1) ... (x-x_{d-1})。也就是说,证明者需要证明的一部分,证明者知道一个多项式的部分解。从验证者的角度看,既然你知道一个多项式的部分解,那你知道的多项式一定能整除t(x)。在随机挑选x的情况下,你都能给出正确的证明,即可认定你知道这个满足条件的多项式。

    • 验证者,随机生成r,并计算出t®,将r发送给证明者

    • 证明者,计算h(x) = p(x)/t(x),并给出p®以及h®

    • 验证者验证,是否p®=t®h®

    该版本要求证明者,知道一个能整除t(x)的多项式。但比较容易发现,该协议存在如下的问题:

    1/ 证明者,可以自己计算出t®,随机生成h®,并构造出p® = t®h®

    2/ 即使不像1,证明者不考虑多项式,直接通过结果伪造证明。证明者,因为知道随机数r,证明者可以使用任何一个多项式,保证存在相同点(r, t®h®)。这样,证明的p®和h®虽然和正确的证明是一样的,但是,证明者却不需要知道正确的多项式。

    3/ 证明者,可以自己构造多项式,只要满足h(x)=p(x)/t(x)即可。

    版本3 - 引入同态加密

    协议2中的问题1/2,都是因为证明者知道随机数r以及t®。引入同态加密解决。数据是加密的,在加密数据的基础上可以进行计算,能和原始数据计算具有同样的“形态”。

    模运算基础上的幂次计算,是同态加密的一种方式,表示为: E(v)=gv(mod n)E(v) = g^v(mod\ n),其中v是需要加密的数据。在同态加密的基础上,可以定义运算:

    加法:加密结果相乘,加密结果相乘等于原始数据相加后的加密结果

    乘法:幂次运算,一个加密结果进行幂次计算等于两个原始数据乘法的加密结果(注意不是同态乘法)

    除法:相对复杂,不深究

    不要被加法(相乘),乘法(幂次)迷惑了。你可以认为,加密结果加法是通过加密结果的乘法实现的。

    注意,乘法不支持两个加密结果乘法。也就是说,只支持一个原始数据和一个同态加密结果进行乘法操作。

    有了同态加密,一个多项式的加密结果,可以通过多项式的各个项的加密结果计算。

    比如说,一个多项式p(x)=x33x2+2xp(x) = x^3 - 3x^2 + 2x。p(x)的加密结果可以通过如下的方式计算:

    E(X3)1E(x2)3E(x)2=(gx3)1(gx2)3(gx)2=gx33x2+2xE(X^3)^1\cdot E(x^2)^{-3}\cdot E(x)^2 = (g^{x^3})^1 \cdot (g^{x^2})^{-3} \cdot (g^{x})^2 = g^{x^3-3x^2+2x}

    显而易见,一个多项式的值,可以通过各项的加密结果乘上各项的系数,计算出多项式的加密结果。

    • 验证者,随机挑选s,计算出多项式各项的加密结果E(s0),E(s1),...E(sd)E(s^0), E(s^1), ... E(s^d),并将这些值发给证明者。同时计算出目标多项式的加密值t(s)
    • 证明者先计算出h(x) = p(x)/t(x),并通过多项式加密计算的方法计算出E(p(s)) 和 E(h(s))
    • 验证者验证:E(p(s)) = E(h(s))*t(s)是否成立

    这个协议,验证者没有暴露随机值s,证明者只能通过多项式计算出h,从而计算出证明。这个协议,也有问题,证明者有可能只用验证者提供的各项加密结果中的几项来构造证明。并且,聪明的证明者可以自己通过多项式的各项的加密结果计算出t(s)。在知道t(s)的情况下,要构造一个证明非常容易,只需要满足幂次计算即可。

    版本4 - KEA(Knowledge-of-Exponent Assumption)

    假设Alice想获得a的幂次结果,具体的幂次不关心。为了限制幂次结果的提供者Bob只在a上进行幂次操作,Alice提供aa以及aαa^{\alpha}。Bob选择一个幂次cc,计算b=acmod nb = a^c mod \ n以及b=(a)cmod nb' = (a')^c mod\ n,并发送给Alice。Alice通过检查bα=bb^\alpha = b'确定是否b是在a基础上的幂次计算。

    (a,aα)(a, a^\alpha)就是“α\alpha对"。通过一个“α\alpha对",数据进行同样的幂次操作。

    在上述同态加密的情况下,幂次计算,是同态加密后的乘法操作。举个例子,有个简单的多项式f(x)=cxf(x)=c\cdot x,验证者为了保证证明者在随机选择的s的加密结果上都“乘以”c,提供(gs,gαs)(g^s, g^{\alpha\cdot s})。证明者,通过提供((gs)c,(gαs)c)((g^{s})^{c},(g^{\alpha\cdot s})^{c}),证明计算是对同一个加密结果进行了乘法操作。

    因为同态加法成立,该方法可以从简单的多项式可以扩展到一半多项式。

    • 验证者提供gs0,gs1,...,gsdg^{s^0}, g^{s^1}, ... , g^{s^d}以及gαs0,gαs1,...,gαsdg^{\alpha\cdot s^0}, g^{\alpha\cdot s^1}, ... , g^{\alpha\cdot s^d}
    • 证明者分别计算两组值:
      • gp=gp(s)=(gs0)c0(gs1)c1...(gsd)cdg^p = g^{p(s)} = (g^{s^0})^{c_0}\cdot (g^{s^1})^{c_1} \cdot... \cdot (g^{s^d})^{c_d}
      • gp=gαp(s)=(gαs0)c0(gαs1)c1...(gαsd)cdg^{p'} = g^{\alpha p(s)} = (g^{\alpha s^0})^{c_0}\cdot (g^{\alpha s^1})^{c_1} \cdot ... \cdot (g^{\alpha s^d})^{c_d}
    • 验证者验证:(gp)α=gp(g^p)^{\alpha} = g ^ {p'}

    从证明可以推导出:gp=gc0αs0+c1αs1+...+cdαsd=gα(c0s0+c1s1+...+cdsd)g^{p'} = g^{c_0 \alpha s^0 + c_1 \alpha s^1+ ... + c_d \alpha s^d} = g^{\alpha(c_0 s^0 + c_1 s^1+ ... + c_d s^d)}

    该协议很好的限制证明者必须在多项式的计算下,每个系数都正确“计算”。但是,这个协议并没有保护证明者的知识:验证者可以从证明信息中暴力反推多项式系数(毕竟现实场景下系数的组合还不算多)。

    版本5 - ZK(零知识)

    为了保护证明信息,也就是保护c0,c1...cdc_0, c_1 ... c_d信息。还是利用“偏移”,在gpgpg^p 和 g^{p'}都“乘”上一个随机系数δ\delta。即使验证者能枚举出(δc0,δc1,δc2...δcd)(\delta c_0, \delta c_1, \delta c_2 ... \delta c_d),也非常难获取(c0,c1,...cd)(c_0, c_1, ... c_d)

    版本6 - 无交互

    之前所有的协议都是交互式的。交互式协议有些问题:

    • 验证者可以和证明者串通,伪造证明
    • 验证者,自己生成证明
    • 在整个交互过程中,验证者必须保存α\alphat(s)t(s)。可能会造成其他攻击的可能。

    配对函数和双线性映射

    到目前为止,验证者需要验证如下的两个等式:

    gp=(gh)t(s)g^p = (g^{h})^{t(s)}

    (gp)α=gp(g^p)^\alpha = g^{p'}

    假设,验证者不存储α\alphat(s)t(s),而存储对应的加密数据。这样在验证的时候,ghg^hgt(s)g^{t(s)}两个加密结果“相乘“,gpg^pgαg^\alpha”相乘“。从同态加密的定义,我们发现两个加密结果不能相乘。于是引入了新的计算特性:双线性映射。

    e(ga,gb)=e(g,g)abe(g^a, g^b) = e(g, g)^{ab}

    双线性映射的核心性质,可以表达成如下的等式:

    e(ga,gb)=e(gb,ga)=e(gab,g1)=e(g1,gab)=e(g1,ga)b=e(g1,g1)abe(g^a, g^b) = e(g^b, g^a) = e(g^{ab}, g^1) = e(g^1, g^{ab}) = e(g^1, g^a)^b = e(g^1, g^1)^{ab}

    在这里插入图片描述

    值的一提的是,e配对函数也具有加法同态:

    e(ga,gb)e(gc,gd)=e(g1,g1)abe(g1,g1)cd=e(g1,g1)ab+cde(g^a, g^b)\cdot e(g^c, g^d) = e(g^1, g^1)^{ab} \cdot e(g^1, g^1)^{cd} = e(g^1, g^1)^{ab+cd}

    到此,一个zk-SNARK的协议样子就出来了:

    • Setup
      • 随机产生ssα\alpha
      • 计算生成gαg^\alpha以及gsi,gαsiidg^{s^i},g^{\alpha s^i} i\in d,其中(gsi,gαsiid)(g^{s^i},g^{\alpha s^i} i\in d)为生成密钥,(gα,gt(s))(g^\alpha, g^{t(s)})为验证密钥
    • Prove
      • 计算h(x) = p(x)/t(x)
      • 利用gsig^{s^i}计算gp(s)g^{p(s)}gh(s)g^{h(s)}
      • 利用gαsig^{\alpha s^i}计算gαp(s)g^{\alpha p(s)}
      • 随机生成δ\delta
      • 生成证明π=(gδp(s),gδh(s),gδαp(s))\pi = (g^{\delta p(s)}, g^{\delta h(s)}, g^{\delta \alpha p(s)})
    • Verification
      • 假设证明π=(gp,gh,gp)\pi = (g^p, g^h, g^{p'})
      • 检查等式e(gp,g)=e(gp,gα)e(g^{p'}, g) = e(g^p, g^{\alpha})
      • 检查等式e(gp,g)=e(gt(s),gh)e(g^p, g) = e(g^{t(s)}, g^h)

    扩展到一般计算

    如果把一个算子的左右两个输入和输出,都看作多项式的话:

    l(x) operator r(x)=o(x)l(x)\ operator\ r(x) = o(x)

    也就是说,l(x) operator r(x)o(x)=0l(x)\ operator\ r(x) - o(x)=0

    可以把l(x) operator r(x)o(x)l(x)\ operator\ r(x) - o(x)看成一个多项式,类似上述的p(x)。通过之前的协议,可以证明证明者知道一个多项式,但是,并没有证明这个多项式的组成方式(不一定具有l(x) operator r(x)o(x)l(x)\ operator\ r(x) - o(x)的形式)。

    通用版本0 - 支持乘法算子

    如果这个算子是乘法的话,并且如果随机数为s的话,l(s)r(s)o(s)=t(s)h(s)l(s)\cdot r(s) - o(s) = t(s)h(s)。也就是说,验证者除了需要验证l,r以及o是多项式外,还需要在加密空间验证等式成立。因为在加密空间做“减”法相对麻烦,需要算逆,可以将等式稍稍变形:

    l(s)r(s)=t(s)h(s)+o(s)l(s)\cdot r(s)= t(s)h(s) + o(s)

    这样,加密空间就能用配对函数进行验证:

    e(gl(s),gr(s))=e(gt(s),gh(s))e(go(s),g)e(g^{l(s)}, g^{r(s)}) = e(g^{t(s)}, g^{h(s)})\cdot e(g^{o(s)}, g)

    e(g,g)l(s)r(s)=e(g,g)t(s)h(s)e(g,g)o(s)e(g,g)^{l(s)r(s)} = e(g,g)^{t(s)h(s)}\cdot e(g, g)^{o(s)}

    e(g,g)l(s)r(s)=e(g,g)t(s)h(s)+o(s)e(g,g)^{l(s)r(s)} = e(g,g)^{t(s)h(s)+o(s)}

    这样,在之前的协议基础上,可以扩展为:

    • Prove
      • 计算h(x)=l(x)r(x)o(x)t(x)h(x) = \frac{l(x)r(x)-o(x)}{t(x)}
      • 利用gsig^{s^i}计算gl(s)g^{l(s)}gr(s)g^{r(s)}go(s)g^{o(s)}gh(s)g^{h(s)}
      • 利用gαsig^{\alpha s^i}计算gαl(s)g^{\alpha l(s)}gαr(s)g^{\alpha r(s)}gαo(s)g^{\alpha o(s)}
      • 生成证明π=(gl(s),gr(s),go(s),gh(s),gαl(s),gαr(s),gαo(s))\pi = (g^{l(s)}, g^{r(s)}, g^{o(s)}, g^{h(s)},g^{\alpha l(s)}, g^{\alpha r(s)}, g^{\alpha o(s)})
    • Verification
      • 假设证明π=(gl,gr,go,gh,gl,gr,go)\pi = (g^l,g^r,g^o, g^h, g^{l'},g^{r'},g^{o'})
      • 检查等式e(gl,g)=e(gl,gα)e(g^{l'}, g) = e(g^l, g^{\alpha})
      • 检查等式e(gr,g)=e(gr,gα)e(g^{r'}, g) = e(g^r, g^{\alpha})
      • 检查等式e(go,g)=e(go,gα)e(g^{o'}, g) = e(g^o, g^{\alpha})
      • 检查等式e(gl,gr)=e(gt(s),gh)e(go,g)e(g^l, g^r) = e(g^{t(s)}, g^h)\cdot e(g^o, g)

    多个乘法,可以采用中间变量,分解成多个乘法操作。比如a*b*c,可以分解成:

    ab=r1a*b = r_1

    r1c=r2r_1*c=r_2

    多个乘法表达式,同样可以表达成l(x)r(x)=o(x)l(x)\cdot r(x) = o(x)。和前一个例子不同的是,需要选择两个x,保证等式成立。可以通过差值计算出l(x), r(x)以及o(x)。通过通用版本0的协议,可以进行证明(扩展t(x) )。

    通用版本1 - 多项式α\alpha

    之前讲的α\alpha对,都是针对多项式中的某一个项。整个多项式,也可以实现α\alpha 对,保证某个多项式乘以一个系数。

    • Setup
      • 随机产生ssα\alpha
      • 计算生成gαg^\alpha以及gl(s)g^{l(s)}gαl(s)g^{\alpha l(s)}
    • Prove
      • 如果多项式的系数为vv
      • 计算生成(gvl(s),gvαl(s))(g^{vl(s)}, g^{v \alpha l(s)})
    • Verification
      • 假设证明π=(gl,gl)\pi = (g^l, g^{l'})
      • 检查等式e(gl,g)=e(gl,gα)e(g^{l'}, g) = e(g^l, g^{\alpha})

    这个协议有个问题,在多项式上做任何偏移,也能让验证等式成立。

    gvl(s)gv=gvl(s)+vg^{vl(s)}\cdot g^{v'} = g^{vl(s)+v'}

    gαvl(s)(gα)v=gα(vl(s)+v)g^{\alpha v l(s)} \cdot (g^{\alpha})^{v'} = g^{\alpha (vl(s) + v')}

    e(gα(vl(s)+v),g)=e(gvl(s)+v,gα)e(g^{\alpha(vl(s)+v')}, g) = e(g^{vl(s)+v'}, g^{\alpha})

    在多个计算情况下,某个算子的输入可能是由多个变量组成:

    a×b=r1a \times b = r_1

    a×c=r2a \times c = r_2

    d×c=r3d \times c = r_3

    可以用如下的多项式来表达左输入:

    L(x)=ala(x)+dld(x)L(x) = al_a(x) + d l_d(x)

    la(x)l_a(x)在x=1,2的时候为1, x=2的时候为0。

    ld(x)l_d(x)在x=1,2的时候为0, x=2的时候为1。

    α\alpha对,不仅对单个多项式有限制作用,对多项式的组合同样有用:

    • Setup
      • 随机产生ssα\alpha
      • 计算生成gαg^\alpha以及gla(s),gld(s)g^{l_a(s)}, g^{l_d(s)}gαla(s),gαld(s)g^{\alpha l_a(s)},g^{\alpha l_d(s)}
    • Prove
      • 计算生成gL(s)=gala(x)+dld(x)=(gla(s))a(gld(s))dg^{L(s)} = g^{al_a(x) + dl_d(x)} = (g^{l_a(s)})^{a}\cdot(g^{l_d(s)})^{d}
      • 计算生成gαL(s)=gαala(x)+αdld(x)=(gαla(s))a(gαld(s))dg^{\alpha L(s)} = g^{\alpha al_a(x) + \alpha dl_d(x)} = (g^{\alpha l_a(s)})^{a}\cdot(g^{\alpha l_d(s)})^{d}
    • Verification
      • 假设证明π=(gL,gL)\pi = (g^L, g^{L'})
      • 检查等式e(gL,g)=e(gL,gα)e(g^{L'}, g) = e(g^L, g^{\alpha})

    也就是说,α\alpha对能保证一种计算结构,加密数据乘上系数的结构。加密数据本身具有加法同态,所以,可以从多项式的一项,扩展为多项式,再扩展为多个多项式。

    通用版本2 - 通用计算

    计算表达也进一步延伸,每个算子的输入和输出都可以是多个变量的累积。

    i=1ncl,ivi×i=1ncr,ivi=i=1nco,ivi\sum_{i=1}^n c_{l,i}\cdot v_i \times \sum_{i=1}^n c_{r, i}\cdot v_i = \sum_{i=1}^{n} c_{o,i}\cdot v_i

    其中,viv_i是各个变量(包括临时变量)。

    假设存在d 个计算表达式,变量个数是n,相应的系数是:CL,i,j,CR,i,j,CO,i,j i1...n,j1...dC_{L,i,j}, C_{R,i,j}, C_{O,i,j} \ i\in {1...n}, j\in {1...d}

    • Setup
      • 通过插值,计算出li(x)ri(x),oi(x),i1...nl_i(x),r_i(x), o_i(x), i\in{1...n}
      • 随机产生ssα\alpha
      • 计算生成gα,gskk1...dg^\alpha, g^{s^k} k \in {1...d}以及gli(s),gri(s),goi(s)g^{l_i(s)}, g^{r_i(s)}, g^{o_i(s)}gαli(s),gαri(s),gαoi(s)g^{\alpha l_i(s)},g^{\alpha r_i(s)},g^{\alpha o_i(s)}
    • Prove
      • 计算h(x)=L(x)×R(x)O(x)t(x)h(x) = \frac{L(x)\times R(x)-O(x)}{t(x)},其中L(x)=i=1nvili(x)L(x) = \sum_{i=1}^n v_i\cdot li(x),R(x)/O(x)类似
      • 计算生成gL(s)=i=1n(gli(s))vi,gR(s)=i=1n(gri(s))vi,gO(s)=i=1n(goi(s))vig^{L(s)} = \prod_{i=1}^n (g^{l_i(s)})^{v_i},g^{R(s)} = \prod_{i=1}^n (g^{r_i(s)})^{v_i},g^{O(s)} = \prod_{i=1}^n (g^{o_i(s)})^{v_i}
      • 计算生成gαL(s)=i=1n(gαli(s))vi,gαR(s)=i=1n(gαri(s))vi,gαO(s)=i=1n(gαoi(s))vig^{\alpha L(s)} = \prod_{i=1}^n (g^{\alpha l_i(s)})^{v_i},g^{\alpha R(s)} = \prod_{i=1}^n (g^{\alpha r_i(s)})^{v_i},g^{\alpha O(s)} = \prod_{i=1}^n (g^{\alpha o_i(s)})^{v_i}
      • 计算生成gh(s)g^{h(s)}
    • Verification
      • 假设证明π=(gL,gR,gO,gL,gR,gO,gh)\pi = (g^L, g^{R}, g^{O}, g^{L'}, g^{R'}, g^{O'}, g^{h})
      • 检查等式e(gL,g)=e(gL,gα),e(gR,g)=e(gR,gα),e(gO,g)=e(gO,gα)e(g^{L'}, g) = e(g^L, g^{\alpha}),e(g^{R'}, g) = e(g^R, g^{\alpha}),e(g^{O'}, g) = e(g^O, g^{\alpha})
      • 检查等式e(gL,gR)=e(gt,gh)e(gO,g)e(g^L, g^R) = e(g^t, g^h)\cdot e(g^O, g)

    通用版本3 - 固定输入和输出

    上述的协议因为对l,r,以及o使用的是同一个α\alpha值,存在如下的问题:

    1. L(x)的计算采用R(x)/O(x)中的多项式:L(s)=o1(s)+r1(s)+r5(s)+...L'(s) = o_1(s) + r_1(s) + r_5(s)+ ...

    2. 输入/输出,换位 :O(s)×R(s)=L(s)O(s) \times R(s) = L(s) (证明者,提供证明时,只是交换O/L的位置,同样能通过验证)

    3. 重用同样的输入: L(s)×L(s)=O(s)L(s) \times L(s) = O(s) (证明者,提供证明时,用L(s)代替R(s) ,同样能通过验证)

    解决上述问题的简单的做法,分别对L(x)/R(x)/O(x)使用不同的α\alpha对。

    通用版本4 - 限定变量

    细心一点会发现,之前的协议并没有限制证明者使用“一致”的变量的取值。也就是说,证明者,可以在计算L(x), R(x), O(x)的时候,使用不同的viv_i

    如何限制证明者使用同样的变量值?还是采用"α\alpha对"的思想,将多项式“累积”在一起,先用统一一个偏移进行限制。

    e(gvL,ili(s)gvR,iri(s)gvO,ioi(s),gβ)=e(gvβ,iβ(li(s)+ri(s)+oi(s)),g)e(g^{v_{L,i}\cdot l_i(s)}\cdot g^{v_{R,i} \cdot r_i(s)}\cdot g^{v_{O,i}\cdot o_i(s)}, g^\beta) = e (g^{v_{\beta, i}\cdot \beta (l_i(s)+r_i(s)+o_i(s))}, g)

    如果vL,i=vR,i=vO,i=vβ,iv_{L,i}=v_{R,i}=v_{O,i}=v_{\beta, i}的话,显然表达式成立。但是,在一些场景下,比如证明者知道L(x)=R(x)的情况下,不需要变量相等,等式也能成立。

    (VL,ili(s)+VR,iri(s)+VO,ioi(s))β=Vβ,iβ(li(s)+ri(s)+oi(s))(V_{L,i}\cdot l_i(s) + V_{R,i}\cdot r_i(s) + V_{O,i}\cdot o_i(s))\cdot \beta = V_{\beta, i}\cdot \beta \cdot (l_i(s) + r_i(s) + o_i(s))

    假设w=l(s)=r(s)w=l(s)=r(s),并且y=o(s)y=o(s)

    β(vLw+vRw+vOy)=vββ(w+w+y)\beta(v_L w+ v_R w + v_O y) = v_{\beta}\cdot \beta(w+w+y)

    证明者,知道这些信息,要让等式成立,可以让vβ=vO,vL=2vOvRv_{\beta} = v_{O}, v_{L} = 2v_O - v_R。也就是存在可能性,不同的变量值,验证等式依然成立。

    进一步优化验证等式,让每个变量采用不同的偏移,记为β\beta对:

    • Setup
      • 额外随机生成βl,βr,βo\beta_l, \beta_r, \beta_o
      • 额外计算{gβlli(s)+βrri(s)+βooi(s)}i{1...n}\{g^{\beta_l l_i(s)+\beta_r r_i(s)+\beta_o o_i(s)}\} i\in \{1...n\}
    • Prove
      • 额外计算gZ(s)=i=1ngzi(s)=gβlL(s)+βrR(s)+βoO(s)g^{Z(s)} = \sum_{i=1}^{n}g^{z_i(s)} = g^{\beta_l L(s) + \beta_r R(s) + \beta_o O(s)}
    • Verification
      • 验证等式:e(gL,gβl)e(gR,gβr)e(gO,gβo)=e(gZ,g)e(g^L, g^{\beta_l})\cdot e(g^R, g^{\beta_r}) \cdot e(g^O, g^{\beta_o}) = e(g^Z, g)

    因为:

    Lβl+Rβr+Oβo=i=0nvili(s)βl+viri(s)βr+vioi(s)βoL\cdot \beta_l + R\cdot \beta_r + O\cdot \beta_o = \sum_{i=0}^n v_il_i(s)\beta_l + v_i r_i(s) \beta_r + v_i o_i(s) \beta_o

    =i=0nvi(li(s)βl+ri(s)βr+oi(s)βo)= \sum_{i=0}^n v_i(l_i(s)\beta_l + r_i(s) \beta_r + o_i(s) \beta_o)

    既然,L/R/O采用通用的变量值v,则L+R+O,可以看成合并的一个多项式。为了避免证明者利用L/R/O的关系,伪造证明,使用多个β\beta对。

    也就是说,α\alpha对限制计算是按照指定的多项式乘加,β\beta对限制计算采用同样的变量值。

    通用版本5 - 不可变形

    上述的协议还存在两种变形问题:

    1/ 变量的多项式变形:α\alpha对限制了计算是按照指定的多项式乘加。比如说,L是多个li(x)l_i(x)乘加。但是因为证明者知道gli(x)g^{l_i(x)}gαg^{\alpha},可以从验证者提供的信息构造gli(x)+1g^{l_i(x)+1}

    2/ 变量取值变形:β\beta对虽然限制了计算需要是li(x)+ri(x)+oi(x)l_i(x) + r_i(x) + o_i(x)的形式,但并没有限制在证明数据上同时偏移。

    这些变形的问题,因为证明者完全知道β\beta的加密结果。解决的办法是:引入γ\gamma,进一步隐藏β\beta的加密结果。

    • Setup
      • 额外随机生成βl,βr,βo,γ\beta_l, \beta_r, \beta_o, \gamma
      • 额外设置验证密钥:gβlγ,gβrγ,gβoγ,gγg^{\beta_l \gamma},g^{\beta_r \gamma},g^{\beta_o \gamma},g^{\gamma}
    • Prove
      • 额外计算gZ(s)=i=1ngzi(s)=gβlγL(s)+βrγR(s)+βoγO(s)g^{Z(s)} = \sum_{i=1}^{n}g^{z_i(s)} = g^{\beta_l \gamma L(s) + \beta_r \gamma R(s) + \beta_o \gamma O(s)}
    • Verification
      • 验证等式:e(gL,gβlγ)e(gR,gβrγ)e(gO,gβoγ)=e(gZ,gγ)e(g^L, g^{\beta_l \gamma})\cdot e(g^R, g^{\beta_r \gamma}) \cdot e(g^O, g^{\beta_o \gamma}) = e(g^Z, g^{\gamma})

    通用版本6 - 优化配对计算个数

    上一个协议需要4个配对函数的计算。皮诺曹协议(Pinocchio protocol )通过对L/R/O,使用不同的生成元,减少了配对函数的计算。

    • Setup
      • 随机生成αl,αr,αo,β,γρl,ρr\alpha_l,\alpha_r, \alpha_o, \beta, \gamma,\rho_l, \rho_r,并设置ρo=ρlρr\rho_o = \rho_l \cdot \rho_r
      • 生成三个生成元:gl=gρl,gr=gρr,go=gρog_l=g^{\rho_l}, g_r=g^{\rho_r}, g_o=g^{\rho_o}
      • 设置证明密钥:{gsk}kd,{glli(s),grri(s),gooi(s),glαlli(s),grαrri(s),goαooi(s),glβli(s),grβri(s),goβoi(s)}\{g^{s^k}\}_{k\in d}, \{g_l^{l_i(s)},g_r^{r_i(s)}, g_o^{o_i(s)}, g_l^{\alpha_l l_i(s)},g_r^{\alpha_r r_i(s)}, g_o^{\alpha_o o_i(s)},g_l^{\beta l_i(s)},g_r^{\beta r_i(s)}, g_o^{\beta o_i(s)}\}
      • 设置验证密钥:got(s),gal,gar,gao,gβγ,gγg_o^{t(s)}, g^{a_l}, g^{a_r}, g^{a_o}, g^{\beta \gamma},g^{\gamma}
    • Prove
      • 额外计算gZ(s)=i=1n(glβli(s)grβri(s)goβoi(s))vig^{Z(s)} = \prod_{i=1}^n(g_l^{\beta l_i(s)}\cdot g_r^{\beta r_i(s)}\cdot g_o^{\beta o_i(s)})^{v_i}
    • Verification
      • 验证是否采用指定的多项式:e(glL,g)=e(glL,gαl)e(g_l^{L'},g) = e(g_l^L, g^{\alpha_l}),同样检查R和O
      • 验证是否采用一致的变量值:e(glLgrRgoO,gβγ)=e(gZ,gγ)e(g_l^L \cdot g_r^R \cdot g_o^O, g^{\beta \gamma}) = e(g^Z, g^{\gamma})
      • 验证计算是否成立:e(glL,grR)=e(got,gh)e(goO,g)e(g_l^L, g_r^R) = e(g_o^t, g^h)\cdot e(g_o^O, g)

    在理解了皮诺曹协议的基础上,再看Groth16算法,就比较简单了。

    总结:

    1. 协议都是建立在多项式基础上。
    2. 多项式分解,提供了一个能证明证明者知道一个满足一定条件多项式的方法。为了能让这种方法工作需要其他一些条件:
      1. 同态加密:随机数以及对应多项式的各个项都能加密的同时,还能进行乘法和加法的计算。同态加密的作用是防止证明者能反推随机数,直接伪造证明。同时还能在加密数据的基础上提供证明者需要的计算。
      2. "α\alpha对"保证证明者的计算都是在加密数据乘法和加法的基础。也就是说,证明者的计算是基于多项式的。
      3. 双线性映射,能让两个加密数据映射成原始数据乘积的加密结果。
    3. zk的实现反倒简单。在证明数据上进行一个偏移。保证证明者的原始数据不泄漏。
    4. Trusted Setup生成初始的参数。
    5. α\alpha参数限制多项式形式。β\beta参数保证多个多项式采用同样的系数。γ\gamma参数防止多项式偏移。

    在这里插入图片描述

    展开全文
  • 区块链与零知识证明

    2021-01-20 13:18:50
    零知识证明零知识证明(Zero Knowledge Proof),是这样的一个过程,证明者在不向验证者提供任何额外信息的前提下,使验证者相信某个论断(Statement)是正确的。 证明过程包括交互式(Interactive) 和 非交互式...
  • 浅谈零知识证明

    2021-01-07 21:03:10
    浅谈零知识证明 概述 零知识证明(zero knowledge),顾名思义其实就是在充分证明自己是某种权益的合法拥有者的同时,又不能把有关的信息泄露出去,即提供给外界的有用信息为”零”。 零知识起源 “零知识”的概念最早...
  • 浅析零知识证明.pdf

    2021-01-26 15:00:56
    零知识证明相关论文
  • ZCash零知识证明

    万次阅读 2019-03-29 09:39:52
    本文将通过打比方的手法,用通俗的语言,解释清楚ZCash的交易原理,以及零知识证明是如何运用到ZCash交易过程中的。 本文的嘉宾是数字货币界最著名CP:Alice和Bob。 一、从比特币说起 直接讲解ZCash的交易过程...

    交易过程完全匿名是数字货币ZCash最大的亮点,正是这一点使得ZCash自提出以来便备受关注。ZCash匿名交易的实现依赖于一种叫做“零知识证明”的密码学手段。本文将通过打比方的手法,用通俗的语言,解释清楚ZCash的交易原理,以及零知识证明是如何运用到ZCash交易过程中的。

    本文的嘉宾是数字货币界最著名CP:Alice和Bob。

    一、从比特币说起

    直接讲解ZCash的交易过程可能会比较抽象。为了有助于理解,我们不妨先分析比特币,作为铺垫。

    我们先来打个比方说明比特币的转账原理。

    演示场景:Alice转1个比特币给Bob。

    转账前,Alice要事先准备1个比特币。为了方便理解,我们把Alice准备转出的这1个比特币看成一张面额为1个比特币的“支票”,如图1。

     

    图1

    从这张“支票”中我们可以获取到如下信息:

    Alice确实拥有1个BTC

    Alice使用私钥对这张支票签名,证明Alice拥有对这笔资产转账的权力。

    支票的面额和转账权都已经明确,Alice就可以给Bob转账了。转账的原理很简单,就

    是给Bob新建一张一样的“支票”,证明Bob拥有了1个比特币。同时撕掉Alice手中那张的“支票”,通过这“破旧”并“立新”的方式,实现资产所有权的转移。如图2。

     

    以上逻辑其实不难理解,因为这和日常生活中的银行转账是一个道理。通过银行转账,我们在交易时不必对实物货币进行转移,而是以银行记账的方式,实现“资产所有权”的转移。比特币交易的过程实质上就是一个“资产所有权”的转移过程,转入比特币的那一方“新建”一份资产所有权,而转出方需要“销毁”原先的资产所有权,被销毁的那张“支票”永远不会再出现。

    二、ZCash的转账原理

    与比特币一样,ZCash的交易过程也是 “资产所有权”的转移。继续沿用前文“支票”的比方。

    演示场景:Alice转1个ZEC给Bob。

    转账前,Alice创建一张面额为1个ZEC的“支票”,如图3。

     

    能从该凭证中获取的信息:

    Alice确实拥有1个ZEC。

    Alice使用私钥对这张支票签名,证明Alice拥有对这笔资产转账的权力。

    这张“凭证”上多了一串随机数,用符号 r 表示。这串随机数的作用好比 “支票代号”,用来唯一识别该支票。Alice的“支票代号”为r1。

    明确以上信息,Alice就可以进行ZEC转账了。

    第一步:比特币一样,要先为Bob新建一张“支票”。Bob的支票代号(r2)与Alice的支票代号(r1)不相同,如图4。

     

    第二步:新的“资产所有权”生成的同时,必须要想办法销毁原来的“资产所有权”。即必须想办法让Alice手中的“支票”失效。与比特币简单粗暴的“直接撕毁”不同,ZCash采用“备注作废”的手段,达到同样的效果。怎么理解呢?就是在不对原先“支票”作任何处理的前提下,新建一个作废文件列表,录入需要作废的“发票代号”。如图5,

     

    从上图可以看出,原先的Alice持有的支票仍旧存在,并没有消失,只是这张支票已经被记入“作废列表”。在确定资产所有权时要同时读取两个列表的信息,能确定Bob拥有资产所有权的判断方法是:作废列表中不存在Bob所持“支票”的代号。

    可是为什么要这样设计呢?其实这样设计的目的是为了在交易过程中运用 “零知识证明”。

    三、零知识证明

    什么是零知识证明?

    零知识证明 (被称为“zk-SNARK”)是实现Zcash的匿名特性的核心技术。“零知识证

    明”的定义是:证明者能够在不向验证者提供任何有用的信息的情况下,使验证者相信某个论断是正确的。举个简单的例子:

    A要向B证明自己拥有某个房间的钥匙,假设该房间只能用钥匙打开锁,而其他任何方

    法都打不开。这时有2个方法:

    (一)A把钥匙出示给B,B用这把钥匙打开该房间的锁,从而证明A拥有该房间的正确的钥匙。

    (二)B确定该房间内有某一物体,A用自己拥有的钥匙打开该房间的门,然后把物体拿出来出示给B,从而证明自己确实拥有该房间的钥匙

    后面这个方法属于零知识证明。好处在于在整个证明的过程中,B始终不能看到钥匙的样子,从而避免了钥匙的泄露。

    那么零知识证明怎么运用到ZCash交易过程中呢?

    我们再回顾比特币和ZCash的例子。

    Alice要向Bob转一个单位的数字货币(BTC/ZEC),即Alice要向Bob转移一个单位的资产所有权。这时有以下两个方法:

    (一)比特币中的做法:Alice拥有一张1BTC的支票,要转账给Bob时,先给Bob新建一张1BTC的支票,同时当着Bob的面将自己原先的支票撕毁。

    (二)ZCash中的做法:Alice拥有一张1ZEC的支票,要转账给Bob时,先给Bob新建一张1ZEC的支票,然后在一张约定有效的作废列表中,记录下Alice的发票的代号,证明Alice的支票已经失效。

    ZCash的方法属于零知识证明。整个交易过程中,Bob并没有见过Alice的支票,但是还是实现了资产所有权的转移。在ZCash的整个交易系统中,Alice和Bob的交易还有其他见证者,即负责记录交易信息的矿工。同样道理,矿工也不必看到Alice的支票,只要能确定代号为r1的支票已经作废了就行。

    四、ZCash完整的匿名交易系统

    有了上述铺垫,就可以进一步解释ZCash的匿名交易过程了。

    还是那个例子:Alice转1 个ZEC给Bob。这个例子中有涉及到的角色有转账双方Alice和Bob,以及记账者(矿工)。

    首先是Alice和Bob都有了一张支票,如图6。

     

    这两张“支票”都是有效的。Alice的支票开始就存在于整个ZCash网络,Bob的支票在生成后也会被广播到全网。

    为了隐藏交易者信息,要对两张支票进行加密处理。在全网中存在的“支票”其实是这样子的,如图7。

     

    信息都是被加密的,可以通过拥有者的私钥解密

    同时,因为资产只能有一份,所有矿工手里还有一个作废列表。Alice要同时广播自己的“发票代号”,录入作废列表中。发票代号也是加密的。所以矿工们能看到的信息其实是这样的。其中Alice的支票是原先存在的,Alice的支票代号r1和Bob的支票是在交易过程中被Alice广播的。如图8。

     

    矿工们能获取的信息相当有限,但是这并不影响对矿工对交易有效性的判断。

    判断的逻辑相当简单:矿工拿到Alice给的支票代号r1,去作废列表中检索,假如作废列表中已经存在r1,则证明r1所对应的的支票早已失效;若作废列表中并不存在r1,则证明r1对应的支票仍旧有效,此时矿工把r1录入作废列表中,把新生成的支票录入支票列表中。所以记账的过程就是对原有支票登记失效,并存入现有支票票的过程。

    在这个过程中,我们不难发现,每笔交易矿工能接收到的东西只有一个发票代号,和一张新的发票,而且这两样东西都是被加密的。所以矿工并不知道转账双方是谁,也不知道转账金额是多少。

    五、数据库

    其实有心人可以发现,按照上文的思路,能写一个用于ZCash匿名交易的数据库。笔者后续的文章中会另起一文专门写数据库的构建。

    展开全文
  • fabric-零知识证明-idemix
  • 零知识证明是什么.mp4

    2020-09-10 10:30:08
    零知识证明是什么:零知识证明是指证明者能够在不向验证者提供信息本身内容的情况下使验证者相信某一论断是真实可信的一种技术。举例:A向B证明自己拥有某个房间的钥匙(假设该房间只能用钥匙打开锁),这时候A可以...
  • NP 问题已有的知识的(黑箱) 零知识证明都是非常数轮的, 因此, 在标准的复杂性假设下, NP 问题是否存在常数轮的(黑箱) 知识的零知识证明是一个有意义的问题. 本文对该问题进行了研究, 在一定的假设下给出了HC 问题的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 804
精华内容 321
热门标签
关键字:

零知识证明