零知识证明零散笔记

零知识证明笔记

一、预备知识

1.1 Reed-Solomon编码

\(n\)个待编码的元素为\(\{a_0,\cdots,a_{n-1}\}\)，它们在点\(r\)处（\(r\in\mathbb F_p\)）的编码结果为 \[ f(r)=\sum^{n-1}_{i=0}a_i\cdot r^i \] 即把待编码元素看成系数，在\(r\)点对多项式求值。

1.2 单变量拉格朗日插值

对向量\((a_0,\cdots,a_{n-1})\in\mathbb F^n\)，存在系数为\(n-1\)的单变量多项式\(q(x)\)，满足 \[ q(i)=a_i,\quad i=0,\cdots,n-1 \]

1.3 单变量低次扩展编码

低次扩展：Low-degree Extension（LDE）

即单变量拉格朗日插值中的\(q(x)\)。

1.4 Schwartz-Zippel引理

对于两个在\(\mathbb F\)上总次数最大为\(d\)的\(m\)变量多项式\(p(x)\)和\(q(x)\)，\(p(x)=q(x)\)对于最多\(d/|\mathbb F|\)个输入成立。

这里的\(x\)可以是多变量的，如\(p(x_1,x_2)\)，所以说总次数最大为\(d\)。

1.5 多线性扩展（MLE）

Multi-Linear Extension

函数\(f:\{0,1\}^l\to\mathbb F\)有唯一的多线性扩展\(\tilde f\)（多线性多项式）。多线性是指每个变量的次数最大是\(1\)。

如对于\(f(0,0)=1,f(0,1)=2,f(1,0)=8,f(1,1)=10\)的多线性扩展为 \[ \tilde f(x_1,x_2)=(1-x_1)(1-x_2)+2(1-x_1)x_2+8x_1(1-x_2)+10x_1x_2 \]

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

即上面例子的更一般化方法。

二、交互式证明

2.1 Sum-check协议

对于多项式\(g(x_1,x_2,x_3)=2x_1^3+x_1x_3+x_2x_3\)， \[ H=\sum_{x_1,x_2,x_3\in\{0,1\}}g(x_1,x_2,x_3)=12 \]

开始

证明者发送\(C_1=12\)，声称它等于\(H\)。

第1轮

证明者发送： \[ \begin{align} g_1(x_1)&=\sum_{x_2,x_3}g(x_1,x_2,x_3)\\ &=g(x_1,0,0)+g(x_1,0,1)+g(x_1,1,0),g(x_1,1,1)\\ &=(2x_1^3)+(2x_1^3+x_1)+(2x_1^3)+(2x_1^3+x_1+1)\\ &=8x_1^3+2x_1+1 \end{align} \] 验证者验证：\(g_1(0)+g_1(1)=1+11=12=C_1\)。

验证者发送随机值：\(r_1=2\)。

第2轮

证明者发送： \[ \begin{align} g_2(x_2)&=\sum_{x_3}g(r_1,x_2,x_3)\\ &=g(2,x_2,0)+g(2,x_2,1)\\ &=(16)+(16+2+x_2)\\ &=x_2+34 \end{align} \] 验证者验证：\(g_2(0)+g_2(1)=34+35=69=g_1(2)\)。

验证者发送随机值：\(r_2=3\)。

第3轮

证明者发送： \[ \begin{align} g_3(x_3)&=g(r_1,r_2,x_3)\\ &=g(2,3,x_3)\\ &=16+2x_3+3x_3\\ &=5x_3+16 \end{align} \] 验证者验证：\(g_3(0)+g_3(1)=16+21=37=g_2(3)\)。

验证者生成随机值：\(r_3=6\)。计算\(g_3(r_3)=g_3(6)=46\)，查询\(g(r_1,r_2,r_3)=g(2,3,6)=16+12+18=46\)，两者一致，验证通过。

2.2 GKR协议

对于层状算术电路，从上（根）到下（叶）逐层规约，每一层之间都使用Sum-check协议。比如先用Sum-check证明第一层的结果由第二层正确得出，但验证者不知道第二层的值，因此再继续往下规约，直到最后一层验证者知道输入值。

参考：GKR协议 - 知乎

2.3 随机预言机模型（ROM）

Random Oracle Model

理想化模型，对于任意输入\(x\in D\)，从值域\(\{0,1\}^k\)中均匀随机选择\(k\)位输出\(R(x)\)。现实中被具体的哈希函数取代。

2.4 Fiat-Shamir变换

Fiat-Shamir变换将任意的公开掷币协议\(I\)转换成非交互式公开可验证的协议\(Q\)。

