证明系统

证明系统 的目标是能够证明有趣的数学或者密码学论述.

通常，在一个给定的协议中，我们想要证明不同公共输入的一系列论述。证明者需要展示他们知道一些隐私输入，满足论述。

为此，我们描绘了一个关系，$\mathcal{R}$，这个关系指定哪些公共输入和隐私输入组合是有效的。

上面的术语和 ZKProof Community Reference 保持一致

准确地说，我们应该区分关系$\mathcal{R}$ 和它在证明系统中实现。后者我们称为电路。

我们用来表示特定证明系统的电路的语言叫做算术化。通常，算术化会以多项式约束的形式定义电路。这些约束作用于某个域上的变量。

将一个特定关系的表达成电路的过程有时也叫作 "算术化", 但是我们避免这种叫法。

为了生成一个论述的证明, 证明者需要知道电路需要的隐私输入以及中间值，这些称为advice。

我们假设我们能通过隐私和公开输入计算出advice。这些advice值依赖于我们实现的电路，而不仅仅取决于论述。

隐私输入和advice一起称为论据（ witness）。

有些作者将隐私输入看成论据, 但是在我们看来, 论据还包括advice，即论据包括证明者提供给电路的所有值。

举个例子, 假设我们想证明原像 $x$ 经过哈希函数 $H$ 得到摘要 $y$：

• 原像 $x$是隐私输入

• 摘要$y$是公开输入

• 关系为 $\{(x,y):H(x)=y\}$.

• 对于特定的公共输入 $Y$, 论述是$\{(x):H(x)=Y\}$.

• advice是实现哈希函数的电路中的所有中间值。论据是$x$和advice。

非交互式证明允许证明者对特定的论述和论据生成一个证明。证明可以使验证者相信存在论据使论述成立。这种证明不能错误地说服验证者的安全特性称为可靠性。

非交互式知识证明（NARK）进一步使验证者确信证明者知道使论述成立的论据。这个安全属性称为知识可靠性，它暗示了可靠性。

在实践中，对于密码协议来说，知识可靠性比可靠性更有用：如果我们对在某个协议中Alice是否持有密钥感兴趣，我们需要Alice证明她知道密钥，而不仅仅是密钥存在。

知识的可靠性是通过一个提取器来证明。提取器精确观察证明生成过程，能计算出论据。

如果证明是可塑的，这个性质有点微妙。 也就是说，有些证明系统，在不知道论据的情况下，在现有证明的基础上修改生成新的证明。使用了可塑证明系统的协议需要考虑这一点。

即使没有可塑性, 证明也很可能回放。举个例子，在我们的例子中，我们不希望Alice能够提交别人生成的证明，证明她知道密钥。

如果一个证明没有论据相关信息(除了论据信息存在和证明者知道这些信息外)， 我们说这样的证明系统是零知识的。

如果证明系统能生成简短的证明 - 相对电路大小多项式对数大小的话，我们说，证明是简洁的。 一个简洁的NARK叫做 snark(简洁的非交互式证明 - Succinct Non-Interactive Argument of Knowledge)。

根据这个定义, 一个SNARK不需要关于电路大小的多项式对数级验证时间。有些论文使用术语有效性（efficient）来描述具有这种性质的SNARK，但我们将避免使用这个术语，因为它对于支持聚合或递归验证的SNARK来说，语义是模糊的，我们稍后会讲。

zk-SNARK 叫做零知识SNARK。