概念速查

VC (Verifiable Computation)

可验证计算

证明和论证 (Proofs and Arguments)

• 证明，或者说交互式证明 (IP)，允许验证者交互式的从一个强大的Prover那里验证一个断言的正确性，例如可以允许一个移动设备检验一台超级计算机的运算正确性
• 论证：和证明相比允许不正确陈述的 "证明"，例如一个论证可能运用一个密码系统，如果这个密码系统被破解，那么就可以为一个错误陈述产生一个正确证明

数学证明(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 的不可伪造性。

当一个作弊证明者产生的错误断言说服验证者的概率小于 $\frac{1}{3}$ 时，我们说该系统是可靠的。

对于一个交互式证明系统，如果 $\mathcal{V}$ 和 $\mathcal{P}$ 交换的消息为 $k$ 条，则 $[k/2]$ 称为其轮复杂度。

论证系统(Argument Systems)

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

RS 指纹 (Reed-Solomon Fingerprints)

Frevialds 算法 (Freivalds' Algorithm)

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$ 的单变量低度扩展。

多线性扩展(Multilinear Extension, MLE)

多线性多项式的拉格朗日插值

计算优化，可略

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|$。通过多次独立选择点并进行检查，我们可以将错误接受不相等多项式的概率降低到一个可忽略的水平。

Sigma Protocols

$\sum \text{Protocol}$

Sigma 协议是一个三轮协议:

典型情况如 Schorr 协议：

1. Prover 选择随机数 $r$ 并计算承诺 $t=g^r$，将 $t$ 发送给 Verifier。
2. Verifier 选择随机挑战 $c$ 并发送给 Prover。
3. Prover 计算响应 $s=r+cx$ 并发送给 Verifier。
4. Verifier 验证 $g^s\stackrel{?}{=}t\cdot y^c$。

可以很容易地转换为非交互式：

1. Prover 计算承诺 $t=g^r$。
2. Prover 计算挑战 $c=H(t,g^r)$，其中 $H$ 是一个哈希函数。
3. Prover 计算响应 $s=r+cx$。
4. Prover 发送 $(t,s)$ 给 Verifier。
5. Verifier 计算挑战 $c=H(t,g^r)$ 并验证 $g^s\stackrel{?}{=}t\cdot y^c$。

Merkle