首页 手机兼职平台区块链正文

技能详解零常识证明完成办法:以 zk-SNARK 为例

admin 区块链 2020-11-25 16:31:15 3404 0

zk-SNARKevenMaksymPetkusWhyandHowzk-SNARKWorks:DefinitiveExplanation

zk-SNARK

咱们都知道它是一种完结零常识证明的办法,也知道它是扩容和隐私方向的利器,但终究什么是零常识证明,zk-SNARK 是怎样完结零常识证明的?这便是本文试着去答复的问题。

阅览这篇文章需求坚持较高的专心度,以及恰当考虑;但本文极力做到没有含混和不流畅之处,所以假如你坚持专心,看完就能了解零常识证明终究是怎样经过 zk-SNARK 做到的,而不是停留在只知道概念的阶段。

那么现在,开端吧。

技能详解零常识证明完成办法:以 zk-SNARK 为例

第一阶段:为运用 zk-SNARK 做预备作业

把零常识证明的需求转化为数学运算电路

保险机构需求知道用户的一个体检数据是否合格,用户只想让保险机构知道数据是否合格,但不泄漏详细的数据给他们。怎样去做?

假定这个体检的隐私数据是 x,x 的值在 0~7 之间(包括 0 和 7)为合格,不然为不合格。那要做首要是把这个需求转化为一个可核算的问题,即有一个程序,其输入为 x,当 x 在 0~7 之间时,输出「真」,当 x 不在该区间时,输出「假」。

该程序的核算进程能够被表达为如下一组方程的验证进程。当输入 x 后,假如这 4 个方程都能被满意,也便是方程左面的核算成果都为 0,就能证明 x 在 0~7 之间,那么就输出「真」,不然输出「假」。这 4 个方程为:

b0 * (b0-1)= 0 

b1 * (b1-1)= 0

b2 * (b2-1)= 0

2^0 * b0 + 2^1 * b1+2^2 * b2 – x = 0

能够把这样的一组方程表达为一个数学运算电路。以 b0 * (b0-1) 为例,它这一部分的电路如下图所示。

技能详解零常识证明完成办法:以 zk-SNARK 为例

而整个程序的核算进程能够笼统表达为下图:

技能详解零常识证明完成办法:以 zk-SNARK 为例

如此一来,零常识证明的问题就被转化为「输入+用作证明的数学运算电路+输出」;假如输出为真,就能够信赖输入为真。在本文的比方中,假如输出为 0,就能够信赖用户的体检数据合格。

把数学运算电路转化为多项式

在把零常识证明的需求转化为数学运算电路后,咱们能够把验证者和证明者这两个人物分隔。而当验证者不是证明者时,就发明了一个能够躲藏输入(原始数据)的时机。

随之而来问题只需一个:验证者凭什么信赖这个「输出」是「输入」经过「用作证明的数学运算电路」核算出来的?最简略的办法便是验证者看着证明者输入和核算,但这样就无法躲藏输入了。

所以咱们要在数学运算电路的根底上接着做转化,把输入、用作证明的数学运算电路、输出这三者绑定到一同,也便是说,能够经过某种办法验证「输出」是否为「输入」经过「用作证明的数学运算电路」核算出来的。

这样一来,在输出为真的条件下,只需该验证经过,证明者就能够信赖输入为真。

为了完结这种绑定,需求把数学运算电路转化为多项式。

(以下为数学转化进程,若无爱好可跳至下一张图片下方的阶段)

首要要把数学运算电路转化为一阶束缚体系(RICS)。

Vitalik 在《Quadratic Arithmetic Programs: from Zero to Hero》一文中详细介绍了这个转化进程,本文为省掉细节描绘,将直接引证 Vitalik 运用的比方。

这是一个数学的进程,咱们只需求知道这种转化是等价的即可,若期望知晓细节,可阅览 Vitalik 的文章。

Vitalik 的那组方程为:




x * x - sym_1 = 0  


sym_1 * x – y = 0

(y + x) * 1 - sym_2 = 0

(sym_2 + 5) * 1 - ~out = 0

