1. Hi区块链首页
  2. 资讯
  3. 区块链

学术向 | 深入浅出zkSNARKs

Quadratic Span Programs

在上一部分中,我们看到了 NP 问题的计算是如何被相互化简的,尤其是那些 NP 完全问题,那些 NP 完全问题基本上又都再次形成了其他的 NP 问题——包括交易验证问题。那么对我…

Quadratic Span Programs

在上一部分中,我们看到了 NP 问题的计算是如何被相互化简的,尤其是那些 NP 完全问题,那些 NP 完全问题基本上又都再次形成了其他的 NP 问题——包括交易验证问题。那么对我们来说找到一个对所有 NP 问题都通用的 zkSNARKs 就变的很容易了:我们只需要选择适合的 NP 完全问题。所以如果我们想展示如何使用 zkSNARKs 来验证交易的话,那么展示如何处理这个确定的 NP 完全问题就是一个有效的方法,并且比从理论上解释更容易让人接受。

接下来就是基于论文GGPR12(这里面链接的技术报告比原文的干货更多)来谈了,这篇论文的作者发现了一个叫做Quadratic Span Programs(QSP)的问题,这个问题完全就是为 zkSNARKs 准备的。一个二次跨度程序 (Quadratic SpanProgram )是由一组多项式和寻找给定多项式倍数的线性组合任务构成。此外,输入字符串的每个单独的 bit 都限制了你能够使用的多项式。详细来说(通常来讲 GSPs 限制不是那么严格,但是我们就是需要这种强限制的版本,因为后面我们会用到)就是:

对于输入长度为n 的在域 F 上的 QSP 问题由下面这些部分构成:

在该域F上的一组多项式v 0,…,vm,w 0,…,w m,

F上的多项式t(目标多项式),

单射函数f:{(i,j)| 1≤i≤n,j∈{0,1}}→{1,…,m}

这里的任务大致是,将多项式乘以因子并将它们相加,使得总和(称为线性组合)是t的倍数。对于每个二进制输入字符串u,函数f限制了可以使用的多项式,或者更严格的讲就是它们必须是线性组合的因子。正式的表示就是:

一个输入 u 会被 QSP 接受(或验证)当且仅当存在来自域F的元组a =(a 1,…,a m),b =(b 1,…,b m)满足:

如果 k = F(i,U [i] )那么  (u[i]是 u 的第 i 位)如果 k = f(i, 1 – u[i]) 那么  a k,b k = 0目标多项式 t 整除  v a w b,  其中v a = v 0 + a 1  v 0 + … + a m v m,w b = w 0 + b 1 w 0 + … + b mw m。

请注意,如果2n小于m,则仍然可以自由选择元组a和b。这意味着QSP仅适用于特定大小的输入 – 这个问题通过使用非统一复杂性来消除,这是我们现在不会涉及的主题,我们只需要知道当输入值很小时,我们的密码学也能良好运转。

作为对布尔公式的可满足性的类比,您可以看到因子a 1,…,am,b 1,…,b m作为变量的赋值,或者通常是NP问题的见证。因为 QSP 是属于 NP 的,那么所有的验证者都必须(只要她知道因子)检查多项式 t 是否能够整除 vawb ,这也是一个多项式时间的问题。

这里我们不会讨论如何将通用计算和线路问题简化成 QSP 问题,因为这对于我们了解基本概念没有任何帮助,我们只需要知道 QSP 是 NP 完全(或者说比一些非均匀分布的像 NP/poly 问题更完全)的就好了。实际上,这个简化是一个“工程”部分——必须要使用一种很聪明的方法才能让 QSP 问题尽可能的小并且有一些其他的优良特性。

关于QSP我们已经可以看到的一件事是如何更有效地验证它们:验证任务包括检查一个多项式是否能整除另一个多项式。如果证明者可以提供一个满足 th = v a w b 的多项式 h,那么这个任务就被转变成了检验一个多项式恒等式,换句话说就是检验 th-v a w b = 0,其实就是检验某个特定的多项式是否是零多项式。虽然这看起来似乎很简单,但是我们接下来要使用的多项式相当巨大(阶数大概是原始电路门数的 100 倍),以至于获得两个多项式的乘积并不是一件容易的事。

所以相比于真正的去计算 v a,w b 以及它们的乘积,验证者只需要选择一个私密的随机点(这个点是 zCash 中 ““有毒废物”(toxic waste”) 的一部分),然后对所有的 k 计算 t(s),v k(s) 和  w k(s) ,并通过它们以及 v a(s)和w b(s)来验证等式:t(s)h(s)= v a(s)w b(s)。  。所有这一系列的多项式加法,标量乘法和一个多项式乘积都可以被简化成域上的乘法和加法。

