零知识证明 SNARKs 第1部分：同态隐藏

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 的结构包含许多元素的精妙组合；完全了解这些元素需要花费一些时间。

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”.

如果你不得不选择 一个最重要的元素，那么你可以把它称为 同态隐藏 (HH) [1]。在这篇博文中，我们将解释 HH
是什么，并解释它为什么如此重要，同时阐述它的构成。

* [1]
同态隐藏并不是密码学中常用的短语，在这里出于解释说明的目的被引入。它与知名的短语“可计算的隐藏承诺”意思相近，但没有这个短语语气强烈。它们的不同点在于，HH
是由输入决定的函数，而承诺则使用了额外的随机性。因此，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 inx and y. For example, they can compute E(x+y) from E(x) and E(y).
具有HH属性 E(x) 是一个关于 x 的函数，它有如下特点：

* 对于大部分的 x，给定某个 E(x) 通常很难求解出 x.
* 不同输入将会得到不同输出 – 因此，如果 x≠y，则 E(x)≠E(y)。
* 如果某人知道了 E(x) 和 E(y)，则他可以生成x 和 y的算术表达式的 HH 函数。比如，他们可以使用 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 numbersx,y such that x+y=7 (Of course,
it’s not too exciting knowing suchx,y, but this is a good example to explain
the concept with).

* Alice sends E(x) and E(y) to Bob.
* Bob computes E(x+y) from these values (which he is able to do since E is an
HH).
* Bob also computes E(7), and now checks whether E(x+y)=E(7). He accepts
Alice’s proof only if equality holds.
以下是关于为什么 HH 可以用于零知识证明的一个简单的例子： 假设 Alice 需要向 Bob 证明她知道数字 x,y 满足 x+y=7 。(当然，知道
x,y, 的具体数字并不会令人非常激动，但这是解释这个概念非常简洁的例子)。

* Alice 发送 E(x) 和 E(y) 的值给 Bob。
* Bob 从得到的数值中计算出 E(x+y) 的值 (因为 E 是一个 HH)。
* Bob 同样计算出了 E(7), 并检查 E(x+y)=E(7)等式是否成立。只有等式成立，他才认可Alice的证明。
As different inputs are mapped by E to different hidings, Bob indeed accepts
the proof only if Alice sent hidings ofx,y such that x+y=7. On the other hand,
Bob does not learnx 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 映射到了不同的匿数，Bob只有在Alice发送满足x+y=7这个条件的 x,y 的匿数时才确切的认可这个证明。 另一方面，Bob
并不知道x 和 y的值，因为他只获得了他们的匿数 [2]。

*
* [2]Bob 确实可以获取与 x 和 y 相关的一些信息。比如，他可以选择一个随机的 x'，并通过计算 E(x') 的方式检查 x=x'
等式是否成立。出于这种原因，上面的协议并不是一个真正的零知识证明协议，它仅仅用于解释。事实上，我们会在以后的文章中看到，HH 最终用在 snark
隐藏验证者挑战数时使用，而不在隐藏证明者秘密时使用。
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:

现在让我们从一个例子中了解匿数是如何构成的。事实上，我们不能使用常规的整数和常规的加法来构造他们，因此，我们需要看看“有限群”：

Let n be some integer. When we write A mod n for an integer A, we mean taking
the remainder ofA after dividing by n. For example, 9 mod 7=2 and 13 mod 12=1.
We can use themod 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).

假设 n 是一个整数。当我们对整数 A 写下 A mod n 时，我们的意思是在 A 除以 n 后取余数。比如 9 mod 7=2 和 13 mod 12=1
。 我们可以使用mod n 在正数集 {0,…,n−1} 上定义加法操作：我们在做常规加法后，对结果应用(mod n)来获取一个在{0,...,n-1}
范围中的数。 我们有时会在右边写下(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 resultmod 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).

对于一个质数 p，我们可以使用 mod p 在集合{1,....,p-1}上定义一个乘法操作，这样操作的结果也会在集合 {1,…,p−1} 中 ——
通过对整数的常规乘法，并对结果进行mod p操作。[3] 比如，2⋅4=1 (mod 7) .

*
* [3]当 p 不是质数时，以上的方式定义乘法是有问题的。其中的一个问题是即便两个参数都不为零，乘积的结果仍可能为零。比如当 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)具有以下这些有用的属性：

* It is a cyclic group; which means that there is some element g in Z(*,p)
called a generator such that all elements ofZ(*,p) can be written as gaga for
somea in {0,..,p−2}, where we define g^0=1.
* The discrete logarithm problem is believed to be hard in Z(*,p). This means
that, when p is large, given an elementh in Z(*,p) it is difficult to find the
integera in 0,..,p−2 such that g^a=h (mod p).
* 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)).
* 它是一个循环群；这意味着，Z(*,p)其中有一些被称为生成器(generator)的元素g，当我们定义g^0=1时，Z(*,p)所有的元素都能被写成
g^a的形式，其中a是{0,...,p-2}的元素 。
* 离散对数问题在 Z(*,p) 中被认为是困难的。这意味着，当 p 值较大时，给定一个在Z(*,p)中的元素h，很难在 0,..,p−2 中找到整数 a
，满足g^a=h (mod p)。
* 由于 “元素相乘时它们的指数会相加”，对于来自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 thatE(x+y) is computable from E(x) and E(y). We assume the input x of E
is fromZ(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).

使用这些特性，我们现在建立一个 “支持加法” 的 HH – 这意味着 E(x+y) 可以由 E(x) 和 E(y) 计算得到。 我们假设 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)。

译者总结

 



数学关系



模型



 

• « 上一篇：Python机器学习资源菜单，选库找工具不愁，GitHub精选列表都在这里了
• » 下一篇：注册免费使用腾讯云企业邮箱