译自 halo2 book：concepts/proofs.md

证明系统

任何证明系统(proof system)的目标都是能够证明有意思的数学或密码学陈述(statement)。

通常，在一个给定的协议中，我们会想要证明一族陈述，这些陈述的区别在于它们的公开输入(public inputs)。证明者(prover)还需要表明他们知道某些使该陈述成立的私有输入(private inputs)。

为此，我们写下一个关系(relation) $\mathcal{R}$，它指定了公开输入与私有输入的哪些组合是有效的。

上述术语意在与 ZKProof Community Reference 保持一致。

准确地说，我们应当区分关系 $\mathcal{R}$ 与它在证明系统中所用的实现。我们称后者为电路(circuit)。

我们用来为特定证明系统表达电路的语言被称为算术化(arithmetization)。通常，一种算术化会以某个域(field)上变量的多项式约束(polynomial constraints)的形式来定义电路。

将某个特定关系表达为电路的这一_过程_有时也被称为“算术化”，但我们会避免这种用法。

为了创建对某个陈述的证明，证明者需要知道私有输入，以及电路所使用的中间值，这些中间值被称为***建议(advice)***值。

我们假设可以根据私有输入和公开输入高效地计算出建议值。具体的建议值取决于我们如何编写电路，而不仅仅取决于高层的陈述。

私有输入与建议值合起来被称为见证(witness)。

有些作者把“见证”仅仅当作私有输入的同义词。但在我们的用法中，见证包含建议值，即它包含证明者提供给电路的所有值。

例如，假设我们想要证明知道一个哈希函数 $H$ 对于摘要 $y$ 的某个原像(preimage) $x$：

• 私有输入是原像 $x$。

• 公开输入是摘要 $y$。

• 关系是 $\{(x,y):H(x)=y\}$。

• 对于某个特定的公开输入 $Y$，陈述是：$\{(x):H(x)=Y\}$。

• 建议值是实现该哈希函数的电路中的所有中间值。见证则是 $x$ 加上建议值。

非交互式论证(Non-interactive Argument)允许证明者(prover)为给定的陈述和见证创建一个证明(proof)。证明是一些数据，可用来使验证者(verifier)相信：_存在_一个见证使该陈述成立。使这类证明无法虚假地说服验证者的那条安全性质称为可靠性(soundness)。

非交互式知识论证(Non-interactive Argument of Knowledge)（NARK）进一步使验证者相信证明者_知道_一个使该陈述成立的见证。这条安全性质称为知识可靠性(knowledge soundness)，它蕴含可靠性。

在实践中，知识可靠性对密码学协议比可靠性更有用：例如，若我们关心 Alice 在某个协议中是否持有一个密钥，我们需要 Alice 证明_她知道_这个密钥，而不仅仅是它存在。

知识可靠性的形式化表述是：必须存在一个能够精确观察证明是如何生成的提取器(extractor)，它能够计算出见证。

鉴于证明可能是可塑的(malleable)，这条性质相当微妙。也就是说，依赖于具体的证明系统，可能可以在不知道见证的情况下，取一个已有的证明（或一组证明）并对其进行修改，从而产生一个针对相同或相关陈述的不同证明。使用可塑证明系统的更高层协议需要把这一点考虑进去。

即便没有可塑性，证明也可能被重放(replayed)。例如，在我们的例子中，我们不希望 Alice 能够出示由别人生成的证明，并使其被当作她知道该密钥的凭证。

如果一个证明除了表明见证存在且为证明者所知之外，不泄露关于见证的任何信息，那么我们就说该证明系统是***零知识(zero knowledge)***的。

如果一个证明系统产生简短的证明——即长度关于电路规模是多对数(polylogarithmic)的——那么我们就说它是简洁(succinct)的。简洁的 NARK 被称为SNARK（简洁非交互式知识论证(Succinct Non-Interactive Argument of Knowledge)）。

按照这个定义，SNARK 不一定要求验证时间关于电路规模是多对数的。有些论文用***高效(efficient)***一词来描述具有该性质的 SNARK，但我们会避免使用这个词，因为对于支持摊销式或递归式验证的 SNARK（后面会谈到），它含义不清。

zk-SNARK 是一种零知识的 SNARK。