以其间的第一个方程 x * x - sym_1 = 0 为例,它被转化为 R1CS 后的办法如下所示:

a = [0, 1, 0, 0, 0, 0]  


b = [0, 1, 0, 0, 0, 0]

c = [0, 0, 0, 1, 0, 0]

s = [~one,x,~out,sym_1,y,sym_2]

R1CS 是由上方 3 个向量(a, b, c)组成的序列,解向量为 s,且满意 s. a * s.b - s.c = 0,这也被称作一个束缚。能够试着核算一下,你会发现 s.a * s.b - s.c = x * x - sym_1,它们是等价的。

Vitalik 的比方包括 4 个拍平后的方程,每个方程对应一个 RICS 束缚,因而总共有 4 个束缚。

接下来是把 R1CS 转化为多项式。仍然不需求深化了解怎样转化,只需求知道转化是等价的。转化进程如下:

总共有 4 个 RICS 束缚,每个束缚中都包括一个向量 a,因而总共有 4 个向量 a,它们别离是:

a = [0, 1, 0, 0, 0, 0]  


a = [0, 0, 0, 1, 0, 0]

a = [0, 1, 0, 0, 1, 0]

a = [5, 0, 0, 0, 0, 1]

经过拉格朗日插值法,能够把这 4 个向量转化为 6 个多项式(由于每个向量包括 6 个值),它们别离是:

–5+ 9.166* x- 5* x^2+0.833* x^3  


8- 11.333 * x + 5 * x^2-0.666 * x^3

0 + 0 * x + 0 * x^2 + 0 * x^3

–6 + 9.5 * x - 4 * x^2 + 0.5 * x^3

4 - 7 * x + 3.5 * x^2 - 0.5 * x^3

–1+ 1.833 * x- 1 * x^2+ 0.166 * x^3

能够试着把 x= 1 代入这 6 个多项式核算,将得到 [0、1、0、0、0、0] 这 6 个值,你会发现它们正是第一个束缚下的向量 a;把 x 等于 2、3、4 别离带入这 6 个多项式,将得到其他 3 个束缚下的向量 a。

向量 a 对应 6 个多项式,向量 b 和向量 c 也是如此,因而总共会有 18 个多项式。当 x=1 时,这 18 个多项式的 18 个解正是第一个束缚;当 x 等于 2、3、4 时,别离得到第 2、3、4 个束缚。多项式与 RICS 是等价的。

到此就完结了从数学运算电路到多项式的转化:

  • 经过 RICS 转化,把证明多个原方程转化为证明多个 s.a * s.b - s.c = 0 ;

  • 经过多项式转化,把证明多个 s.a * s.b - s.c = 0 转化为证明在 x=1、x=2、x=3、x=4 时,A(x) * B(x) – C(x) = 0,其间 A(x) = s.a,B(x) = s.b,C(x) = s.c。如下图所示。

图中最左面一行数字 [1, 3, 35, 9, 27, 30] 为 Vitalik 比方中的解向量 s。A1(x) 为 a 的第 1 个多项式在 x 处的取值,比方 A1(1)=0;A1(x)~A6(x) 构成第 x 个束缚的向量 a,比方 x=1 时,a=[0、1、0、0、0、0];其他同理。

技能详解零常识证明完成办法:以 zk-SNARK 为例

(若越过转化,可从此处接着阅览)

咱们似乎是在经过一个繁琐的进程,把原本简略的证明变成了杂乱的证明,为什么?假如你仔细调查,就会发现一件奇特的作业产生了:

原本验证者需求验证的是:输入经过用作证明的数学运算电路,输出为真;但现在验证者需求验证的是,当 x=1、x=2、x=3、x=4 时,A(x) * B(x)–C(x) = 0。

A(x) * B(x)–C(x) 中包括了解向量 s,它是把输入、输出、电路绑定在一同的;验证 A(x) * B(x)–C(x) = 0,便是在验证输入和输出是否满意用作证明的数学运算电路。