只在一个单点而不是在路径的所有点上验证多项式恒等式会降低安全性,但是证明者唯一可以作弊的情况是当  th-va wb不是零多项式时,即使证明者成功的获得了多项式的一个零项,但是她也不知道 s,并且比起 s(域中元素的数量)可能的值,0 的数量是很少的,所以实际中只在一个单点验证也是非常安全的。

 

zkSNARK详细信息

我们现在详细描述QSP上的zkSNARK。它在开始设置阶段会执行每一个单独的 QSP。在zCash中,交易验证的线路是固定的,因此QSP的多项式也是固定的,这个 QSP 在设置阶段只允许被执行一次,然后在所有的只有输入 u 不同的交易上复用。这个开始的的设置会生成一个公共参考字符串(CRS),验证者选择随机且和私密字域元素s并加密该点处的多项式的值。验证者使用一些特定的加密E并在CRS中把E(v k(s))和E(w k(s))公布。CRS还包含几个其他值,这使得验证更有效,并且还增加了零知识属性。在这里使用的加密E具有一定的同态特性,这允许证明者在不实际知道v k(s)的情况下计算E(v(s))。

 

如何使用零知识来简单估计一个多项式

 

让我们首先看一个更简单的情况,即一个多项式在私密点上的加密估值,而不是完整的QSP问题。

为此,我们选择一个群(这里通常选择椭圆曲线)和生成器g。请记住,如果存在数字n(群顺序),则组元素称为生成器,使得列表g 0,g 1,g 2,…,gn-1包含组中的所有元素。那么我们就称 g 为“生成器”。加密方法很简单:E(x):= g x  。现在验证者选择一个私密域元素 s 并把它作为 CRS 的一部分公布出来。

E(s 0),E(s 1),…,E(s d)—- d是所有多项式的最高阶

在那之后,s就可以(并且必须)被遗忘。这正是zCash所谓的“有毒废物”,因为如果有人可以恢复这个以及后来选择的其他秘密值,他们可以通过在多项式中找到零来项,随意的伪造证据。

在不知道 s 的情况下,证明者可以使用这些值对任意多项式 f 计算 E(f(s)):假设我们的多项式是  要计算 E(f(s)) 的话,我们可以得到 E(f(s))= E(4s 2 + 2s + 4)= g 4s 2 + 2s + 4 = E(s 2)4 E(s 1)2 E(s 0)4, 这些值我们都可以从公开的CRS中获取,而不需要知道确定的 s。

这里唯一的问题是s被破坏后,验证者无法检查证明者是否正确地计算了多项式。为此,我们还选择另一个秘密字段元素α,并公开下面的“转移”值:

E(αS 0),E(αS1),…,E(αS d)

设置阶段之后  α会随着 s 一起被销毁掉,验证者和证明者都不知道这个值。但是使用这些加密的值,证明者可以轻易的计算出 E(α f(s)),用上面的例子就是:E(4αS 2 +2αs+4α)= E(αS 2)4 E(αS 1)2 E(αS 0)4  。所以证明者只要公布 A := E(f(s)) 和 B := E(α f(s))),那么验证者就可以验证这些值是否匹配了。要验证是否匹配就要用到我们的另一个主要的手法”配对函数”e 了。椭圆曲线和配对函数一定要一起选择,那么 x 和 y 就会满足下面的式子:

e(g x,g y)=e(g,g)xy

使用该配对功能,所述检验器检查该E(A,G α)= E(B,g) -注意,gα是已知的检验器,因为它是CRS的一部分作为E(αS 0)。如果证明者没有作弊,为了看到这个检查是有效的,让我们看看以下的等式:

e(A,gα)= e(g f(s),gα)= e(g,g)αf(s)

e(B,g)= e(gαf(s),g)= e(g,g)αf(s)

然而,还有一个更重要的问题是证明者能否提供满足e(A,gα)= e(B,g)而不是  E(f(s))和E(αf(s))  的 A 和 B。这个问题的答案是『我们希望他不能』。严格地说,我们称之为『d 次方指数知识假设』,而且我们也不知道一个想作弊的证明者能不能做到这一点。这个假设同时也是其他用来证明公钥加密方案安全性的类似的假设的拓展,而这些假设似乎也不能确认他们到底是不是正确的。

