SNARKs 系列：同态隐藏(进阶)

警惕，前方数学高能....

同态隐藏，英文缩写为 HH ,本文意在解释 HH 是什么，它的应用实例以及构建过程

参数为 x 的 HH 函数 E(x) 满足以下条件：
1）对于绝大多数的 x,在给定 E(x)的情况下难以找到 x 
2)不同的输入对应不同的输出 ，即如果 x $\neq$ y,那么 E(x) $\neq$ E(y)
3)如果知道 E(x)和 E(y),那么可以生成 x 和 y 的算术表达式的同态隐藏，即可基于 E(x)和E(y)来计算 E(x+y)

举个例子来说明 HH 在零知识证明系统中的作用：
假设 Alice 想向 Bob 证明她知道数字 X,y 及
x+y=7
1)Alice 向 Bob 发送 E(x) 和 E(y)
2)Bob 基于这些值来计算 E(x+y)
3)Bob 同时计算E(7),并检查 E(x+y)是否等于 E(7) ，当且仅当等式成立时，Bob 才会接受 Alice 的证明

因为不同的输入由 E 映射到不同的加密隐藏 ,所以 Bob 只有在 Alice 发送 x,y 的加密隐藏以证明 x+y =7 。从另一方面来说，Bob 并不知道 x 和 y ,他只有访问 x 和 y 的加密隐藏的权限

我们不能用常规的整数构造它们，这里需要用到有限群：
设 n 为某整数 ，A mod n 意味着取 A 除以 n 之后所留的余数
以此可以使用 mod n 操作来定义数字的加法运算{0，.....,n-1} :
进行常规的加法操作过后，对其使用 mod n 操作，使结果在 {0,....,n-1} 区间

对于素数 p ，基于 mod p 操作可以在 {1,....p-1} 上定义乘法运算，使乘法结果总是在 {1,...,p-1}集合内 ，通过在常规的整数乘法结果添加 mod p,举个例子 2*4 =1 (mod 7)

附带操作运算符的元素集合统称为 $\mathbb{Z}^*_p$  组
$\mathbb{Z}^*_p$ 组有以下几种属性：
1.它是一个循环群，即在 $\mathbb{Z}^*_p$ 组中存在生成器 g,使得 $\mathbb{Z}^*_p$ 组中所有的元素都可以写作 $g^a$ ,其中 a 的取值范围落在 {0,...,p-2} 集合中，并且 $g^0$=1

2.当 p 取值很大时，给定 $\mathbb{Z}^*_p$ 中的元素 h ,很难找到落在 {0,...,p-2} 集合中的 a,使得 $g^a=h$(mod p)

3.落在集合 {0,....,p-2}中的元素 a,b ,
有 $g^a*g^b$ = $g^{a+b(mod p-1)}$

基于这些性质，可以构建支持加法的同态隐藏，即 E(X+y) 可由 E(x)和 E(y) 计算获得
假定 E(x) 的输入 x 来自 $\mathbb{Z}_{p-1}$,因此它的区间是 {0,....,p-2}
对于每个这样的 x ,定义 E(x)=$g^x$ ,并且声明
E 满足 HH 的性质：
第一个性质使 $\mathbb{Z}_{p-1}$中的 x 映射到不同的输出；
第二个性质使在给定 E(x)=$g^x$的情况下难以找到 x
最后使用第三个性质，给定 E(x) 和 E(y) ,可以计算出 E(x+y) ,因为 E(x+y)=$g^{x+y}$ = $g^x * g^y$ = $E(x)*E(y)$