1

P vs NP 及其在零知识证明中的应用

RareSkills 的 Zero Knowledge Proofs 系列文章之《P vs NP 及其在零知识证明中的应用》。

2

ZK的算术电路

文章介绍了在零知识证明中使用的算术电路（Arithmetic Circuits）与布尔电路（Boolean Circuits）的对比，并展示了如何将算术电路用于求解NP问题。文章详细解释了算术电路的原理、实现方法，并提供了多个具体示例，如三色图问题和排序列表问题。

3

用于零知识证明的有限域与模运算

本文详细介绍了有限域在零知识证明电路中的应用，包括有限域的定义、模运算、加法逆元、乘法逆元等概念，并通过代码示例展示了如何在Python中实现这些操作。

4

为程序员准备的基础集合论

RareSkills 的 Zero Knowledge Proofs 系列文章之一，介绍了集合论的基础知识。翻译的过程中完成了其中的练习题。

5

抽象代数

本文介绍了抽象代数中的基本概念，如群、半群和 Monoid ，并解释了它们在零知识证明中的应用。

6

程序员的基本群论

本文详细介绍了代数群的基本概念，通过多个例子帮助读者建立对群的直觉，包括群的定义、阿贝尔群、有限群、循环群等，并探讨了这些群在零知识证明中的应用。

7

同态映射

本文通过多个例子详细解释了同态映射的概念，并探讨了其在加密技术和零知识证明中的应用。文章结构清晰，分为简单和复杂例子两部分，并附有详细的数学公式和Python代码示例。

8

椭圆曲线点加法

本文详细介绍了椭圆曲线加法在实数域上的工作原理，通过群论的角度解释了椭圆曲线点的加法操作，并展示了如何在椭圆曲线上进行点加法的具体公式和几何解释。文章还包括了代码示例和数学公式，深入探讨了椭圆曲线的代数性质。

9

有限域上的椭圆曲线

文章详细介绍了有限域上的椭圆曲线，包括它们的绘制、数学性质以及在密码学中的应用。通过多个示例和代码，展示了如何生成和操作这些曲线，并解释了其与有限域的循环群特性。

10

Python、Solidity 和 EVM 中的双线性配对(Bilinear Pairings)

这篇文章深入探讨了双线性映射（bilinear pairings）的原理及其在密码学中的应用，特别是在验证乘积的离散对数时。

11

将代数电路转换为R1CS（一阶约束系统）

文章详细介绍了如何将一组算术约束转换为Rank One Constraint System (R1CS)，涵盖了转换中的优化和Circom库的实现方法。

12

从R1CS构建零知识证明

文章详细介绍了如何通过将Rank 1 Constraint System (R1CS)中的见证向量转换为有限域椭圆曲线点，并使用双线性配对来实现零知识证明。文中还讨论了验证步骤的实现细节，并指出了该算法在实际应用中的低效性。

13

使用Python实现拉格朗日插值

介绍了拉格朗日插值法，通过一组点计算一个经过这些点的多项式，并提供了Python代码示例。

14

Schwartz-Zippel 引理及其在零知识证明中的应用

文章详细介绍了Schwartz-Zippel Lemma在零知识证明（ZK-Proof）中的应用，通过多项式例子和Python代码展示了如何利用该引理进行多项式相等性测试和向量相等性测试。

15

二次算术程序

文章详细介绍了二次算术程序（QAP）的概念及其在零知识证明中的应用，特别是如何通过拉格朗日插值将Rank 1约束系统（R1CS）转换为QAP，并通过Schwartz-Zippel引理在O(1)时间内验证QAP的等式。

16

在Python中将R1CS转换为有限域上的二次算术程序(QAP)

本文详细介绍了如何将R1CS（Rank 1 Constraint System）转换为QAP（Quadratic Arithmetic Program），并通过Python代码演示了实现过程，包括有限域算术、多项式插值等关键步骤。

17

可信设置

文章介绍了ZK-SNARKs中使用的可信设置机制，详细解释了如何在保密值上计算多项式，并提供了Python代码示例。

18

在可信设置中评估和二次算术程序

