原文出自：https://blog.z.cash/snark-explain2/
作者：Ariel Gabizon
譯者：Matter實(shí)驗(yàn)室
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.
在這篇文章中，我們將回顧多項(xiàng)式的概念，解釋多項(xiàng)式“盲估”的概念，以及如何使用同態(tài)隱藏 (HH) 來(lái)實(shí)現(xiàn)這一方案。(請(qǐng)看 第一部分 對(duì)于 HH 的解釋)。 在未來(lái)的文章中，我們將會(huì)認(rèn)識(shí)到盲估是構(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 來(lái)表示 p 的域的大?。灰簿褪钦f(shuō)，跟第一部分說(shuō)明的一樣，Fp 中的元素是 {0,...,p-1} ，并且加法和乘法都會(huì)執(zhí)行 mod p。
POLYNOMIALS AND LINEAR COMBINATIONS
多項(xiàng)式和線性組合
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 階多項(xiàng)式，是一個(gè)下面這種形式的表達(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 點(diǎn)上計(jì)算 P，讓 s 代替 X，并計(jì)算總和。
P(s)=a0+a1?( s )+a2?( s^2 )+…+ad?( s^d)
根據(jù)大家所了解的 P，P(s) 的值是 1,(s),…,(s^d) 值的一個(gè)線性組合?！?線性組合僅意味著“加權(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 是一個(gè)采用難離散對(duì)數(shù)問(wèn)題的群生成器。我們提到，這種HH“加法支持”，能用E(x)和E(y)計(jì)算出E(x+y)。 我們?cè)谶@兒指出，HH一樣能“支持線性組合”；這意味著，給定 a,b,E(x),E(y) ，我們能計(jì)算出 E(ax+by)。原理很簡(jiǎn)單，因?yàn)椋?/p>
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
某個(gè)多項(xiàng)式的盲估
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 階多項(xiàng)式 P， 并且 Bob 可以隨機(jī)地選擇一個(gè)點(diǎn) s∈Fp ， Bob 期望知道 E(P(s))，這就是于 s 點(diǎn)對(duì) P 進(jìn)行評(píng)估的同態(tài)隱藏(HH)，做到這點(diǎn)有兩種簡(jiǎn)單的方式：
- Alice 發(fā)送 P 給 Bob，從而 Bob 可以自行計(jì)算 E(P(s))。
- Bob 發(fā)送 s 給 Alice；Alice計(jì)算 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.
然而，在盲估問(wèn)題中，我們希望 Bob 在不了解 P 的情況下了解 E(P(s)) – 這將排除第一種選擇； 更重要的是，我們不希望 Alice 了解 s ，這將排除第二種選擇 [1]。
- [1] 我們不想將 P 發(fā)送給 Bob 的主要原因是，僅僅是因?yàn)樗罅恕?strong>(d+1)個(gè)元素，比如，現(xiàn)有的Zcash協(xié)議中 d 的值將近2百萬(wàn)；它最終會(huì)與“簡(jiǎn)潔的” SNARKs 協(xié)同工作。事實(shí)上，上面Bob發(fā)送給Alice的匿數(shù)序列也一樣長(zhǎng)，但是這個(gè)序列能夠作為系統(tǒng)的參數(shù)硬編碼到系統(tǒng)中，而每次SNARK證明時(shí)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，我們可以像下面一樣進(jìn)行盲估。
- Bob發(fā)送匿數(shù) E(1),E(s),…,E(s^d) 給Alice。
- Alice根據(jù)送達(dá)的匿數(shù)計(jì)算 E(P(s)) ，并且發(fā)送 E(P(s)) 給Bob。(Alice能夠利用E對(duì)線性組合的支持進(jìn)行計(jì)算，并且 P(s) 就是 1,s,...,s^d 的線性組合。)
可以注意到，因?yàn)橹挥心鋽?shù)被發(fā)送，Alice不會(huì)了解 s[2],Bob也不會(huì)了解 P.
- [2] 事實(shí)上，隱藏特性僅僅保證了 s 不能由 E(s) 反推得到，但在這里，我們想強(qiáng)調(diào)它同樣不可能由序列 E(s),…,E(s^d) 反推得到，雖然這個(gè)序列包涵了很多 s 的信息。這樣的判斷緣于 Diffie-Hellman 假設(shè)，這個(gè)假設(shè)論證了 SNARK 的安全性。
WHY IS THIS USEFUL?
為什么這是一個(gè)有用的方法
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。 大致的解釋是，驗(yàn)證器在內(nèi)部有一個(gè) “正確的”多項(xiàng)式，它需要檢查是否證明方知道這件事。這將使得證明方可以在一個(gè)他們不知道的隨機(jī)的點(diǎn)上驗(yàn)證他們是否知道這個(gè)多項(xiàng)式，并保證證明方的多項(xiàng)式如果不正確，他有更高的幾率得到一個(gè)報(bào)錯(cuò)。這種做法依賴于Schwartz-Zippel引理說(shuō)明，即“不同多項(xiàng)式在大多數(shù)點(diǎn)是相同的”。
譯者總結(jié)
