零知识证明月球数学

零知识证明可以证明你正确执行了某项计算，而无需透露该计算的输入。零知识编程语言则是表示这种计算的一种便捷方式。

关于零知识证明，一个常见但具有误导性的比喻是：“我可以在不给你看身份证的情况下证明我已年满 21 岁”。如果这样表述，你是无法创建零知识证明的。

零知识证明并非证明**知识。它们证明的是在不泄露计算输入的情况下，对公开算法的公开输出进行了正确的计算**。

因此，零知识身份证并不是那样运作的。让我们来看一个真实的例子。你可以拿一个已知的数字（比如 1,093,073），并创建一个证明，证明你通过将两个数字相乘得到了它，而无需透露这两个数字（在这个例子中是 1103 和 991）。

这个过程的零知识证明包含三个组成部分：

• 两个数字（我们称之为 域），在这个例子中，是加密版本的 1103 和 991
• 一个大型字节串（证明）
• 乘法算法的程序化描述

将输入称为“加密的”有些误导，因为并没有一种自然的方法可以对其进行解密，但这是一种合理的思考方式。你可以对输入进行在数学上有意义的操作，但无法确定它们的原始值是什么）。

你可以将零知识证明视为数字签名的高度泛化版本。

在使用数字签名时，你是在不共享私钥的情况下证明对私钥的了解。你通过首先公开一条消息和一个公钥来证明这种知识。然后，你展示一个与该消息和公钥相一致的签名。

对于零知识证明，这个类比如下所示：

(公开输出, 加密输入, 零知识证明) —> 数字签名

(算法) —> 公钥。

你生成一个与输出和算法相一致的证明（字节串）。验证者实际上无法执行该计算，但他们可以验证

• 算法
• 输出
• 加密输入，以及
• 证明字符串

彼此之间是否全部保持一致。

在数字签名中，公共地址是预先知道的。在零知识应用中，你正在执行的算法是预先知道的。数字签名会根据你签署的消息而变化。同样，在零知识证明中，你的证明字符串也会随着你所证明的输入和输出的变化而改变。

一般情况下，零知识计算的形式如下：

Copy
prove(inputs, algorithm_description) -> (encrypted_inputs, proof, public_output)
verify(encrypted_inputs, proof, algorithm_description) == public_output

一个更有趣的例子是在像 zcash 这样的加密货币中进行资金转移。每一笔转移资金的交易都是一次状态转换，这本身就是一种计算。公开输出是总供应量（在不考虑矿工奖励的情况下保持不变）。加密输入则是地址之间的余额转账。

既然零知识证明只是计算，它们就很自然地适合用编程语言来描述。还记得前面提到的乘法算法的程序化描述吗？它可以方便地用传统编程语言来表示，然后在后台编译成“月球数学”。

废话不多说，以下是零知识编程语言的列表。

Circom，由 iden3 开发

如果你拥有电气工程背景，那么恭喜你。在零知识证明中，表示计算的主要方式是布尔电路。布尔电路实际上是庞大的数学方程，因此它们很容易转换为在后台运行的月球数学方程。

你可能会想，如果零知识是用电路表示的，那么像哈希算法或 for 循环这样的操作是如何执行的呢？这需要多个步骤，而电路则是一次性计算出结果的。

这是通过将每个步骤视为一个单独的电路并为每个步骤提供一个证明列表来实现的。这对我们来说很幸运，因为用电路来描述大多数计算是非常具有挑战性的。

幸运的是，我们不必自己实现 ALU（算术逻辑单元），Circom 在其之上提供了一层抽象。以下是将两个数字相加的代码

Copy
pragma circom 2.0.0;

template Add(){
    //Declaration of signals
    signal input in1;
    signal input in2;
    signal output out;
    out <== in1 + in2;
}

component main {public [in1,in2]} = Add();

这些模板允许你将构建块组合在一起，以执行更复杂的操作，例如拼接字节串、椭圆曲线算术或哈希函数。

Zokrates

