写在前面

本次电路设计未选取Circom直接进行,而是以Plonk零知识证明体系为基础,通过自写类进行编辑。

自写类文件为Ciucrit.h,项目文件为MIN-MAX.cpp,其余文件为其他电路设计。

若要查看完整证明过程,则请访问Zk-snarks example文件夹。

设计目标

Write a circuit to prove that your CET6 grade is larger than 425. (注意:由于CET6满分710,因此我们只需证明成绩在425-710即可)

设计**

基础电路设计


为叙述简便,我们不妨设n=3,即构造范围审查为(0,$2^3$)的电路。

其中,隐私值为x以及x的各比特位$b_{xi}$(此处由生成函数生产),首先我们需要构造约束来确保所输入$b_{xi}$是二进制,即约束$b_{xi}$ * (1-$b_{xi}$)=0。

Image text

之后对隐私值进行处理,构造门电路$b_{x0}$+$2^1$ * $b_{x1}$ + $2^2$ * $b_{x2}$-X=0,即$b_{x0}$+$2^1$ * $b_{x1}$+$2^2$ * $b_{x2}$=X

Image text

对电路中的隐私输入、公共输入以及加法门/乘法门进行编号和标注,加法门/乘法门均由三组连线组成:a、b、c,分别代表该门的左右输入和输出。

Image text Image text

以编号为10的乘法门为例,此乘法门约束为$a_{10}$ * $b_{10}$=$c_{10}$。

得到该范围审查问题的模拟电路后,我们需要将其转化为多项式形式。

PLONK电路中存在两种约束,即门约束和复制约束,其中门约束是对单个门的依赖关系的限制,线约束是对门之间的共享值的限制。

首先,从门约束来看,此处电路共用了4种门:加法门、乘法门、布尔门、公共输入门。PLONK系统对门约束的一般定义为:

$Q_{L_i}$ $a_i$+$Q_{R_i}$ $b_i$+$Q_{O_i}$ $c_i$+$Q_{M_i}$ $a_i$ $b_i$+$Q_{C_i}$=0

其中,L代表左输入,R代表右输入,O代表输出,M代表乘法,C代表常量。再此要求下,我们可以给出各门所使用的参数。

加法门:

$Q_{L_i}$=1,$Q_{R_i}$=1,$Q_{M_i}$=0,$Q_{O_i}$=-1,$Q_{C_i}$=0

乘法门:

$Q_{L_i}$=0,$Q_{R_i}$=0,$Q_{M_i}$=1,$Q_{O_i}$=-1,$Q_{C_i}$=0

布尔门:

$Q_{L_i}$=-1,$Q_{R_i}$=0,$Q_{M_i}$=1,$Q_{O_i}$=0,$Q_{C_i}$=0

公共输入:

$Q_{L_i}$=1,$Q_{R_i}$=0,$Q_{M_i}$=0,$Q_{O_i}$=0,$Q_{C_i}$=-1

总的来说,我们可以根据以上特性,使用压缩多项式来表达电路特征,即:

$Q_L$(x)a(x)+$Q_R$(x)b(x)+$Q_O$(x)c(x)+$Q_M$(x)a(x)b(x)+$Q_C$(x)=0

解决每个门的单独约束后,我们还需要定义各门之间的约束关系,即定义复制约束。当每个门之间的复制约束确定后,我们就得到了一个完整的电路系统。

顾名思义,复制约束就是约束各门的输入哪些是相等的数据,在此,我们的处理方法是:创建一个顺序的permutation数组,由于我们在创建门电路时已经将相同的线输入创建为相同变量,因此我们遍历寻找到相同的线输入,将其对应的permutation数组参数做一个调换,之后将其传入协议中进行处理。

根据上述两种约束条件,我们可以得出(0,$2^3$)的最终范围审查电路,并进一步实现(0,$2^n$)的范围审查电路。接下来我们可以根据这类电路转化为任意范围电路数据。

自主电路设计


考虑到现实情况,(0,$2^n$)无法满足多样化应用场景,因此本产品通过相关数学原理设计出了将审查范围扩大到任意整数的电路结构。

数学原理

定义两个数字Max、Min作为范围审查边界,由基本电路可知,我们可以证明0<x<$2^n$,如果我们将x替换为Max-x,x-Min,我们可以得出0 < Max – x < $2^n$,0 < x – Min < $2^n$,即Max - $2^n$ < x < Max,Min < x < $2^n$ - Min,若Max、Min满足Max – Min < $2^n$,Max + Min < $2^n$,我们就能得到Min < x < Max。针对现实应用场景,我们可以将n取64来构造支持范围较大的审查电路。

电路进阶

针对普通电路来说,我们需要新增4个门:两个公共输入门,两个加法门。公共输入门代表两个范围值,加法门用来约束Max-x与x-Min。

Image text

之后根据基本审查电路原理,分别对a、b进行基本范围审查(n=64),需要注意的是,电路中门的数量必须是2的幂次,因此我们需要将后续的门全补为空门。至此,任意范围的审查电路构造完毕。简单来说,此电路的实现原理就是求出Max-x与x-Min,之后调用两次基本范围审查分别查验两值,以此达到任意范围审查的目的。