原文出自：https://blog.z.cash/snark-explain2/
作者：Ariel Gabizon
譯者：Matter實驗室
In this post, we recall the notion of a polynomial, and explain the notion of “blind evaluation” of a polynomial, and how it is implemented using Homomorphic Hiding (HH). (See Part I for an explanation of HH. ) In future posts, we will see that blind evaluation is a central tool in SNARK constructions.
在這篇文章中，我們將回顧多項式的概念瓦侮，解釋多項式“盲估”的概念，以及如何使用同態(tài)隱藏 (HH) 來實現(xiàn)這一方案忍坷。(請看 第一部分 對于 HH 的解釋)。 在未來的文章中革砸，我們將會認(rèn)識到盲估是構(gòu)建 SNARK 的核心工具氢橙。
We denote by Fp the field of size p; that is, the elements of Fp are {0,…,p?1} and addition and multiplication are done mod p as explained in Part I.
我們使用 Fp 來表示 p 的域的大小赔桌；也就是說供炎，跟第一部分說明的一樣，Fp 中的元素是 {0,...,p-1} 疾党，并且加法和乘法都會執(zhí)行 mod p音诫。
POLYNOMIALS AND LINEAR COMBINATIONS
多項式和線性組合
Recall that a polynomial P of degree d over Fp is an expression of the form
P(X)=a0+a1?( X )+a2?( X^2 ) +…+ ad?( X^d )
, for some a0,…,ad ∈ Fp.
回憶一下具有 在 Fp 上的 d 階多項式，是一個下面這種形式的表達式：
P(X)=a0+a1?( X )+a2?( X^2 ) +…+ ad?( X^d )
其中 a0,…,ad ∈ Fp
We can evaluate P at a point s ∈ Fp by substituting s for X, and computing the resultant sum
P(s)=a0+a1?( s )+a2?( s^2 )+…+ad?( s^d)
For someone that knows P, the value P(s) is a linear combination of the values 1,(s),…,(s^d) – where linear combination just means “weighted sum”, in the case of P(s) the “weights” are a0,…,ad.
我們可以這樣在 s ∈ Fp 點上計算 P雪位，讓 s 代替 X竭钝，并計算總和。
P(s)=a0+a1?( s )+a2?( s^2 )+…+ad?( s^d)
根據(jù)大家所了解的 P雹洗，P(s) 的值是 1,(s),…,(s^d) 值的一個線性組合香罐。—— 線性組合僅意味著“加權(quán)和”时肿，在 P(s) 一例中權(quán)重就是 a0,…,ad穴吹。
In the last post, we saw the HH E defined by E(x)=g^x where g was a generator of a group with a hard discrete log problem. We mentioned that this HH “supports addition” in the sense that E(x+y) can be computed from E(x) and E(y). We note here that it also “supports linear combinations”; meaning that, given a,b,E(x),E(y), we can compute E(ax+by). This is simply because
E(ax+by)=g^( ax+by )=g^( ax )?g^( by )=( ( g^x )^a )?( ( g^y )^b )=( E(x)^a )?( E(y)^b ).
在上一篇文章中，我們看到了用 E(x)=g^x 定義的帶HH性質(zhì)的 E嗜侮，其中 g 是一個采用難離散對數(shù)問題的群生成器。我們提到啥容，這種HH“加法支持”锈颗，能用E(x)和E(y)計算出E(x+y)。 我們在這兒指出咪惠，HH一樣能“支持線性組合”击吱；這意味著，給定 a,b,E(x),E(y) 遥昧，我們能計算出 E(ax+by)覆醇。原理很簡單，因為：
E(ax+by)=g^( ax+by )=g^( ax )?g^( by )=( ( g^x )^a )?( ( g^y )^b )=( E(x)^a )?( E(y)^b )
BLIND EVALUATION OF A POLYNOMIAL
某個多項式的盲估
Suppose Alice has a polynomial P of degree d, and Bob has a point s ∈ Fp that he chose randomly. Bob wishes to learn E(P(s)), i.e., the HH of the evaluation of P at s. Two simple ways to do this are:
- Alice sends P to Bob, and he computes E(P(s)) by himself.
- Bob sends s to Alice; she computes E(P(s)) and sends it to Bob.
假設(shè) Alice 有 d 階多項式 P炭臭， 并且 Bob 可以隨機地選擇一個點 s∈Fp 永脓， Bob 期望知道 E(P(s))，這就是于 s 點對 P 進行評估的同態(tài)隱藏(HH)鞋仍，做到這點有兩種簡單的方式：
- Alice 發(fā)送 P 給 Bob常摧，從而 Bob 可以自行計算 E(P(s))。
- Bob 發(fā)送 s 給 Alice威创；Alice計算 E(P(s)) 并發(fā)送給 Bob落午。
However, in the blind evaluation problem we want Bob to learn E(P(s)) without learning P – which precludes the first option; and, most importantly, we don’t want Alice to learn s, which rules out the second [1].
[1] The main reason we don’t want to send P to Bob, is simply that it is large – (d+1) elements, where, for example, d~2000000 in the current Zcash protocol; this ultimately has to do with the “Succinct” part of SNARKs. It is true that the sequence of hidings Bob is sending to Alice above is just as long, but it will turn out this sequence can be “hard-coded” in the parameters of the system, whereas Alice’s message will be different for each SNARK proof.
然而，在盲估問題中肚豺，我們希望 Bob 在不了解 P 的情況下了解 E(P(s)) – 這將排除第一種選擇溃斋； 更重要的是，我們不希望 Alice 了解 s 吸申，這將排除第二種選擇 [1]梗劫。
- [1] 我們不想將 P 發(fā)送給 Bob 的主要原因是享甸，僅僅是因為它太大了——(d+1)個元素，比如在跳，現(xiàn)有的Zcash協(xié)議中 d 的值將近2百萬枪萄；它最終會與“簡潔的” SNARKs 協(xié)同工作。事實上猫妙，上面Bob發(fā)送給Alice的匿數(shù)序列也一樣長瓷翻，但是這個序列能夠作為系統(tǒng)的參數(shù)硬編碼到系統(tǒng)中，而每次SNARK證明時Alice的消息都不相同割坠。
Using HH, we can perform blind evaluation as follows.
Bob sends to Alice the hidings E(1),E(s),…,E(s^d).
Alice computes E(P(s)) from the elements sent in the first step, and sends E(P(s)) to Bob. (Alice can do this since E supports linear combinations, and P(s) is a linear combination of 1,s,…,sd.)
Note that, as only hidings were sent, neither Alice learned s [2], nor Bob learned P.
[2] Actually, the hiding property only guarantees s not being recoverable from E(s), but here we want to claim it is also not recoverable from the sequence E(s),…,E(s^d) that potentially contains more information about s. This follows from the d-power Diffie-Hellman assumption, which is needed in several SNARK security proofs.
使用HH齐帚，我們可以像下面一樣進行盲估。
- Bob發(fā)送匿數(shù) E(1),E(s),…,E(s^d) 給Alice彼哼。
- Alice根據(jù)送達的匿數(shù)計算 E(P(s)) 对妄，并且發(fā)送 E(P(s)) 給Bob。(Alice能夠利用E對線性組合的支持進行計算敢朱，并且 P(s) 就是 1,s,...,s^d 的線性組合剪菱。)
可以注意到，因為只有匿數(shù)被發(fā)送拴签，Alice不會了解 s[2],Bob也不會了解 P.
- [2] 事實上孝常，隱藏特性僅僅保證了 s 不能由 E(s) 反推得到，但在這里蚓哩，我們想強調(diào)它同樣不可能由序列 E(s),…,E(s^d) 反推得到构灸，雖然這個序列包涵了很多 s 的信息。這樣的判斷緣于 Diffie-Hellman 假設(shè)岸梨，這個假設(shè)論證了 SNARK 的安全性喜颁。
WHY IS THIS USEFUL?
為什么這是一個有用的方法
Subsequent posts will go into more detail as to how blind evaluation is used in SNARKs. The rough intuition is that the verifier has a “correct” polynomial in mind, and wishes to check the prover knows it. Making the prover blindly evaluate their polynomial at a random point not known to them, ensures the prover will give the wrong answer with high probability if their polynomial is not the correct one. This, in turn, relies on the Schwartz-Zippel Lemma stating that “different polynomials are different at most points”.
在后面的文章中，我們將詳細(xì)討論盲估技術(shù)如何被應(yīng)用于 SNARKs曹阔。 大致的解釋是半开，驗證器在內(nèi)部有一個 “正確的”多項式，它需要檢查是否證明方知道這件事次兆。這將使得證明方可以在一個他們不知道的隨機的點上驗證他們是否知道這個多項式稿茉，并保證證明方的多項式如果不正確，他有更高的幾率得到一個報錯芥炭。這種做法依賴于Schwartz-Zippel引理說明漓库，即“不同多項式在大多數(shù)點是相同的”。
譯者總結(jié)