这便处理了本节开端时提出的问题:验证者凭什么信赖「输出」是「输入」经过「用作证明的数学运算电路」核算出来的。

如此一来,验证者就不需求重视详细的输入和核算进程,只需求验证 A(x) * B(x) – C(x) = 0 自身是否建立。这让咱们真实有了时机去躲藏输入。

到此处能够长舒一口气了,尽管还没开端进入 zk-SNARK,但咱们现已完结了最困难的部分。假如转化部分没有了解清楚也不要紧,你只需求知道:

经过 zk-SNARK 完结零常识证明,实践上是要在 zk-SNARK 的协助下,验证当 x= 1、2、3、……、n 时,A(x) * B(x)–C(x) = 0,其间 n 是 RICS 束缚的个数;而不同的零常识证明问题,差异只在于它们的 A(x)、B(x)、C(x) 不同。

把屡次验证转化为一次验证

关于包括 n 个束缚的零常识证明问题,需求进行 n 次 A(x) * B(x)–C(x) 是否为零的验证。可不能够把 n 次验证变为一次验证?能够。

  • 界说 t(x) = (x-1) * (x-2) * …… * ( x-n),t(x) 在 x=1、x=2、…… 、x=n 处必定等于零;

  • 那么假如有一个多项式 h(x),使得 A(x) * B(x)–C(x) = t(x) * h(x) 建立,便意味着 A(x) * B(x)–C(x) 这个多项式能够被 t(x) 整除,那么这个多项式在 x=1、x=2、…… 、x=n 处也必定等于零。

也便是说,验证 A(x) * B(x)–C(x) = t(x) * h(x) ,就能够一次完结悉数 RICS 束缚的验证;而一旦这个验证经过,就能够信赖输入为真。

现在总算能够把接力棒交给 zk-SNARK 了,它要做的作业便是协助验证 A(x) * B(x)–C(x) = t(x) * h(x)。

验证的进程是怎样的?很简略。verifier (验证者)挑选一个随机数 x 建议应战,prover (证明者)证明在这个 x 处, A(x) * B(x)–C(x) = t(x) * h(x)。

在不知不觉中,一件要害又风趣的作业产生了:

证明者原本需求证明在 x=1、x=2、…… 、x=n 时,A(x) * B(x)–C(x) = 0,这是一种推理式证明,就像咱们解数学题,需求一步步地推导和核算,在这种证明进程中,要躲藏解题的常识是困难的。

但现在,推理式证明变成了交互式证明:verifier 在一个随机点上提出应战,prover 给出这个点上的解呼应应战;prover 需求有「常识」才干核算出随机点上的解,但这个解自身不会走漏「常识」。

而这,便是零常识证明得以建立的条件,或者说,假如没有交互式证明这种证明办法,零常识证明这个范畴便不会存在。

接下来只剩下一个问题:为什么能经过验证多项式上的一个点来确认两个多项式 A(x) * B(x)–C(x) 与 t(x) * h(x) 是否持平?

这是由多项式的特性决议的,「一个多项式在恣意点的核算成果都能够看做是其仅有身份的表明」。(引自 Maksym)

用图形阐明更为直观。下图是两个多项式,蓝色曲线是 f(x) = x^3– 6 * x^2+ 11 * x– 6,绿色曲线是 f(x) = x^3– 6 * x^2+ 10 * x– 5,不难发现,两个多项式只需细小的不同,但它们的曲线却是悬殊的。

技能详解零常识证明完成办法:以 zk-SNARK 为例

就像世界上没有两片相同的树叶,世界上也没有会在某个区域重合的两条不同曲线,它们只会在有限的点上相交。关于两个阶数为 d (x 的最大指数)的多项式,它们相交的点数不会超越 d。

在本文的运用中,有一个多项式 A(x) * B(x)–C(x),一个多项式 t(x) * h(x),假如它们不持平,它们只会在最多 d 个点上相交,也便是在 d 个点上的解相同。

这意味着只需当验证者挑选的随机应战点 x 恰好是这 d 个点中的一个时,才有或许产生误判,即在 A(x) * B(x)–C(x) 与 t(x) * h(x) 不相同的情况下误以为它们相同。

