MENU

零知识证明

• September 14, 2022 • Read: 1929 • 隐私计算

概念

零知识证明（Zero-Knowledge Proof，ZKP）技术指的是证明者能够在不向验证者提供任何有用信息的情况下，使炎症者相信某个论断是正确的，允许证明者（Prover）向验证者（Verifier）证明某项提议的真实性，但是却不必泄露出了“提议是真实的”之外的任何信息。

这听起来可能有些匪夷所思，我在不知道任何信息的情况下如何相信这个提议是真实的呢？下面有几个例子可以帮助理解：

我们应该都在社交媒体上收到一种“眼力挑战”，比如给了你一堆 9，并让你寻找到隐藏在其中的 6，可能找了很久还是没有找到，这时候寻找的人就会怀疑这些 9 中其实并没有 6。在这个事件中，“整个字符串中含有 6”就可以作为一个提议，寻找的人可以作为验证者，发送消息的人作为证明者（前提是他找到了 6）。那根据零知识证明的概念，证明者不能向验证者泄露除了“整个字符串中含有 6”意外的任何信息，也就是说证明者不能直接指给验证者说你看 6 就在这里，这样就泄露了 “6 所在的位置”这一信息，那么应该怎么办呢？证明者找到一张大于手机屏幕的纸，并且这张纸不会透光，也就是无法通过透过纸的图像来推测位置。证明者将这张纸切开一个仅能透过一个字符的小洞，然后将纸盖在手机上，并将其中的 6 透过纸上的小洞展现出来，这样一来验证者可以很清楚地看到确实是有 6 的，并且并没有得到其他的任何信息，这样就完成了对“整个字符串中含有 6”这一提议的零知识证明

有一个密码箱，在其上方有一个小缝，可以塞入纸张，我们假定这个缝是单向的，也就是只能进不能出，箱子其中的东西没有密码是不能取出来的。这时 Alice 和 Bob 说，我知道这个密码箱的密码，这时“Alice 知道密码箱的密码”就可以作为一个提议，那么如何证明呢？Bob 拿出一张纸条，在上面写上只有自己知道的秘密（至少保证 Alice 绝对不知道）并从小缝塞入密码箱中，然后背过身去，不能观看 Alice 打开箱子的过程。这时 Alice 输入密码打开箱子并取出字条，告知 Bob 纸条上的内容，如果 Alice 说对了，就说明他是知道箱子的密码的，而 Bob 也没有获得除了这个消息意外的任何信息，这样就完成了对“Alice知道密码箱的密码”这一提议的零知识证明

我们以 RSA 算法为例，如何证明“Alice 拥有私钥”这一提议呢？其实解决方法和例子二有一些相似，我们可以将 Bob 塞入密码箱的秘密看作未加密的信息，密码箱看作由公钥加密过后的密文，而私钥就是密码箱的密码，这样问题也就和例子二相同了，Alice 只需要将 Bob 发送过来的密文解密后再发送回去就可以证明自己是拥有私钥的

这个例子揭示了零知识证明其实是一种基于概率上的验证方法，它并不是百分百确定的，例子是这样的，有一堆纸片，他们有的写着 0，有的写着 1，除此之外毫无差别。Alice 从中取出两张纸片，一张写着 0，一张写着 1，他和 Bob 说，我这两张纸片上的数字是不同的，而“两张纸片上的数字是不同的”就作为一个提议。那如何证明呢？Bob 拿过两张纸片，但注意，他并不将纸片翻过来，也就是他不能够查看上面的数字。Bob 将纸片拿到身后，进行交换，他可以选择交换或不交换，操作完成后 Bob 再将纸片按交换顺序交还给 Alice，并让 Alice 回答自己是否交换过两张纸片，如果 Alice 答对了，就说明他是知道上面的内容的，上面的数字是不一样的（相同的数字交换怎么能看得出来呢？）。那这时候又出现一个问题，如果 Alice 是碰巧猜对的呢？他猜对的可能性有足足 $ \frac{1}{2} $ 呢！我们只需要多次重复进行这个操作，如果每次 Alice 都答对了，那么我们就可以确定，Alice 确实是选出了两张有不同数字的卡片，毕竟如果他不知道的话，进行多次实验每次都猜对的可能性可是非常小的（$ \lim\limits_{n \to \infty}(\frac{1}{2})^{n} = 0 $），从这里也可以看出，零知识证明是基于概率的

