零知识证明-Intro： 从 Schnorr 协议到NIZK

[SpaceStation09]

提到零知识证明的机制，就不得不提到一个简洁的交互协议Schnorr协议。其本质是一种零知识的技术，i.e. Prover 声明自己知道一个密钥 x 的值，通过使用Schnorr 协议，可以在不向Verifier揭露x的值的前提下，向Verifier证明自己确实知道x的值。

Schnorr 机制由德国数学家和密码学家 Claus-Peter Schnorr 在 1990 年提出，是一种基于离散对数难题的知识证明机制。

Schnorr 协议涉及到的技术主要有：

• 哈希函数
• 椭圆曲线的离散对数难题：已知，椭圆曲线E 和其上的一个点G，随机选择一个整数d，容易计算 Q = d * G， 但是给定点 Q 和 G，很难计算出其对应的d。

[SpaceStation09]

初见 Schnorr 协议

Alice 有一个 secret a,我们可以把它当作一个“私钥”，然后我们把这个“私钥” 投射到一个椭圆曲线上的一个点a*G上 （简写为aG）。我们让这个“私钥”所对应的“公钥” $$PK = aG$$ ,此时, 我们有:

• sk = a
• PK = aG

Schnorr 协议的流程图如下所示，其是一个交互式的零知识证明协议：

• Alice 首先产生一个随机数 r，这个随机数是用来保护我们的私钥不会被 Bob抽取出来。这个随机数，我们也要投射到椭圆曲线上后才能发给Bob，这使得r 也不会被计算出来。
• Bob 自己也生成一个挑战随机数 c。
• Alice 根据 c ,r ,a 计算出一个“签名”， $s=r+c*a$ ，然后把 z 发给Bob。
• Bob 通过验证以下等式来验证“签名”的有效性: $s*G = R + c*PK$ 。

为什么以上式子的验证，可以证明 Alice 确实拥有secret a呢？

1. 在正常情况下，有 $s = r +c*a$, 然后，我们要计算s*G 时，实际得到的答案应该是： $(r+c * a) * G = r * G + c* a*G = R + c * PK$ 。此时，理所当然的，推导出了上述式子的成立。
2. 假如Alice 实际并没有secret a时，她伪造了一个a', 然后刻意使用了一个 r’ (而不是随机数生成），她想要骗过Bob的话，就必须使得 $r+c*a = r' + c *a'$ 成立。c是Bob提供的一个随机数，所以对Alice来说，这应该是个变量。那么，我们就可以这么理解，Alice 想要作弊的话她需要做到，能找到一组(r', a')使得这个多项式等式成立： $r+a*x = r' +a'*x$ 。根据 Schwatz-Zippel 定理，极大概率上 r = r', a = a'都成立，那么说明，Alice 在不知道 'c' 的情况下，很难找到这样一组(r', a') 。

[SpaceStation09]

延伸： ECDSA签名攻击

使用交互的方式定义一下类似ECDSA的认证方案：

攻击方式： 如果，Alice在交互过程中两次使用同一个r, 那么Alice的私钥a可以被计算出来：

• Bob 发送两个不同的c（我们标记为c 和c'），来得到s和s'。
• 此时，我们可以计算出r：

$$s = (c+a*e)/r   s' = (c' + a*e)/r$$