本文详细介绍了如何在可信设置的基础上评估二次算术程序（QAP），并解释了如何在不泄露证据的情况下证明QAP的满足性，使用恒定大小的证明。同时还涉及了R1CS、椭圆曲线配对等技术的详细实现。

19

Groth16 详解

本文详细介绍了Groth16零知识证明算法的原理、实现及其应用，包括可信设置、证明生成和验证的步骤，并讨论了防止伪造证明的方法以及算法中的安全问题。

20

Circom 零知识电路简介

本文介绍了 Circom 编程语言，它用于创建 Rank 1 Constraint Systems (R1CS) 并填充 R1CS 的 witness 向量，主要是为了简化约束系统的设计和自动化 witness 的生成。文章还解释了 Circom 存在的意义，以及它如何帮助开发者更轻松地进行零知识证明相关的开发，最后说明了学习 Circom 的理由，并概述了资源结构，包括语法和约束设计。

21

Circom 之 Hello World

本文介绍了Circom代码与其编译成的Rank 1 Constraint System (R1CS)之间的关系，并通过几个例子详细解释了如何在Circom中编写约束，以及如何使用Circom命令行工具编译电路、生成witness，并验证电路的正确性。文章还介绍了zkRepl在线IDE的使用，以及Circom中有限域的概念，以及如何将snarkjs导出的R1CS约束转换为Circom中的原始约束。

22

Circom模板参数、变量、循环、If语句、断言

本文介绍了Circom中定义Rank 1约束系统(R1CS)的基本语法，包括模板参数的使用、循环和变量的声明与应用、以及如何在满足特定条件时生成约束。此外，还强调了在Circom中约束必须是静态的，不能依赖于信号动态改变，但变量可以作为常量参与R1CS运算，并解释了`if`语句在Circom中的使用限制，着重介绍了 variables 的使用方法，以及 signals 的使用限制。

23

二次约束 - Circom

本文介绍了Circom中Rank 1约束系统的规则，即每个约束最多只能有一个信号间的乘法，超过则会报错。文章通过正反例解释了这一规则，并说明了常量乘法、加法、减法是被允许的。此外，还解释了Circom如何处理除法，以及为何数组索引、模运算、左移等操作不被允许。最后总结了约束系统的限制，并提及了绕过这些限制的设计模式。

24

Circom中的符号变量

本文介绍了Circom中的符号变量，它是被赋值为信号值的变量，常用于在循环中对信号求和。文章解释了符号变量的定义、使用场景，例如校验数组求和、校验二进制表示，以及如何避免因符号变量导致的二次约束冲突。此外，还阐述了非符号变量在模运算和位移操作中的使用限制，以及符号变量在循环边界和条件判断中的禁用。

25

Circom 中间信号与子组件

本文介绍了 Circom 中的 `<==` 和 `==>` 操作符，它们用于在电路中自动计算和赋值中间信号，从而避免手动提供所有信号作为输入。文章还展示了如何使用模板将电路拆分成更易于管理的模块，以及如何在组件之间传递结果。此外，还强调了组件的输出信号必须被约束使用，以防止恶意证明者篡改。

26

先指示再约束 - 在 Circom 中复杂约束条件的方法

本文介绍了在 Circom 中使用 indicator signals 和 Circomlib comparator library 来实现复杂约束条件的方法。

27

先计算，后约束 - ZK 电路设计模式

本文介绍了零知识电路中的“计算后约束”设计模式，它首先在没有约束的情况下计算算法的正确输出，然后通过强制执行与算法相关的约束来验证解决方案的正确性。

28

Circom循环中的组件

本文介绍了在 Circom 中如何在循环中使用组件。由于 Circom 不允许在循环中直接实例化组件，文章提供了通过预先声明组件数组并在循环内指定组件类型的方式来解决这一问题，并提供了三个实际案例：求数组最大值、检查数组是否已排序以及确保数组中所有元素都是唯一的，展示了如何在循环中有效地使用 Circom 组件，以及一些使用 circom 的小技巧。

29

使用虚假证明攻击欠约束的Circom电路