实际上,上述协议并不真正允许验证者检查证明者提供的多项式f(x)= 4x 2 + 2x + 4,验证者其实只需要在点 s 上验证『几个』多项式就可以了。QSP 问题的 zkSNARK 还包含另外一个值,这个值可以让验证者确认证明者是否真的求出了正确的多项式。

这里的这个示例告诉我们验证者并不需要求出完整的多项式来证明这一点,仅仅使用配对函数就可以了。下一步我们就要添加零知识的部分了,这样验证者就不能构建任何关于 f(s) 值了,甚至连 E(f(s)) 这种加密信息也不行。

为此,证明者选择随机得δ而不是A:= E(f(s))和B:= E(αf(s))),她发送A’:= E(δ+ f(s))))和B:= E(α(δ+ f(s)))。如果我们假设加密不能被破坏,那么零知识属性就非常明显了。我们现在必须检查两件事:1。证明者实际上可以计算这些值; 2.验证者的检查仍然是true。

对第一件事来说,注意,A’ = E(δ+ F(S))=g δ+f(S) =g δgf(S) = E(δ)E(f(S))= E(δ )A,同样的,B’ = E(α(δ+ F(S))))= E(αδ+αf(S)))= g αδ+αF(S) = g αδαF(S)= E(α)δ E(αf(S))= E(α)δ B.

对第二件事.,请注意,验证者唯一检查的是,她收到的值A和B满足基于某个a的等式A = E(a)和B = E(αa),这显然是=δ+ f(s),实际上就是a = f(s)。

好的,现在我们总算知道了一点关于在验证者不知道那个值的情况下,证明者是如何在一个加密的私密点上面计算出多项式加密值的。现在让我们将其应用于QSP问题。

 

QSP问题的SNARK

请记住,在QSP中,我们给出多项式v 0,…,v m,w 0,…,w m,目标多项式t(最高阶为d)和二进制输入字符串u。证明者找到a1,…,am , b 1,…,b m(这些值都取决于u)和多项式h使得

th =(v 0 + a 1 v 1 + … + a m v m)(w 0 + b 1 w 1 + … + b m w m)。

在上一节中,我们已经解释了CRS如何生成。现在我们选择一个秘密号码s和α并公布公布出来:

E(S 0),E(S 1),…,E(S d)和E(αS 0),E(αS 1),…,E(αS d

因为我们没有单个多项式,而是针对问题这一列多项式是固定的,我们需要把推出的多项式公布出来

E(t(s)),E(αt(s)),

E(V 0(S)),…,E(V m(S)),E(αv 0(S)),…,E(αv m(S)),

E(w0(S)),…,E(wm(S)),E(αw0(S)),…,E(αwm(S)),

我们还需要之后用的的秘密数字β v,β w ,γ(它们会被用来验那些多项式是推算出来的,而不是任意的多项式),然后把它们公布出来:

E(γ),E(β v γ),E(β w ^γ)

E(βv V 1(S)),…,E(βv V m(S))

E(βw W1(S)),…,E(βw Wm(S))

E(βv  t(S)),E(βw  t(S))

这是完整的CRS(公共引用字符串)。在实际实现中,CRS的一些元素并不是必须的,但这会使表达式复杂化。

现在证明者还需要做什么?她使用上面解释的还原函数来找到多项式h和值a 1,…,a m, b 1,…,b m。这里有一点非常重要,就是要使用一个 witness-preserving reduction(见上文)因为只有这样,值a 1,…,a m, b 1,…,b m可以与reduction一起计算出来,否则将会非常非常困难。为了描述证明者作为证据发送给验证者的内容,我们必须回到QSP的定义。

这里有一个限制  a 1,…,a m, b 1,…,bm这些值的单射函数 f:{(i,j)| 1≤i≤n,j∈{0,1}}→{1,…,m} 。因为相对来说 m 是比较大的,所以对于任何输入,函数 f 的输出的都不会包含这些数字。而这些下标没有被限制,然后基于Ifree中的所有下标 k 定义Vfree(X)=Σ ķaķ v ķ(X),  。对于等式w(x)= b 1 w 1(x)+ … + b m w m(x) 来说,我们的证明将由下面的式子构成:

V free:= E(V free(s)),W:= E(w(s)),H:= E(h(s)),

V’ free  := E(αvfree(s)),W’:= E(αw(s)),H’:= E(αh(s)),

Y:= E(βv V free (S)+βww(S)))