$$ => s' - s = ((c' + a * e) - (c + a*e)) / r = (c' - c) / r$$

$$ => r = (s' -s) / (c' -c) $$

• 计算出 r 后，接着 Alice的私钥 a 也可以被计算出来了：

$$a = (s*r - c) / e$$

[SpaceStation09]

NIZK: Random Oracle Model (ROM)

通过随机数挑战是交互式零知识证明的信任根基。

当我们由交互式零知识证明转向NIZK时，我们需要用别的方式来填补这一信任根基。这个方法就是，引入第三方。引入第三方的方式有几种，这一部分将描述第一种：Random Oracle Model。

Intro: 3-Step Schnorr => 1-Step Schnorr

我们可以将一个3步的交互式Schnorr协议转变为1步的：

• 将Bob生成挑战随机数c的方式转化为： c = Hash(PK, R)

• 在产生承诺R 之前，Alice 无法预测 c的值，即使c的值是Alice产生的。
• 由于hash函数是单向的（密码学安全的hash函数），我们也无需担心Alice先选择一个c的值，然后反推出R的值。

这个方案看起来似乎有点眼熟？对的，再改进一下，我们就得到了“数字签名”方案。从zk的角度看，我们用的是：c = H(m, R)。

Fiat-Shamir 变换

像以上这样，Prover通过用一个函数（常常是一个hash函数）自己计算挑战随机数，来替代交互式地由Verifier生成挑战随机数的理念，就是Fiat-Shamir 变换。

Random Oracle Model

Random Oracle 的运行就是一个黑盒，其内部是一个完全随机的函数，但对于相同的输入，他输出的结果将是一样的；如果输入不同，那么其输出将是两个毫无关系的，完全不同的结果。

我们可以将前面提到的Fiat-Shamir 变换中的函数替换为这个Random Oracle, be like:

我们对Random Oracle的想象非常美好，因为这个Oracle 就像是一个“黑魔法”在运行，他拥有真正的随机性，他每次的运算结果，都是一个具有一致性分布的真随机数。但，真正的随机预言机并不存在，所以，我们选择还是使用密码学安全的Hash方法来充当一个伪随机预言机。那么，当我们使用这一套方案时，我们实际就是有一个安全假设的： 一个密码学安全的hash函数可以近似地模拟一个随机数预言机。

[SpaceStation09]

小心：Fiat-Shamir 变换的安全隐患

之前看到过SlowMist有关FS变换的冰心漏洞的探索文章，了解到，现在不少大家常用的zk库在处理FS变换时，使用了weak F·S transform，导致了安全问题。

Schnorr可以在有限域 或者 椭圆曲线上实现，其spec基本相同，接下来的论证以椭圆曲线为例。
在交互式Schnorr协议中，我们的公式是这样：

• Alice的sk是a, pk 是A。
• Alice 生成随机数 v, 及其对应的commitment V = v*G。
• Bob 生成挑战随机数c。
• Alice 计算：r = v + a*c 并发送给Bob。
• Bob验证： r*G ?= V + A * c

NIZK:

• Strong F·S transform: c = H(G || V || A || UserID || OtherInfo)
• Weak F·S transform: c = H( G || V)
  他们的主要区别在于，在Weak F·S transform中，c的计算并没有加入A的部分。
  当大家使用Weak F·S transform时，我们可以在不知情 sk的情况下，重新构造(A, r)使得Verifier 依然验证成功：

1. 生成随机数: r, v。
2. 计算 $a' = (r -v) / c$ 。 此时，我们可以这样计算的原因是，我们的c的生成，并不要求A的值。
3. 计算得到 $A = a'*G = (r - v)/c * G$
4. 代入验证方程：
   $$V+A*c = V + (r-v) /c * c *G = v*G + (r -v)*G = r*G$$

可以看出，我们在不知道实际的sk: a的情况下，也构造出了一对(A, r) 使得Bob的验证能够成功。

报告冰心漏洞的具体论文在这：

• Weak Fiat-Shamir Attacks on Modern Proof Systems

Implementation Survey Result

文章中展示了他们调研的zk库中，有关Weak F·S transform的使用情况，如下：

♦ = has been fixed as of May 15, 2023.

[SpaceStation09]

NIZK: Common Reference String (CRS)

前面一个section提到：

当我们由交互式零知识证明转向NIZK时，我们需要用别的方式来填补这一信任根基。这个方法就是，引入第三方。

除了前面提到的ROM外，我们还有一个方案那就是公共参考串(Common Reference String)。简单来说，在CRS这个方案中，在Prover 和 Verifier 开始交互前，可信的参与方会生成一个公共字符串CRS，这个字符串可以被所有参与方访问到，Prover在CRS的参与下，生成一个证明，并将其发给Verifier，然后 Verifier可以结合CRS完成对证明的验证。

[顺带一提： 我们现在常用的一些zk的方案，也算是基于CRS演化出来的（e.g. SRS）， 比如groth16， plonk。 我们常提到的trusted setup的过程，其中就包含生成CRS的过程。]

[SpaceStation09]

从汉密尔顿环路问题理解如何使用CRS构造ZKP

ZK-HAM

1. 首先，我们先构造一个三步交互的协议，用来帮助Prover 向Verifier 证明，其知道某图G上存在一条汉密尔顿环路：

   • 公共输入：图G，一个有6个顶点的图，可以用一个 6*6 的邻接矩阵表示。

   • 秘密输入：G中的汉密尔顿回路C。

   • 第一步：Alice 随机选择一个置换：Perm()，然后我们得到一个新的图G' = Perm(G)。置换后的图G 和G'是同构的，如下图：
     

   • 第二步：Alice 将G'的邻接矩阵的每一个单元加密，产生一个新的矩阵commit(G')发给Bob。相当于 Bob收到了一个每一个单元都被加密的 6*6的邻接矩阵，他无法直接获取图的信息。

   • 第三步：Bob随机选择 b in {0, 1}对Alice 进行挑战。

   • 第四步， Alice 根据b的值份情况进行操作：

     • 如果b 为0， Alice 给Bob发送置换函数Perm()，并且reveal G'，至此，Bob可以核验Perm() 是否正确。
     • 如果b 为1，Alice 就reveal G'中的汉密尔顿环路C'，此时Bob可以验证C'是否是一个汉密尔顿环路，就像下图：
     

     图来自sec-bit的zkp-intro资料

   至此，这个协议的步骤已经描述完毕。如果这个协议只运行一遍，Alice 是有概率可以作弊然后蒙骗过Bob的验证的，就像我们最初了解零知识证明时，都会看到的阿里巴巴和盗贼的例子，或者，猜红蓝球的例子一样。如果，我们将协议重复很多遍，那么Alice 作弊成功的概率将指数级减小。