本文深入探讨了 Circom 中的 `<--` 操作符的一个潜在漏洞，展示了如何通过创建伪造的见证文件来利用这一漏洞，从而违背开发者对电路期望的假设。在详细的步骤中，介绍了生成有效证明的过程，以及如何修改二进制见证文件以实现攻击。此漏洞的理解对于开发安全的电路至关重要。

30

Circomlib中的AliasCheck和Num2Bits strict

本文探讨了 Circom 中的 alias bug 及其潜在安全隐患，介绍了如何通过溢出特定的域元素大小（p）来伪造证明。文中给出了该漏洞的示例代码，并介绍了如何通过严格的 Num2Bits 和 Bits2Num 函数，使得编码的二进制数组不会超过 p，从而避免此类攻击，同时还描述了挑战中的漏洞及其利用方式。

31

Circom 中的条件语句

本文深入探讨了 Circom 中 if 语句的使用限制，明确指出信号不能用于改变 if 语句的行为，也不能在依赖于信号的 if 语句中赋值。

32

Quin Selector(选择器)

本文介绍了Quin Selector这一设计模式，它允许使用信号作为信号数组的索引。文章通过代码示例，展示了如何在Circom中实现Quin Selector，并讨论了优化方法。同时，文章还提到了Circomlib库中的multiplexer组件，它可以实现类似的功能，并提供了一个使用示例。最后，文章提到了该算法的历史渊源。

33

ZK 中有状态计算简介

文章介绍了在算术电路中进行迭代计算（如幂、阶乘或计算斐波那契数列）时，如何通过预先计算所有可能的值并使用 Quin 选择器来解决条件停止的问题。文章通过阶乘和斐波那契数列的例子，展示了如何在 Circom 中实现这种方法，并强调了约束的重要性，最后提供了一个关于幂运算的练习。

34

在Circom中交换数组中的两个条目

本文介绍了如何在Circom中交换信号列表中的两个信号，这是排序算法的重要子程序，并解释了在ZK电路中执行此操作的复杂性，由于信号的不可变性，需要创建一个新数组并将旧值复制到新数组，在特定条件下进行修改，文章还指出了代码中的一个错误，即未考虑s等于t的情况，并提供了修复方案，最后总结了在Circom中操作数组的通用模式。

35

选择排序的零知识证明

本文介绍了如何在零知识电路中证明选择排序算法的正确执行过程。由于ZK电路中信号的不可变性，每次交换都需要创建一个新的列表快照。为此，文章详细展示了如何通过多个中间状态的转换来证明排序的正确性，包括查找子列表中最小值的索引、交换列表中的两个元素等关键步骤, 并提供相应的代码模版。

36

在 ZK 中建模栈数据结构 - 如何在 Circom 中创建一个堆栈

本文详细介绍了如何在 Circom 中创建一个栈数据结构，以及如何使用零知识证明（ZK proofs）来验证栈的操作，包括 push、pop 和 no change。通过定义栈的最大高度和使用栈指针（stack pointer）来跟踪栈的使用情况，并详细描述了在不同操作下栈状态的转换和约束。

37

ZKVM 的工作原理

本文介绍了零知识虚拟机（ZKVM）的概念，它能创建零知识证明来验证机器指令的正确执行。文章通过一个简化的栈式ZKVM示例，展示了如何使用Circom实现基本的算术运算，并探讨了提高ZKVM效率的现代方法，如查找表和递归证明。 ZKVM在零知识Layer2区块链中至关重要，并可用于验证机器学习算法的正确执行。

38

ZK中的32位仿真

本文介绍了如何在零知识证明（ZK）电路中模拟32位算术运算，由于ZK默认数据类型是有限域元素，而实际计算常用32位、64位或256位数字，因此需要用域元素来模拟传统数据类型。文章详细讲解了32位范围检查、加法、乘法、除法与取模、位移以及位运算的实现方法，并提供了相应的Circom代码示例，同时还讨论了ZK EVM如何处理256位数字。

39

Circom 中的 MD5 哈希