如果用六行代码把两个数字相加让你望而却步，幸运的是，还有更高级别的抽象。以下是 Zokrates 的实现方式。

Copy
def main(field x, field y) -> field {
    field z = x + y;
    return z;
}

为什么零知识编程语言将数字称为域（fields）？零知识证明中的数学运算总是对一个大质数进行取模（正如大多数密码学算法一样）。这里的术语“域”是“有限域”的简称，因为数字可能取值的数量是有限的。具体来说，它是你进行模算术运算的质数的大小。

显然，在不透露两个数字的情况下证明你知道它们的和并没有多大意思。下面结合开头提到的例子，展示一个更好的应用。

Zokrates 中的零知识身份证

零知识证明身份证算法

经过一些修改，我们可以让零知识身份证运作起来。

首先，如果没有权威机构验证你出生于特定日期，是不可能证明你的年龄的。但这里有一种方法，可以将对某个事实的了解转化为对某个计算的证明。

政府会获取你的生日、公民身份证号以及一个随机盐值（salt）。他们将这些字符串拼接在一起，对其进行哈希处理，并对哈希摘要进行数字签名。当你去某个机构订购需要证明你已年满 21 岁的物品时，你需要提供你加密后的生日、加密后的公民身份证号、加密后的随机盐值、政府签名的哈希值以及字节串证明。

其目标是证明你能正确执行该算法以生成带有签名的哈希值。

通常情况下，你无法将加密值拼接在一起并恢复出带有签名的哈希值，但这正是零知识编程的用武之地。你实际上并没有对加密输入进行哈希处理，而是在不泄露输入的情况下，证明你正确地进行了计算。

在 Zokrates 中，这看起来异常易用：

Copy
import "hashes/sha256/512bitPacked" as sha256packed;

def main(private field birthday,
         private field citizenId,
         private field salt,
         public requiredBirthday,
         public field hashFirst128bits,
         public field hashSecond128bits) {

    field[2] hash = sha256packed([birthday, citizenId, salt]);
    assert(hash[0] == hashFirst128bits);
    assert(hash[1] == hashSecond128bits);
    assert(birthday < requiredBirthday);
    return;
}

// the signature for the hash would be validated in a traditional way

这看起来并不可怕，不是吗！？我们正在确保秘密值的哈希结果符合预期的哈希值，并确保对应于生日的输入达到了阈值。

有一点非常引人注目：下面这行代码

Copy
assert(birthday < requiredBirthday)

在 birthday 被加密的情况下是如何执行的？

这段代码被编译成了数学公式，在这里它实际上是有意义的——它并不是以我们通常认为的方式被“执行”的。同样地，哈希电路实际上并没有对输入进行哈希处理。它只是在验证加密输入与作为底层电路及随附证明函数的公开哈希输出之间的一致性。

