零知识证明

起源

零知识证明（ZKPs）的概念最早由Shafi Goldwasser、Silvio Micali和Charles Rackoff在他们在1980年的重要论文交互式证明系统的知识复杂性中首次提出。

尽管被视为理论上的突破，当这个想法诞生时，甚至密码学界也将该方案标记为在实践中不可能的。由于近年来许多突破，特别是许多Web3项目如ZCash和Aztec的贡献，我们已经看到了零知识证明系统性能的摩尔定律式提升。

什么是零知识证明系统？

零知识证明系统是一种协议，通过该协议，某人（证明者）可以向他人（验证者）证明某个语句的正确性，而无需透露任何额外信息。它由以下元素组成并满足以下属性。

零知识证明系统的要素

• 语句：我们要证明真实性的语句。
• 公共输入：证明者和验证者都可获得的信息。
• 证人：只有证明者知道的足以证明该语句的信息。证明者希望将此信息对验证者保密。
• 证明：由证明者从语句、公共输入和证人中派生的信息，可根据语句和公共输入验证以测试声明的真实性。

零知识证明系统的属性

通常，零知识证明系统必须满足以下3个关键属性：

• 完备性：一个诚实的证明者可以使验证者相信他/她所知的任何语句。
• 可靠性：计算能力有限的证明者不能放弃可以说服诚实验证者的证明。
• 零知识性：证明不泄露除语句本身的真实性以外的任何信息。

示例

为了更好地说明ZKP系统，让我们在有限域$\mathbb{F}_7$中运行一个简单的例子。

• 语句：$2$是$\mathbb{F}_7$中的一个平方数
• 公共输入：$x = 2$。
• 证人：$w = 4$，因为在$\mathbb{F}_7$中$4^2 = 2$。

协议包括以下步骤：

1. 证明者选择一个随机非零的$a \in \mathbb{F}_7$并向验证者发送$y = a^2$。
2. 验证者选择$b \in {0, 1}$并将其发送给证明者。
3. 证明者向验证者发送证明$\pi = w^b a$。
4. 验证者接受证明，如果$\pi^2 = x^b y$。

然后，他们根据不同的$a$值重复上述协议，直到验证者确信。

让我们检查上述协议是否满足所需的属性：

1. 完备性：显而易见，因为$\pi^2 = w^{2b} a^2 = x^b y$。
2. 可靠性：不诚实的证明者可能会尝试通过在步骤1中发送一个不是平方的$y$来欺骗验证者。在这种情况下，当验证者选择$b = 0$时，他们将在一半的情况下拒绝证明。如果$y$是一个平方，但$x$不是，当$b = 1$时，验证者将拒绝证明。不诚实的证明者在每次迭代中都有$1/2$的概率欺骗协议，因此通过足够次数的迭代，可以使此概率变得可以忽略。
3. 零知识性：如果$b = 0$，证明者在证明的任何时候都不使用$w$，因此它不能泄露。如果$b=1$，证明者仅在$\pi = w a$中使用$w$，而验证者在不知道$a$的情况下无法提取$w$。只要证明者不对相同的$a$重复上述协议以获取不同的$b$，协议就保持零知识性。

知识的简洁非交互性论证（SNARKs）

一种特别重要的ZKP系统是SNARKs，满足以下额外属性：

• 知识性论证：证明者想要证明对证人本身的知识。在上述例子中，语句将是“我知道在$\mathbb{F}_7$中$2$的平方根”。可以展示上述协议也证明了这个更强的语句，因此使其成为知识性论证。

• 简洁性：与语句的电路大小（即计算量）相比，证明大小是常数或对数。上述协议也是简洁的，因为证明只是$\mathbb{F}_7$中的一个数字。

• 非交互性：证明生成和证明验证在两个连续的回合中发生：首先证明者运行一个函数$\textsf{prove}$生成一个证明，然后验证者运行一个函数$\textsf{verify}$来验证它。上述协议是交互式的，即它不满足这个属性，因为证明者和验证者之间有持续的通信。

设置

SNARKs需要额外的元素才能得到正确的定义

• 设置：用于执行$\textsf{prove}$和$\textsf{verify}$函数的一组生成和验证密钥。

在基于配对的证明系统（如Groth16）中，设置包括一组椭圆曲线点，这些点由随机采样的种子生成，更常见地称为有毒废物。对此种子的了解允许攻击者为虚假语句制造有效的ZKP，因此生成密钥的过程的安全执行是至关重要的，即没有人知道用于生成它们的有毒废物。这通常通过称为可信设置的多方计算来完成。

SNARK的简单定义

一旦所有元素都固定，SNARK被定义为一对函数

• prove(Setup, Public Input, Witness) -> Proof：使用公共输入和证人生成知识的证明。
• verify(Setup, Public Input, Proof) -> bool：根据公共输入验证证明。