本文详细介绍了如何在 Circom 中实现 MD5 哈希算法，包括计算哈希值和约束其正确性。文章首先介绍了 MD5 哈希的原理和步骤，然后展示了如何在 Circom 中构建实现 MD5 哈希所需的各种组件，如位运算、循环左移、32 位加法以及初始填充。并通过一个python的例子，展示了MD5哈希的计算过程。

40

零知识证明友好的哈希函数

本文介绍了在零知识证明友好的哈希函数，重点介绍了Minimal Multiplicative Complexity (MiMC) 和 Poseidon 这两个流行的 ZK 友好哈希函数的工作原理和性能, 并对比了他们的优劣. 此外还提及了基于椭圆曲线的Pedersen哈希，并指出了以太坊基金会悬赏征集MiMC哈希碰撞，以及对Poseidon安全性的研究。

41

排列论证 - The Permutation Argument

本文档介绍了使用排列参数证明两个列表包含相同的元素，但顺序可能不同的证明。

42

Tornado Cash 的工作原理（开发者逐行解析）

本文详细介绍了Tornado Cash的工作原理，包括零知识证明、Merkle Tree的使用以及如何实现匿名加密货币转账。文章还讨论了Tornado Cash的智能合约架构、合法性问题以及潜在的安全风险。

43

BulletProofs 详解

该文章深入探讨了Zero Knowledge Bulletproofs的概念，详细介绍了其原理、实现及应用。文章结构清晰，搭配丰富的数学公式和代码块，适合希望了解零知识证明的开发者和研究者。

44

什么是Pedersen承诺及其工作原理

Pedersen承诺是一种密码学技术，允许在不暴露向量内容的情况下对其进行编码，广泛应用于零知识证明和区块链技术中。本文深入探讨了Pedersen承诺的原理、构建、优点和应用，包括对内部乘积和矢量承诺的解释，适合对密码学有一定了解的读者。

45

多项式承诺通过 Pedersen 承诺实现

本文详细介绍了多项式承诺机制的原理和实现，特别是如何使用Pedersen承诺和椭圆曲线来验证多项式在特定点的估值，而不泄露多项式本身。文章还讨论了验证步骤的工作原理和为什么验证者无法被欺骗。

46

零知识乘法

文章详细介绍了如何使用多项式承诺方案在零知识证明中验证多项式乘法的正确性，包括算法步骤和优化方法，并附有代码实现。

47

内积的零知识证明

本文详细介绍了如何在零知识证明中构造内积证明，通过向量多项式和内积计算，展示了如何在不泄露原始数据的情况下证明内积计算的正确性。文章还提供了相关算法的具体实现步骤，并指出如何进一步优化证明大小。

48

向量承诺的简洁证明

文章介绍了如何在不发送整个向量的情况下，证明已知 Pedersen 向量承诺的开启，并详细描述了算法的实现和安全问题。

49

对数大小的承诺证明

本文详细阐述了如何在零知识证明（ZKP）中通过递归折叠的方法，减少向验证者传输的数据量，从而高效地证明内积和向量的承诺。文章包括算法的详细描述、数学推导和代码实现。

50

Bulletproofs零知识证明：内积的零知识与简洁证明

本文详细介绍了Bulletproofs零知识证明算法，包括其在椭圆曲线上的内积证明实现。文章通过问题陈述、算法步骤以及非交互式证明等技术，系统地展示了如何在不泄露向量和内积的情况下进行高效证明。

51

内积代数

文章介绍了在推导范围证明和编码电路时，内积运算的一些有用代数技巧，并提供了每个规则的简单证明。

52

通过随机线性组合减少等式检查（约束）的数量

本文深入探讨了如何在零知识证明算法中利用随机线性组合来有效地检查多个等式的相等性。通过实例展示了Pedersen承诺的等式验证过程，并提出了一种减少通信开销的方法。这种技术能够实现对多个内积同时进行验证，从而提高效率。

53

范围证明

本文详细介绍了Bulletproofs在范围证明中的构建方法，通过验证向量aL的二值性和其与向量2n的内积来证明标量v的范围在2^n内。文章还展示了几种代数技巧，并通过Monero的使用实例说明了该技术的应用。