零知识证明编程 - 使用 Circom、Groth16 构建证明及验证

  • oskarth
  • 更新于 2024-09-02 12:18
  • 阅读 2309

本文提供了一份面向程序员的零知识证明(ZKP)教程,使用了 Circom 这种用于编写 ZKP 电路的领域特定语言。文档解释了 ZKP 的概念、约束条件的重要性以及设置、构建和验证 ZKP 电路的过程。它还涵盖了基本 ZKP、使用哈希函数和承诺实现数字签名方案,以及群签名方案。

为工作程序员提供的 ZKP 教程介绍。

你知道为什么斑马有条纹吗?一种理论是这是一种伪装。当斑马聚集在一起时,这使得狮子更难以区分它们的猎物。狮子必须将猎物从群体中隔离出来才能追捕它[^1]。

人类也喜欢在人群中隐藏。一个具体的例子是,当多个人在一个集体名称下作为一个整体行动时。《联邦党人文集》就是这样创作的[^2]。 另一个例子是 Bourbaki,这是 1930 年代一群法国数学家的集体笔名。这导致了现代数学大部分内容的彻底重写,重点在于严谨性和公理化方法[^3]。

Bourbaki Congress

在数字时代,假设你在一个群聊中,想要发送一条有争议的信息。你想证明你是其中的一员,而不透露是哪一位。我们如何在数字领域使用密码学来做到这一点?我们可以使用一种叫做 群签名 的东西。

从传统上讲,群签名在数学上相当复杂且难以实现。然而,使用零知识证明(ZKP),这个数学问题变成了一个简单的编程任务。在本文结束时,你将能够自己编写群签名。

介绍

这篇文章将向你展示如何从零开始编写基本的零知识证明(ZKP)。

在学习新的技术栈时,我们希望尽快掌握编辑-构建-运行的循环。只有这样,我们才能开始从自己的经验中学习。

我们将首先让你设置环境,编写一个简单的程序,执行所谓的可信设置,然后尽快生成和验证证明。之后,我们将识别一些改进我们程序的方法,实施这些改进并进行测试。在此过程中,我们将建立一个更好的心理模型,以便在实践中编程 ZKP。最后,你将熟悉(某种方式)从零开始编写 ZKP。

我们将逐步构建一个简单的签名方案,你可以证明你发送了特定的消息。你将能够理解这段代码的作用及其原因:

    template SignMessage () {
      signal input identity_secret;
      signal input identity_commitment;
      signal input message;
      signal output signature;

      component identityHasher = Poseidon(1);
      identityHasher.inputs[0] <== identity_secret;
      identity_commitment === identityHasher.out;

      component signatureHasher = Poseidon(2);
      signatureHasher.inputs[0] <== identity_secret;
      signatureHasher.inputs[1] <== message;
      signature <== signatureHasher.out;
    }

    component main {public [identity_commitment, message]} = SignMessage();

你还将获得所有必要的工具和技术,以修改此代码以支持上述群签名方案。

预备条件

我们假设你是一名软件工程师,具有多种编程语言的工作经验,基本熟悉使用 Unix 风格的命令行界面。我们还假设你对 数字签名公钥密码学哈希函数 等概念有一定的了解。尽管如此,我们将在相关时介绍它们的相关属性。

在谈到 零知识证明 时,我们假设你已经阅读了我之前的文章,零知识的友好介绍。如果你没有阅读这篇文章,我们将在这里快速回顾最重要的内容。为了更好地理解,我们建议先阅读上述文章。如果你已经阅读过,可以安全跳过以下内容。

ZKP 回顾

零知识证明(ZKP)是一种相对较新的密码学形式,最近在实际应用中越来越多。传统的密码学允许我们进行签名和加密等操作,而 ZKP 允许我们以通用的方式证明任意陈述。

除了证明任意陈述外,ZKP 还赋予我们两个关键属性:隐私和压缩。这分别被称为零知识和简洁性。隐私意味着我们可以证明某件事而不透露其他任何信息。压缩意味着任意陈述的证明在大小上大致保持不变,无论我们证明的计算有多复杂。ZKP 也是通用的。大致来说,这就像是计算器和计算机之间的区别,前者是为特定任务而设计的,后者可以计算任何东西。

两个具体的 ZKP 示例:

  • 我们可以拿一张数字身份证明我们超过 18 岁
    • 而不透露其他任何信息,比如你的全名或地址
  • 我们可以证明所有状态转换都已正确执行
    • 比如在公共区块链中,结果证明非常小

我们可以通过编写称为电路的特殊程序来编程许多常见类型的 ZKP。这允许一方,即证明者,创建某个陈述的证明。另一方,即验证者,可以验证该证明。像普通程序一样,这个程序可以接受输入并产生输出。对于这些特殊程序,我们可以指定输入是私有的还是公共的。如果是私有的,意味着只有证明者可以看到该输入。我们通过指定约束来编程电路。一个约束的例子是“在数独谜题中,所有数字 1 到 9 必须在一行中恰好使用一次”。

ZKP 相对较新,但它们在公共区块链中已经被广泛使用,例如,允许使用可替代货币进行私人支付,或允许更快地处理更多交易。

每天都有越来越多的应用被发现和开发。ZKP 也有许多不同的变种,每种都有自己的一套权衡,这是一个非常活跃的研究领域。这些不同的变种正在迅速发展,并允许提高效率和其他便利。

概述

我们将使用 Circom 和 Groth16。Circom 是一种用于编写 ZKP 电路的领域特定语言(DSL)。Groth16 是一种常见且流行的证明系统。大致来说,证明系统只是编程 ZKP 的一种方式。其他 DSL 和证明系统也存在。

我们将首先安装一些工具和依赖项。之后,我们将按照以下大致步骤进行:

  • 编写(编写电路)
  • 构建(构建电路)
  • 设置(可信设置)
  • 证明(生成证明)
  • 验证(验证证明)