误判的概率存在,但咱们不必为此忧虑,比较 d 个点和 x 的取值规模,这件事产生的概率极低;结合后续在 zk-SNARK 协议中运用的密码学办法,这件事能够被以为几乎不或许产生。

那么现在,在悉数的预备作业完结后,本文进入下一个阶段。对第一阶段的笼统总结便是:零常识证明的问题便是验证核算满意多个束缚的问题,而多项式能够一个点验证多个束缚。

第二阶段:运用 zk-SNARK 完结零常识证明

得益于交互式证明和多项式的特性,咱们能够经过验证应战点 x 上多项式 A(x) * B(x)–C(x) 的解与 t(x) * h(x) 的解是否持平来验证 A(x) * B(x)–C(x) = t(x) * h(x) 是否建立,这种办法是能够躲藏 A(x) * B(x)–C(x) 这个多项式的系数的。

多项式的系数便是零常识证明中的「常识 」,最显着的,这个系数里是包括了想要躲藏的隐秘输入(解向量 s)的。

运用 zk-SNARK 完结零常识证明,便是完结 verifier 给出随机点进行应战的作业和 prover 给出随机点上的解完结证明的作业,这实践上是_互不信赖的 verifier 和 prover 之间的一场攻防战,他们运用的兵器是密码学_。

verifier 加密应战点

剖析需求被验证的 A(x) * B(x)–C(x) = t(x) * h(x):

  • t(x) 是 verifier 和 prover 两边都知道的一个多项式,t(x) = (x-1) * (x-2) * …… * ( x-n);

  • A(x) * B(x) – C(x) 只需 prover 知道,它的系数包括着常识;

  • h(x) 也只需 prover 知道,是用 A(x) * B(x) – C(x) 除以 t(x) 核算出来的,h(x) 不能被 verifier 知道,由于能够经过 t(x) 和 h(x) 核算出 A(x) * B(x) – C(x)。

为了明晰起见,先把 A(x) * B(x)–C(x) 写为 p(x),把要证明的问题简化为证明 p(x) = t(x) * h(x)。

其证明进程包括如下 3 步:

  • verifier 挑选随机应战点 x,假定 x= r;

  • prover 收到 r 后,核算 p(r) 和 h(r),并把这两个值给 verifier;

  • verifier 核算 t(r),然后核算 t(r) * h(r),并判别 t(r) * h(r) = p(r) 是否建立,若建立,则验证经过。

这实践上便是 zk-SNARK 的根底作业流程,但直接这样做会有一个问题:

prover 是知道 t(x) 的,假如把 r 给他,他就能够核算出 t(r),那么他完全能够结构出一对假的 p(x) 和 h(x),使得 p(r)= t(r) * h(r),成果便是他尽管不知道真实的 p(x),却能骗过 verifier。

处理这一问题的办法便是对 r 加密,使得 prover 能够核算某种办法下 p(r) 和 h(r),但却不能经过该办法下的 t(r) 结构假的满意验证要求的 p(x) 和 h(x)。

调查 prover 的证明进程,他需求核算 p(x) 和 h(x) 这两个多项式,但不论哪一个,其办法均为:c0+ c1*x^1+ ……+ cn*x^n;prover 自身知道 c0、c1 等等悉数系数。

假如 verifier 把 x 给 prover,假定 x= s,prover 就能完结悉数核算;但假如 verifier 把加密后的 s 给 prover,prover 是不能完结核算的,由于他无法用加密后的 s 核算出 s^2、……、s^n。

所以当 verifier 确认随机点 s 后,需求把加密后的 s、s^2、……、s^n 悉数给 prover,这样 prover 才干完结核算。

在实践运用中,verifier 是把 E(s)、E(s^2)、……、E(s^n) 给到 prover,其间 E(s) 是 s 的加密值,E(s) = g^s (mod n),这是一种同态加密办法。

