©2016-2024 Matools All rights reserved,
粤ICP备17059708号
In part V we saw how a statement Alice would like to prove to Bob can be
converted into an equivalent form in the “language of polynomials” called a
Quadratic Arithmetic Program (QAP).
在第五部分，我们看到了Alice如何能将他想对Bob证明的语句，转换为一个我们称之为二次算术程序的采用多项式语言的等式。
In this part, we show how Alice can send a very short proof to Bob showing she
has a satisfying assignment to a QAP. We will use the Pinocchio Protocol of
Parno, Howell, Gentry and Raykova. But first let us recall the definition of a
QAP we gave last time:
在这个部分，我们将展示Alice如何能发送一个非常短的证明给Bob，以显示她有一个满足QAP的成真指派。我们将采用皮诺曹协议(Parno, Howell,
Gentry and Raykova)。但是首先让我们回忆一下我们上次学到的QAP的定义：
A Quadratic Arithmetic Program Q of degree d and size m consists of polynomials
L1,…,Lm, R1,…,Rm, O1,…,Om and a target polynomial T of degree d.
一个d阶m大小的二次算术程序Q，由多项式L1,…,Lm, R1,…,Rm, O1,…,Om和一个d阶目标多项式T构成。
An assignment (c1,…,cm) satisfies Q if, defining
L:=∑(m,i=1) ci⋅Li
R:=∑(m,i=1) ci⋅Ri
O:=∑(m,i=1) ci⋅Oi
and
P:=L⋅R−O
we have that T divides P.
对于有一个值(c1,…,cm)满足Q，如果定义
L:=∑(m,i=1) ci⋅Li
R:=∑(m,i=1) ci⋅Ri
O:=∑(m,i=1) ci⋅Oi
并且定义
P:=L⋅R−O
我们可以判断T能整除P
As we saw in Part V, Alice will typically want to prove she has a satisfying
assignment possessing some additional constraints, e.g.cm=7; but we ignore this
here for simplicity, and show how to just prove knowledge of some satisfying
assignment.
就像我们在第五部分看到的那样，Alice 特别想要通过证明她有个具有一些特定限制的成真指派，比如cm=7
；但是为简单起见，我们在这儿忽略这个，仅仅展示如何证明一些成真指派的知识。
If Alice has a satisfying assignment it means that, defining L,R,O,P as above,
there exists a polynomialH such that P=H⋅T. In particular, for any s∈Fp we have
P(s)=H(s)⋅T(s).
如果Alice有一个成真指派，它意味着，像上面一样定义L,R,O,P，存在一个多项式H，满足P=H⋅T。尤其是，对于任何的s∈Fp，我们有
P(s)=H(s)⋅T(s)。
Suppose now that Alice doesn’t have a satisfying assignment, but she still
constructsL,R,O,P as above from some unsatisfying assignment (c1,…,cm). Then we
are guaranteed thatT does not divide P. This means that for any polynomial H of
degree at mostd, P and L,R,O,H will be different polynomials. Note that P and
L,R,O,H here are both of degree at most 2d.
假设现在Alice没有一个成真指派，但是她依然像上面那样用一个非成真指派(c1,…,cm)构造了L,R,O,P 。这种情况下我们确保T不能整除P
。这意味着，对于任何最高为d阶的多项式H，P and H⋅T 将是不同的多项式。注意到这儿的P和H⋅T阶最多是2d。
Now we can use the famous Schwartz-Zippel Lemma that tells us that two
different polynomials of degree at most2d can agree on at most 2d points s∈Fp.
Thus, ifp is much larger than 2d the probability that P(s)=H(s)⋅T(s) for a
randomly chosens∈Fp is very small.
现在我们能采用著名的Schwartz-Zippel引理，这告诉我们两个不同的最高为2d阶的多项式能够在最多2d个点s∈Fp上相等。因此，如果p比2d
要大的多，那么P(s)=H(s)⋅T(s)能够随机的选中s∈Fp的几率非常的小。
This suggests the following protocol sketch to test whether Alice has a
satisfying assignment.
*
Alice chooses polynomials L,R,O,H of degree at most d.
*
Bob chooses a random point s∈Fp, and computes E(T(s)).
*
Alice sends Bob the hidings of all these polynomials evaluated at s, i.e.
E(L(s)),E(R(s)),E(O(s)),E(H(s)).
*
Bob checks if the desired equation holds at s. That is, he checks whether
E(L(s)⋅R(s)−O(s))=E(T(s)⋅H(s))
这表明接下来的协议描绘了，测试Alice是否有一个成真指派。
*
Alice选择最大阶数为d的多项式L,R,O,H。
*
Bob选择一个随机的点s∈Fp，并计算出E(T(s))。
*
Alice将这些多项式在s点计算出的值的匿数传给Bob，比如 E(L(s)),E(R(s)),E(O(s)),E(H(s))。
*
Bob检查这是否是于s点想要的等式。那就是，他检查E(L(s)⋅R(s)−O(s))=E(T(s)⋅H(s))
Again, the point is that if Alice does not have a satisfying assignment, she
will end up using polynomials where the equation does not hold identically, and
thus does not hold at most choices ofs. Therefore, Bob will reject with high
probability over his choice ofs in such a case.
接下来，如果 ALice 没有一个成真指派，她将最终使用一个让等式不成立的多项式，因此在大多数 s 的选择上不成立。因此，Bob 在这种情况下有很高的概率在s
上拒绝这种情况。
The question is whether we have the tools to implement this sketch. The most
crucial point is that Alice must choose the polynomials she will use, without
knowings. But this is exactly the problem we solved in the verifiable blind
evaluation protocol, that was developed in Parts II-IV.
问题是是否我们有实现这个草案的工具。最至关重要的点是Alice必须选择她要用的多项式，在不知道s
的情况下。但是这是一个我们已经解决的很明确的问题，那就是在2-4部分我们开发出来的可验证盲估协议。
MAKING SURE ALICE CHOOSES HER POLYNOMIALS ACCORDING TO AN ASSIGNMENT
确保Alice根据一个赋值选择她的多项式
Here is an important point: If Alice doesn’t have a satisfying assignment, it
doesn’t mean she can’t find any polynomialsL,R,O,H of degree at most d with
L⋅R−O=T⋅H, it just means she can’t find such polynomials where L,R and O were
“produced from an assignment”; namely, thatL:=∑(m,i=1) ci⋅Li,R:=∑(m,i=1)
ci⋅Ri,O:=∑(m,i=1) ci⋅Oi for the same (c1,…,cm).
有一个要点：如果Alice没有一个成真指派，也不意味着通过L⋅R−O=T⋅H她不能找到某个最高阶为d的多项式L,R,O,H，这仅意味着她不能找到L,R 和 O
是“从赋值产生的”这样的多项式；也就是，从同一个(c1,…,cm)，产生的L:=∑(m,i=1) ci⋅Li,R:=∑(m,i=1)
ci⋅Ri,O:=∑(m,i=1) ci⋅Oi。
The protocol of Part IV just guarantees she is using some polynomials L,R,O of
the right degree, but not that they were produced from an assignment. This is a
point where the formal proof gets a little subtle; here we sketch the solution
imprecisely.
第四章的协议仅确保Alice正在使用一些阶数正确的多项式L,R,O，而非他们从某个赋值产生。这儿的形式化证明比较精妙；所以我们粗略的描述一下解决方案。
Let’s combine the polynomials L,R,O into one polynomial F as follows:
F=L+( X^(d+1) )⋅R+( X^(2(d+1)) )⋅O
The point of multiplying R by X^(d+1) and O by X^(2(d+1)) is that the
coefficients ofL,R,O “do not mix” in F: The coefficients of 1,X,…,X^d in F are
precisely the coefficients ofL, the next d+1 coefficients of ( X^( d+1 ) ) ,…,
( X^( 2d+1 ) ) are precisely the coefficients of R, and the last d+1
coefficients are those ofO.
让我们像下面这样合并这三个多项式L,R,O成为一个新的多项式：
F=L+( X^(d+1) )⋅R+( X^(2(d+1)) )⋅O
将R和X^(d+1)相乘、O 和 X^(2(d+1))相乘的关键点是L,R,O的系数不会在F中被混合： 1,X,…,X^d在F中的系数恰好是L的系数，接下来
X^( d+1 ),…,X^( 2d+1 )的d+1个系数恰好是R的系数，最后d+1个系数全部都是O的。
Let’s combine the polynomials in the QAP definition in a similar way, defining
for eachi∈{1,…,m} a polynomial Fi whose first d+1 coefficients are the
coefficients ofLi, followed be the coefficients of Ri and then Oi. That is, for
eachi∈{1,…,m} we define the polynomial
Fi=Li+( X^(d+1) )⋅Ri+( X^2(d+1) )⋅Oi
Note that when we sum two of the Fi’s the Li, Ri, and Oi “sum separately”. For
example,F1+F2=(L1+L2)+( X^(d+1) )⋅(R1+R2)+( X^(2(d+1)) )⋅(O1+O2).
让我们用类似的方法在QAP的定义里面来组合多项式，为每个i∈{1,…,m}定义一个多项式Fi，这个多项式的第一个d+1个系数是Li的系数，接下来是Ri的系数和
Oi的系数。那么，对于每个i∈{1,…,m}我们定义多项式：
Fi=Li+( X^(d+1) )⋅Ri+( X^2(d+1) )⋅Oi
注意到当我们将两个Fi相加的时候，Li、Ri 和 Oi “分别相加”。例如F1+F2=(L1+L2)+( X^(d+1) )⋅(R1+R2)+(
X^(2(d+1)) )⋅(O1+O2)。
More generally, suppose that we had F=∑(m,i=1) ci⋅Fi for some (c1,…,cm). Then
we’ll also haveL=∑(m,i=1) ci⋅Li,R=∑(m,i=1) ci⋅Ri,O=∑(m,i=1)ci⋅Oi for the same
coefficients(c1,…,cm). In other words, if F is a linear combination of the Fi’s
it means thatL,R,O were indeed produced from an assignment.
更一般化，假设我们对于(c1,…,cm)有F=∑(m,i=1) ci⋅Fi。然后对于同样的系数(c1,…,cm)，我们将同样有L=∑(m,i=1)
ci⋅Li,R=∑(m,i=1) ci⋅Ri,O=∑(m,i=1)ci⋅Oi。换句话说，如果F是一个Fi的线性组合，它意味着L,R,O确实从赋值产生。
Therefore, Bob will ask Alice to prove to him that F is a linear combination
of theFi’s. This is done in a similar way to the protocol for verifiable
evaluation:
所以，Bob会要求Alice向他证明，F是一个Fi的线性组合。这跟可验证评估协议的做法类似。
Bob chooses a random β∈F(∗,p), and sends to Alice the hidings
E(β⋅F1(s)),…,E(β⋅Fm(s)). He then asks Alice to send him the element E(β⋅F(s)).
If she succeeds, an extended version of the Knowledge of Coefficient
Assumptionimplies she knows how to writeF as a linear combination of the Fi’s.
Bob随机选择一个β∈F(∗,p)，并且将匿数E(β⋅F1(s)),…,E(β⋅Fm(s))发送给Alice。他然后要求Alice发送给他E(β⋅F(s))
。如果她成功了，作为一个知识系数假设的扩展版本，她知道如何写出F作为Fi的线性组合。
ADDING THE ZERO-KNOWLEDGE PART – CONCEALING THE ASSIGNMENT
添加零知识部分-隐藏赋值
In a zk-SNARK Alice wants to conceal all information about her assignment.
However the hidingsE(L(s)),E(R(s)),E(O(s)),E(H(s)) do provide some information
about the assignment.
用zkSNARK，Alice想隐藏她所有赋值的信息。然而，匿数E(L(s)),E(R(s)),E(O(s)),E(H(s)) 确实提供了一些关于所赋值的信息。
For example, given some other satisfying assignment (c′1,…,c′m) Bob could
compute the correspondingL′,R′,O′,H′and hidings
E(L′(s)),E(R′(s)),E(O′(s)),E(H′(s)). If these come out different from Alice’s
hidings, he could deduce that(c′1,…,c′m) is not Alice’s assignment.
例如，给出一些其他的成真指派(c′1,…,c′m)，Bob可以计算相关的L′,R′,O′,H′以及匿数
E(L′(s)),E(R′(s)),E(O′(s)),E(H′(s))。如果这些不同于Alice的匿数，她可以推断出(c′1,…,c′m)不是Alice的赋值。
To avoid such information leakage about her assignment, Alice will conceal her
assignment by adding a “randomT-shift” to each polynomial. That is, she chooses
randomδ1,δ2,δ3∈F(∗,p), and defines Lz:=L+δ1⋅T,Rz:=R+δ2⋅T,Oz:=O+δ3⋅T.
要阻止这样的关于Alice自己赋值信息的泄漏，Alice将采用对每个多项式添加一个随机的T-shift来隐藏她的赋值信息。那就是，她选择一个随机的
δ1,δ2,δ3∈F(∗,p)，并且定义Lz:=L+δ1⋅T,Rz:=R+δ2⋅T,Oz:=O+δ3⋅T。
Assume L,R,O were produced from a satisfying assignment; hence, L⋅R−O=T⋅H for
some polynomialH. As we’ve just added a multiple of T everywhere, T also divides
Lz⋅Rz−Oz. Let’s do the calculation to see this:
Lz⋅Rz−Oz=
(L+δ1⋅T)(R+δ2⋅T)–O−δ3⋅T
(L⋅R−O)+L⋅δ2⋅T+δ1⋅T⋅R+δ1δ2⋅(T^2)–δ3⋅T=
T⋅(H+L⋅δ2+δ1⋅R+δ1δ2⋅T–δ3)
Thus, defining
Hz=H+L⋅δ2+δ1⋅R+δ1δ2⋅T−δ3
we have that Lz⋅Rz−Oz=T⋅Hz. Therefore, if Alice uses the polynomials
Lz,Rz,Oz,Hz instead of L,R,O,H, Bob will always accept.
假设 L,R,O 是从一个成真指派所产生的；因此，对于某个多项式H 有 L⋅R−O=T⋅H。当我们对所有地方都仅仅加上T的倍数，T同样能整除Lz⋅Rz−Oz
。让我们进行一些运算看看：
Lz⋅Rz−Oz=
(L+δ1⋅T)(R+δ2⋅T)–O−δ3⋅T
(L⋅R−O)+L⋅δ2⋅T+δ1⋅T⋅R+δ1δ2⋅(T^2)–δ3⋅T=
T⋅(H+L⋅δ2+δ1⋅R+δ1δ2⋅T–δ3)
因此，定义
Hz=H+L⋅δ2+δ1⋅R+δ1δ2⋅T−δ3
我们有Lz⋅Rz−Oz=T⋅Hz。因此，如果Alice使用多项式Lz,Rz,Oz,Hz代替L,R,O,H，Bob总是可以接受。
On the other hand, these polynomials evaluated at s∈Fp with T(s)≠0 (which is
all butd s’s), reveal no information about the assignment. For example, as T(s)
is non-zero andδ1 is random, δ1⋅T(s) is a random value, and therefore
Lz(s)=L(s)+δ1⋅T(s) reveals no information about L(s) as it is masked by this
random value.
另一方面，这些多项式在s∈Fp处用T(s)≠0评估，没有披漏任何关于赋值的信息。例如，当T(s)非零而且δ1是随机的时候。δ1⋅T(s)是一个随机值，所以，
Lz(s)=L(s)+δ1⋅T(s)没有披漏任何关于L(s)的信息，因为它被这个随机值给掩盖了。
WHAT’S LEFT FOR NEXT TIME?
下回文章还剩下什么？
We presented a sketch of the Pinocchio Protocol in which Alice can convince
Bob she possesses a satisfying assignment for a QAP, without revealing
information about that assignment. There are two main issues that still need to
be resolved in order to obtain a zk-SNARK:
我们展示了皮诺曹协议的草案，用这个协议，Alice可以说服Bob
她拥有一个QAP的成真指派，而不泄漏任何关于这个赋值的信息。为了获得zkSNARK，有两个主要的问题仍然需要解决。
* In the sketch, Bob needs an H that “supports multiplication”. For example,
he needs to computeE(H(s)⋅T(s)) from E(H(s)) and E(T(s)). However, we have not
seen so far an example of anH that enables this. We have only seen an H that
supports addition and linear combinations.
* 在草案中，Bob需要一个支持乘法的H。例如，他需要从E(H(s)) 与 E(T(s)) 去计算 E(H(s)⋅T(s))
。然而，我们到目前未知没有见过一个H的例子能做这个事情。我们只看见一个支持加法和线性组合的H。
* Throughout this series, we have discussed interactive protocols between
Alice and Bob. Our final goal, though, is to enable Alice to send
single-message non-interactive proofs, that are publicly verifiable – meaning
that anybody seeing this single message proof will be convinced of its
validity, not just Bob (who had prior communication with Alice).
贯穿本系列，我们以及讨论了Alice和Bob的交互协议。尽管，我们最终的目的，是使Alice发送一个简单的没有交互的证明消息，这些证明消息是公开的可验证的——意味着任何人看到这个简单的证明消息，都将被它的有效性说服，而不只是Bob(他先与Alice联系）。
Both these issues can be resolved by the use of pairings of elliptic curves,
which we will discuss in the next and final part.
依靠采用椭圆曲线对，这两个问题能被解决，这个我们在下一部分，也是最后一部分讨论。
热门工具 换一换