原文出自：https://blog.z.cash/snark-explain/
作者：Ariel Gabizon
譯者：Matter實驗室

Constructions of zk-SNARKs involve a careful combination of several ingredients; fully understanding how these ingredients all work together can take a while.

zk-SNARKs 的結(jié)構(gòu)包含許多元素的精妙組合泞辐；完全了解這些元素需要花費一些時間裂允。

If I had to choose one ingredient whose role is most prominent, it would be what I will call here Homomorphic Hiding(HH) [1]. In this post we explain what an HH is, and then give an example of why it is useful and how it is constructed.

[1] Homomorphic hiding is not a term formally used in cryptography, and is introduced here for didactic purposes. It is similar to but weaker than the well-known notion of a computationally hiding commitment. The difference is that an HH is a deterministic function of the input, whereas a commitment uses additional randomness. As a consequence, HHs essentially ”hide most x’s” whereas commitments ”hide every x”.

如果你不得不選擇 一個最重要的元素沉颂，那么你可以把它稱為 同態(tài)隱藏 (HH) [1]。在這篇博文中，我們將解釋 HH 是什么，并解釋它為什么如此重要让蕾，同時闡述它的構(gòu)成涡戳。

• [1] 同態(tài)隱藏并不是密碼學(xué)中常用的短語结蟋，在這里出于解釋說明的目的被引入。它與知名的短語“可計算的隱藏承諾”意思相近渔彰，但沒有這個短語語氣強烈嵌屎。它們的不同點在于，HH 是由輸入決定的函數(shù)恍涂，而承諾則使用了額外的隨機(jī)性宝惰。因此，HH 可以基本“隱藏絕大部分 x”再沧，而承諾則可以“隱藏每一個x”尼夺。

An HH E(x) of a number x is a function satisfying the following properties:

• For most x’s, given E(x) it is hard to find x.
• Different inputs lead to different outputs – so if x≠y, then E(x)≠E(y).
• If someone knows E(x) and E(y), they can generate the HH of arithmetic expressions in x and y. For example, they can compute E(x+y) from E(x) and E(y).

具有HH屬性 E(x) 是一個關(guān)于 x 的函數(shù)，它有如下特點：

• 對于大部分的 x，給定某個 E(x) 通常很難求解出 x.
• 不同輸入將會得到不同輸出 – 因此汞斧，如果 x≠y夜郁，則 E(x)≠E(y)。
• 如果某人知道了 E(x) 和 E(y)粘勒，則他可以生成x 和 y的算術(shù)表達(dá)式的 HH 函數(shù)竞端。比如，他們可以使用 E(x) 和 E(y) 來計算 E(x+y)庙睡。

Here’s a toy example of why HH is useful for Zero-Knowledge proofs: Suppose Alice wants to prove to Bob she knows numbers x,y such that x+y=7 (Of course, it’s not too exciting knowing such x,y, but this is a good example to explain the concept with).

1. Alice sends E(x) and E(y) to Bob.
2. Bob computes E(x+y) from these values (which he is able to do since E is an HH).
3. Bob also computes E(7), and now checks whether E(x+y)=E(7). He accepts Alice’s proof only if equality holds.

以下是關(guān)于為什么 HH 可以用于零知識證明的一個簡單的例子： 假設(shè) Alice 需要向 Bob 證明她知道數(shù)字 x,y 滿足 x+y=7 事富。(當(dāng)然，知道 x,y, 的具體數(shù)字并不會令人非常激動乘陪，但這是解釋這個概念非常簡潔的例子)统台。

1. Alice 發(fā)送 E(x) 和 E(y) 的值給 Bob。
2. Bob 從得到的數(shù)值中計算出 E(x+y) 的值 (因為 E 是一個 HH)啡邑。
3. Bob 同樣計算出了 E(7), 并檢查 E(x+y)=E(7)等式是否成立贱勃。只有等式成立，他才認(rèn)可Alice的證明谤逼。

As different inputs are mapped by E to different hidings, Bob indeed accepts the proof only if Alice sent hidings of x,y such that x+y=7. On the other hand, Bob does not learn x and y, as he just has access to their hidings [2].

[2] Bob does learn some information about x and y. For example, he can choose a random x’, and check whether x=x’ by computing E(x’). For this reason the above protocol is not really a Zero-Knowledge protocol, and is only used here for explanatory purposes. In fact, as we shall see in later posts, HH is ultimately used in snarks to conceal verifier challenges rather than prover secrets.

由于不同的輸入被 E 映射到了不同的匿數(shù)贵扰，Bob只有在Alice發(fā)送滿足x+y=7這個條件的 x,y 的匿數(shù)時才確切的認(rèn)可這個證明。 另一方面流部，Bob 并不知道 x 和 y的值戚绕，因為他只獲得了他們的匿數(shù) [2]。

• • [2]Bob 確實可以獲取與 x 和 y 相關(guān)的一些信息枝冀。比如舞丛，他可以選擇一個隨機(jī)的 x'，并通過計算 E(x') 的方式檢查 x=x' 等式是否成立果漾。出于這種原因球切，上面的協(xié)議并不是一個真正的零知識證明協(xié)議，它僅僅用于解釋跨晴。事實上欧聘，我們會在以后的文章中看到，HH 最終用在 snark 隱藏驗證者挑戰(zhàn)數(shù)時使用端盆，而不在隱藏證明者秘密時使用。

Now let’s see an example of how such hidings are constructed. We actually cannot construct them for regular integers with regular addition, but need to look at finite groups:

現(xiàn)在讓我們從一個例子中了解匿數(shù)是如何構(gòu)成的费封。事實上焕妙，我們不能使用常規(guī)的整數(shù)和常規(guī)的加法來構(gòu)造他們，因此弓摘，我們需要看看“有限群”：