最后一个等式用来检验是否使用了正确的多项式(这一部分还没有讲到,不过其他的例子会说到它)。要注意的是,我们所有的加密值,证明者只需要知道 CRS 就可以全部推算出来。

验证者还要做的有:

由于k的值(其中k不是“free”下标)可以直接从输入u计算(验证者也知道,这是要验证的值),验证者可以通过v计算出总和:

E(V’free(S))= E(Σ ķak vķ(S)),其中k的范围在所有索引不是Ifree

有了这个,验证者现在使用配对函数e确认以下等式(不要害怕):

e(V ‘ free,g)= E(V free,gα)=,e(W’,E(1))= e(W,E(α)),e(H’,E(1))= e(H,E(α))

e(E(γ),Y)= e(E(βv γ),V free)e(E(β w γ),W)

e(E(v 0(s))E(v in(s))V free,E(w 0(s))W)= e(H,E(t(s)))

要了解这里关键概念的知识,你必须要知道配对函数是允许我们在加密信息上进行一些有限的计算的:首先我们可以使用任意多次的加法,但是不能使用乘法。其次这个加法是来自加密方法本身的加同态,乘法则是通过配对函数的两个参数来实现的。所以  e(W’,E(1))= e(W,E(α))基本上就是在加密空间中用 1 乘以 W’,然后和α乘以 W 做比较。回想一下上面的定义你就会发现 W 和 W’ 应该就是 E(w(s)) 和 E(α w(s)),如果证明者提供的是正确的证明.

如果你还记得上面关于如何在一个私密点上推算多项式的话,这三个首先要检查的点基本上就可以确认证明者确实知道一些用 CRS 中的部分构造的多项式。第二个条目往往是用来确保证明者使用的是正确的多项式 v 和 w,而不是任意的多项式。而它背后的逻辑则是除了从E(vfree(s)和E)w(s))中获取精确的值之外,证明者没办法计算出加密组合E(βvvfree(S)+βw  w(S)))。因为  βv在 CRS 中是隔离的,并不是 CRS 中的一部分,只有在和多项式 w k(s) 组合起来的时候才知道w k(s)  的值。而将它们“混合”起来的唯一方法则是通过同样的加密 γ。

假设证明者提供了正确的证明,那么让我们检查一下是否正确。左边和右边分别是

e(E(γ),Y)= e(E(γ),E(β v vfree(S)+βww(S)))= e(g,g)γ(β v vfree(S )+βw W(S))

e(E(β v γ),Vfree)e(E(βw γ),W)= e(E(β v γ),E(vfree(S)))e(E(βw γ) ,E(W(S)))= e(g,g)(β v γ)vfree(S) e(g,g)(β w γ)W(S)  = e(g,g)γ( βvVfree(S)+βw W(S)) 

第三项基本上就是检查了(v 0(s)+ a 1 v 1(s)+ … + a m v m(s))(w 0(s)+ b 1 w 1(s)+ … + b m w m(s))= h(s)t(s),这也是QSP问题的主要条件。需要注意的是,要将加密值的乘法转换为未加密值的加法,因为E(x)E(y)= g x g y = g x + y = E(x + y)。

添加零知识

正如我在开始时所说的,关于zkSNARKS的显着特征是简洁而不是零知识部分。我们现在将看到如何添加零知识,下一节将简要介绍一下简洁性。

这个想法就是证明者现在通过一个随机私密的值来进行“移位”,然后再在其他的等式中“移位回来”以取得平衡。证明者会选择 δfree,δ,然后在证明中执行下面的替换:

用 Vfree(s)+δfree t(s)来替换 Vfree(s)

用w(s)+δw t(s )来替换  w(s)

通过这两个替换, Vfree 和 W 这两个包含 witness 因子编码的值基本上就变成了无法区别的随机值,因此要从 witness 中提取出来也不可能。大部分的等式检验对修改都是『免疫』的,而我们要确保正确的值就是 H 或者说是 h(s)。那我们就要确保

(v 0(s)+ a 1 v 1(s)+ … + a m v m(s))(w 0(s)+ b 1 w 1(s)+ … + b m w m(s))= h(s)t(s),或换句话说

(v 0(s)+ v in(s)+ v free(s))(w 0(s)+ w(s))= h(s)t(s)

这两个等式成立。通过修改,我们得到了

(V 0(S)+ V in(S)+ V free(S)+δfree t(S))(W 0(s)+ W(s)+δt(S))

然后将结果展开,我们看到用h替换h(s)