交互式零知识证明

上面的几个例子基本上都属于交互式零知识证明，证明者和验证者双方有多次交互，并且证明者需时刻在线来回应验证者的交互，交互式零知识证明分为以下几个阶段（以上方例子4为例）：

  1. 承诺阶段
    Alice 选出两个数字互不相同的纸片扣着放在桌子上，并作出“两张纸片的数字不同”的承诺

  2. 挑战阶段
    Bob 在不看到数字也不让 Alice 看到交换过程的情况下在身后偷偷交换/不交换两纸片位置，并向 Alice 提出自己有没有交换位置的挑战

  3. 回应挑战阶段
    Alice 给出位置是否交换过的答案

  4. 验证阶段
    Bob 查看 Alice 给出的答案是否正确

  5. 重复阶段
    重复阶段 2-4，发起足够多的挑战，直到 Bob 确信 Alice 选出的两张纸片确实是有不同数字的

非交互式零知识证明

上面提到过交互式零知识证明需要双方进行交互，且证明者需要一直在线，而这也是交互式的缺点，同时如果还有其他人也想参与，整个过程就会变得很复杂，这使得交互式零知识证明的应用场景存在一定的限制

zkSNARK（zero-knowledge Succinct Non-interactive Arguments of Knowledge）是一种用于实现非交互式零知识证明的技术，其技术特征基本都包含在了其命名中：

  • Succinct：最终生成的证明具有简洁性
  • Non-interactive：没有或者只有很少的交互
  • Arguments：证明者在不知道见证（Witness，只有证明者知道的私密数据）的情况下不可能构造出证明
  • zero-knowledge：验证着无法获取证明者的任何隐私信息

zkSNARK的构造过程如下图：

zkSNARK构造过程

  • 将所有要声明的内容的计算算法用算术电路来表示（所有 NP 问题都可以有效地转换为算术电路）
  • 将电路用 R1CS（Rank-1 Constraint System，一阶约束系统）描述
  • 将 R1CS 变换为 QAP（Quadratic Arithmetic Problem）形式。R1CS 与 QAP 形式上的区别是 QAP 使用多项式来代替点积运算，而它们的实现逻辑完全相同
  • QAP 还要变换成 LPCP（Linear Probabilistically Checkable Proof）。PCP 是指所有的 NP 问题都可以在多项式时间内通过概率验证的方法被证明。LPCP 是指任意一个多项式都可以通过随机验证多项式在几个点上的取值来确定多项式的每一项系数是否满足特定的要求
  • 还要通过一系列步骤将 LPCP 变换为 LIP（Linear Interactive Proof），再转变成 LNIP（Linear Non- interactive Proof），最后才能构建出一个 zkSNARK

通过 R1CS 来描述算术电路

我们假设 Alice 想要证明自己知道如下方程的解：$ x^{3} + x + 5 = ~out $，其中 $ ~out $ 是大家都知道的一个数，这里假设 $ ~out $ 为 35，而 $ x = 3 $ 是这个方程的解。

我们可以写出如下一个程序：

def qeval(x): 
    y = x ** 3
    return x + y + 5

该方程的算术电路如下所示

方程的算术电路

拍平

第一步是“扁平化”过程，我们将可能包含任意复杂语句和表达式的原始代码转换为具有两种形式的语句序列：$ x = y $ 或 $ x = y (op) z $ 形式的等式，其中 $ op $ 可以是加减乘除运算符中的一种。我们可以将这些语句中的每一个都视为电路中的逻辑门。上述代码的展平过程结果如下：