Zokrates 的原始白皮书，发表于 IEEE 2018 (http://www.ise.tu-berlin.de/fileadmin/fg308/publications/2018/2018_eberhardt_ZoKrates.pdf)

Leo

Aleo blockchain 是一个专注于隐私的智能合约链，而 Leo 是其主要的编程语言。你可以在他们的在线 Playground中体验这门语言是什么样的。

在撰写本文时，仅推出了测试网（testnet）。

下面是该语言将两个数字相加的示例。

Copy
program helloworld.aleo {
  transition main(public a: u32, b: u32) -> u32 {
      let c: u32 = a + b;
      return c;
  }
}

Leo 白皮书/学术论文：https://eprint.iacr.org/2021/651.pdf

Layer Two 应用

尽管零知识证明以隐私性闻名，但它们在区块链可扩展性方面也有强大的用例。请记住，验证者实际上无法将加密的输入进行哈希处理或相加并获得合理的结果。他们只是验证输入、输出、电路和证明是否一致。

有趣的是，在计算上，证明一致性比执行实际计算要容易得多。这意味着组装交易的区块生产者承受了相当大的计算负担，因为他们必须执行计算并生成证明，但其他正在验证所提议区块的验证者要做的工作却少得多，因为他们只需要验证证明，这在渐近复杂度上要容易得多。

共识并不是在区块产生时达成的，而是在网络中超过三分之二的节点同意该区块有效时达成的。他们必须执行的计算量越大，达成共识所需的时间就越长，这就导致了吞吐量瓶颈。

由于这个用例是为了快速验证而优化的，你不应该假设这些操作默认是私密的。除非明确说明，否则以下语言的实现不一定是为了保护隐私而优化的。

Noir，由 Aztec 开发

Noir 是 Aztec 的语言，Aztec 是一个专注于隐私的 Ethereum L2。其语法深受 Rust 启发；甚至构建工具也被称为“nargo”，显然是在致敬 Rust 的 cargo。

下面是 Noir 将两个数字相加的示例

Copy
fn foo(x : Field, y : Field) -> Field {
    x + y
}

如果你想知道为什么 return 语句不见了，那是因为在 Rust 以及 Noir 中，没有分号的语句会被解释为函数的返回值。

Cairo，由 Starkware 开发

Starknet 是另一个 L2。

这个名字是 CPU 代数中间表示（CPU Algebraic Intermediate Representation）的缩合词。中间表示语言旨在“仅略高于汇编”，但在零知识证明中，“汇编”就是用于证明零知识的代数公式。

C 或 C++ 开发者（或是习惯使用汇编的 Solidity 开发者）会对这门语言感到亲切，因为它相对底层。这里是 Cairo 的 Playground。

遵循传统，Cairo 将数字称为“域（fields）”，但将其称为“域元素（field elements）”，在语法中被缩写为“felt”（field + element）。

下面是 Cairo 将两个数字相加的示例

Copy
%builtins output

// Import the serialize_word() function.
from starkware.cairo.common.serialize import serialize_word

func main{output_ptr: felt*}() {
    tempvar x = 12;
    tempvar y = 14;
    tempvar z = x + y;
    serialize_word(z);
    return ();
}

Cairo 白皮书：https://eprint.iacr.org/2021/1063.pdf

Solidity

没想到会在这里看到它吧？！

你可能听说过一些关于 Polygon 和 Matter Labs 正在开发的“zk evms”的炒作。该炒作的亮点在于，你可以将原生的 Solidity 编译为常规的 EVM 字节码，并同时生成一个零知识证明来证明你正确执行了该字节码。这当然需要一个专门的虚拟机，这些公司倾向于将其打造成“zk evm”的某种变体品牌。

你可以将 EVM 的状态视为由两个数组表示：栈（stack）和内存（memory）。每一个操作都会改变栈和/或内存。每一步都是一个证明，证明你改变状态的方式与刚刚执行的操作码（opcode）以及之前的状态是一致的。

由于这项创新，Solidity 可能会在很长一段时间内保持其相关性，因此请查看我们的 Solidity 训练营! 这是参加我们 zero knowledge 训练营的先决条件。

我应该使用哪一个，以及更多资源

如果你计划在 Aleo、Starknet 或 Aztec 上进行开发，你必须使用它们各自的语言。但如果你打算在 Ethereum 上开发一个专注于隐私的智能合约，你需要使用 Circom 或 Zokrates。目前，Noir 对编译为 Solidity 也有有限的支持。

虽然直接跳转到使用比 Circom 更友好的语言可能很诱人，但培养对电路编程如何运作的直觉是值得的。毕竟，这里的语言最终都会编译成与之类似的东西。你会注意到该列表中排在 Circom 之后的语言中存在一些奇怪的约束，除非你了解底层发生了什么，否则这些约束是没有意义的。例如，在 Zokrates 中，“if”语句的所有分支都会被执行，而在 Cairo 中内存是无法被覆盖的。

要想温和地了解零知识证明背后的数学原理是不可能的，但任何学过微积分预备课程或基础密码学课程的人，应该都能看懂这篇论文。

练习零知识谜题

如果你想温和地入门 Circom，请阅读他们的文档，并尝试解决我们开源的 Zero Knowledge Puzzles。

最初发表于 2022 年 12 月 22 日