同态加密有一个性质,便是先加密后核算的解与先核算后加密的解与是相同的。也便是说:

  • c0+ c1*E(s)+ ……+ cnE(s^n) = g^(c0+ c1s^1+ ……+ cn*s^n);

  • 即,p(E(s)) = E(p(s)) = g^p(s),h(E(s)) = E(h(s)) =g^h(s);

  • 那么,prover 就能经过核算 p(E(s)) 和 h(E(s)),得到 g^p(s) 和 g^h(s)。

此处只需求知道这种核算的确可行即可,假如想了解密码学部分的作业原理,可看我之前的一篇文章,《一文读懂零常识证明背面的简略逻辑》。

所以现在,证明进程变成了如下 3 步:

  • verifier 挑选随机应战点 x,假定 x= s,然后把一整套 s 的加密值给 prover;

  • prover 收到后,核算 g^p(s) 和 g^h(s),并把这两个值给 verifier;

  • verifier 核算 t(s),然后核算 (g^h(s))^ t(s),并判别 (g^h(s))^t(s) = g^p(s) 是否建立,若建立,则验证经过,由于这意味着 h(s) * t(s) = p(s)。

经过对随机点 s 加密,能够防止 prover 做弊,但 prover 还有一个缝隙可钻,即他不运用 verifier 给出的应战点 s 核算 h(s) 和 t(s),而是用其他值核算并诈骗 verifier。

所以 verifier 还需求一个办法,该办法能够证明 prover 给出的值的确是用 s 核算出来的。

本文将不详细打开这一部分,简略而言便是 verifier 除了挑选随机数 s 外,还要挑选一个随机数α,prover 给出的解需求保持 s 和α 之间的联系,假如这个联系被破坏了,则证明他没有用 s 在核算。

该办法被称作指数常识假定,若想了解详细内容,可阅览 Maksym 的文章。

在 verifier 完结了他的防卫战后,轮到 prover 了。

prover 加密核算成果

尽管 prover 只把多项式在应战点 x 上的解给了 verifier,但假如多项式系数的取值规模较小,verifier 是有或许经过暴力破解从解核算出多项式系数,即常识的。因而,prover 需求对解加密。

证明进程变成如下 3 步:

  • verifier 挑选随机应战点 x,假定 x= s,以及随机数α,然后把一整套 s 的加密值、以及一整套α * s 的加密值给 prover;

  • prover 收到后,核算 g^p(s)、g^h(s)、g^(α*p(s));挑选随机数δ 对解加密,变为 (g^p(s))^δ、(g^h(s))^δ、(g^(α*p(s)))^δ;然后把这 3 个加密值给 verifier;

  • verifier 核算 t(s),然后核算 ((g^h(s))^δ)^t(s),并判别 ((g^h(s))^δ)^t(s) = (g^p(s))^δ是否建立,若建立,则意味着 h(s) * t(s) = p(s);

  • 与此同时,verifier 还需求验证 ((g^p(s))^δ)^α = (g^(α*p(s)))^δ是否建立,若建立,则证明 prover 给出的解是用 s 核算出来的。

如此一来,prover 也就完结了自己的攻防战。

从交互变为非交互

zk-SNARK 的 N 是指 Non-Interactive,即非交互,但不难发现在上述的证明进程中,是需求 verifier 和 prover 交互的,并且咱们都知道,交互式证明自身是零常识证明得以建立的条件。那非交互是指什么?

很简略,所谓的非交互只不过是把 verifier 挑选随机数的作业交给了「可信设置」来完结,也便是由一个可信赖的第三方在证明开端前挑选随机应战点 x。

这种改动对 prover 没什么影响,由于他需求的始终是一组与 x 相关的加密值,而不必管这些加密值来自 verifier,仍是来自可信第三方。但这种改动对 verifier 有影响,由于他原本知道 x,能够用 x 核算 t(x),但现在他不知道了。

所以从交互到非交互,最首要的改动便是要在可信设置中把 t(x) 给到 verifier,以便他能完结验证作业。

