Polygon zkEMV STARK to SANRK

在Stark 证明转换过程如下所示，可以将STARK 证明转换为STARK 证明或SNARK 证明。

对于STARK 转换为STARK, 首先通过PIL2Circom 过程，生成circom 验证电路，用于验证STARK证明； 再将circom 电路编译成R1CS 之后，转换变Plonk 形式的电路，再生成PIL 的描述，通过这个过程，可以用于验证STARK 证明的PIL约束； 然后根据PIL, 可以生成新的STARK证明；

对于STARK 转换为SNARK, 首先通过PIL2Circom 过程，生成circom 验证电路，用于验证STARK证明； 再将circom 电路编译成R1CS 之后，直接生成SNARK证明即可。

上图所示过程涉及 STARK证明（Golldilock） -> STARK C12a 证明（Goldilocks）-> STARK C12b 证明（BN128）-> SNARK 证明 。 原因在于在Goldilocks域上效率更高，中间c12a-> c12b是为了进一步优化验证电路，最后生成SNARK 必须在 BN128 上执行。

更多了解：

BN128:https://hackmd.io/@vivi432/bn128-in-c

详细过程

STARK 到SNARK证明更详细的过程如下所示：

[图片上传失败...(image-b9f91f-1695101788379)]

注：上图描述的是pil-stark 是第一版本，没有c12a->c12b 的转换过程。

其中汲及多个编译转换过程，关键的步骤主要是：

• 将PIL 生成Circom 电路，需要pil2circom 编译器；
• 将r1cs 转换为 PIL, 需要 r1cs-> plonk-> PIL转换过程；

pil2circom 实现

下面以Fibonacci 为例，分析整个实现过程：

实现过程

/usr/local/bin/node --max-old-space-size=32000 src/main_pil2circom.js -p /Users/tron/test/polygon_zkevm/pil-stark/test/sm_fibonacci/fibonacci_main.pil -s /Users/tron/test/polygon_zkevm/pil-stark/test/sm_fibonacci/fibonacci.starkstruct.json -v /Users/tron/test/polygon_zkevm/pil-stark/tmp/fibonacci.verkey.json -o /Users/tron/test/polygon_zkevm/pil-stark/tmp/fibonacci.verifier.circom

输入为：

• Fibonacci_main.pil