sym_1 = x * x
y = sym_1 * x
sym_2 = y + x
~out = sym_2 + 5

转化为三向量组

接下来需要将算术电路用 R1CS 来描述。R1CS是一个由三个向量 $ (a, b, c) $ 组成的序列，还有一个解向量 $ s $，$ s $ 必须满足 $ s • a \times s • b - s • c = 0 $ 这个约束，其中“•”表示向量的内积运算。这里的解向量 $ s $ 就是见证（Witness）。

随后 Alice 需要将每个逻辑门（拍平后的语句）转化成一个三向量组 $ s • a \times s • b - s • c = 0 $。在本例中，除了拍平后的5个变量（x, ~out, sym_1, y, sym_2）以外，还需要在第一个分量位置引入一个冗余变量 ～one 来表示数字1.就这个系统而言，一个向量所对应的6个分量是（～one, x, ~out, sym_1, y, sym_2）。变量和分量也可以是其他顺序，只要一一对应即可。

  • 通常得到的向量都是稀疏的，对于第一个乘法门 $ sym_1 = x \times x $，它的三向量组如下：

    a = [0, 1, 0, 0, 0, 0]    # 对应乘法门的第一个输入x
b = [0, 1, 0, 0, 0, 0]    # 对应乘法门的第二个输入x
c = [0, 0, 0, 1, 0, 0]    # 对应乘法门的输出sym_1

    对于此向量组可以解出符合的解向量为 $ s = [1, 3, ?, 9, ?, ?] $

  • 类似的，对于第二个乘法门 $ y = sym_1 \times x $ 有三向量组：

    a = [0, 0, 0, 1, 0, 0]    # 对应乘法门的第一个输入sym_1
b = [0, 1, 0, 0, 0, 0]    # 对应乘法门的第二个输入x
c = [0, 1, 0, 0, 0, 0]    # 对应乘法门的输出y

    得到符合的解向量为 $ s = [1, 3, ?, 9, 27, ?] $

  • 对于第三个加法门 $ sym_2 = y + x $ 有所不同，它的三向量组为：

    a = [0, 1, 0, 0, 1, 0]    # 对应乘法门的第一个输入x和y
b = [1, 0, 0, 0, 0, 0]    # 对应乘法门的第二个输入1
c = [0, 0, 0, 0, 0, 1]    # 对应乘法门的输出sym_2

    解出符合的解向量为 $ s = [1, 3, ?, 9, 27, 30] $

  • 最后一个门 $ ~out = sym_2 + 5 $ 的三向量组为：

    a = [5, 0, 0, 0, 0, 1]    # 对应乘法门的第一个输入sym_2和5
b = [1, 0, 0, 0, 0, 0]    # 对应乘法门的第二个输入1
c = [0, 0, 1, 0, 0, 0]    # 对应乘法门的输出~out

    解出符合的解向量为 $ s = [1, 3, 35, 9, 27, 30] $

获得完整的 R1CS

最后，汇总上面所得的向量组可获得完整的 R1CS：

A
[0, 1, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 1, 0]
[5, 0, 0, 0, 0, 1]
B
[0, 1, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
C
[0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0]

开发步骤

获得完成的 R1CS 后，再将 R1CS 转化为 QAP 形式。

应用 zkSNARK 技术实现一个非交互式零知识证明应用的开发步骤大体如下：

  1. 使用 R1CS 形式编写计算的验证逻辑
  2. 声称证明密钥（Proving Key）和验证密钥（Verification Key）
  3. Alice 使用证明密钥和其可行性解构造证明
  4. Bob 使用验证密钥验证 Alice 发过来的证明

参考文献

隐私计算零知识证明概率R1CSzkSNARK
Leave a Comment