[[# Arithmetic circuits
- **Flattening：将电路的执行转换成计算轨迹，**即将复合函数以乘法为基本单元拆解成一组有序的简单函数
$\{constraint_1,…,constraint_n\}$ ，其中-
$constraint_i:=w_i=(u_{i1}+…+u_{it})*(v_{i1}+…+v_{iv})$ ,$w_i$ 为输出变量，$\{u_1,…,u_n\}$ 为左输入变量，$\{ v_1,…,v_m\}$ 为右输入变量 - 这里的有序是指按电路执行的顺序
- 这里会引入中间变量
$\{sym\_1,…,sym\_k\}$ - 除了根节点处的门之外，其它的门的输出引脚添加对应的中间变量
$sym\_i$ - 除了叶子节点处的门之外，其他的门的输入引脚添加中间变量
$sym\_i$ ，该中间变量来自于另一个门的输出 - 举例说明：若门A的输出引脚接入到门B的输入引脚，则为门A的输出引脚和门B的输入引脚添加同一个中间变量
$sym\_i$
- 除了根节点处的门之外，其它的门的输出引脚添加对应的中间变量
-
-
重组
$\{constraints\}$ 中的数据：将其变成一阶约束系统R1CS：$W·\vec{a}=U·\vec{a}\circ V·\vec{a}$ (注：$\circ$ 为Hadamard product，按位乘法):-
$\vec{a}:=\{one\}+\{out\}+\{x_1,…,x_h\}+\{sym\_1,…,sym\_k\}$ ，即由表示1的冗余变量，函数输出，输入变量，中间变量构成的集合对应的向量。 -
$W:=\{constraint_1,…,constraint_n\}$ 的输出变量基于$\vec{a}$ 的选择向量构成的矩阵 -
$U:=\{constraint_1,…,constraint_n\}$ 的左输入变量基于$\vec{a}$ 的选择向量构成的矩阵 -
$V:=\{constraint_1,…,constraint_n\}$ 的右输入变量基于$\vec{a}$ 的选择向量构成的矩阵
-
- 注：矩阵的行数等于乘法门的数量，矩阵的列数等于
$\vec{a}$ 中元素的数量，即变量的数量
- **Flattening：**即将复合函数拆解成一组离散的门
$\{constraint_1,…,constraint_n\}$ ，其中-
$constraint_i:=q_{Oi}w_i=q_{Li}u_i+q_{Ri}v_i+q_{Mi} u_iv_i+q_{Ci}c_i$ ，$w_i$ 为输出变量，$u_i$ 为左输入变量，$v_i$ 为右输入变量，$c_i$ 为常量，$q_{Oi}$ 为输出选择器，$q_{Li}$ 为左输入变量选择器，$q_{Ri}$ 为右输入变量选择器，$q_{Mi}$ 为乘积选择器，$q_{Ci}$ 为常数选择器 - **注：**矩阵的行数等于所有门的数量，即约束的数量，n。
- 这里的有序是指计算的顺序
- 这里会引入中间变量
$\{sym\_1,…,sym\_k\}$ - 除了根节点处的门之外，其它的门的输出引脚添加对应的中间变量
$sym\_i$ - 除了叶子节点处的门之外，其他的门的输入引脚添加中间变量
$sym\_i$ ，该中间变量来自于另一个门的输出 - 举例说明：若门A的输出引脚接入到门B的输入引脚，则为门A的输出引脚和门B的输入引脚添加同一个中间变量
$sym\_i$
- 除了根节点处的门之外，其它的门的输出引脚添加对应的中间变量
-
- **重组
$\{constraint_1,…,constraint_n\}$ 中的数据：**将其变成：$\vec{q_O}\circ \vec{w}=\vec{q_L}\circ\vec{u}+\vec{q_R}\circ\vec{v}+\vec{q_M}\circ(\vec{u}\circ\vec{v})+\vec{q_C}$ (注：$\circ$ 为Hadamard product，按位乘法)-
$Q:=\{\vec{q_O},\vec{q_L},\vec{q_R},\vec{q_M},\vec{q_C}\}$ ，即选择器矩阵 -
$W:=\{\vec{w},\vec{u},\vec{v}\}$ ，即变量矩阵 -
$S^\delta:=$ 轮换置换后得到的位置集合，来自于Wiring
-
-
Wiring(Copy Constraints)
-
分析：Wiring即将离散的门连接起来，即某一个门的输出引脚要接入另一个门的输入引脚
$\iff$ 约束变量矩阵$W$中某几个位置的元素是相等的$\iff$ 这一个元素出现在$W$ 矩阵的多个位置处 -
Wiring实现思路：
- 把
$W$ 矩阵中的每一个位置从1到3n进行唯一编号，则所有的编号构成一个位置集合$S$ ，将位置集合$S$对应的元素取出构成一个multiset$S_e$ - 把每个元素出现在$W$中的位置编号取出放在一个集合中
$s$ ，即一个元素对应一个位置集合$s$ 。将位置集合对应的元素取出构成一个multiset$s_e$ 。所有元素的$s$的并集即为$S$ ，$s_e$ 的并集为$S_e$ -
$\forall s$ ，要使得$s_e$ 中元素全部相等
$\iff$ $\forall s_e$ ，$s_e$ 与其进行轮换置换$\delta$ 后得到的集合$s_{e}^{\delta}$ 在Multiset的意义上是等价的$\iff$ $\forall s_e$ ，$\vec{ s_{e}}+\vec{ s}$ 与$\vec{s_{e}}+\vec{ s^{\sigma}}$ 在Multiset的意义上是等价的$\Leftarrow$ 令$S$ 为所有$s$ 的并集，$S^\sigma$ 为所有$s^{\sigma}$ 的并集，$S_e$ 为所有$s_{e}$ 的并集，$\vec{ S_e}+\vec{ S}$ 与$\vec{ S_e}+\vec{S^{\sigma}}$ 在Multiset的意义上是等价的$\iff$令$\vec T=\vec{ S_e}+\vec{ S}\ ,\vec{ T^{\sigma}}=\vec{ S_e}+\vec{S^{\sigma}}$ ，取随机数$\gamma$ ，有$(\gamma-t_0)(\gamma-t_1)...(\gamma-t_{n-1})=(\gamma-t^\sigma_0)(\gamma-t^\sigma_1)...(\gamma-t^\sigma_{n-1})$ $即\prod \limits_{i\in[n]}(\gamma-t_i)=\prod\limits_{i\in[n]}(\gamma-t^\sigma_i)$ $即\prod\limits_{i\in[n]}\frac{(\gamma-t_i)}{(\gamma-t^\sigma_i)}=1$ -
至此，问题转化成如何证明连乘等式
$b_0\cdot b_1\cdot b_2\cdot ...b_{n-1}=c$ ，即证明一个n步递归，- 初始值：
$r_0=1$ - 递归定义：
$r_i=r_{i-1}\cdot b_{i-1}$ - 终止条件：
$r_n=c$
则有
$b_0\cdot b_1\cdot b_2\cdot ...b_{n-1}=c \\ \iff r_0=1 ,r_{i}=r_{i-1} \cdot b_{i-1} ，r_{n}=c$ 所有
$r_i$ 构成向量$\vec r$ - 至此，Wiring转化成三个约束
-
$r_0=1和r_n=c$ 即约束向量的指定位的值为k，即约束$\vec r$ 的第1位($r_0$ )的值为1，第n+1位($r_{n}$ )的值为$c$ 。设
$e_i$ 为n维向量空间的标准基的第i个基向量，向量$\vec r$ 的第$i$ 位为$k$ 等价于：$\vec e_i \circ \vec r=k\times \vec e_i$ -
$r_{i}=r_{i-1} \cdot b_{i-1}$
-
- 初始值：
- 把
-
-
$Lemma1:$ 带有Hadamard product运算的n维向量的群$\mathbb { M_n}$ ，和带有乘法运算的在$H$上的最高项次数不大于n-1的单变量多项式$\mathbb H_p^{(\leq n-1)} [X]$ 的群，映射：$h:\mathbb M_n \to \mathbb H_p^{(\leq n-1)}$ ,令$L_i(X)为Lagrange Basis$ ，有$h(\vec m)= \langle \vec m,\vec L_i(X) \rangle$ ，是群同态 -
$Lemma2:由Lemma1，有$ $W_{m\times n}·\vec{a}=U_{m\times n}·\vec{a}\circ V_{m\times n}·\vec{a}$ $\iff \forall X\in H,\ \left \langle \overrightarrow{ \langle \vec w,\vec L_i(X) \rangle},\vec a \right \rangle =\left \langle \overrightarrow{\langle \vec u,\vec L_i(X) \rangle},\vec a \right\rangle \cdot \left\langle \overrightarrow {\langle \vec v,\vec L_i(X) \rangle},\vec a \right\rangle$ -
$Lemma3:令c(X)=\left \langle \overrightarrow{ \langle \vec w,\vec L_i(X) \rangle},\vec a \right \rangle ,a(X)=\left \langle \overrightarrow{\langle \vec u,\vec L_i(X) \rangle},\vec a \right\rangle，b(X)=\left\langle \overrightarrow {\langle \vec v,\vec L_i(X) \rangle},\vec a \right\rangle,有$ $\forall X\in H,c(X)=a(X) \cdot b(X) $ $\iff \forall X\in H,a(X) \cdot b(X)-c(X)=0 \\ \iff f(X)=a(X) \cdot b(X)-c(X) =0\ 以H为根，X\in F \\ \iff f(X)能被z_H(X)=(X-h_0)(X-h_1)(X-h_2)...(X-h_{n-1})整除,h_i\in H$ -
令
$q(x)=f(X)/z_H(X)$ , 至此，完成了从R1CS到QAP到转换
Plonkish Arithmetization包含两部分约束：
第一部分约束每个门是正确计算的，即所谓算术约束；第二部分约束门与门之间正确连接，即所谓复制约束。
首先来转换算术约束：
-
$Lemma4:$ 带有加法的n维向量的群$\mathbb { M_n}$ ，和带有加法的在$H$上的最高项次数不大于n-1的单变量多项式$\mathbb H_p^{(\leq n-1)} [X]$ 的群，映射：$h:\mathbb M_n \to \mathbb H_p^{(\leq n-1)}$ ，令$L_i(X)为Lagrange Basis$ ，有$h(\vec m)= \langle \vec m,\vec L(X) \rangle$，是群同态 -
$Lemma5:$ 同态映射的复合映射必定是同态映射 $由Lemma1,Lemma4,Lemma5,有$
令
- 至此，n个算术约束转化成了一个由八个n-1次多项式之间构成的约束。
接着转换复制约束：
- 由
$Lemma1$ ，有
有
- 令
$L_i(X)$ 为定义在乘法子群$H$上的$Lagrange Basis$ ，由$Lemma1$ ,有
- 至此，复制约束转换成了三个多项式约束。
在2.3中得到了一系列多项式之间的约束，本节我们来看如何实现多项式约束，
令：
-
$setup(\lambda) \to pp$ 计算public parameter -
$commit(pp,f,r) \to com_f$ $基于随机数r对f\in \mathcal F的承诺$ -
$eval(prover \ P,verifier\ V)$ 对于给定的$com_f$ ，以及$x\in X,y\in Y:证明f(x)=y,即所谓的将f在点(x,y)处打开$ $P(pp,f,x,y,r) \to 简短证明\pi$ $V(pp,com_f,x,y,\pi)\to 接受/拒绝$
- Polynominal commitments：次数不大于d的单变量多项式承诺
$f(X)\in \mathbb F_p^{(\leq d)} [X]$ - Multilinear commitments：次数小于等于1的多变量多项式承诺
$f(X_1,...,X_k)\in \mathbb F_p^{(\leq 1)}[X_1,...,X_K]$ - Linear commitments：
$f_{\vec v}(\vec u)= \left \langle \vec u, \vec v \right \rangle=\sum _{i=1}^nu_iv_i$
这三者从上到下，越来越general
适用于次数不大于d的单变量多项式
- Bulletproofs：基于椭圆曲线，verifier的算法复杂度与d成线性相关
- KZG‘10，Dory’20：基于双线性椭圆曲线
- Dark’20：基于阶未知的群
- FRI：基于hash Function
-
预备知识：
$阶为p的群\ \mathbb G:=\{1,G,2\cdot G,3\cdot G,...,(p-1)\cdot G\} ,其中，G为生成元$ -
$setup(\lambda) \to pp$ - 取随机数
$\alpha\in \mathbb F_p$ $pp=(H_0=1,H_1=\alpha \cdot G,H_2=\alpha^2 \cdot G,...,H_d=\alpha^d \cdot G)\in \mathbb G^{d+1}$ - 删除
$\alpha$ ，$\alpha$ 也称为God key，即除了上帝，$\alpha$ 不能被任何人知道
- 取随机数
-
$commit(pp,f,r) \to com_f$ -
$com_f:=f(\alpha)\cdot G \in \mathbb G$ ：具体的计算方法如下：
$f(X)=f_0+f_1X+...+f_dX^d$ $\implies com_f=f_0\cdot 1+f_1\cdot\alpha G+f_2\cdot\alpha^2 G+ ...+f_d\cdot \alpha^dG$ $\iff com_f=f_0\cdot H——1+f_1\cdot H1+...+f_d\cdot H_d$ - 注意，此处是Binding的，但由于未做随机处理，故不是Hiding的，若需Hiding，需要extend
-
-
$eval(prover \ P,verifier\ V)$ -
目标：证明
$f(u)=v$ $f(u)=v$ $\iff u是 \hat f =f-v的根$ $\iff (X-u)整除\hat f$ $\iff \exists q\in \mathbb{F}_p[X]\ \ s.t.\ \ q(X)\cdot(X-u)=f(X)-v$ -
$Prover(pp,f,u,v)$ 计算$商多项式q(X) 及其承诺com_q$，发送给Verifier -
$Verifier(pp,com_f,u,v)$ 检查$(\alpha-u)\cdot com_q=com_f-v\cdot G$ 是否成立- 此处的问题是
$\alpha$ 是不可知的，那如何在不用显式地知道$\alpha$ 的前提下验证等式$(\alpha-u)\cdot com_q=com_f-v\cdot G$ 呢？在$com_q和com_f$ 中我们通过setup步骤将$\alpha$ 隐藏了，那么等式左侧的$(\alpha-u)$ 是不是同样也可以通过setup隐藏起来？为达到这个目的，我们需要扩展setup成如下 -
$setup(\lambda) \to pp$ - 取随机数
$\alpha\in \mathbb F_p$ -
$pp=(H_0=1,H_1=\alpha \cdot G,H_2=\alpha^2 \cdot G,...,H_d=\alpha^d \cdot G)\in \mathbb G^{d+1} + (T_0=1,T_1=\alpha \cdot G_2) \in \mathbb G_2^1$ ， - 删除
$\alpha$ ，$\alpha$ 也称为God key，即除了上帝，$\alpha$ 不能被任何人知道
- 取随机数
-
$Verifier(pp,com_f,u,v)$ - 引入双线性映射关系$
e\in \mathbb G \times \mathbb G_2 \to \mathbb G_X$ - 至此，将原来需要验证的
$(\alpha-u)\cdot com_q\overset {?}{=}com_f-v\cdot G$ ，转换成了 在$\mathbb G_X$ 上验证$e(com_q,T_1-u\cdot T_0)\overset {?}{=}e(com_f-v\cdot G,T_0)$
- 引入双线性映射关系$
- 此处的问题是
-
-
Lemma1: Schwartz zipple定理
-
Lemma2: 单位根和乘法子群**：**
令
$\omega \in \mathbb{F}_p$ 为k次单位根，即$\omega^k =1$ 乘法子群
$H:=\{1,\omega,\omega^2,...,\omega^{k-1}\} \subseteq \mathbb{F}_p$ 由于单位根的对称性，有
$\prod \limits_{i=0}^{k-1}(X-\omega ^i)=X^k-1$ -
Lemma3:
$H$ 中的元素$\omega^i$ 均为$f$ 的根，即$f在H上均为0$ $\iff$ $f(x) 能被\prod \limits_{i=0}^{k-1}(X-\omega ^i) 整除$ $\iff$ $f(x) 能被X^k-1 整除$ $\iff$ 存在商多项式$q(X)=f(X)/(X^k-1)$
- Task1 zero-test：证明$f$在H上等于0，即证明H中的元素均为$f$的根
-
Task2 sum-check：证明
$\sum_{a\in H}f(a)=b$ ，即证明$f$在H上全部取值的和等于b -
Task3 prod-check：证明
$\prod_{a\in H}f(a)=c$ ，即证明$f$在H上全部取值的和等于c
- Prover 向 Verifier Commit
$f(X)和q(X),即Com_f,Com_q$ - Verifier 向Prover 发送随机数r
- Verifier 检查
$f(r)\overset {?}{=}q(r)\cdot (r^k-1)$
https://github.com/sec-bit/learning-zkp/blob/develop/plonk-intro-cn/plonk-arithmetization.md
https://www.youtube.com/watch?v=J4pVTamUBvU&list=PLj80z0cJm8QErn3akRcqvxUsyXWC81OGq&index=2
https://github.com/sec-bit/learning-zkp/blob/develop/plonk-intro-cn/plonk-polycom.md ](https://github.com/zkp-co-learning/ZKP/edit/main/%E7%AC%AC%E4%BA%8C%E7%AB%A0.md)https://github.com/zkp-co-learning/ZKP/edit/main/%E7%AC%AC%E4%BA%8C%E7%AB%A0.md](https://github.com/zkp-co-learning/ZKP/edit/main/%E7%AC%AC%E4%BA%8C%E7%AB%A0.md)https://github.com/zkp-co-learning/ZKP/edit/main/%E7%AC%AC%E4%BA%8C%E7%AB%A0.md