h(S)+δfree(W 0(s)+ W(s))+δw(V 0(S)+ Vin(S)+ Vfree(S))+(δfreeδw)t(s)

在输入和 Witness 大小之间取一个折中的值

就像你在上面这些小节中看到的一样,我们的证明由一个群(就是一个椭圆曲线)的 7 个元素组成。而且验证者的工作就是检验一些配对函数的等式是否成立以及计算 E(Vin(s)) 这样一个跟随输入大小的线性任务。最主要的是,在这个验证过程中,既不需要  witness 字符串的大小,又不需要计算工作量来验证 QSP(没有 SNARKs)。这就意味着 SNARKs 的校验是个很复杂的问题,而简单的问题往往都是一样的。造成这个结果的主要原因则是,因为我们只在一个单独的点上面检验了多项式的一致性,而不是全部的点。多项式可以变的非常非常复杂,但是一个点始终是一个点。而唯一能影响到验证结果的参数就是安全性的等级(比如群的大小)和输入值的最大尺寸。

减小第二个参数是可行的,将输入值的一部分移动到 witness 中:

我们不验证函数 f(u, w),u 是输入,w 是 witness,而是做一次 hash,然后验证:

f’(H,(u,w)):= f(u,w)∧h(u)= H

这样就意味着我们可以用一个 hash 来代表输入 h(u) 了(这样就会变的更短),除了验证 f(x, w),我们还需要验证某个值 x 的 hash 等于 H(u)(这样的话,那 x 极有可能就等于 u 了)。这样就将原始输入 u 移动到 witness 字符串中了,这样虽然会增大 witness 的大小,但是输入值的大小就减小为一个常数了。

这是非常了不起的,因为它允许我们在恒定时间内验证任意复杂的语句。

这与以太坊有什么关系?

因为验证计算是以太坊区块链的核心,所zkSNARK和以太坊关系紧密相连。有 zkSNARKs,我们不但可以完成任何人都可证实的私密的计算,而且还可以高效的完成。

虽然以太坊使用了一个图灵完备的虚拟机,但目前还无法在以太坊中实现zkSNARK验证。验证者任务在概念上看似简单,但配对函数实际上很难计算,而且在单个区块中还会消耗更多的 gas。椭圆曲线乘法已经相对复杂,而配对函数将这个复杂度又增加了一个级别。

像zCash这样的现有zkSNARK系统对每个任务都使用相同的问题/电路/计算。在zCash里,它是交易验证。在以太坊上,zkSNARKs不会局限于单一的计算问题,而是让所有的人都能够在不发布一个新的区块链的情况下构建他们自己的 zkSNARK 系统。添加到以太坊的每个新zkSNARK系统都需要一个新的私密的可信任的准备阶段(某些部分可以重复使用,但不是全部),即必须生成新的CRS。也可以为“通用虚拟机”添加zkSNARK系统。这样的话当你使用一个新的实例时,你就不需要重新设置了,因为你将不再需要为以太坊上新的智能合约发布一个新的区块链。

将zkSNARKs结合到以太坊上

有多种方法可以为以太坊启用zkSNARK。所有这些都降低了配对函数和椭圆曲线操作的实际成本(其他所需的操作已经足够便宜),因此也可以降低这些操作的gas。

1.提高(保证)EVM的性能

2.仅针对某些配对函数和椭圆曲线乘法提高EVM的性能

第一种选择当然是从长远来看更好的回报,但更难实现。我们目前正致力于为EVM添加功能和限制,如这将更好的支持即时编译和在现存实现下最小改动的解释器的实现,而无需在现有实现中进行太多必需的更改。另一种可能性是完全换掉EVM并使用类似eWASM的东西。

第二个选项可以通过强制所有以太坊客户端执行现某个确定的配对函数和确定的椭圆曲线上的乘法作为所谓的预编译合约来实现。这样做的好处是可能更容易和更快地实现,缺点是我们固定在确定的配对函数和确定的椭圆曲线上。以太坊的任何新客户都必须重新实施这些预编译合约。此外,如果有什么新的进展并且有人找到更好的zkSNARK,更好的配对函数或更好的椭圆曲线,或者如果在椭圆曲线,配对函数或zkSNARK中发现缺陷,我们将不得不添加新的预编译合约。

 

来源:格密链

声明:登载此文出于传递更多信息之目的,观点仅代表作者本人,绝不代表Hi区块链赞同其观点或证实其描述。
提示:投资有风险,入市须谨慎。本资讯不作为投资理财建议。