原文出自：https://blog.z.cash/snark-explain4/
作者：Ariel Gabizon
译者：Matter实验室
In this part, we build on Part II and III to develop a protocol for verifiable blind evaluation of polynomials, which we will define shortly. In Part V we’ll start to see how such a protocol can be used for constructing SNARKs, so bear with me a little bit longer for the connection to SNARKs :).
在这一部分中，我们在第二部分和第三部分的基础上开发可验证的多项式盲估协议，我们将在稍后给出它的定义。在第五部分中，我们将开始看到如何用这个协议构建SNARKs，因此，请稍微忍受长一点点时间，让我们来建立和SNARKs的联系。:)
Suppose, as in Part II, that Alice has a polynomial P of degree d and Bob has a point s∈Fp that he chose randomly. We want to construct a protocol that allows Bob to learn E(P(s)), i.e. the hiding of P evaluated at s, with two additional properties:
- Blindness: Alice will not learn s (and Bob will not learn P).
- Verifiability: The probability that Alice sends a value not of the form E(P(s)) for P of degree d that is known to her, but Bob still accepts – is negligible.
This is what we call verifiable blind evaluation of a polynomial. The protocol in Part II gave us the first item but not the second. To get verifiability we need an extended version of the Knowledge of Coefficient Assumption (KCA) that was presented in Part III.
假设，在 第二部分 中，Alice 有 d 阶多项式 P，Bob 有它随机选择的点 s∈Fp 。我们希望建立一个可以让 Bob 知道 E(P(s)) 的协议，比如，采用两种额外的特性，评估 P 在 s 上的匿数：
- 盲的： Alice 将不会知道 s (同时 Bob 也不会知道 P )。
- 可验证性：Alice发送一个不是她所知道的以d阶多项式P所构成的E(P(s))形式的值，而Bob仍然接受的可能性，微乎其微。
这就是我们所说的可验证多项式盲估。第二部分的协议给出了我们需要的第一个条款，但没有包括第二个。为了实现可验证性，我们需要一个利用第三部分所描述的知识系数假设(KCA)来进行扩展的版本。
The verifiability and blindness properties are useful together because they make Alice decide what polynomial P she will use without seeing s. [1] This, in a sense, commits Alice to an “answer polynomial” without seeing the “challenge point” s. This intuition will become more clear in the next parts of the series.
[1] In the fully formal proof, things are somewhat more subtle, as Alice does see some information about s before deciding on her P – for example, the hidings of s ,…, s^d.
可验证性和盲的特性合在一起非常有用，因为它可以让 Alice 在没看到 s 的情况下，决定使用何种多项式 P。[1] 这在某种意义上，可以保证 Alice 在没看到 “挑战点” s 的情况下得到”答案多项式”。这种直觉将在后面的系列中变得更加清晰。
- [1]在完全正式的证明中，这些是多少有些微妙的，比如 Alice 在决定她的P 之前确实看到了一些关于 s 的信息 —— 比如，s ,…, s^d的匿数。
AN EXTENDED KCA
扩展的知识系数假设(KCA)
The KCA as we defined it in Part III essentially said something like this: If Bob gives Alice some α-pair (a,b=α⋅a) and then Alice generates another α-pair (a′,b′), then she knows c such that a′=c⋅a. In other words, Alice knows the relation between a′ and a.
我们在第三部分提出的KCA定义从本质上说像这样：如果Bob给了Alice某个α-pair (a,b=α⋅a)，那么Alice生成另外的α-pair (a′,b′)，则Alice就知道 c 满足a′=c⋅a。换句话说，Alice知道a′ 和 a之间的关系。
Now, suppose that instead of one, Bob sends Alice several α-pairs (a1,b1),…,(ad,bd) (for the same α); and that again, after receiving these pairs, Alice is challenged to generate some other α-pair (a′,b′). Recall that the main point is that Alice must do so although she does not know α.
现在，假设Bob发送给Alice不是一个而是多个α-pairs (a1,b1),…,(ad,bd)（以相同的α）；同样，在收到这些对之后，Alice被挑战来产生另外一些α-pair (a′,b′)。回想一下，关键点在于 Alice 必须在她不知道α的前提下这么做。
As we saw in Part III, a natural way for Alice to generate such an α-pair, would be to take one of the pairs (ai,bi) she received from Bob, and multiply both elements by some c∈F(∗,p); if (ai,bi) was an α-pair, then (c⋅ai,c⋅bi) will be one too. But can Alice generate α-pairs in more ways now that she’s received multiple α-pairs? Perhaps using several of the received α-pairs simultaneously to get a new one?
正如我们在第三部分看到的，一个让 Alice 产生这样的 α-pair 的自然方式，是选取她从 Bob 处收到的配对中的一个 (ai,bi)，并将两个元素都与某个 c∈F(∗,p) 相乘； 如果 (ai,bi) 是一个 α-pair，则 (c⋅ai,c⋅bi) 将同样也是。 但是，既然Alice收到了多个α-pairs，那么她能以多种方式产生α-pairs吗？或许可以同时使用多个收到的 α-pairs 来产生一个新的配对？
The answer is yes: For example, Alice can choose two values c1,c2∈Fp and compute the pair (a′,b′)=(c1⋅a1+c2⋅a2,c1⋅b1+c2⋅b2). An easy computation shows that, as long as a′ is non-zero, this is also an α-pair:
b′=c1⋅b1+c2⋅b2=c1α⋅a1+c2α⋅a2=α(c1⋅a1+c2⋅a2)=α⋅a′.
答案是肯定的: 例如, Alice能选择两个值 c1,c2∈Fp 并计算配对 (a′,b′)=(c1⋅a1+c2⋅a2,c1⋅b1+c2⋅b2). 一个简单的计算显示，只要a′不为零，这就是一个**
α**-pair：
b′=c1⋅b1+c2⋅b2=c1α⋅a1+c2α⋅a2=α(c1⋅a1+c2⋅a2)=α⋅a′.
More generally, Alice can take any linear combination of the given d pairs – that is choose any c1 ,…, cd ∈ Fp and define (a′,b′)=(∑(d,i=1)ci⋅ai,∑(d,i=1)ci⋅bi).
更一般的，Alice 可以使用给定的d个配对的任何线性组合——那就选择任意的 c1,…,cd∈Fp，同时定义 (a′,b′)=(∑(d,i=1)ci⋅ai,∑(d,i=1)ci⋅bi).
Note that, if Alice uses this strategy to generate her α-pair she will know some linear relation between a′ and a1,…,ad; that is, she knows c1,…,cd such that a′=∑(d,i=1) ci⋅ai.
注意到，如果 Alice 使用这种策略生成她的 α-pair，她将知道某种 a′ 和 a1,…,ad 之间的线性关系；也就是说，她将知道c1,…,cd可以满足a′=∑(d,i=1) ci⋅ai。
The extended KCA states, essentially, that this is the only way Alice can generate an α-pair; that is, whenever she succeeds, she will know such a linear relation between a′ and a1,…,ad. More formally, suppose that G is a group of size p with generator g written additively as in Part III. The d-power Knowledge of Coefficient Assumption (d-KCA) [2] in G is as follows:
The d-KCA was introduced in a paper of Jens Groth
扩充的 KCA 表明，本质上，这是 Alice 产生一个 α-pair 的唯一方式； 并且，当她成功时，她会知道 a′ 与 a1,…,ad 之间有这样的线性关系。 更正式地来说，假设 G 是一个像第三部分说的那样，拥有字面加法的生成器g，并且以p为大小的群。 在G中的d次知识系数假设(d-KCA)[2]就是下面这样：
- [2]d-KCA在Jens Groth的论文中有介绍。
d-KCA: Suppose Bob chooses random α∈F(∗,p) and s∈Fp, and sends to Alice the α-pairs (g,α⋅g),(s⋅g,αs⋅g),…,(( s^d )⋅g, α⋅(s^d )⋅g). Suppose that Alice then outputs another α-pair (a′,b′). Then, except with negligible probability, Alice knows c0,…,cd∈Fp such that ∑(d,i=0) ci⋅( s^i )⋅g=a′.
d-KCA： 假设 Bob 随机选择 α∈F(∗,p) 和 s∈Fp, 并且发送给 Alice α-pairs (g,α⋅g),(s⋅g,α⋅s⋅g),…,(( s^d )⋅g, α⋅( s^d )⋅g). 假设 Alice 随后输出了另外一个 α-pair (a′,b′)。这时，除了微乎其微的可能性外，Alice 知道 c0,…,cd∈Fp 满足 ∑(d,i=0) ci⋅( s^i )⋅g=a′.
Note that in the d-KCA Bob does not send an arbitrary set of α-pairs, but one with a certain “polynomial structure”. This will be useful in the protocol below.
注意到，在 d-KCA 中，Bob 并没有发送任意的 α-pairs，而是发送了有特定“多项式结构” 的多项式。这将对下面提到的协议有所帮助。
THE VERIFIABLE BLIND EVALUATION PROTOCOL
可验证的盲估协议
Assume that our HH is the mapping E(x)=x⋅g for a generator g of G as above.
For simplicity, we present the protocol for this particular E:
Bob chooses a random α∈F(∗,p), and sends to Alice the hidings g,( s )⋅g, … ,( s^d )⋅g (of 1,s,…,s^d) and also the hidings α⋅g,α⋅( s )⋅g,…,α⋅( s^d )⋅g (of α,α⋅( s ),…,α⋅(s^d )).
Alice computes a=P(s)⋅g and b=α⋅P(s)⋅g using the elements sent in the first step, and sends both to Bob.
Bob checks that b=α⋅a, and accepts if and only if this equality holds.
假设我们的HH是由上面说到的G的一个生成器g所构成的映射 E(x)=x⋅g
为了简单，我们就这个特定的E来描述一下协议：
-
Bob 选择一个随机的 α∈F(∗,p)，并且发送给 Alice 一系列匿数 g,( s )⋅g, … ,( s^d )⋅g (对应着 1,s,…,s^d) ，以及匿数 α⋅g,α⋅( s )⋅g,…,α⋅( s^d )⋅g (对应着 α,α⋅( s ),…,α⋅(s^d ))。
-
Alice 使用第一步中发送的元素计算出 a=P(s)⋅g 和 b=α⋅P(s)⋅g，并且都发送给 Bob。
-
Bob 检查 b=α⋅a，当且仅当这个等式成立就会将(a,b)接受。
First, note that given the coefficients of P, P(s)⋅g is a linear combination of g,( s )⋅g,…,( s^d )⋅g; and αP(s)⋅g is a linear combination of α⋅g,α⋅( s )⋅g,…,α⋅( s^d )⋅g. Thus, similarly to the protocol of Part II, Alice can indeed compute these values from Bob’s messages for a polynomial P that she knows.
首先，注意到对于给定的系数 P，P(s)⋅g 是 g,( s )⋅g,…,( s^d )⋅g 的线性组合；而 αP(s)⋅g 是 α⋅g,α⋅( s )⋅g,…,α⋅( s^d )⋅g 的线性组合。 因此，与第二部分的协议相似，Alice 确实能由她所知道的多项式P根据Bob的消息计算出这些值。
Second, by the d-KCA if Alice sends a,b such that b=α⋅a then almost surely she knows c0,…,cd∈Fp such that a=∑(d,i=0)ci⋅( s^i )⋅g. In that case, a=P(s)⋅g for the polynomial P(X)=∑(d,i=0)ci⋅( X^i ) known to Alice. In other words, the probability that Bob accepts in Step 3 while at the same time Alice does not know such a P is negligible.
其次，通过d-KCA，如果Alice发送的 a,b 满足 b=α⋅a，则几乎可以确认她知道 c0,…,cd∈Fp 满足 a=∑(d,i=0)ci⋅( s^i )⋅g。在这种情况下，Alice是知道由多项式P(X)=∑(d,i=0)ci⋅( X^i )所构成的a=P(s)⋅g的。换句话说，Bob在第三步成功接受的同时，Alice并不知道这样的P的可能性微乎其微。
To summarize, using the d-KCA we’ve developed a protocol for verifiable blind evaluation of polynomials. In the next posts, we will see how this building block comes to play in SNARK constructions.
总结一下，通过使用d-KCA，我们已经开发出一个协议来进行可验证多项式盲估。在接下来的文章中，我们将看到在SNARK的架构下，如何
总结，通过使用 d-KCA ，我们已经研发出了可验证的盲评价多项式的协议。在下面的博文中，我们将看到这样的构建块，如何在SNARK结构中产生作用。
译者总结
数学关系
交互模型
网友评论