namespace Fibonacci(%N);


    pol constant L1, LLAST;
    pol commit l1,l2;

    pol l2c = l2;

    public in1 = l2c(0);
    public in2 = l1(0);
    public out = l1(%N-1);

    (l2' - l1)*(1-LLAST) = 0;

    pol next = l1*l1 + l2*l2;

    (l1' - next)*(1-LLAST) = 0;

    L1 * (l2 - :in1) = 0;
    L1 * (l1 - :in2) = 0;
    LLAST * (l1 - :out) = 0;

• Fibonacci.starkstruct.json

{
            "nBits": 10,
            "nBitsExt": 11,
            "nQueries": 8,
            "verificationHashType": "GL",
            "steps": [
                {"nBits": 11},
                {"nBits": 7},
                {"nBits": 3}
            ]
}

• Fibonacci.verkey.json

{
 "constRoot": [
  8072859658275330050,
  6129740704102247485,
  16008196867495226449,
  2863018592730207411
 ]
}

输出为生成的circom 电路：

Fibonacci.verifier.circom

主要采用 ejs ，将Fibonacci 的信息注入stark 验证电路模板中，生成最后的Fibonacci stark 证明的验证电路。

    const obj = {
        F: F,
        starkInfo: starkInfo,
        starkStruct: starkStruct,
        constRoot: constRoot,
        pil: pil,
        options: options
    };

    return ejs.render(template ,  obj);

verifier.circom

下面以fibonacci.verrifer.circom 过程为例，分析生成的用于验证STARK 证明的circom 电路。

main 是 circom 程序的入口，其中publics 声明为公开输入。

component main {public [publics]}= StarkVerifier();

Merkle 树

下面的代码声明验证需要用的Merkle 根：

    signal input publics[3];  // Fibonacci中的三个公开输入
    signal input root1[4];  // commit多项式对应的Merkle 根  
    signal input root2[4];  // plookup 多项式对应的Merkle 根
    signal input root3[4];  // plookup/permutation/connection Z 多项式对应的根
    signal input root4[4];  // q多项式 约束对应的Merkle 根

    signal rootC[4];  // 常量多项式对应的Merkle 根
    rootC[0] <== 8072859658275330050;   //从fibonacci.verkey.json 导入的常量根
    rootC[1] <== 6129740704102247485;
    rootC[2] <== 16008196867495226449;
    rootC[3] <== 2863018592730207411;

以下涉及FRI 过程对应的叶子节点和Merkle 路径：

    signal input evals[8][3];  // 对应starkinfo 中 evMap中各个承诺多项式的值。

    signal input s0_vals1[8][2];  //FRI proof[0]:  8 表示查询点的个数，2表示commit多项式的个数（cm1_2ns）
    signal input s0_vals4[8][4];  // 8 表示查询点的个数，4表示q多项式的个数（q_2ns）
    //注：Fibonacci s0_vals2, so_vals3对应的约束不存在，所有没有生成
    signal input s0_valsC[8][2];   //  8 表示查询点的个数，2表示 常量多项式 的个数
    signal input s0_siblings1[8][11][4]; //s0_vals1对应的Merkle 路径，有11层，每个节点由4个Goldilocks 元素组成
    signal input s0_siblings4[8][11][4]; 
    signal input s0_siblingsC[8][11][4];

    signal input s1_root[4];  // fri step 1 root
    signal input s2_root[4];  // fri step 2 root

    signal input s1_vals[8][48];         // fri 1 tree对应查询点的叶子节点，48为对应叶子width, 即： (1 <<   
                                        // (starkStruct.steps[s-1].nBits -   starkStruct.steps[s].nBits))*3
   
    signal input s1_siblings[8][7][4]; // fri 1 tree 对应的Merkle路径
    signal input s2_vals[8][48];     //与以上类似
    signal input s2_siblings[8][3][4];

    signal input finalPol[8][3];  // 最后一轮，每个都为宽度为3的值

FRI 参数

FRI 的相关参数值定义：

    signal enable;  // enable input 
    enable <== 1;


    signal challenges[8][3];  // 固定的8个chanllenge 值
    signal s0_specialX[3];   // fri计算过程中涉及到的special_x, 和fri的 steps 个数相等
    signal s1_specialX[3];
    signal s2_specialX[3];

    signal ys[8][11];     // 查询点索引值

FRI 相关参数值的计算：

    component tcHahs_0 = Poseidon(12);
    tcHahs_0.in[0] <== root1[0];
    tcHahs_0.in[1] <== root1[1];
    tcHahs_0.in[2] <== root1[2];
    tcHahs_0.in[3] <== root1[3];
    tcHahs_0.in[4] <== 0;
    tcHahs_0.in[5] <== 0;
    tcHahs_0.in[6] <== 0;
    tcHahs_0.in[7] <== 0;
    tcHahs_0.capacity[0] <== 0;
    tcHahs_0.capacity[1] <== 0;
    tcHahs_0.capacity[2] <== 0;
    tcHahs_0.capacity[3] <== 0;
    challenges[0][0] <== tcHahs_0.out[0];
    challenges[0][1] <== tcHahs_0.out[1];
    challenges[0][2] <== tcHahs_0.out[2];
    challenges[1][0] <== tcHahs_0.out[3];
    challenges[1][1] <== tcHahs_0.out[4];
    challenges[1][2] <== tcHahs_0.out[5];
    ......

后续代码类似，依次完成challenge, special_x, ys 计算过程。

约束多项式检查

///////////
// Constrain polynomial check in vauations
///////////
    component verifyEvaluations = VerifyEvaluations();
    verifyEvaluations.enable <== enable;
    for (var i=0; i<8; i++) {
        for (var k=0; k<3; k++) {
            verifyEvaluations.challenges[i][k] <== challenges[i][k];
        }
    }
    for (var i=0; i<3; i++) {
        verifyEvaluations.publics[i] <== publics[i];
    }
    for (var i=0; i<8; i++) {
        for (var k=0; k<3; k++) {
            verifyEvaluations.evals[i][k] <== evals[i][k];
        }
    }

FRI 表达式验证

///////////
// Step0 Check and evaluate queries
///////////

    component verifyQueries[8];
    component s0_merkle1[8];


    component s0_merkle4[8];
    component s0_merkleC[8];
    component s0_lowValues[8];
    
    ...

FRI tree 1 验证

    component s1_merkle[8];
    component s1_fft[8];
    component s1_evalPol[8];
    component s1_lowValues[8];
    signal s1_sx[8][7];
    
    ......

FRI tree 2 验证

    component s2_merkle[8];
    component s2_fft[8];
    component s2_evalPol[8];
    component s2_lowValues[8];
    signal s2_sx[8][3];
    ...

低度测试

最后一轮的低度，判定最后的多项式次数小于4。

///////
// Check Degree last pol
///////
// Last FFT
    component lastIFFT = FFT(3, 3, 1, 1 );

    for (var k=0; k< 8; k++ ){
        for (var e=0; e<3; e++) {
            lastIFFT.in[k][e] <== finalPol[k][e];
        }
    }

    for (var k= 4; k< 8; k++ ) {  
        for (var e=0; e<3; e++) {
            enable * lastIFFT.out[k][e] === 0;
        }
    }

main_compressor12_setup

main_compressor12_setup 主要用于将Stark proof 生成stark 证明的初始设置，其中涉及R1CS-> Plonk 电路 -> pil 的转换过程。

输入输出

程序执行命令为：

/usr/local/bin/node --max-old-space-size=32000 src/compressor12/main_compressor12_setup.js -r /Users/tron/test/polygon_zkevm/pil-stark/tmp/fibonacci.verifier.r1cs -p /Users/tron/test/polygon_zkevm/pil-stark/tmp/fibonacci.c12.pil -c /Users/tron/test/polygon_zkevm/pil-stark/tmp/fibonacci.c12.const -e /Users/tron/test/polygon_zkevm/pil-stark/tmp/fibonacci.c12.exec

其中输入为circom 编译程生成的生成的 r1cs ：

fibonacci.verifier.r1cs

输出为：

• fibonacci.c12.pil

constant %N = 2**17;

namespace Global(%N);
    pol constant L1;

namespace Compressor(%N);
    pol constant S[12];
    pol constant Qm, Ql, Qr, Qo, Qk, QMDS, QCMul;
    pol commit a[12];

    public pub0 = a[0](0);
    public pub1 = a[1](0);
    public pub2 = a[2](0);
    Global.L1 * (a[0] - :pub0) = 0;
    Global.L1 * (a[1] - :pub1) = 0;
    Global.L1 * (a[2] - :pub2) = 0;

// Normal plonk ecuations
    pol a01 = a[0]*a[1];
    Qm*a01 + Ql*a[0] + Qr*a[1] + Qo*a[2] + Qk = 0;

    pol a34 = a[3]*a[4];
    Qm*a34 + Ql*a[3] + Qr*a[4] + Qo*a[5] + Qk = 0;

    pol a67 = a[6]*a[7];
    Qm*a67 + Ql*a[6] + Qr*a[7] + Qo*a[8] +Qk = 0;

    pol a910 = a[9]*a[10];
    Qm*a910 + Ql*a[9] + Qr*a[10] + Qo*a[11] +Qk = 0;

// MDS

    QMDS * (a[ 0]' - (25*a[0] + 15*a[1] + 41*a[2] + 16*a[3] +  2*a[4] + 28*a[5] + 13*a[6] + 13*a[7] + 39*a[8] + 18*a[9] + 34*a[10] + 20*a[11])) = 0;
    QMDS * (a[ 1]' - (20*a[0] + 17*a[1] + 15*a[2] + 41*a[3] + 16*a[4] +  2*a[5] + 28*a[6] + 13*a[7] + 13*a[8] + 39*a[9] + 18*a[10] + 34*a[11])) = 0;
    QMDS * (a[ 2]' - (34*a[0] + 20*a[1] + 17*a[2] + 15*a[3] + 41*a[4] + 16*a[5] +  2*a[6] + 28*a[7] + 13*a[8] + 13*a[9] + 39*a[10] + 18*a[11])) = 0;
    QMDS * (a[ 3]' - (18*a[0] + 34*a[1] + 20*a[2] + 17*a[3] + 15*a[4] + 41*a[5] + 16*a[6] +  2*a[7] + 28*a[8] + 13*a[9] + 13*a[10] + 39*a[11])) = 0;
    QMDS * (a[ 4]' - (39*a[0] + 18*a[1] + 34*a[2] + 20*a[3] + 17*a[4] + 15*a[5] + 41*a[6] + 16*a[7] +  2*a[8] + 28*a[9] + 13*a[10] + 13*a[11])) = 0;
    QMDS * (a[ 5]' - (13*a[0] + 39*a[1] + 18*a[2] + 34*a[3] + 20*a[4] + 17*a[5] + 15*a[6] + 41*a[7] + 16*a[8] +  2*a[9] + 28*a[10] + 13*a[11])) = 0;
    QMDS * (a[ 6]' - (13*a[0] + 13*a[1] + 39*a[2] + 18*a[3] + 34*a[4] + 20*a[5] + 17*a[6] + 15*a[7] + 41*a[8] + 16*a[9] +  2*a[10] + 28*a[11])) = 0;
    QMDS * (a[ 7]' - (28*a[0] + 13*a[1] + 13*a[2] + 39*a[3] + 18*a[4] + 34*a[5] + 20*a[6] + 17*a[7] + 15*a[8] + 41*a[9] + 16*a[10] +  2*a[11])) = 0;
    QMDS * (a[ 8]' - ( 2*a[0] + 28*a[1] + 13*a[2] + 13*a[3] + 39*a[4] + 18*a[5] + 34*a[6] + 20*a[7] + 17*a[8] + 15*a[9] + 41*a[10] + 16*a[11])) = 0;
    QMDS * (a[ 9]' - (16*a[0] +  2*a[1] + 28*a[2] + 13*a[3] + 13*a[4] + 39*a[5] + 18*a[6] + 34*a[7] + 20*a[8] + 17*a[9] + 15*a[10] + 41*a[11])) = 0;
    QMDS * (a[10]' - (41*a[0] + 16*a[1] +  2*a[2] + 28*a[3] + 13*a[4] + 13*a[5] + 39*a[6] + 18*a[7] + 34*a[8] + 20*a[9] + 17*a[10] + 15*a[11])) = 0;
    QMDS * (a[11]' - (15*a[0] + 41*a[1] + 16*a[2] +  2*a[3] + 28*a[4] + 13*a[5] + 13*a[6] + 39*a[7] + 18*a[8] + 34*a[9] + 20*a[10] + 17*a[11])) = 0;

// CMUL

    pol A = (a[0] + a[1])  * (a[3] + a[4]);
    pol B = (a[0] + a[2])  * (a[3] + a[5]);
    pol C = (a[1] + a[2])  * (a[4] + a[5]);
    pol D = a[0]*a[3];
    pol E = a[1]*a[4];
    pol F = a[2]*a[5];

    QCMul * (a[6] - (C + D - E - F)) = 0;
    QCMul * (a[7] - (A + C - 2*E - D)) = 0;
    QCMul * (a[8] - (B - D + E)) = 0;

// Connection equations
    {a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], a[9], a[10], a[11]} connect
        {S[0], S[1], S[2], S[3], S[4], S[5], S[6], S[7], S[8], S[9], S[10], S[11]};

• fibonacci.c12.const
• Fibonacci.c12.exec

r1cs2plonk

首先读取r1cs 文件

 const r1cs = await readR1cs(r1csFile, {F: F, logger:console });

r1cs 的结构为：

• constraints: 所有的约束条件，对于Fibonacci例子，总共有331913个；

每个约束条件的形式为：

其中 为系数， 分别为输入的变量。

• customGates:

包含了两个定制电路，分别为MDS 和 CMul 。

• customGatesUses

定制电路的使用次数，总共13845个。

• F: F3G
• n8：16
• nConstraints: 331913
• nLabels: 678212
• nOutputs: 0
• nPrvInputs: 2280
• nPubInputs: 3
• nVars: 496743
• prime: 18446744069414584321n
• useCustomGates: true

然后将r1cs 电路转换为plonk 电路：

const F = new F3G();
const [plonkConstraints, plonkAdditions] = r1cs2plonk(F, r1cs);

首先读取每个每个约束条件：

for (let c=0; c<r1cs.constraints.length; c++) {
        if ((logger)&&(c%10000 == 0)) logger.debug(`processing constraints: ${c}/${r1cs.nConstraints}`);
        process(...r1cs.constraints[c]);
    }

以第一个为例， 其形式为：

lcA:{
  "0": 18446744069414584320n,   // 表示常数项
  "2251": 14151741787267893881n,  //key 表示变量， value 表示对应的系数 
}

lcB:{
  "2338": 1n,
}

lcC:{
  "2339": 18446744069414584320n,
}

然后根据lcA 和 lcB 的类型，分别进行处理：

    function process(lcA, lcB, lcC) {
        const lctA = getLCType(lcA);
        const lctB = getLCType(lcB);
        if ((lctA == "0") || (lctB == "0")) {
            normalize(lcC);
            addConstraintSum(lcC);
        } else if (lctA == "k") {
            const lcCC = join(lcB, lcA[0], lcC);
            addConstraintSum(lcCC);
        } else if (lctB == "k") {
            const lcCC = join(lcA, lcB[0], lcC);
            addConstraintSum(lcCC);
        } else {
            addConstraintMul(lcA, lcB, lcC);
        }
    }

• getLCType 主要获取线性组合类型，返回大于0的数表示带变量的线性组合，返回k 表示常量，返回0 表示0。

• normalize 剔除系数为0的变量；

• addContraintSum 表示转换加法的Plonk 电路：

    function addConstraintSum(lc) {
        const C = reduceCoefs(lc, 3);
        const sl = C.s[0];
        const sr = C.s[1];
        const so = C.s[2];
        const qm = F.zero;
        const ql = C.coefs[0];
        const qr = C.coefs[1];
        const qo = C.coefs[2];
        const qc = C.k;
        plonkConstraints.push([sl, sr, so, qm, ql, qr, qo, qc]);
    }

注： plonk 电路的标准形式为：

• addConstraintMul 表示转换为Plonk 乘法电路：

    function addConstraintMul(lcA, lcB, lcC) {
        const A = reduceCoefs(lcA, 1);
        const B = reduceCoefs(lcB, 1);
        const C = reduceCoefs(lcC, 1);


        const sl = A.s[0];
        const sr = B.s[0];
        const so = C.s[0];
        const qm = F.mul(A.coefs[0], B.coefs[0]);
        const ql = F.mul(A.coefs[0], B.k);
        const qr = F.mul(A.k, B.coefs[0]);
        const qo = F.neg(C.coefs[0]);
        const qc = F.sub(F.mul(A.k, B.k) , C.k);
        plonkConstraints.push([sl, sr, so, qm, ql, qr, qo, qc]);
    }

上述对Plonk 加法和乘法电路的处理过程中，用到了reduceCoefs 函数 ，它可以将过长的线性组合进行拆分，通过定义的新中间变量将其都生成PLonk 约束条件。

最终生成plonkConstraints 和 plonkAdditions， 分别别表Plonk 约束条件和 Plonk 加法运算。

plonkConstraints.push([sl, sr, so, qm, ql, qr, qo, qc]);

plonkAdditions.push([sl, sr, c1[1], c2[1]]);

PIL 生成

首先生成plonkInfo, 具体结构为：

{
   N：85280， // 使用 Plonk的 行数
   nConstraints: 331913,  // R1CS 约束条件个数
   nPlonkAdditions: 7530,  // Plonk 加法个数
   nPlonkConstraints: 339443 // Plonk 约束条件个数 = r1cs + plonk addition
}

然后获取定制门信息customGatesInfo ，具体结构为：

{
   CMDSId: 0,  // 表示MDS 定制门
   CMulId: 1,   // 表示乘法定制门
   nCMul: 375,  // 乘法定制门个数
   nMDS: 13470  // MDS 定制门个数
}

其中乘法定制门为：

template custom CMul() {
    signal input ina[3];
    signal input inb[3];
    signal output out[3];

    var A = (ina[0] + ina[1])  * (inb[0] + inb[1]);
    var B = (ina[0] + ina[2])  * (inb[0] + inb[2]);
    var C = (ina[1] + ina[2])  * (inb[1] + inb[2]);
    var D = ina[0]*inb[0];
    var E = ina[1]*inb[1];
    var F = ina[2]*inb[2];
    var G = D-E;

    out[0] <-- C+G-F;
    out[1] <-- A+C-E-E-D;
    out[2] <-- B-G;
}

MDS定制门为：

template custom MDS() {
    signal input in[12];
    signal output out[12];

    out[ 0] <-- 25*in[0] + 15*in[1] + 41*in[2] + 16*in[3] +  2*in[4] + 28*in[5] + 13*in[6] + 13*in[7] + 39*in[8] + 18*in[9] + 34*in[10] + 20*in[11];
    out[ 1] <-- 20*in[0] + 17*in[1] + 15*in[2] + 41*in[3] + 16*in[4] +  2*in[5] + 28*in[6] + 13*in[7] + 13*in[8] + 39*in[9] + 18*in[10] + 34*in[11];
    out[ 2] <-- 34*in[0] + 20*in[1] + 17*in[2] + 15*in[3] + 41*in[4] + 16*in[5] +  2*in[6] + 28*in[7] + 13*in[8] + 13*in[9] + 39*in[10] + 18*in[11];
    out[ 3] <-- 18*in[0] + 34*in[1] + 20*in[2] + 17*in[3] + 15*in[4] + 41*in[5] + 16*in[6] +  2*in[7] + 28*in[8] + 13*in[9] + 13*in[10] + 39*in[11];
    out[ 4] <-- 39*in[0] + 18*in[1] + 34*in[2] + 20*in[3] + 17*in[4] + 15*in[5] + 41*in[6] + 16*in[7] +  2*in[8] + 28*in[9] + 13*in[10] + 13*in[11];
    out[ 5] <-- 13*in[0] + 39*in[1] + 18*in[2] + 34*in[3] + 20*in[4] + 17*in[5] + 15*in[6] + 41*in[7] + 16*in[8] +  2*in[9] + 28*in[10] + 13*in[11];
    out[ 6] <-- 13*in[0] + 13*in[1] + 39*in[2] + 18*in[3] + 34*in[4] + 20*in[5] + 17*in[6] + 15*in[7] + 41*in[8] + 16*in[9] +  2*in[10] + 28*in[11];
    out[ 7] <-- 28*in[0] + 13*in[1] + 13*in[2] + 39*in[3] + 18*in[4] + 34*in[5] + 20*in[6] + 17*in[7] + 15*in[8] + 41*in[9] + 16*in[10] +  2*in[11];
    out[ 8] <--  2*in[0] + 28*in[1] + 13*in[2] + 13*in[3] + 39*in[4] + 18*in[5] + 34*in[6] + 20*in[7] + 17*in[8] + 15*in[9] + 41*in[10] + 16*in[11];
    out[ 9] <-- 16*in[0] +  2*in[1] + 28*in[2] + 13*in[3] + 13*in[4] + 39*in[5] + 18*in[6] + 34*in[7] + 20*in[8] + 17*in[9] + 15*in[10] + 41*in[11];
    out[10] <-- 41*in[0] + 16*in[1] +  2*in[2] + 28*in[3] + 13*in[4] + 13*in[5] + 39*in[6] + 18*in[7] + 34*in[8] + 20*in[9] + 17*in[10] + 15*in[11];
    out[11] <-- 15*in[0] + 41*in[1] + 16*in[2] +  2*in[3] + 28*in[4] + 13*in[5] + 13*in[6] + 39*in[7] + 18*in[8] + 34*in[9] + 20*in[10] + 17*in[11];
}

然后计算Plonk 使用的行数：

    // 公开输入占的行数，每行12个寄存器
    const nPublics = r1cs.nOutputs + r1cs.nPubInputs;
    const nPublicRows = Math.floor((nPublics - 1) / 12) + 1;
     
    // nPublicRows: 公开输入的行数
    // plonkInfo.N: plonk点用的行数
    // nCmul: 乘法定制门个数，每个一行
    // nMDS: MDS定制门个数，每个占用两行
    const NUsed = nPublicRows + plonkInfo.N + customGatesInfo.nCMul + customGatesInfo.nMDS * 2;   // 表示使用的行数
    const nBits = log2(NUsed - 1) + 1; // 扩展为2的幂
    const N = 1 << nBits;

然后生成PIL 文件：

    const template = await fs.promises.readFile(path.join(__dirname, "compressor12.pil.ejs"), "utf8");
    const obj = {
        N: N,   // Plonk 总行数
        NUsed: NUsed,  // Plonk 使用的行数
        nBits: nBits,   // 占用的bits 长度
        nPublics: nPublics  // 公开输入的个数
    };

    const pilStr = ejs.render(template, obj);
    const pilFile = await tmpName();
    await fs.promises.writeFile(pilFile, pilStr, "utf8");

最终生成PIL文件的内容为：

constant %N = 2**17;

namespace Global(%N);
    pol constant L1;

namespace Compressor(%N);
    pol constant S[12];  // 用于copy constraints
    pol constant Qm, Ql, Qr, Qo, Qk, QMDS, QCMul; // 选择子
    pol commit a[12];    //寄存器

    public pub0 = a[0](0);  // 公开输入
    public pub1 = a[1](0); 
    public pub2 = a[2](0);
    Global.L1 * (a[0] - :pub0) = 0;
    Global.L1 * (a[1] - :pub1) = 0;
    Global.L1 * (a[2] - :pub2) = 0;

// Normal plonk ecuations   //标准Plonk 电路，一行有4个Plonk 标准电路
    pol a01 = a[0]*a[1];
    Qm*a01 + Ql*a[0] + Qr*a[1] + Qo*a[2] + Qk = 0;

    pol a34 = a[3]*a[4];
    Qm*a34 + Ql*a[3] + Qr*a[4] + Qo*a[5] + Qk = 0;

    pol a67 = a[6]*a[7];
    Qm*a67 + Ql*a[6] + Qr*a[7] + Qo*a[8] +Qk = 0;

    pol a910 = a[9]*a[10];
    Qm*a910 + Ql*a[9] + Qr*a[10] + Qo*a[11] +Qk = 0;

// MDS  定制电路，一个电路占用两行

    QMDS * (a[ 0]' - (25*a[0] + 15*a[1] + 41*a[2] + 16*a[3] +  2*a[4] + 28*a[5] + 13*a[6] + 13*a[7] + 39*a[8] + 18*a[9] + 34*a[10] + 20*a[11])) = 0;
    QMDS * (a[ 1]' - (20*a[0] + 17*a[1] + 15*a[2] + 41*a[3] + 16*a[4] +  2*a[5] + 28*a[6] + 13*a[7] + 13*a[8] + 39*a[9] + 18*a[10] + 34*a[11])) = 0;
    QMDS * (a[ 2]' - (34*a[0] + 20*a[1] + 17*a[2] + 15*a[3] + 41*a[4] + 16*a[5] +  2*a[6] + 28*a[7] + 13*a[8] + 13*a[9] + 39*a[10] + 18*a[11])) = 0;
    QMDS * (a[ 3]' - (18*a[0] + 34*a[1] + 20*a[2] + 17*a[3] + 15*a[4] + 41*a[5] + 16*a[6] +  2*a[7] + 28*a[8] + 13*a[9] + 13*a[10] + 39*a[11])) = 0;
    QMDS * (a[ 4]' - (39*a[0] + 18*a[1] + 34*a[2] + 20*a[3] + 17*a[4] + 15*a[5] + 41*a[6] + 16*a[7] +  2*a[8] + 28*a[9] + 13*a[10] + 13*a[11])) = 0;
    QMDS * (a[ 5]' - (13*a[0] + 39*a[1] + 18*a[2] + 34*a[3] + 20*a[4] + 17*a[5] + 15*a[6] + 41*a[7] + 16*a[8] +  2*a[9] + 28*a[10] + 13*a[11])) = 0;
    QMDS * (a[ 6]' - (13*a[0] + 13*a[1] + 39*a[2] + 18*a[3] + 34*a[4] + 20*a[5] + 17*a[6] + 15*a[7] + 41*a[8] + 16*a[9] +  2*a[10] + 28*a[11])) = 0;
    QMDS * (a[ 7]' - (28*a[0] + 13*a[1] + 13*a[2] + 39*a[3] + 18*a[4] + 34*a[5] + 20*a[6] + 17*a[7] + 15*a[8] + 41*a[9] + 16*a[10] +  2*a[11])) = 0;
    QMDS * (a[ 8]' - ( 2*a[0] + 28*a[1] + 13*a[2] + 13*a[3] + 39*a[4] + 18*a[5] + 34*a[6] + 20*a[7] + 17*a[8] + 15*a[9] + 41*a[10] + 16*a[11])) = 0;
    QMDS * (a[ 9]' - (16*a[0] +  2*a[1] + 28*a[2] + 13*a[3] + 13*a[4] + 39*a[5] + 18*a[6] + 34*a[7] + 20*a[8] + 17*a[9] + 15*a[10] + 41*a[11])) = 0;
    QMDS * (a[10]' - (41*a[0] + 16*a[1] +  2*a[2] + 28*a[3] + 13*a[4] + 13*a[5] + 39*a[6] + 18*a[7] + 34*a[8] + 20*a[9] + 17*a[10] + 15*a[11])) = 0;
    QMDS * (a[11]' - (15*a[0] + 41*a[1] + 16*a[2] +  2*a[3] + 28*a[4] + 13*a[5] + 13*a[6] + 39*a[7] + 18*a[8] + 34*a[9] + 20*a[10] + 17*a[11])) = 0;

// CMUL // mul 乘法定制电路，一个占用一行

    pol A = (a[0] + a[1])  * (a[3] + a[4]);
    pol B = (a[0] + a[2])  * (a[3] + a[5]);
    pol C = (a[1] + a[2])  * (a[4] + a[5]);
    pol D = a[0]*a[3];
    pol E = a[1]*a[4];
    pol F = a[2]*a[5];

    QCMul * (a[6] - (C + D - E - F)) = 0;
    QCMul * (a[7] - (A + C - 2*E - D)) = 0;
    QCMul * (a[8] - (B - D + E)) = 0;

// Connection equations
    {a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], a[9], a[10], a[11]} connect
        {S[0], S[1], S[2], S[3], S[4], S[5], S[6], S[7], S[8], S[9], S[10], S[11]};

公开输入的处理

    const sMap = []; // sMap 主要用于处理copy constraint
    for (let i = 0; i < 12; i++) {  // 12对应着12列，即12个寄存器
        sMap[i] = new Uint32Array(NUsed);
    }

    let r = 0; // 用于标识所处理行的位置

    // Paste public inputs.
    for (let i = 0; i < nPublicRows; i++) { // 处理公开输入时，其余选择子置为 0
        constPols.Compressor.Qm[r + i] = 0n;
        constPols.Compressor.Ql[r + i] = 0n;
        constPols.Compressor.Qr[r + i] = 0n;
        constPols.Compressor.Qo[r + i] = 0n;
        constPols.Compressor.Qk[r + i] = 0n;
        constPols.Compressor.QCMul[r + i] = 0n;
        constPols.Compressor.QMDS[r + i] = 0n;
    }

    for (let i = 0; i < nPublics; i++) { // sMap 赋值
        sMap[i % 12][r + Math.floor(1 / 12)] = 1 + i;
    }

    for (let i = nPublics; i < nPublicRows * 12; i++) { // 其余补 0
        sMap[i % 12][r + Math.floor(1 / 12)] = 0;
    }
    r += nPublicRows;

PLonk 标准电路处理

本部分主要对plonk 选择子，以及sMap 进行赋值，将具有相同系数的Plonk 电路，每4个放于一行上，以减少Plonk 电路的行数。

    // Paste plonk constraints.
    const partialRows = {};
    for (let i = 0; i < plonkConstraints.length; i++) {
        if ((i % 10000) == 0) console.log(`Processing constraint... ${i}/${plonkConstraints.length}`);
        const c = plonkConstraints[i];
        const k = c.slice(3, 8).map(a => a.toString(16)).join(",");
        if (partialRows[k]) {  // 对于具有相同系数的数Plonk 电路，每4个放于一行上
            const pr = partialRows[k];
            sMap[pr.nUsed * 3][pr.row] = c[0];
            sMap[pr.nUsed * 3 + 1][pr.row] = c[1];
            sMap[pr.nUsed * 3 + 2][pr.row] = c[2];
            pr.nUsed++;
            if (pr.nUsed == 4) {
                delete partialRows[k];
            }
        } else {
            constPols.Compressor.Qm[r] = c[3]; // Plonk 选择子赋值
            constPols.Compressor.Ql[r] = c[4];
            constPols.Compressor.Qr[r] = c[5];
            constPols.Compressor.Qo[r] = c[6];
            constPols.Compressor.Qk[r] = c[7];
            constPols.Compressor.QCMul[r] = 0n;  // 定制电路的选择子赋0
            constPols.Compressor.QMDS[r] = 0n;
            sMap[0][r] = c[0];  // sMap 赋值
            sMap[1][r] = c[1];
            sMap[2][r] = c[2];
            partialRows[k] = {
                row: r,
                nUsed: 1
            };
            r++;
        }
    }

对于相同系数Plonk约束不是4的整数倍的，需要进行填充处理：

 // Terminate the empty rows (Copyn the same constraint)
    const openRows = Object.keys(partialRows);
    for (let i = 0; i < openRows.length; i++) {
        const pr = partialRows[openRows[i]];
        for (let j = pr.nUsed; j < 4; j++) {
            sMap[j * 3][pr.row] = sMap[0][pr.row]; // 填充为该行的第一个Plonk 约束
            sMap[j * 3 + 1][pr.row] = sMap[1][pr.row];;
            sMap[j * 3 + 2][pr.row] = sMap[2][pr.row];;
        }
    }

Plonk 定制电路处理

对涉及到的定制电路 MDS 和 MUL 的常量多项式，以及sMap 分别进行赋值。

    // Generate Custom Gates
    for (let i = 0; i < r1cs.customGatesUses.length; i++) {
        if ((i % 10000) == 0) console.log(`Processing custom gates... ${i}/${r1cs.customGatesUses.length}`);
        const cgu = r1cs.customGatesUses[i];
        if (cgu.id == customGatesInfo.CMDSId) { // MDS 定制电路
            assert(cgu.signals.length == 24);
            for (let i = 0; i < 12; i++) {
                sMap[i][r] = cgu.signals[i];     // sMap 赋值
                sMap[i][r + 1] = cgu.signals[i + 12];
            }
            constPols.Compressor.Qm[r] = 0n;
            constPols.Compressor.Ql[r] = 0n;
            constPols.Compressor.Qr[r] = 0n;
            constPols.Compressor.Qo[r] = 0n;
            constPols.Compressor.Qk[r] = 0n;
            constPols.Compressor.QCMul[r] = 0n;
            constPols.Compressor.QMDS[r] = 1n;     // MDS 选择子
            constPols.Compressor.Qm[r + 1] = 0n;
            constPols.Compressor.Ql[r + 1] = 0n;
            constPols.Compressor.Qr[r + 1] = 0n;
            constPols.Compressor.Qo[r + 1] = 0n;
            constPols.Compressor.Qk[r + 1] = 0n;
            constPols.Compressor.QCMul[r + 1] = 0n;
            constPols.Compressor.QMDS[r + 1] = 0n;

            r += 2;     // 占用两行 
        } else if (cgu.id == customGatesInfo.CMulId) {   // MUL 定制电路
            for (let i = 0; i < 9; i++) {
                sMap[i][r] = cgu.signals[i];  // sMap 赋值，占用9例
            }
            for (let i = 9; i < 12; i++) {
                sMap[i][r] = 0;      // sMap其实赋0
            }
            constPols.Compressor.Qm[r] = 0n;
            constPols.Compressor.Ql[r] = 0n;
            constPols.Compressor.Qr[r] = 0n;
            constPols.Compressor.Qo[r] = 0n;
            constPols.Compressor.Qk[r] = 0n;
            constPols.Compressor.QCMul[r] = 1n;
            constPols.Compressor.QMDS[r] = 0n;

            r += 1;    // 占用一行
        }
    }

计算S多项式

    // Calculate S Polynomials
    const ks = getKs(F, 11);   // 对应着12列， 即w^i, kw^i, k^2 w^i,... , k^{11}w^i, i 表示行号
    let w = F.one;
    for (let i = 0; i < N; i++) {
        if ((i % 10000) == 0) console.log(`Preparing S... ${i}/${N}`);
        constPols.Compressor.S[0][i] = w;
        for (let j = 1; j < 12; j++) {
            constPols.Compressor.S[j][i] = F.mul(w, ks[j - 1]);
        }
        w = F.mul(w, F.w[nBits]);
    }

调整具有相等值的位置索引，实现复制约束（copy constraints）：

    const lastSignal = {}
    for (let i = 0; i < r; i++) {
        if ((i % 10000) == 0) console.log(`Connection S... ${i}/${r}`);
        for (let j = 0; j < 12; j++) {
            if (sMap[j][i]) {
                if (typeof lastSignal[sMap[j][i]] !== "undefined") {
                    const ls = lastSignal[sMap[j][i]];
                    connect(constPols.Compressor.S[ls.col], ls.row, constPols.Compressor.S[j], i);  // connect 运算
                } else {
                    lastSignal[sMap[j][i]] = {
                        col: j,
                        row: i
                    };
                }
            }
        }
    }

其中最关键的是connect 函数 ,主要实现两个相同值坐标的交换：

    function connect(p1, i1, p2, i2) {
        [p1[i1], p2[i2]] = [p2[i2], p1[i1]];
    }

填充处理

对作剩作的Plonk 行，全部填充为0.

    // Fill unused rows
    while (r < N) {
        if ((r % 100000) == 0) console.log(`Empty gates... ${r}/${N}`);
        constPols.Compressor.Qm[r] = 0n;
        constPols.Compressor.Ql[r] = 0n;
        constPols.Compressor.Qr[r] = 0n;
        constPols.Compressor.Qo[r] = 0n;
        constPols.Compressor.Qk[r] = 0n;
        constPols.Compressor.QCMul[r] = 0n;
        constPols.Compressor.QMDS[r] = 0n;
        r += 1;
    }

然后处理Lagrange 常量多项式, 主要是

    for (let i = 0; i < nPublicRows; i++) {
        const L = constPols.Global["L" + (i + 1)];
        for (let i = 0; i < N; i++) {
            L[i] = 0n;
        }
        L[i] = 1n;
    }

最终结果

PlonkSetup 最终返回的结果为：

pilStr: 生成的PIL 文件内容
constPols: PIL 涉及到的常量多项式赋值
sMap: 主要用于copy constaints, 值为R1CS 变量编号
plonkAdditions: Plonk 所有加法操作

然后将相应的结果保存在文件中：

await fs.promises.writeFile(pilFile, res.pilStr, "utf8"); // 保存生成的PIL

await res.constPols.saveToFile(constFile);  // 保存生成的常量多项式

// 保存 plonkAdditions + sMap 数据
await writeExecFile(execFile,res.plonkAdditions,  res.sMap); 

main_compressor12_exec

主要用于生成承诺多项式的赋值，然后就可以利用STARK 生成证明。

输入输出

/usr/local/bin/node --max-old-space-size=32000 src/compressor12/main_compressor12_exec.js -i /Users/tron/test/polygon_zkevm/pil-stark/tmp/fibonacci.proof.zkin.json -w /Users/tron/test/polygon_zkevm/pil-stark/tmp/fibonacci.verifier_js/fibonacci.verifier.wasm -p /Users/tron/test/polygon_zkevm/pil-stark/tmp/fibonacci.c12.pil -e /Users/tron/test/polygon_zkevm/pil-stark/tmp/fibonacci.c12.exec -m /Users/tron/test/polygon_zkevm/pil-stark/tmp/fibonacci.c12.commit

涉及的输入为：

• fibonacci.proof.zkin.json ： 基于Goldilocks 生成的STARK 证明
• fibonacci.verifier.wasm: 用于生成witness 的wasm
• fibonacci.c12.pil: main_compressor12_setup 过程生成的 pil

输出为：

• fibonacci.c12.commit : 生成的承诺多项式

r1cs witness 生成

对r1cs 电路中的withness 赋值，首先将stark 证明作为输入，生成withness w；

其后由于转换为于Plonk电路，生成了一些临时变量，对这些变量进行赋值。

    const pil = await compile(F, pilFile, null, pilConfig);

    const cmPols = newCommitPolsArray(pil); // 用于保存生成的withness 

    const wc = await WitnessCalculatorBuilder(wasm);
    const w = await wc.calculateWitness(input); // 将stark proof 作为输入

    for (let i=0; i<nAdds; i++) {  // 对于转换为Plonk电路时生成的临时变量进行赋值
        w.push( F.add( F.mul( w[addsBuff[i*4]], addsBuff[i*4 + 2]), F.mul( w[addsBuff[i*4+1]],  addsBuff[i*4+3]  )));
    }

承诺多项式赋值

根据sMap， 对PIL 中的承诺多项式a[12] 进行赋值，并将最后生成的承诺多项式保存起来。

    for (let i=0; i<nSMap; i++) {
        for (let j=0; j<12; j++) {
            if (sMapBuff[12*i+j] != 0) {
                cmPols.Compressor.a[j][i] = w[sMapBuff[12*i+j]];
            } else {
                cmPols.Compressor.a[j][i] = 0n;
            }
        }
    }

    for (let i=nSMap; i<N; i++) {
        for (let j=0; j<12; j++) {
            cmPols.Compressor.a[j][i] = 0n;
        }
    }
    
await cmPols.saveToFile(commitFile);

SNARK 证明

Circom 是基于Rust开发的编译器，主要编译circom 语言开发的电路，输出约束系统的表示，由snarkjs 生成SNARK 证明。

Rank-1 constraint system

R1CS 约束系统具有如下形式：

证明者需要提供有效的witness 生成零知识证明。

示例

电路编译

pragma circom 2.0.0;

template Multiplier2() {
    signal input a;
    signal input b;
    signal output c;
    c <== a*b;
 }

 component main = Multiplier2();

然后对电路编译：

circom multiplier2.circom --r1cs --wasm --sym --c

• --r1cs: 生成multiplier2.r1cs ， 包含约束系统的描述；
• --wasm: 生成 Wasm 代码，用于生成witness ;
• --sym: 生成·multiplier2.sys 符号文件用于调试；
• --c: 生成C代码用于生成witness.

生成witness

构建输入input.json 为：

{"a": 3, "b": 11}

然后调用Wasm 生成witness 为：

node generate_witness.js multiplier2.wasm input.json witness.wtns

生成证明

开启Powers of tau

snarkjs powersoftau new bn128 12 pot12_0000.ptau -v

参与Powers of tau

snarkjs powersoftau contribute pot12_0000.ptau pot12_0001.ptau --name="First contribution" -v

开始阶段2

阶段2与电路相关，通过以下命令开始启动阶段2：

snarkjs powersoftau prepare phase2 pot12_0001.ptau pot12_final.ptau -v

然后生成.zkey 文件包含证明和验证密钥，执行如下命令：

snarkjs groth16 setup multiplier2.r1cs pot12_final.ptau multiplier2_0000.zkey

参与阶段2：

snarkjs zkey contribute multiplier2_0000.zkey multiplier2_0001.zkey --name="1st Contributor Name" -v

导出验证密钥：

snarkjs zkey export verificationkey multiplier2_0001.zkey verification_key.json

生成的验证密钥verification_key.json为：

{
 "pi_a": [
  "12760910679062051146028245764180144304135176860171829439423433793987947801318",
  "15627351643566791700410887806223057411723190268680338266476116334981291160699",
  "1"
 ],
 "pi_b": [
  [
   "1765658782548091050330101314873972200746475466904382545933668714427728146407",
   "8831055067363820406189809670502192437243044552509000960737961795818836572464"
  ],
  [
   "17406360157052120611680078243109373801402264858772382543913010037295998951887",
   "13607675671111808291939915735439749555363789088081636489573695410874630259559"
  ],
  [
   "1",
   "0"
  ]
 ],
 "pi_c": [
  "2792640172422648679222543320314624195856069203876481047009502575189585240826",
  "5913917177125152097186179448098822785808387757499429789332191237284364705015",
  "1"
 ],
 "protocol": "groth16",
 "curve": "bn128"
}

生成证明

snarkjs groth16 prove multiplier2_0001.zkey witness.wtns proof.json public.json

其中public.json 为：

[
 "33"
]

proof.json 为：

{
 "pi_a": [
  "12760910679062051146028245764180144304135176860171829439423433793987947801318",
  "15627351643566791700410887806223057411723190268680338266476116334981291160699",
  "1"
 ],
 "pi_b": [
  [
   "1765658782548091050330101314873972200746475466904382545933668714427728146407",
   "8831055067363820406189809670502192437243044552509000960737961795818836572464"
  ],
  [
   "17406360157052120611680078243109373801402264858772382543913010037295998951887",
   "13607675671111808291939915735439749555363789088081636489573695410874630259559"
  ],
  [
   "1",
   "0"
  ]
 ],
 "pi_c": [
  "2792640172422648679222543320314624195856069203876481047009502575189585240826",
  "5913917177125152097186179448098822785808387757499429789332191237284364705015",
  "1"
 ],
 "protocol": "groth16",
 "curve": "bn128"
}

生成验证合约

可以生成Solidity 验证合约，如下所示：

snarkjs zkey export solidityverifier multiplier2_0001.zkey verifier.sol

生成合约调用参数：

snarkjs generatecall

参考

https://github.com/0xPolygonHermez/pil-stark

https://github.com/0xPolygonHermez/pil-stark/blob/main/src/main_pil2circom.js

https://docs.circom.io/

https://github.com/0xPolygonHermez/pil-stark/blob/main/src/compressor12/main_compressor12_setup.js

https://github.com/0xPolygonHermez/pil-stark/blob/main/src/compressor12/main_compressor12_exec.js