将验证者在\(I\)中第\(i\)轮的消息替换为查询ROM的结果即可得到\(Q\)。查询的输入为证明者在第\(1,\cdots,i\)轮中发送的所有消息。

2.5 随机存取机（RAM）

Random Access Machine

由主存、寄存器、指令（类似RISC）、程序计数器组成的硬件模型。程序运行时间为\(T(n)\)指在RAM上所需的指令长度为\(T(n)\)。

2.6 计算机程序转换为电路可满足性实例

任何在\(T\)时间内运行的计算机程序，都可以被高效地转换成一个等效的电路可满足性的实例\((C,x,y)\)，其中电路\(C\)的大小接近\(T\)，深度接近\(\log T\)。输入\(x\)时输出\(y\)当且仅当存在\(w\)，使得\(C(x,w)=y\)。

三、承诺方案

两个过程：承诺（Commit）和打开（open）。

满足：绑定性（Binding）和隐藏性（Hiding）。

3.1 Pedersen承诺

群\(G\)的阶是\(q\)，\(g\)和\(h\)是两个生成元（它们的离散对数关系未知）。

• 承诺：\(s\)是秘密，\(t\)是采样的随机数。承诺\(c=C_{g,h}(s,t)=g^sh^t\)。
• 打开：给出\(s\)和\(t\)。

满足不可区分性（indistinguishable）：因为有\(t\)的存在，（在\(s\)取值很少的情况下）攻击者不能通过枚举\(s\)比较得出秘密（guess and check）。

3.2 KZG承诺

三个群\(\mathbb G_1\)、\(\mathbb G_2\)、\(\mathbb G_T\)，阶为\(q\)。\(g_1\)和\(g_2\)分别是\(\mathbb G_1\)和\(\mathbb G_2\)的生成元。\(e\)是\(\mathbb G_1\times\mathbb G_2\to\mathbb G_T\)。\(t\)是多项式的最大次数。要承诺的多项式为\(f(x)=\sum_{i=0}^t c_i\cdot x^i\)。

• 可信设置：从\(\mathbb Z_q\)中随机采样\(\alpha\)，\(SK=\alpha\)，\(SK\)需要销毁。 \[ PK=<g_1,\alpha g_1,\alpha^2g_1\cdots,\alpha^tg_1,g_2,\alpha g_2> \]

• 承诺：承诺了\(f(x)\)在至多\(t\)个点的取值。 \[ C=f(\alpha)\cdot g_1=\sum_{i=0}^{t}c_i\cdot(\alpha^i\cdot g_1) \]

• 打开：即在\(x_0\)点揭示多项式值为\(f(x_0)\)，等价于 \[ f(x)-f(x_0)=(x-x_0)f'(x) \] 其中 \[ f'(x)=\frac{f(x)-f(x_0)}{x-x_0}=\sum_{i=0}^{t-1}d_i\cdot x^i \] 证明方需要发送的witness为 \[ w=f'(\alpha)\cdot g_1=\sum_{i=0}^{t-1}d_i\cdot(\alpha^i\cdot g_1) \] 所以证明方一共需要发送\(<x_0,f(x_0),w>\)。

  上述过程只揭示了\(x_0\)处的取值，实际上承诺是承诺了\(t\)个点处的取值，因此验证方可以在至多\(t\)个点（\(x_0,x_1,\cdots\)）处打开承诺。

• 验证：检查如下pairing \[ e(C,g_2)=e(w,(\alpha-x_0)\cdot g_2)\cdot e(g_1,g_2)^{f(x_0)} \] 因为 \[ \begin{align} &e(w,(\alpha-x_0)\cdot g_2)\cdot e(g_1,g_2)^{f(x_0)}\\ &=e(f'(\alpha)\cdot g_1,(\alpha-x_0)\cdot g_2)\cdot e(g_1,g_2)^{f(x_0)}\\ &=e(g_1,g_2)^{f'(\alpha)\cdot(\alpha-x_0)+f(x_0)}\\ &=e(g_1,g_2)^{\frac{f(\alpha)-f(x_0)}{\alpha-x_0}\cdot(\alpha-x_0)+f(x_0)}\\ &=e(g_1,g_2)^{f(\alpha)}\\ &=e(f(\alpha)\cdot g_1,g_2)\\ &=e(C,g_2) \end{align} \]

上面的承诺还不满足不可区分性，修复方法：

• 方法一：多承诺一个随机点处的值，即多项式\(f(x)\)变为\(t+1\)次的。
• 方法二：用两组\(\mathbb G_1\)的生成元（关系未知），类似Pedersen承诺。