t(x) 需求被加密,由于 prover 能够运用 t(x) 的值做弊;但加密后的 t(x) 又要能被用于核算,由于 verifier 需求核算 h(x) * t(x)。这便是这一部分的难点地点:h(x) 和 t(x) 都是加密值,但之前运用的同态加密办法不支持两个加密值的乘法。

zk-SNARK 运用配对操作处理这一问题,用公式表达便是 e(g^a, g^b)= a^g * b^g=(a * b)^g,其间 g^a 和 g^b 是加密值。配对操作能够把两个加密值映射为它们的乘积。

可信设置经过该办法把 t(x) 给到 verifier。所以,证明进程变为如下 3 步:

  • 可信设置:可信第三方挑选随机应战点 x,假定 x= s,以及随机数α,然后把一整套 s 的加密值、以及一整套α * s 的加密值给 prover;再把 t(s) 的加密值 g^t(s) 和α 的加密值 g^α 给 verifier;

  • prover 收到后,核算 g^p(s)、g^h(s)、g^(α*p(s));挑选随机数δ 对解加密,变为 (g^p(s))^δ、(g^h(s))^δ、(g^(α*p(s)))^δ;然后把这 3 个加密值给 verifier;

  • verifier 核算并判别 e(g^p, g) = e(g^t(s), g^h) 是否建立,若建立,则意味着 h(s) * t(s) = p(s);g^p、g^h、g^p′ 为 prover 供给的 3 个加密值的简写。

  • 与此同时,verifier 还需求验证 e(g^p′ , g) = e(g^p, g^α) 是否建立,若建立,则证明 prover 给出的解是用 s 核算出来的。

到这一步,咱们就基本完结了 zk-SNARK 协议的结构作业,它能够在不走漏多项式系数的情况下证明多项式,即完结零常识证明。

额定一提,在可信设置阶段为 prover 和 verifier 预备的加密值被称作 CRS (common reference string),用以生成 CRS 的随机数是要被毁掉的,它们可用于做弊;可信设置需求可信第三方,经过什么机制挑选可信第三方是一个议题。

可信设置影响 zk-SNARK 的通用性,因而也开展出了不需求可信设置的 zk-SNARK,其含义严重但了解起来并不难:只不过是换了一种办法供给随机应战点 x。

不论有多少种 zk-SNARK,咱们需求知道的是:零常识证明是一种交互式的证明体系,对它而言重要的、也是与安全和资源相关的一个作业便是,以什么样的办法供给随机应战点。

把 p(x) 还原为 A(x) * B(x)–C(x)

zk-SNARK 协议需求证明的多项式是 A(x) * B(x)–C(x),假如把 p(x) 还原为 A(x) * B(x)–C(x),相较于 p(x) 时的协议,首要差异在于:

  • prover 需求别离供给 A(s)、B(s)、C(s) 的加密值;

  • verifier 需求验证 A(s) * B(s) = h(s) * t(s)+ C(s);

  • 在对 prover 的核算进行束缚时(比方必须用 s 核算),需求有 3 个不同的α 别离对应于 A(s)、B(s)、C(s);当 prover 对核算成果加密时,需求有 3 个不同的δ别离加密 A(s)、B(s)、C(s)。

在详细的 zk-SNARK 协议中,还会经过一些规划来改善协议,本文不再逐个论说,zk-SNARK 的探秘之旅到这儿就悉数完毕啦。

在旅程完毕之际,有几点阐明:

1.zk-SNARK 有不同的组合完结办法,本文首要是以 Pinocchio 协议为头绪;密码学所涉甚广,文章不免会有遗漏和了解不当之处,请不要尽信,深化研究需以论文为参阅。
2. 本文在构建 zk-SNARK 协议部分(第二部分)采用了 Maksym 文章的结构;Maksym 的文章极有条理地介绍了 zk-SNARK,但或许关于不太具有相关布景常识的读者来说仍有必定的了解难度,这也是我写这篇文章的原因地点。

mp.weixin.qq.com

版权声明

本文仅代表作者观点,不代表网赚之家本站立场。
本文系作者授权发表,未经许可,不得转载。

评论