6.The_Pinocchio_Protocol.md

该repository作为本人读书笔记, 记录知识的获取, 以blog的形式记录下来. 该文库我会不断更新, 如果喜欢的话麻烦点一下star.

The Pinocchio Protocol

<<part V

If Alice has a satisfying assignment it means that, defining as above, there exists a polynomial such that . In particular, for any we have .

📖 如果 Alice 有满足等式那就意味着, 如上定义了 , 并且存在多项式 满足等式 . 尤其, 对于任何 , 都满足 .

Suppose now that Alice doesn’t have a satisfying assignment, but she still constructs as above from some unsatisfying assignment . Then we are guaranteed that does not divide . This means that for any polynomial of degree at most , and will be different polynomials. Note that here is of degree at most , here are of degree at most and here is degree at most .

📖 假设现在 Alice 没有满足条件的等式, 但她仍然可以从不满足的赋值 构建 . 然我们只要保证 无法整除 . 那就意味着任意的最高 阶多项式 , 和 会是不同的多项式. 注意到 这里阶最高为 , 在这里最高为 阶而 最高为 阶.

Now we can use the famous Schwartz-Zippel Lemma that tells us that two different polynomials of degree at most can agree on at most points . Thus, if is much larger than the probability that for a randomly chosen is very small.

📖 现在我们使用著名的 Schwartz-Zippel 定理告诉我们两个最高 阶不同的多项式能够有 个点, 在满足 的情况. 因此, 如果 的范围远大与 的量级, 在 取随机点满足 的概率是非常小的.

This suggests the following protocol sketch to test whether Alice has a satisfying assignment.

1. Alice chooses polynomials of degree at most .
2. Bob chooses a random point , and computes .
3. Alice sends Bob the hidings of all these polynomials evaluated at , i.e. .
4. Bob checks if the desired equation holds at . That is, he checks whether .

📖 建议的检查 Alice 是否有满足条件的赋值的协议:

1. Alice 选择最大 阶多项式 .
2. Bob 选择一个随机点 并且计算 .
3. Alice 发送给 Bob 在 隐藏的多项式, 例如 .
4. Bob 检查在 对应的多项式是否满足: .

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 of . Therefore, Bob will reject with high probability over his choice of in such a case.

📖 另外如果 Alice 没有满足的赋值, 那么她最终给出的等式最终无法相等, 而且是在大多数的 都不成立. 因此, Bob 会大概率拒绝 Alice 提供的多项式在他选择的 的情况下.

Making sure Alice chooses her polynomials according to an assignment

Here is an important point: If Alice doesn’t have a satisfying assignment, it doesn’t mean she can’t find any polynomials of degree at most with , it just means she can’t find such polynomials where and were “produced from an assignment”; namely, that for the same .

📖 这里有一个重要的点: 如果 Alice 没有满足条件的赋值, 并不意为着她不能在最高的 阶多项式找到 满足 , 这只意味着她找不到多项式 和 来源与复制产生; 也就是 通过相同的 产生 .

The protocol of Part IV just guarantees she is using some polynomials 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.

📖 第四部分的协议保证了她是使用了一些多项式的 在正确的阶数, 但是他们不是由赋值中产生的. 在这一点上, 形式证明有些微妙. 在这里我们不精确地描述解决方案.

Let’s combine the polynomials into one polynomial as follows:

让我们组合多项式到同一个多项式如下所示:

Note that when we sum two of the ’s the , , and “sum separately”. For example,

现在但我们将两个所包含的, , 和 相加,举例来说:

More generally, suppose that we had for some . Then we’ll also have for the same coefficients . In other words, if is a linear combination of the ’s it means that were indeed produced from an assignment.

更普遍的情况, 假设我们对于有. 那么对于相同的系数我们可以得到. 总而言之, 如果是’s的线性组合那就意味着确实由一个等式生成.

Therefore, Bob will ask Alice to prove to him that is a linear combination of the ’s. This is done in a similar way to the protocol for verifiable evaluation:

Bob chooses a random , and sends to Alice the hidings . He then asks Alice to send him the element . If she succeeds, an extended version of the Knowledge of Coefficient Assumption implies she knows how to write as a linear combination of the ’s.

因此, Bob 将要求 Alice 提供给他是's的证明. 这可以通过可评估的验证协议来完成:

Bob选择一个随机数, 并且发送给 Alice以下隐藏值. 然后他要求 Alice 发送给他元素 . 如果成功, 扩展版本的Knowledge of Coefficient Assumption说明她知道与的线性组合.

Adding the zero-knowledge part – concealing the assignment

In a zk-SNARK Alice wants to conceal all information about her assignment. However the hidings do provide some information about the assignment.

在zk-SNARK中 Alice 想要隐瞒关于她的等式所有信息. 然而隐藏式已经确实提供了一些信息在等式中.

For example, given some other satisfying assignment Bob could compute the corresponding and hidings . If these come out different from Alice’s hidings, he could deduce that is not Alice’s assignment.

例如, 提供其他满足等式的系数 Bob能够计算相应的和隐藏式. 如果这与Alice's 隐藏式存在出入, 她能够推断出并非Alice's的等式.

To avoid such information leakage about her assignment, Alice will conceal her assignment by adding a “random -shift” to each polynomial. That is, she chooses random , and defines .

为了避免关于她等式的这些信息的提供， Alice 会在每一个等式中增加一个“随机T”. 然后, 她就选择随机数, 并定义.

Assume were produced from a satisfying assignment; hence, for some polynomial . As we’ve just added a multiple of everywhere, also divides . Let’s do the calculation to see this:

)

假设是从一个满足的等式中产生; 因此 对于一些多项式. 对于我刚到处添加的多项式, 同样除以. 让我们来做如此的计算:

)

Thus, defining , we have that . Therefore, if Alice uses the polynomials instead of , Bob will always accept.

那么, 定义, 我们有. 因此, 如果 Alice 使用多项式代替, Bob往往可以接受.

On the other hand, these polynomials evaluated at with (which is all but d s’s), reveal no information about the assignment. For example, as is non-zero and is random, is a random value, and therefore reveals no information about as it is masked by this random value.

另一方面, 这些多项式满足在的情况下, 对于等式不会揭示任何信息. 举个例子, 对于是非零的而是随机的, 那么是随机值, 因此没有暴露任何信息, 对于被定义为随机值.

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:

• In the sketch, Bob needs an that "supports multiplication". For example, he needs to compute from and . However, we have not seen so far an example of an that enables this. We have only seen an that supports addition and linear combinations.
• 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).

Both these issues can be resolved by the use of pairings of elliptic curves, which we will discuss in the next and final part.

我们提供了Pinocchio协议的草图, 在该协议中, 爱丽丝可以说服鲍勃, 她拥有满足条件的QAP, 并且不泄露这个等式的信息. 一下还有两点需要解决以实现zk-SNARK:

• 在草案中, Bob需要一个多项式并且支持乘法. 例如, 他需要从计算 和 中计算. 然而他到目前为止他都并没有看到一个多项式满足这种情况. 我们只能看到有一个多项式支持加法和现行组合.
• 整个系列中, 我们都在讨论 Alice 和 Bob 之间的交互协议. 然而, 我们的目标是希望 Alice 仅发送一个非交互式交易证明, 而这个式公共证明, 意味着任何人都能看见这个单一消息证明并确信他的有效性, 而不仅只是 Bob(作为事先与 Alice 交流的人).

以上两点都可以通过使用椭圆曲线对来解决, 这我们将留到最后讨论.