在经历过一次这个流程后,我们将查看当前方法的一些问题。然后,我们将进行几次增量改进,逐步构建到上述签名方案。在此过程中,我们将解释必要的概念和语法。

在每个部分的末尾,我们还将包括一些简单的练习,以检查你的理解。这些练习是推荐的。在文章的最后,我们还将包括一个问题列表。问题是可选的,并需要更多的努力。

准备

首先,我们需要安装一些工具和依赖项。我们准备了一个 git 仓库,使你可以更轻松地入门,而不会在细节中迷失。如果你不想安装任何软件,请参见本节末尾。

我们需要的预备条件是:

  • rust(编程语言)
  • just(现代 make
  • npm(JavaScript 的包管理器)

我们实际使用的 ZKP 工具是:

  • circom(用于构建我们的特殊程序或 电路
  • snarkjs(用于设置和生成/验证证明)
  • just 任务(简化与上述相关的常见操作)

要安装上述内容并使构建和运行更容易,你可以克隆并使用 git 仓库。这应该可以在任何类 Unix 系统上运行,如 MacOS 和 Linux。如果你使用 Windows,我们建议使用 Linux 虚拟机、Windows 子系统 Linux(WSL)或类似的开发环境。

# 克隆仓库并运行准备脚本
git clone git@github.com:oskarth/zkintro-tutorial.git
cd zkintro-tutorial

# 在执行之前浏览此文件的内容
less ./scripts/prepare.sh
./scripts/prepare.sh

我们建议你浏览 ./scripts/prepare.sh 的内容,以查看这将安装什么,或者如果你更喜欢手动安装。执行后,你应该看到 Installation complete 并且没有错误。

如果你遇到问题,请查看最新的官方文档 这里。完成后,你应该安装以下版本(或更高版本):

> circom --version
circom compiler 2.1.8

> snarkjs | head -n 1
snarkjs@0.7.4

在仓库中有一个 justfile,定义了一组常见命令。这些 just 命令旨在简化 ZKP 上的常见操作,以便你可以专注于实际步骤的概念理解。这使得在开始时过程更不容易出错。

如果你想更详细地查看正在执行的命令,我们建议你查看 justfilescripts 文件夹中的各种脚本。

我们强烈建议安装上述软件,以便跟随教程并建立直觉。然而,如果你不想安装任何软件,你可以使用在线 REPL(读取-求值-打印循环)工具 zkrepl.dev 以有限的能力进行跟随。如果你不想安装 just 并希望自己执行所有命令,你可以通过使用附带的 shell 脚本稍微多花点力气来做到这一点。

第一次迭代

我们现在准备开始编码。为了构建上述提到的签名方案,我们将从一个非常简单的程序开始,相当于其他编程语言中的“Hello World”。

在实际操作中,我们将编写一个特殊程序,帮助我们证明对两个秘密数字的知识,其乘积是一个公共数字,而 从不揭示秘密数字本身。例如,公共数字可能是“33”,而秘密数字是“11”和“3”。这是数字签名的重要一步,并将帮助理解 ZKP 的工作原理。如果你熟悉公钥密码学,你可以 - 非常松散地 - 将秘密数字视为“私钥”,将公共数字视为“公钥”。

由于这是一种涉及许多新概念的不同编程方式,因此如果一开始事情不明白也不要担心。你可以继续关注代码、生成证明等,稍后再回到特定部分。

编写特殊程序

与大多数其他编程不同,编写这些特殊程序、电路,看起来有点不同。我们感兴趣的是证明一 组约束[^4]。 我们可以证明的最简单的约束集由一个约束组成。 ^5 我们将约束的是两个数字相乘等于第三个数字。

请转到上述 zkintro-tutorial 仓库中的 example1 文件夹。example1.circom 中有一个骨架程序。将其修改为如下所示:

pragma circom 2.0.0;

template Multiplier2 () {
  signal input a;
  signal input b;
  signal output c;
  c <== a * b;
}

component main = Multiplier2();

这就是我们的特殊程序或 电路。 [^6] 按行分析:

  • pragma circom 2.0.0; - 定义所使用的 Circom 版本
  • template Multiplier() - 模板是大多数编程语言中对象的等价物,是一种常见的抽象形式
  • signal input a; - 我们的第一个输入,a;输入默认是私有的
  • signal input b; - 我们的第二个输入,b;同样默认是私有的
  • signal output b; - 我们的输出,c;输出始终是公共的
  • c <== a * b; - 这做了两件事:将信号 c 赋值 约束 c 等于 ab 的乘积
  • component main = Multiplier2() - 实例化我们的主组件

最重要的行是 c <== a * b;。这是我们实际声明约束的地方。这个表达式实际上是两个的组合:<--(赋值)和 ===(等式约束)。 [^7] Circom 中的约束只能使用涉及常量、加法或乘法的操作。它强制要求方程的两边必须相等。 [^8]

关于约束

约束是如何工作的?在类似数独的上下文中,我们可能会说一个约束是“一个介于 1 和 9 之间的数字”。然而,在 Circom 的上下文中,这不是一个单一的约束,而是我们必须使用一组更简单的等式约束(===)来表达的东西。 [^9]

为什么会这样?这与底层的数学原理有关。从根本上讲,大多数 ZKP 使用 算术电路,它表示对 多项式 的计算。在处理多项式时,你可以轻松引入常量,将它们相加、相乘并检查它们是否相等。 [^10] 其他操作必须用这些基本操作来表达。你不必详细了解这一点才能编写 ZKP,但了解底层发生的事情可能会很有用。 [^11]

我们可以将电路可视化如下:

example1 circuit

构建我们的电路

供你参考,最终文件可以在 example1-solution.circom 中找到。有关语法的更多详细信息,请参见 官方文档

我们可以通过运行以下命令来编译我们的电路:

example1 build

这是调用 circom 创建 example1.r1csexample1.wasm 文件的一个简单包装。你应该会看到类似以下内容:

template instances: 1
non-linear constraints: 1
linear constraints: 0
public inputs: 0
private inputs: 2
public outputs: 1
wires: 4
labels: 4
Written successfully: example/target/example1.r1cs
Written successfully: example/target/example1_js/example1.wasm 在这种情况下,我们有以下内容:
  • 两个私有输入,ab
  • 一个公共输出,c
  • 一个(非线性)约束,c <== a * b

我们暂时忽略上面输出的其他部分。[^12] 现在我们有两个文件:example1.r1csexample1.wasm

r1cs 代表 Rank 1 Constraint System。这个文件以二进制形式包含我们的电路,并对应于我们如何在数学上定义我们的约束。[^13]

.wasm 文件包含 WebAssembly,这是我们生成 witness 所需的。witness 是我们指定希望保持私密的输入,同时仍然使用它们来创建证明的方式。

不过我们还没有准备好进行证明。首先,我们需要执行一个 setup 来获取我们的证明者和验证密钥。

如果这一切还不太明白,不用担心。这是一种新的做法,需要一段时间来适应。

可信设置

通过我们上面生成的工件,我们可以执行 trusted setup

可信设置是我们作为预处理步骤运行一次的东西。这生成了一个称为 Common Reference String (CRS) 的东西,它由 proving keyverification key 组成。这些密钥可以在每次生成和验证证明时使用。

Trusted setup

我们为什么需要这些密钥,谁应该有权访问它们?证明者密钥嵌入了生成特定电路的证明所需的所有信息,以零知识保护的方式进行。类似地,验证者密钥嵌入了验证证明确实正确所需的所有信息。这些不是私钥,而是可以并且应该公开分发的信息。任何需要生成或验证证明的方都应该能够访问它们。^14

我们为什么称之为可信设置?执行设置是一个涉及多个参与者的过程,有时称为 ceremony。[^15] 所有参与者合作创建一个加密“秘密”,这就是证明和验证密钥构造的基础。如果这个过程被操纵,从加密学上讲,可能会创建虚假的证明或错误地声称无效的证明已被验证。因此,存在一种信任假设,即至少有一些参与者在设置过程中是诚实的,这就产生了“可信设置”这个术语。

作为起点,我们将自己运行可信设置。运行以下命令:

just trusted_setup example1

example1 trusted setup

系统会要求你提供两次随机文本或熵。^16 完成后,你应该看到“Trusted setup completed.”和密钥的位置。以 .zkey 结尾的文件是我们的证明密钥。虽然深入探讨可信设置的细节超出了本文的范围,但有一些有用的事项需要了解。

首先,上述方法有什么问题?由于我们只有一个参与者,使用该设置的加密密钥材料的其他所有人都在信任该个人及其计算机环境。这在生产场景中是行不通的,因为我们希望最大化参与者的数量,以使设置更可信。如果有 100 个人参与,由于这个加密秘密的构造方式,只要有一个人诚实就足够了。[^17]

还值得注意的是,不同的 ZKP 系统在安全性、性能和适应性方面具有不同的属性。虽然所有 ZKP 系统都需要某种形式的设置,但并非所有系统都需要可信设置。在那些需要的系统中,有些在要求上有所不同。

在 Circom 中,我们使用的 Groth16 proof system 确实需要可信设置。具体来说,设置分为两个阶段:阶段 1 和阶段 2。阶段 1 与电路无关,可以被任何 ZKP 程序使用,直到某个大小,而阶段 2 是 电路特定的。当我们运行上述命令时,我们执行了两个阶段。

你可能会想,如果可以避免,为什么还要使用可信设置?很多人同意这种观点。然而,人们使用这些系统仍然有很好的理由,例如更成熟的工具和生态系统,以及低廉的验证成本。低廉的验证成本在验证公共区块链(如以太坊)上的证明时尤其重要。根据你的用例,你的选择可能会有所不同。在另一篇文章中,我们将更深入地探讨可信设置及其权衡,以及不同的证明系统。

生成证明

通过上面完成的可信设置,我们有了证明密钥和验证密钥。我们现在可以生成一个证明,证明我们知道两个秘密值,其乘积是另一个公共数字。

具体来说,让我们证明我们知道 33 可以通过将数字 3 和 11 相乘来构造。回想一下,我们的私有输入由信号 ab 组成。我们在 example1/input.json 文件中如下指定:

也就是说,我们将输入指定为 JSON 映射,其中键是信号名称,值是我们要分配给它的值。请注意,尽管值在概念上是一个数字,但它是一个字符串。这是 Circom 及其 JS API 的一个怪癖。由于 ZKP 的性质,我们通常处理需要使用 BigInt 的非常大的数字。在 JSON 文件中指定如此大的数字的最简单方法是将其作为字符串,然后转换为 BigInt。

我们可以通过运行以下命令,使用我们编译的电路(以 WASM 形式)、我们的证明密钥和输入来创建证明:

just generate_proof example1

example1 generate proof

在后台,此命令接受输入并为我们的特定电路生成一个 witness。[^18] 通常,witness 仅指我们用来生成证明的私有输入。在 Circom 的上下文中,witness 是所有信号的完整分配,包括私有和公共信号,以证明软件可以处理的形式。这种形式是二进制格式的内部表示。[^19]

通过生成的 witness,我们可以使用 snarkjs 创建证明。最后,我们得到了一个证明和一些公共输出。

证明看起来像这样:

{
  "pi_a": ["15932[...]3948", "66284[...]7222", "1"],
  "pi_b": [
    ["17667[...]0525", "13094[...]1600"],
    ["12020[...]5738", "10182[...]7650"],
    ["1", "0"]
  ],
  "pi_c": ["18501[...]3969", "13175[...]3552", "1"],
  "protocol": "groth16",
  "curve": "bn128"
}

这以一些数学对象(三个椭圆曲线元素)pi_api_bpi_c 的形式指定了证明。[^20] 它还包括有关协议(groth16)和使用的 curvebn128,我们暂时忽略的数学实现细节)的元数据。这使得验证者知道如何处理此证明以正确验证。

请注意,证明是多么简短;无论我们的特殊程序多么复杂,它的大小都只有这个。这展示了我们在 友好的零知识证明介绍 中讨论的 ZKP 的 succinctness 属性。上述命令还输出了我们的 公共输出

这是与我们的见证和电路对应的所有公共输出的列表。在这种情况下,有一个公共输出对应于 c:33。[^21]

我们证明了什么?我们知道两个秘密值 ab,它们的乘积是 33。这展示了我们在上一篇文章中讨论的 隐私 属性。

请注意,证明在孤立状态下没有用,它需要随之而来的公共输出。

验证证明

接下来,让我们验证这个证明。运行:

just verify_proof example1

example1 verify proof

这需要验证密钥、公共输出和证明。通过这些,我们能够验证证明。它应该打印“证明已验证”。请注意,验证者从未接触到任何私有输入。

如果我们更改输出会发生什么?打开 example1/target/public.json,将 33 更改为 34,然后再次运行上述命令。

你会注意到证明不再被验证。这是因为我们的证明并没有证明我们有两个数字,其乘积是 34。

恭喜你,你现在已经编写了你的第一个 ZKP 程序,进行了可信设置,生成了证明并最终验证了它!

练习

  1. ZKP 的两个关键属性是什么,它们意味着什么?
  2. 证明者的角色是什么,她需要什么输入?验证者呢?
  3. 解释 c <== a * b; 这一行的作用。
  4. 为什么我们需要进行可信设置?我们如何使用其产物?
  5. 代码:完成 example1,直到你生成并验证了一个证明。

第二次迭代

通过上述电路,我们证明了我们知道两个(秘密)数字的乘积。这与 质因数分解 问题密切相关,这是许多密码学的基础。[^22] 这个想法是,如果你有一个非常大的数字,找到两个质数使其乘积等于这个大数字是很困难的。相反,检查两个数字的乘积是否等于另一个数字是非常简单的。[^23]

然而,我们的电路存在一个大问题。你能看到吗?

我们可以轻松地将输入更改为“1”和“33”。也就是说,一个数字 c 始终是 1 和 c 的乘积。这一点并不令人印象深刻,对吧?

我们想要做的是添加另一个 约束,使得 ab 不能等于 1。这样,我们就被迫进行适当的整数因式分解。

我们如何添加这个约束,需要做哪些更改?

更新我们的电路

我们将为这些更改使用 example2 文件夹。不幸的是,我们不能仅仅写 a !== 1,因为这不是一个有效的约束。[^24] 它不是由常量、加法、乘法和等式检查组成的。我们如何表达“某物不是”?

这并不是立即直观的,这种类型的问题是编写电路的艺术所在。发展这种技能需要时间,并超出了本初始教程的范围;幸运的是,有许多好的资源可以参考。[^25]

不过,有一些常见的习语。基本的想法是使用 IsZero() 模板来检查一个表达式是否等于零。它对真值输出 1,对假值输出 0。

使用真值表[^26] 来显示可能的值通常是有帮助的。以下是 IsZero() 的真值表:

输入 输出
0 1
n 0

这是一个如此有用的构建块,以至于它被包含在 Circom 的库 circomlib 中。在 circomlib 中还有许多其他有用的组件。[^27]

我们可以通过创建一个 npm 项目(JavaScript)并将其作为依赖项添加来包含它。在 example2 文件夹中,我们已经为你完成了这一步。要导入相关模块,我们在 example2.circom 的顶部添加以下行:

include "circomlib/circuits/comparators.circom";

使用 IsZero(),我们可以检查 ab 是否等于 1。修改 example2.circom 文件,使其包含以下行:

component isZeroCheck = IsZero();
isZeroCheck.in <== (a - 1) * (b - 1);
isZeroCheck.out === 0;

在上述代码片段中,我们创建了一个新的组件 isZeroCheck,实例化 IsZero() 模板。如果 ab 等于 1,isZeroCheck.in 将被赋值为 0,而 isZeroCheck.out 将为 1。由于我们有一个约束,表示 isZeroCheck.out === 0,这个约束将失败。这意味着我们不能再提供 ab 等于 1 的输入。

我鼓励你在脑海中或使用纸笔(也许使用真值表?)说服自己,这是真的。如果你想挑战一下,可以尝试弄清楚 IsZero() 是如何实现的。它只有几行代码。你可以在 circomlibcomparators.circom 文件中查看代码。[^28]

供你参考,最终文件可以在 example2-solution.circom 中找到。通过上述更改,我们可以安装 npm circomlib 依赖项并构建我们的电路:

just build example2

重新运行我们的可信设置

使用 Circom 和 Groth16,每次我们更改电路时都必须重新运行我们的可信设置。这意味着你最好在发布之前确保你的电路是稳固的。特别是如果你正在进行涉及许多参与者的正式仪式。

更具体地说,我们只需要再次运行电路特定的(第二阶段)可信设置。这是因为第一阶段是针对 任何 在 Circom 中编写的 Groth16 电路的通用设置,直到某个大小。当我们在上面执行可信设置时,我们进行了第一阶段和第二阶段,但为了简单起见省略了第一阶段的细节。以下是第一阶段的一些更多细节,以提供更完整的图景。

Trusted setup (both phases)

第一阶段可信设置的结果保存在 .ptau 文件中,其中 ptau 代表 tau 的幂。[^29] 从数学上讲,这个文件包含一些随机秘密的幂。这使我们能够“容纳”一定数量的约束。我们不需要理解它在数学上是如何工作的,但有两个关键事实是有用的: (a) .ptau 是电路无关的 (b) 它的大小表示其容量。给定 ptau 的“容量”是 2^n - 1 个约束,其中 n 是某个数字。例如,pot12.ptau 表示它可以容纳的约束数量是 2^12 - 1,即略多于 4000 个约束。

由于我们不想再次运行第一阶段,我们只想运行第二阶段。这将使用先前生成的 pot12.ptau(存储在 ptau 目录中)作为输入。我们可以通过以下命令运行我们的第二阶段可信设置:

just trusted_setup_phase2 example2

example2 trusted setup

测试我们的更改

通过这个,我们可以运行:

just generate_proof example2
just verify_proof example2

它仍然按预期生成和验证证明。

如果我们将 example2/input.json 的输入更改为 133 并尝试运行上述命令,我们将看到一个断言错误。也就是说,Circom 甚至不会让我们生成证明,因为输入违反了我们的约束。

完整流程图

现在我们已经经历了整个流程两次,让我们退后一步,看看所有部分是如何结合在一起的。

example2 complete flow

希望事情开始变得有些明朗。接下来,让我们提升一下,让我们的电路更有用。

练习

  1. 为什么我们必须运行 example2 的第 2 阶段,而不是第 1 阶段?
  2. 上一个例子的主要问题是什么,我们是如何解决的?
  3. 代码:完成 example2,直到你无法生成证明。

第三次迭代

通过上述电路,我们已经证明了我们知道两个秘密值的乘积。单靠这一点并不是很有用。在现实世界中,有用的是 数字签名方案。通过它,你可以向其他人证明你写了特定的消息。我们如何使用 ZKP 来实现这一点?要实现这一点,我们必须首先涵盖一些基本概念。

现在是短暂休息的好时机,去喝一杯你最喜欢的饮料。

数字签名

数字签名已经存在,并且在我们的数字时代无处不在。现代互联网没有它们是无法运作的。通常,这些是使用 公钥密码学 实现的。在公钥密码学中,你有一个私钥和一个公钥。私钥仅供你自己使用,而公钥是公开共享的,代表你的身份。

数字签名方案由以下部分组成:

  • 密钥生成:生成一个私钥和相应的公钥
  • 签名:使用私钥和消息创建签名
  • 签名验证:验证消息是否由相应的公钥签名

虽然具体细节看起来不同,但我们编写的程序和上述密钥生成算法共享一个共同元素:它们都使用 单向函数,更具体地说是 陷门函数。陷门是容易掉进去但难以爬出来的东西(除非你能找到一把隐藏的梯子) [^30]。

example3 trapdoor

对于公钥密码学,从私钥构造公钥是容易的,但反过来却非常困难。我们的前一个程序也是如此。如果这两个秘密数字是非常大的质数,那么将该乘积转回原始值是非常困难的。现代公钥密码学通常在底层使用 椭圆曲线密码学

传统上,创建像这些数字签名方案这样的密码协议需要大量的工作,并需要提出一个涉及一些巧妙数学的特定协议。我们不想这样做。相反,我们想使用 ZKP 编写一个程序,以实现相同的结果。

而不是这样:[^31]

Signature verification

我们只想编写一个程序,生成我们想要的证明,然后验证这个证明。

哈希函数和承诺

我们将使用两个更简单的工具:哈希函数承诺,而不是使用椭圆曲线密码学。

哈希函数也是一种单向函数。例如,在命令行中,我们可以这样使用 SHA-256 哈希函数:

echo -n "foo" | shasum -a 256

以生成 "foo" 的哈希:0beec7[...]a8a33(缩写)。 [^32]

单独来看,哈希函数不是陷门函数。没有特殊的知识可以让我们检索原始值。它更像是一个绞肉机,而不是一个带有隐藏梯子的陷门。

那么承诺呢?承诺 只是承诺(“承诺”)一个秘密值的一种方式,以便我们不能在之后改变主意。在我们的案例中,我们将使用承诺来生成相当于公钥的某个秘密值。我们可以使用哈希函数来做到这一点。

承诺方案是一种非常常见的密码原语。 [^33] 它们允许我们:

  • 承诺:承诺一个特定的值,同时保持其隐藏
  • 揭示:揭示这个值,以便可以验证其正确性

这给我们两个关键属性:

  • 隐藏:值保持隐藏
  • 绑定:你不能改变对该值的承诺

一种理解承诺的方式是想象把一个锁箱给朋友。你不能在事后改变箱子的内容,但你的朋友不能查看里面。只有当你给他们钥匙时,他们才能打开它。

example3 lockbox

回到我们的数字签名方案,我们有:

  • 密钥生成:创建一些秘密字符串并哈希以创建承诺
  • 签名:通过将秘密与消息一起哈希来创建签名
  • 验证:使用承诺、消息和签名(公共输出)验证证明

在伪代码中,这就是我们想在电路中做的:

commitment = hash(some_secret)
signature = hash(some_secret, message)

此时你可能有一些问题。让我们解决一些你脑海中可能存在的问题。

首先,为什么这有效,我们为什么需要 ZKP?当有人验证证明时,他们只能访问承诺、消息和签名。没有直接的方法可以验证承诺是否对应于秘密,而不揭示秘密。在这种情况下,我们只是在生成证明时“揭示”秘密,因此我们的秘密保持安全。

其次,为什么在 ZKP 内部使用这些哈希函数和承诺,而不是公钥密码学?你绝对可以在 ZKP 内部使用公钥密码学,并且这样做是有合理理由的。就约束而言,它的实现成本远高于上述方案。这使得它比上述更慢,更复杂。正如我们将在下一节中看到的,哈希函数的选择非常重要。

最后,为什么在我们已经拥有公钥密码学的情况下还要使用 ZKP?在这个简单的例子中,没有必要使用 ZKP。然而,它作为更有趣的应用的构建块,例如本文开头提到的群签名示例。毕竟,我们想要 编程密码学

这真是太多了!幸运的是,我们已经过了难关。让我们开始编码吧。如果你一开始没有完全理解上述内容,也不用担心。习惯这种推理方式需要一些时间。

回到代码

我们将从 example3 目录开始工作。

要实现数字签名,我们需要做的第一件事是生成我们的密钥。这些对应于公钥密码学中的私钥和公钥。由于密钥对应于一个身份(你,证明者),我们将分别称其为 identity_secretidentity_commitment。它们共同形成一个身份对。

这些将作为电路的输入,与我们要签名的消息一起使用。作为公共输出,我们将拥有签名、承诺和消息。这将允许某人验证签名确实是正确的。

由于我们需要身份对作为电路的输入,因此我们将单独生成这些:just generate_identity

这会产生类似于以下内容:

identity_secret: 43047[...]2270
identity_commitment: 21618[...]0684

为了保持秘密的安全,我们使用一个大而随机的数字。与我们之前看到的不同,我们并没有使用像 SHA-256 这样的哈希函数来创建承诺。相反,我们使用的是一种称为 ZK-Friendly hash function 的东西。这是一种特别的哈希函数,经过优化以用于 ZKP。当你进行大量哈希时,这在性能上非常重要。我们使用的 ZK 友好哈希函数称为 Poseidon hash function。[^34]

在底层,这使用 circomlibjs 库来包装 circomlib。这是一个 JavaScript 库,允许我们使用 Circom 电路。这确保我们的 identity_commitment 在 JavaScript/命令行中与在电路中生成的方式完全相同。如果你想查看脚本源代码,可以在 example3/generate_identity.js 中找到。

就像我们之前对 IsZero 所做的那样,我们需要包含 Poseidon 模板。我们通过以下包含来实现:

include "circomlib/circuits/poseidon.circom";

Poseidon 哈希模板的使用如下:

component hasher = Poseidon(2);
hasher.inputs[0] = foo;
hasher.inputs[1] = bar;
quux <== hasher.out

我们指定 hasher 组件期望两个参数,这些参数在 .inputs[] 数组中指定。然后将输出信号分配给 .out。在这个例子中,它将 foobar 作为输入,将它们哈希在一起,结果是 quux。[^35]

最后,我们引入了一种新的语法:

component main {public [identity_commitment, message]} = SignMessage();

默认情况下,我们电路的所有输入都是私有的。通过这个,我们明确标记 identity_commitmentmessage 为公共。这意味着它们将成为公共输出的一部分。

有了这些信息,你应该有足够的知识来完成 example3.circom 电路。如果你仍然卡住,可以参考 example3-solution.circom 获取完整代码。

像之前一样,我们必须构建电路并运行受信任设置的第 2 阶段:

just build example3
just trusted_setup_phase2 example3

在构建电路时,你可能会注意到与 example2 相比,约束的数量增加了很多。这主要是由于使用了两个 Poseidon 哈希。[^36]

测试我们的电路

作为参考,这里是我们完成的电路的插图:

example3 circuit

我们现在可以生成一个证明。我们在 example3/input.json 中有以下输入:

{
  "identity_secret": "21879[...]1709",
  "identity_commitment": "48269[...]7915",
  "message": "42"
}

随意将身份对更改为你自己使用 just generate_identity 生成的身份对。毕竟,你想把身份秘密保留给自己!

你可能会注意到消息只是一个作为字符串引用的数字 ("42")。不幸的是,由于约束在数学上的工作方式(使用线性代数和 算术电路),我们只能使用数字而不能使用字符串。电路内部支持的唯一操作是基本的算术操作,如加法和乘法。[^37]

我们现在可以生成和验证一个证明:

just generate_proof example3
just verify_proof example3

与之前一样,证明的大小保持不变,即使我们做了更多的事情。example3/target/public.json 中找到的公共输出是:

["48968[...]5499", "48269[...]7915", "42"]

这分别对应于签名、承诺和消息。

让我们看看如果我们不小心,事情可能会出错。 [^38]

首先,如果我们将身份承诺更改为 input.json 中的随机内容,会发生什么?你会注意到我们无法再生成证明。这是因为我们还在电路内部检查身份承诺。保持身份秘密和承诺之间的关系至关重要。

其次,如果我们不将消息包含在输出中,会发生什么?我们确实得到了一个证明,并且它得到了验证。但消息可以是 任何东西,因此它实际上并不能证明你发送了特定的消息。类似地,如果我们不将身份承诺包含在公共输出中,会发生什么?这意味着身份承诺可以是任何东西,因此我们实际上不知道 签署了消息。

作为思考练习,想想如果我们省略这两个关键约束中的任何一个会发生什么:

  • identity_commitment === identityHasher.out
  • signature <== signatureHasher.out

恭喜你,现在你知道如何编程加密了![^39]

练习

  1. 数字签名方案的三个组成部分是什么?
  2. 使用像 Poseidon 这样的 "ZK-Friendly hash function" 的目的是什么?
  3. 什么是承诺?我们如何将它们用于数字签名方案?
  4. 为什么我们将身份承诺和消息标记为公共?
  5. 为什么我们需要身份承诺和签名约束?
  6. 代码:完成 example3,直到你生成并验证了一个证明。

下一步

通过上述数字签名方案,以及我们在文章中看到的一些技巧,你拥有了实现文章开头提到的 群签名方案 的所有工具。[^40]

example4 中存在骨架代码。你只需要 5-10 行代码。唯一的新语法是 for 循环,它的工作方式与大多数其他语言相同。[^41]。

这个电路将允许你:

  • 签署一条消息
  • 证明你是三个人之一(身份承诺)
  • 但不透露是哪一个

你可以把它看作一个谜题。关键的见解基本上归结为一个算术表达式。如果可以的话,尝试在纸上解决它。如果你卡住了,可以像之前一样查看解决方案。

最后,如果你想要一些额外的挑战,这里有一些扩展的方法:

  1. 允许组内任意多的人
  2. 实现一个新的电路 reveal,证明你签署了特定的消息
  3. 实现一个新的电路 deny,证明你没有签署特定的消息

使用经典工具创建这样的加密协议将是一项巨大的任务,需要大量的专业知识。[^42] 使用 ZKP,你可以在一个下午变得高效和危险,将这些问题视为编程任务。这只是我们可以做的冰山一角。

练习

  1. 群签名与普通签名有什么不同?它们可以如何使用?

问题

这些问题是可选的,需要更多的努力。

  1. 找出 IsZero() 是如何实现的。
  2. 代码:完成上述群签名方案(见 example4)。
  3. 代码:扩展上述群签名示例:允许更多人并实现 reveal 和/或 deny 电路。
  4. 你将如何设计一个 "ZK 身份" 系统来证明你已满 18 岁?你可能想证明的其他属性是什么?从高层次来看,你将如何实现它,以及你看到的挑战是什么?研究现有解决方案以更好地理解它们是如何实现的。
  5. 对于像以太坊这样的公共区块链,有时会使用 Layer 2 (L2) 来允许更快、更便宜和更多的交易。从高层次来看,你将如何使用 ZKP 设计一个 L2?解释你看到的一些挑战。研究现有解决方案以更好地理解它们是如何实现的。## 结论

在本教程介绍中,我们熟悉了如何从头开始编写和修改基本的零知识证明(ZKPs)。我们设置了编程环境并编写了一个基本电路。然后我们进行了可信设置,创建并验证了证明。我们识别了一些问题并改进了电路,确保测试我们的更改。之后,我们使用哈希函数和承诺实现了一个基本的数字签名方案。

我们还学习了足够的技能和工具,以便能够实现群体签名,这在没有零知识证明的情况下是很难实现的。

我希望你对编写零知识证明所涉及的内容有了更好的心理模型,并对实际中的编辑-运行-调试周期有了更好的理解。这将为你将来可能编写的任何其他零知识证明程序打下良好的基础,无论你最终使用什么技术栈。

致谢

感谢 Hanno Cornelius、Marc Köhlbrugge、Michelle Lai、lenilsonjr 和 Chih-Cheng Liang 阅读草稿并提供反馈。

图片

  • Bourbaki Congress 1938 - 未知,公有领域,通过 Wikimedia
  • Hartmann's Zebras - J. Huber,CC BY-SA 2.0,通过 Wikimedia
  • Trapdoor Spider - P.S. Foresman,公有领域,通过 Wikimedia
  • Kingsley Lockbox - P.S. Foresman,公有领域,通过 Wikimedia

我是 AI 翻译官,为大家转译优秀英文文章,如有翻译不通的地方,在这里修改,还请包涵~

参考文献

[^1]: 虽然作为隐喻很有说明性,但这只是几种理论中的一种。如果你感兴趣,可以查看 https://en.wikipedia.org/wiki/Zebra#Function

[^2]: 参见 联邦党人文集(维基百科)

[^3]: 参见 Bourbaki(维基百科)

[^4]: 除非你做过某种形式的声明式编程(例如:非过程式的,如 Prolog),否则这对你来说可能是新的。在某种程度上,我们在 SQL 中也这样做。我们描述 我们想要什么,而不一定是 我们想要它如何完成

[^6]: 我们称之为 电路,更准确地说是 算术电路,因为它以类似于 NAND、AND、NOT、XOR 等逻辑门的方式连接输入和输出。由此我们可以构建一个通用计算机或通用电路。

[^7]: 一般来说,不推荐使用 <--,你几乎总是应该避免使用它,而是使用 <==

[^8]: 这使得编写约束相当具有挑战性,正如你可以想象的那样。有关 Circom 中约束的更多详细信息,请参见 https://docs.circom.io/circom-language/constraint-generation/

[^9]: 要说“这个数字在 1 和 9 之间”,我们必须实现一个 范围检查。这包括将数字分解为位并对它们进行相等性检查。幸运的是,这些类型的约束已经有很多被编写并可以重用,正如我们稍后在 circomlib 中看到的那样。

[^10]: 例如 p(x) = ax^2 + bx + c 可以很容易地相加、相乘或与 q(x) = dx^2 + 2bx + e 进行比较。值得注意的是,在零知识证明中,我们在有限域上操作,而不是实数。尽管这超出了本文的范围。

[^11]: 虽然大多数零知识证明使用 算术电路,但还有其他证明系统使用其他抽象。例如,zkSTARKs 和 Bulletproofs。

[^12]: 线性约束意味着它可以仅通过加法表示为线性组合。这相当于使用常数进行乘法。需要注意的主要是线性约束比非线性约束更简单。有关更多详细信息,请参见 约束生成。电线和标签指的是 算术电路 的外观。这通常不是你需要关心的事情。有关更多详细信息,请参见 算术电路

[^13]: 从数学上讲,我们所做的是确保方程 Az * Bz = Cz 成立,其中 Z=(W,x,1)ABC 是矩阵,W 是见证(私有输入),x 是公共输入/输出。虽然知道这一点很有用,但编写电路时并不需要理解这一点。有关更多详细信息,请参见 Rank-1 约束系统

[^15]: 正如在 友好的介绍 文章中提到的那样,2016 年 Zcash 举办的仪式有一个很好的外行播客,你可以在 这里 收听。自那时以来,可信设置在许多方面发生了变化,运行和参与变得容易得多。

[^17]: 我们称之为 1-out-of N 信任模型。还有许多其他信任模型;你最熟悉的可能是多数规则,即你信任大多数人做出正确的决定。这基本上就是民主和大多数投票的运作方式。

[^18]: 由于我们总是将见证与证明一起生成,因此生成的二进制文件 witness.wtns 大多是一个中间步骤和实现细节。我们立即使用它来生成证明,这就是它在图中被省略的原因。

[^19]: 在文献中,见证只是 R1CS 中向量 Z=(W,x,1)W 部分,其中 x 是所有公共/输入信号。在 Circom 中,整个向量被称为见证。另请参见注释 13。

[^20]: 为了简洁,数字已缩写为 [...]。从数学上讲,这些是 bn128 曲线上的椭圆曲线点,字段大小为 254 位。一个 254 位的数字在其十进制表示中最多可以有 77 位。

[^21]: 输出有点不直观,因为它并不映射到原始信号名称,如此:{"c": "33"} 。这要求开发者根据电路中定义的顺序重新映射输出。这是由于 snarkjs 的实现,我们在证明生成中丢失了变量信息。

[^22]: 也称为 密码学难度假设。请参见 计算难度假设 (维基百科)

[^23]: 有关更多信息,请参见 https://en.wikipedia.org/wiki/Integer_factorization

[^24]: 虽然我们可以添加 asserts,但这些实际上不是约束,仅用于清理输入。有关其工作原理,请参见 https://docs.circom.io/circom-language/code-quality/code-assertion/https://www.chainsecurity.com/blog/circom-assertions-misconceptions-and-deceptions 以获取误用 asserts 可能出错的示例。有关约束的更多直观理解,请参见前一节 关于约束

[^25]: 这份由 0xPARC 提供的资源非常出色,如果你想深入了解编写 (Circom) 电路的艺术: https://learn.0xparc.org/materials/circom/learning-group-1/circom-1/ (特别是 Circom 研讨会)。阅读标准库也可以提供启发,见第 26 条。

[^26]: 由于编写约束的性质,这种情况经常出现。请参见 https://en.wikipedia.org/wiki/Truth_table

[^27]: 有关 circomlib 的更多信息,请参见 https://github.com/iden3/circomlib

[^28]: 请参见 https://github.com/iden3/circomlib/blob/master/circuits/comparators.circom

[^29]: 人们通常在项目之间共享这些 ptau 文件以提高安全性。有关详细信息,请参见 https://github.com/privacy-scaling-explorations/perpetualpowersoftau。你还可以在 https://github.com/iden3/snarkjs 找到这些不同大小的 ptau 文件列表。

[^30]: 这里的梯子代表某种值,使我们能够以相反的“困难”方式进行。另一种思考方式是将其视为一个挂锁。你可以轻松锁定它,但很难解锁,除非你有钥匙。陷门函数也有更正式的定义,请参见 https://en.wikipedia.org/wiki/Trapdoor_function

[^31]: 来自维基百科的截图。请参见 ECDSA (维基百科)

[^32]: 此命令应在大多数 Unix 风格的系统上工作。我们使用 -n 来指定不带换行符(foo,而不是 foo\n),并使用 -a 来指定我们想要 SHA256。

[^33]: 请参见 https://en.wikipedia.org/wiki/Commitment_scheme 。请注意,我们并不总是需要“隐藏”属性。例如,在使用 ZKP 使以太坊更具可扩展性时,我们只想要状态树的高效子集揭示。

[^34]: 我们使用 Poseidon,但还有许多其他选择。为什么它更快?这些 ZK 友好的哈希函数是使用素数域上的算术运算实现的,而不是像 SHA256 这样的按位运算。实现所需的约束少得多,这导致证明时间更快。这两者之间的性能差异可以达到两个数量级。相反,像 SHA256 这样的哈希函数比大多数这些新的 ZK 友好的哈希函数经过了更严格的研究。

[^35]: 在 ZKP 中,我们通常希望将多个事物一起哈希。与传统上下文不同,我们不能仅仅将字符串连接在一起(“foo bar”),因此我们需要指定输入到哈希函数的数量。

[^36]: 如上面的注释所述,如果使用 SHA-256 或进行某些椭圆曲线数学,约束计数将高得多。如果我们有超过 4000 个约束,我们将不得不执行(或重用)另一个阶段 1 受信任的设置,使用更高容量的 ptau。

[^37]: 然而,我们可以将字符串编码为字节数组,使用 Unicode 或 ASCII。在实际应用中,你可能会使用消息的 BigInt 表示形式的哈希。

[^38]: 在现实世界的数字签名方案中,当多个消息交换时,我们可能还希望引入一个加密随机数。这是为了避免重放攻击,即某人可以在稍后时间重用相同的签名。请参见 https://en.wikipedia.org/wiki/Replay_attack

[^39]: 对于现实世界的应用,尽量重用现有的工作和最佳实践。 如果不小心,很多事情可能会出错。幸运的是,随着 ZKP 生态系统的成熟,这变得越来越容易。在某个阶段,许多高风险应用会进行安全审计,以确保其应用程序是安全的(或至少不是可证明的不安全)。

[^40]: 在 ZKP 中实现群签名的灵感来自 0xPARC,请参见 https://0xparc.org/blog/zk-group-sigs

[^41]: 请参见 https://docs.circom.io/circom-language/control-flow/

[^42]: 相比之下,实施群签名的论文如 https://eprint.iacr.org/2015/043.pdf 涉及一些复杂的密码学和数学。

点赞 0
收藏 1
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

2 条评论

请先 登录 后评论
oskarth
oskarth
freedom maxi | global zkman | http://zkintro.com, folding, mobile proving, etc