Polygon zkevm main_compressor12_setup

main_compressor12_setup 主要用于将Stark proof 生成 BN128 域上的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个；

每个约束条件的形式为：
$(a_{0} + a_{1}l_1 + a_{2}l_2+\cdots+a_{n}l_{n})\cdot(b_{0} + b_1r_1 + b_2r_2+\cdots+b_nr_{n})+(c_{0} + c_1o_1+\cdots+c_no_n)=0$
其中 $a, b, c$ 为系数， $l, r, o$ 分别为输入的变量。

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 电路的标准形式为：
$q_l\cdot s_l+q_r\cdot s_r+ q_o\cdot s_o+q_m\cdot q_l\cdot q_r + q_c = 0$

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 常量多项式, 主要是 $L_1(0)=1$

    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);

参考

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