Let n be some integer. When we write A mod n for an integer A, we mean taking the remainder of A after dividing by n. For example, 9 mod 7=2 and 13 mod 12=1. We can use the mod n operation to define an addition operation on the numbers {0,…,n?1}: We do regular addition but then apply (mod n) on the result to get back a number in the range {0,…,n?1}. We sometimes write (mod n) on the right to clarify we are using this type of addition. For example, 2+3=1(mod4). We call the set of elements {0,…,n?1} together with this addition operation the group Z(+,n).

假設(shè) n 是一個整數(shù)焚鹊。當(dāng)我們對整數(shù) A 寫下 A mod n 時，我們的意思是在 A 除以 n 后取余數(shù)韧献。比如 9 mod 7=2 和 13 mod 12=1末患。 我們可以使用 mod n 在正數(shù)集 {0,…,n?1} 上定義加法操作：我們在做常規(guī)加法后研叫，對結(jié)果應(yīng)用(mod n)來獲取一個在{0,...,n-1}范圍中的數(shù)。 我們有時會在右邊寫下 (modn) 來聲明我們使用的是此種類型的加法璧针。 比如嚷炉，2+3=1(mod4)。 我們稱帶有這種加法操作的集合 {0,…,n?1} 為 Z(+,n)探橱。

For a prime p, we can use the mod p operation to also define a multiplication operation over the numbers {1,…,p?1} in a way that the multiplication result is also always in the set {1,…,p?1} – by performing regular multiplication of integers, and then taking the result mod p. [3] For example, 2?4=1 (mod 7).

[3]When p is not a prime it is problematic to define multiplication this way. One issue is that the multiplication result can be zero even when both arguments are not zero. For example when p=4, we can get 2*2=0 (mod 4).

對于一個質(zhì)數(shù) p申屹，我們可以使用 mod p 在集合{1,....,p-1}上定義一個乘法操作，這樣操作的結(jié)果也會在集合 {1,…,p?1} 中 —— 通過對整數(shù)的常規(guī)乘法隧膏，并對結(jié)果進(jìn)行mod p操作哗讥。[3] 比如，2?4=1 (mod 7) .

• • [3]當(dāng) p 不是質(zhì)數(shù)時胞枕，以上的方式定義乘法是有問題的杆煞。其中的一個問題是即便兩個參數(shù)都不為零，乘積的結(jié)果仍可能為零腐泻。比如當(dāng) p = 4 是决乎，我們可以得到 2*2=0 (mod 4)

This set of elements together with this operation is referred to as the group Z(*,p). Z(*,p) has the following useful properties:

這樣的集合和操作一起被稱為群 Z(*,p)。 Z(*,p)具有以下這些有用的屬性：

1. It is a cyclic group; which means that there is some element g in Z(*,p) called a generator such that all elements of Z(*,p) can be written as gaga for some a in {0,..,p?2}, where we define g^0=1.
2. The discrete logarithm problem is believed to be hard in Z(*,p). This means that, when p is large, given an element h in Z(*,p) it is difficult to find the integer a in 0,..,p?2 such that g^a=h (mod p).
3. As ”exponents add up when elements are multiplied”, we have for a,b in 0,..,p?2 ; ( g^a )?( g^b )=g^(a+b (mod p?1)).

1. 它是一個循環(huán)群贫悄；這意味著瑞驱，Z(*,p)其中有一些被稱為生成器(generator)的元素g，當(dāng)我們定義g^0=1時窄坦，Z(*,p)所有的元素都能被寫成g^a的形式唤反，其中a是{0,...,p-2}的元素 。
2. 離散對數(shù)問題在 Z(*,p) 中被認(rèn)為是困難的鸭津。這意味著彤侍，當(dāng) p 值較大時，給定一個在Z(*,p)中的元素h逆趋，很難在 0,..,p?2 中找到整數(shù) a 盏阶，滿足 g^a=h (mod p)。
3. 由于 “元素相乘時它們的指數(shù)會相加”闻书，對于來自0,..,p-2的a,b名斟，等式( g^a )?( g^b )=g^( a+b (mod p-2) )成立。

Using these properties, we now construct an HH that ”supports addition” – meaning that E(x+y) is computable from E(x) and E(y). We assume the input x of E is from Z(p?1), so it is in the range {0,…,p?2}. We define E(x)=g^x for each such x, and claim that E is an HH: The first property implies that different x’s in Z(p?1) are mapped to different outputs. The second property implies that given E(x)=g^x it is hard to find x. Finally, using the third property, given E(x) and E(y) we can compute E(x+y) as E(x+y)=g^( x+y (mod p?1) )=( g^x )?( g^y )=E(x)?E(y).

使用這些特性魄眉，我們現(xiàn)在建立一個 “支持加法” 的 HH – 這意味著 E(x+y) 可以由 E(x) 和 E(y) 計算得到砰盐。 我們假設(shè) E 的輸入 x 來自 Z(*,p-1)，因此它的范圍是 {0,..,p?2}坑律。 我們對每個這樣的 x 定義 E(x)=g^x 岩梳，并稱這樣的 E 是一個 HH： 第一個特性表明，在 Z(*,p?1) 中的不同 x 會映射到不同的輸出。 第二個特性表明冀值，給定一個 E(x)=g^x 也物，很難計算出 x。 最終列疗，使用第三個特性滑蚯，對于給定的 E(x) 和 E(y)，我們可以計算出 E(x+y) 作彤，因為 E(x+y) as E(x+y)=g^( x+y (mod p?1) )=( g^x )?( g^y )=E(x)?E(y)膘魄。

譯者總結(jié)

數(shù)學(xué)關(guān)系

模型