概念速查

VC (Verifiable Computation)

可验证计算

数学证明(Mathematical Proof)

既对于一个问题，Prover 能够给出一个证明，使得 Verifier 能够通过该证明确认问题的正确性。

证明系统(Proof system)

A “proof system” is any procedure that decides what is and is not a convincing proof. That is, a proof system is specified by a verification procedure that takes as input any statement and a claimed “proof” that the statement is true, and decides whether or not the proof is valid.

完备性(Completeness)

Any true statement should have a convincing proof of its validity.This property is typically referred to as completeness.

可靠性(Soundness)

No false statement should have a convincing proof. This property is referred to as soundness.

IP (Interactive Proofs)

交互式证明，简单说，对于一个问题，Prover 和 Verifier 通过多轮交互来完成证明过程，具体来说，对于一个数独或者图着色问题的证明就是交互的。

对于一个函数 $f$ 的论证系统是 $f$ 的交互式证明，并且只需在多项式时间下保证Prover 的不可伪造性。

论证系统(Argument Systems)

论证系统属于IP，但是只能保证在仅拥有多项式时间 (PPt) 能力的Prover不能欺骗并说服一个Verifier接受他的证明。简单来说，可以把其视作一个密码系统，对于拥有有限计算力的Prover显然无法欺骗Verifier。

PCP (Probabilistically Checkable Proofs)

概率可检验证明，既对于一个系统，Verifier 只需要随机检查证明的一小部分就能决定是否接受该证明，并且Prover作恶的概率是可忽略的。

IOP(Interactive Oracle Proofs)

交互式预言机证明

一元拉格朗日插值与低度扩展

Details

拉格朗日插值是一种通过已知的数据点构造多项式的方法。给定 n+1 个不同的点 $(x_0,y_0),(x_1,y_1),...,(x_n,y_n)$，拉格朗日插值公式可以构造一个次数不超过 n 的多项式 $P(x)$，使得 $P(x_i)=y_i$。

拉格朗日插值多项式的公式为：

$$P(x)=\sum _{i=0}^n{y}_i\cdot L_i(x)$$

其中 $L_i(x)$ 是拉格朗日基多项式：

$$L_i(x)=\prod _{j=0,j\ne i}^n\frac{x-x_j}{x_i-x_j}$$

简单理解：假设对于有三个点 $(x_1,y_1),(x_2,y_2),(x_3,y_3)$，显然我们的思想是让 $P(x_i)=y_i$，既在取值 $y_i$ 时最好只有 $L_i(x)$，显然容易构建：

$$L_1(x)=\frac{(x-x_2)(x-x_3)}{(x_1-x_2)(x_1-x_3)}$$

显然只有当 $x=x_1$ 时，$L_1(x)=1$ 并且不为零，故而得到 $P(x_1)=y_1\ast 1=y_1$，而在 $x=x_2$ 或 $x=x_3$ 时，$L_1(x)=0$，故而 $P(x_2)$ 和 $P(x_3)$ 不包含 $y_1$ 的影响。

低度扩展 (Low Degree Extension，LDE)

故而，对于一个 $n$ 次多项式 $P(x)$，我们可以用一个向量 $a=<a_0,a_1,...,a_{n-1}>$ 来表示其系数从而表示出一个多项式；但是，有了拉格朗日插值，我们也可以通过对 $n$ 个点的评估 $<P(x_0),P(x_1),...,P(x_{n-1})>$ 来表示该多项式，记为 $q_a(X)$。这里的 $q_a(X)$ 就是 $a$ 的单变量低度扩展。

Evaluations

评估，或者我更喜欢称为多项式求值&赋值， 即对于一个多项式 $P(x)$ 和一个点 $x=a$，计算 $P(a)$ 的值。由于在前面我们知道通过插值可以恢复一个多项式，故而对于一个 n 次的多项式，我们也可以用其 n 个评估来表示，或者说编码一个多项式。

Schwartz-Zippel 引理

Details

对于一个 $m$ 元多项式 $g$, 其次数 $deg(g)=d$, 则有：

$$P{r}_{x\leftarrow S^m}[g(x)=0]\le \frac{d}{|S|}$$

其中，$S$ 指多项式所在域的元素集合，$|S|$ 表示集合的大小， $x\leftarrow S^m$ 表示 $x$ 是从 $S$ 中均匀随机选择的 $m$ 维向量。

如果 $x$ 是随机均匀选取的，那么 $g(x)=0$ 的概率至多为 $d/|S|$。

特别地, 如果在 $S^m$ 上选取两个不同的次数最多为$d$多项式，二者最多只有 $(\frac{d}{|S|}\times |S^m|)$ 个点相同， 既 $g_1(x)-g_2(x)$ 最多只有 $d\times |S^{m-1}|$ 个根。

这对我们对于后面构建证明系统非常关键，因为如果我们想要证明两个多项式 $g_1(x)$ 和 $g_2(x)$ 相等，我们只需要随机选择一个点 $x$ 并检查 $g_1(x)=g_2(x)$。根据 Schwartz-Zippel 引理，如果 $g_1(x)$ 和 $g_2(x)$ 不相等，那么它们在随机选择的点上相等的概率至多为 $d/|S|$。通过多次独立选择点并进行检查，我们可以将错误接受不相等多项式的概率降低到一个可忽略的水平。