2. 将上面这个三步交互的协议，进行一点变形，这个变形将基于这个一个原理：如果一个仅包含环路的子图C是图G的子图，C<= G 那么说明G包含汉密尔顿环路。<=> 一个!G(G的补集)是!C的子图， i.e. !G <= !C。这样，我们可以设计如下的协议：

   • 公共输入：图G，一个有6个顶点的图，可以用一个 6*6 的邻接矩阵表示。
   • 秘密输入：G中的汉密尔顿回路C。
   • 第一步：Alice 随机选择一个置换：Perm()，使用这个置换，得到一个新的图C' = Perm(C)。Alice 此时用邻接矩阵的方式描述图C‘，然后对C'的每一个单位进行加密后，得到Commit(C')并发送给Bob。如下图：

   

   • 第二步：Bob 选择 b in {0, 1}进行挑战。
   • 第三步：Alice 根据b的值份情况进行操作：
     • 如果b 为0，Alice 给Bob reveal 完整的C'，然后Bob验证C‘是否是一个汉密尔顿环路子图。
     • 如果b 为1，Alice 给Bob发送置换函数Perm()，同时揭露 G' = Perm(G)中所有值为0的单元位置所对应的C'中的单元的值，验证其是否都为0。本质此处就是在验证!G' <= !C'。

   至此，就是这个协议的全部内容， 我们可以发现，在第一步中，Alice 不再是发送与G相关的内容。这样，进一步思考，我们是否可以将这个承诺改成改成一个由可信第三方事先准备好的比特串（一个正确的环路子图）。如此一来，Bob也不用发送b = 0来挑战了，最后，这个协议就可以简化为一个一步的交互协议，进而有望实现NIZK。如下图：

   

   图来自sec-bit的zkp-intro资料

此时，这个协议还并不是NIZK，因为这个可信第三方提供的字符串，并不可以对Bob公开，因为知晓的话，Bob就可以计算出真正的环路C，这就没有零知识性了。

[SpaceStation09]

Hidden Bits

所谓Hidden Bits就是在上一节中，提到的一串随机产生的比特值。Alice 可以完全知道这串比特的值，并可以有选择的揭露其中某个或某些比特给Bob。
我们可以通过 HB来尝试进一步修改上面的协议：假设现在有一个可信的第三方产生了一个随机的环路子图C‘, 并将其编码成了邻接矩阵的比特串作为Hidden Bits。这个比特串的长度就是V*V（V为城市的数量）。剩下的，就像上面一节中最后的图一样，完成协议步骤，此处主要描述几点：

• Alice 产生的证明主要包括两个部分：
  • 置换函数： Perm()。
  • G‘的邻接矩阵中所有值为0的单元位置所对应的C'邻接矩阵中单元的值。这就是Alice要在Hidden Bits中为Bob 揭露的值。
• Bob的验证环节，主要也是两件事：
  • 置换函数Perm() 是否是一个valid的置换。
  • 验证!G' ?<= !C'，也就是说，Alice揭露给Bob的值是否均为0。

完备性： Alice 如果没有作弊，通过Bob的验证是完全没有问题的。
可靠性：经过Bob的验证，Alice揭露给Bob的值均为0，且置换函数是没有问题的（图G 与G', C与C'同构），已经可以说明!G <= !C，那么这就等同于，G >= C, 图G一定包含一个汉密尔顿回路。

我们在这里做一个假设，假设：这个HB 并不是一个可信的第三方产生的，那么，它几乎可以帮双边作弊。Alice 如果让HB的值全部为0，那么其毫无疑问可以通过Bob的验证。相反地，如果Bob 可以直接从第三方那拿到HB，那么他可以直接计算出C的值（知道C' 和 Perm())。这样，这个协议实在太依赖这个第三方的honest程度了。

再次升级！

第一个升级是让隐藏比特串变成一个「一致性均匀分布」的随机的隐藏比特串，是一个看起来相当随机的比特串，而不是一个刻意摆放好的哈密尔顿子图。接下来，如何让这样一个相当随机的比特串中能有一个汉密尔顿环路子图的邻接矩阵的比特串呢？答案是：让这个随机比特串足够长，长到足够找到一个随机的汉密尔顿环路为止。

但，这样操作，找到一个随机的汉密尔顿环路的概率实在不高，那么我们可以有一些优化操作，进而提高验证与证明生成的效率：参考secbit：云中“秘密”：构建非交互式零知识证明 。本篇笔记，不打算做过多详细描述。

解放隐藏特性！！

接下来，我们要真正解放Hidden Bits 让它转化为Common Reference String (CRS)。我们需要一个密码学工具： 陷门置换(Trapdoor Permutation)。
【名词解释】：所谓陷门置换是指，我们现在有一个置换函数 $F(x) (x \in S)$。F(x)可以将x映射到集合S中的另一个元素y。同时F(x)具有单向性，我们很难通过y推导出x。但如果我们拥有陷门t， 那么我们就可以反向计算 $F^{ -1}(t,y) = x$ 。此外，陷门置换还可以匹配一个Hardcore Predicate， $h(x): \lbrace 0,1 \rbrace ^\lambda$ 它可以根据集合S中的元素产生一个一致性分布的比特串。

那么有了这个陷门置换，我们就可以这样升级我们的协议：

• 首先有一个可信第三方生成一个CRS
• Alice 生成证明的流程：
  • Alice 随机生成一个Trapdoor Permutation 确定了F(x), h, t。
  • 根据CRS中的每一个 $y_i$ 以及陷门，计算出其对应的原象 $x_i$ 。
  • 根据 x，和h(x)计算出HB： $b_i = h(x_i)$ 。此处注意：我们不可以用y直接作为计算HB的原象，否则，Bob就可以根据CRS直接计算出HB了。
  • Alice 想要揭露HB中的哪些位置的bit，就给Bob发送对应位置的x就可以了。例如，想要揭露的位置集合为 $\lbrace r_1,r_2, ..., r_l \rbrace$ 那么，她就要分享 $\lbrace x_{r_1},x_{r_2}, ..., x_{r_l} \rbrace$ ，附带还需要给Bob 发送，F(x)和 h(x)。
• Bob 验证的操作：
  • 确认F(x)和 h(x)是否是valid。
  • 根据h(x)计算 HB中 Alice希望他看到的bit。到这一步，我们就实现了最初HB模型的基本setup

这一套就是FLS范式，将HB-NIZK 转化为标准的NIZK。

回归现实

在我们的实际应用中，找到一个完全符合理想的Trapdoor Permutation，其实是很难的。所谓的理想化是指，每一个 n-bit 字符串都能唯一变成另一个 n-bit 字符串，并且不会出现「多对一」的映射关系。Alice 需要随机抽样一个 Index，发给 Bob，然后 Bob 要能检查出这个 Index 所对应的F(x) 是否是一个「完美」的置换。问题来了，怎么 Bob 怎么能在多项式时间内检查出来呢？如果 Bob 不能检查，那么 Alice 就可以抽样一个不完美的 Permutation（比如一个「多对一」的函数），从而可能作弊。

寻找理想的Trapdoor Permutation的路很长，各路密码学家都在努力，2018年，一个由Ran Canetti 与 Amit Lichtenberg 提出的 Certifiable Injective Trapdoor Function 满足路FLS变换的要求。

这些年来，密码学家们发明的 NIZK 方案有很多，但 Hidden Bits 方法是目前已知唯一的办法，(1) 基于「一致性分布」的共享 CRS，(2) 实现任意 NP 语言的 NIZK Proofs（Not Arguments）。

[SpaceStation09]

参考

[1] 云中秘密：构建非交互是零知识证明
[2] 随机「挑战」
[3] SlowMist: Exploring the Frozen Heart Vulnerability in the Fiat-Shamir Scheme