投稿
  1. 首页
  2. 区块链

Polygon zkEVM中的常量多项式

虚拟人生2秘籍 • 2022-9-23 • 区块链 • 阅读 18

Polygon zkEVM中的常量多项式,第1张

1. 引言

具体见：

https://github.com/0xPolygonHermez/zkevm-proverjs/blob/main/pil/l 2. Global.pil中的常量多项式

Polygon zkEVM全局多项式Global.pil中包含3个constant多项式：

1）L1 constant多项式2）BYTE constant多项式3）BYTE2 constant多项式 
namespace Global(%N);
pol constant L1;    // 1, 0, 0, 0, 0,
pol constant BYTE;
pol constant BYTE2;

这些全局constant多项式的基本赋值情况为：

module.exports.buildConstants = async function (pols) {

    const F = new F1Field("0xFFFFFFFF00000001");

    const N = pols.BYTE.length;
    buidBYTE(pols.BYTE, F, N);
    buidBYTE2(pols.BYTE2, F, N);
    buildL1(pols.L1, F, N);

};

function buidBYTE2(pol, F, N) {
    const m = 1<<16;
    if (N<m) throw new Error("GLOBAL.BYTE does not fit");
    for (let i=0; i<m; i++) {
        pol[i] = BigInt(i);
    }

    for (let i=m; i<N; i++) {
        pol[i] = 0n;
    }
}

function buidBYTE(pol, F, N) {
    if (N<256) throw new Error("GLOBAL.BYTE does not fit");

    for (let i=0; i<256; i++) {
        pol[i] = BigInt(i);
    }

    for (let i=256; i<N; i++) {
        pol[i] = 0n;
    }
}

function buildL1(pol, F, N) {
    pol[0] = 1n;
    for ( let i=1; i<N; i++) pol[i] = 0n;
}

以 N = 2 31 N=2^{31} N=231为例，这些全局常量多项式的具体赋值为：

indexL1BYTEBYTE2
0100
1011
2022
3033
⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮
2540254254
2550255255
25600256
25700257
⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮
2 16 − 1 2^{16}-1 216−100 2 16 − 1 2^{16}-1 216−1
2 16 2^{16} 216000
2 16 + 1 2^{16}+1 216+1000
⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮
2 21 − 1 2^{21}-1 221−1000
3. main.pil中的常量多项式

main.pil中包含一个常量多项式STEP：【注意，在zkasm.js中，将STEP定义为只读寄存器。】

/// Constant Polynomials
pol constant STEP;  // 0, 1, 2, 3, .......

相应的赋值为：

module.exports = async function (pols) {

    const N = pols.STEP.length;

    for ( let i=0; i<N; i++) {
        pols.STEP[i] = BigInt(i);
    }
}

以 N = 2 31 N=2^{31} N=231为例，该常量多项式的具体赋值为：

indexSTEP
00
11
22
33
⋮ \vdots ⋮ ⋮ \vdots ⋮
2 21 − 1 2^{21}-1 221−1 2 21 − 1 2^{21}-1 221−1
4. rom.pil中的常量多项式

rom.pil中包含的常量多项式有：

namespace Rom(%N);

    pol constant CONST0;
    pol constant CONST1;
    pol constant CONST2;
    pol constant CONST3;
    pol constant CONST4;
    pol constant CONST5;
    pol constant CONST6;
    pol constant CONST7;
    pol constant offset;
    pol constant inA, inB, inC, inROTL_C, inD, inE, inSR, inFREE, inCTX, inSP, inPC, inGAS, inMAXMEM, inHASHPOS, inSTEP, inRR;
    pol constant setA, setB, setC, setD, setE, setSR, setCTX, setSP, setPC, setGAS, setMAXMEM, setHASHPOS, JMP, JMPN, JMPC, setRR;
    pol constant incStack, incCode;
    pol constant isStack;
    pol constant isCode;
    pol constant isMem;
    pol constant ind, indRR;
    pol constant useCTX;
    pol constant mOp, mWR;
    pol constant sWR, sRD;
    pol constant arith;
    pol constant arithEq0;
    pol constant arithEq1;
    pol constant arithEq2;
    pol constant arithEq3;
    pol constant memAlign, memAlignWR, memAlignWR8;
    pol constant hashK, hashKLen, hashKDigest;
    pol constant hashP, hashPLen, hashPDigest;
    pol constant bin;
    pol constant binOpcode;
    pol constant assert;

    pol constant line;

不过，rom.pil中的常量多项式的值不是固定的，而是根据zkasm编译出的json文件来设定：

module.exports.buildConstants = async function buildConstants(pols, rom) {

    const F = new F1Field("0xFFFFFFFF00000001");

    const N = pols.inA.length;

    const twoTo31 = Scalar.e(0x80000000);
    const maxInt = 2147483647;
    const minInt = -2147483648;
    const maxUInt = 0xFFFFFFFF;
    const minUInt = 0;

    if (rom.program.length>N) throw new Error("Rom is too big for this N");

    for (let i=0; i<rom.program.length; i++) {

        if (rom.program[i].CONST) {
            if (rom.program[i].CONSTL) throw new Error("Program mixed with long and short constants");
            pols.CONST0[i] = rom.program[i].CONST ? F.e(rom.program[i].CONST) : F.zero;
            pols.CONST1[i] = F.zero;
            pols.CONST2[i] = F.zero;
            pols.CONST3[i] = F.zero;
            pols.CONST4[i] = F.zero;
            pols.CONST5[i] = F.zero;
            pols.CONST6[i] = F.zero;
            pols.CONST7[i] = F.zero;
        } else if (rom.program[i].CONSTL) {
            [
                pols.CONST0[i],
                pols.CONST1[i],
                pols.CONST2[i],
                pols.CONST3[i],
                pols.CONST4[i],
                pols.CONST5[i],
                pols.CONST6[i],
                pols.CONST7[i],
            ] = scalar2fea(F, BigInt(rom.program[i].CONSTL));
        } else {
            pols.CONST0[i] = F.zero;
            pols.CONST1[i] = F.zero;
            pols.CONST2[i] = F.zero;
            pols.CONST3[i] = F.zero;
            pols.CONST4[i] = F.zero;
            pols.CONST5[i] = F.zero;
            pols.CONST6[i] = F.zero;
            pols.CONST7[i] = F.zero;
        }
        pols.offset[i] = rom.program[i].offset ? BigInt(rom.program[i].offset) : 0n;

        pols.inA[i] = rom.program[i].inA ? F.e(rom.program[i].inA) : F.zero;
        pols.inB[i] = rom.program[i].inB ? F.e(rom.program[i].inB) : F.zero;
        pols.inC[i] = rom.program[i].inC ? F.e(rom.program[i].inC) : F.zero;
        pols.inD[i] = rom.program[i].inD ? F.e(rom.program[i].inD) : F.zero;
        pols.inE[i] = rom.program[i].inE ? F.e(rom.program[i].inE) : F.zero;
        pols.inSR[i] = rom.program[i].inSR ? F.e(rom.program[i].inSR) : F.zero;
        pols.inCTX[i] = rom.program[i].inCTX ? F.e(rom.program[i].inCTX) : F.zero;
        pols.inSP[i] = rom.program[i].inSP ? F.e(rom.program[i].inSP) : F.zero;
        pols.inPC[i] = rom.program[i].inPC ? F.e(rom.program[i].inPC) : F.zero;
        pols.inMAXMEM[i] = rom.program[i].inMAXMEM ? F.e(rom.program[i].inMAXMEM) : F.zero;
        pols.inSTEP[i] = rom.program[i].inSTEP ? F.e(rom.program[i].inSTEP) : F.zero;
        pols.inFREE[i] = rom.program[i].inFREE ? F.e(rom.program[i].inFREE) : F.zero;
        pols.inGAS[i] = rom.program[i].inGAS ? F.e(rom.program[i].inGAS) : F.zero;
        pols.inRR[i] = rom.program[i].inRR ? F.e(rom.program[i].inRR) : F.zero;
        pols.inHASHPOS[i] = rom.program[i].inHASHPOS ? F.e(rom.program[i].inHASHPOS) : F.zero;
        pols.inROTL_C[i] = rom.program[i].inROTL_C ? F.e(rom.program[i].inROTL_C) : F.zero;

        pols.setA[i] = rom.program[i].setA ? 1n : 0n;
        pols.setB[i] = rom.program[i].setB ? 1n : 0n;
        pols.setC[i] = rom.program[i].setC ? 1n : 0n;
        pols.setD[i] = rom.program[i].setD ? 1n : 0n;
        pols.setE[i] = rom.program[i].setE ? 1n : 0n;
        pols.setSR[i] = rom.program[i].setSR ? 1n : 0n;
        pols.setCTX[i] = rom.program[i].setCTX ? 1n : 0n;
        pols.setSP[i] = rom.program[i].setSP ? 1n : 0n;
        pols.setPC[i] = rom.program[i].setPC ? 1n : 0n;
        pols.setGAS[i] = rom.program[i].setGAS ? 1n : 0n;
        pols.setMAXMEM[i] = rom.program[i].setMAXMEM ? 1n : 0n;
        pols.setRR[i] = rom.program[i].setRR ? 1n : 0n;
        pols.setHASHPOS[i] = rom.program[i].setHASHPOS ? 1n : 0n;

        pols.JMP[i] = rom.program[i].JMP ? 1n : 0n;
        pols.JMPC[i] = rom.program[i].JMPC ? 1n : 0n;
        pols.JMPN[i] = rom.program[i].JMPN ? 1n : 0n;

        pols.incStack[i] = rom.program[i].incStack ? BigInt(rom.program[i].incStack) : 0n;
        pols.incCode[i] = rom.program[i].incCode ? BigInt(rom.program[i].incCode) : 0n;

        pols.isStack[i] = rom.program[i].isStack ? 1n : 0n;
        pols.isCode[i] = rom.program[i].isCode ? 1n : 0n;
        pols.isMem[i] = rom.program[i].isMem ? 1n : 0n;
        pols.ind[i] = rom.program[i].ind ? 1n : 0n;
        pols.indRR[i] = rom.program[i].indRR ? 1n : 0n;
        pols.useCTX[i] = rom.program[i].useCTX ? 1n : 0n;

        pols.mOp[i] = rom.program[i].mOp ? 1n : 0n;
        pols.mWR[i] = rom.program[i].mWR ? 1n : 0n;
        pols.sRD[i] = rom.program[i].sRD ? 1n : 0n;
        pols.sWR[i] = rom.program[i].sWR ? 1n : 0n;
        pols.arith[i] = rom.program[i].arith ? 1n : 0n;
        pols.arithEq0[i] = rom.program[i].arithEq0 ? 1n : 0n;
        pols.arithEq1[i] = rom.program[i].arithEq1 ? 1n : 0n;
        pols.arithEq2[i] = rom.program[i].arithEq2 ? 1n : 0n;
        pols.arithEq3[i] = rom.program[i].arithEq3 ? 1n : 0n;
        pols.memAlign[i] = rom.program[i].memAlign ? 1n : 0n;
        pols.memAlignWR[i] = rom.program[i].memAlignWR ? 1n : 0n;
        pols.memAlignWR8[i] = rom.program[i].memAlignWR8 ? 1n : 0n;
        pols.hashK[i] = rom.program[i].hashK ? 1n : 0n;
        pols.hashKLen[i] = rom.program[i].hashKLen ? 1n : 0n;
        pols.hashKDigest[i] = rom.program[i].hashKDigest ? 1n : 0n;
        pols.hashP[i] = rom.program[i].hashP ? 1n : 0n;
        pols.hashPLen[i] = rom.program[i].hashPLen ? 1n : 0n;
        pols.hashPDigest[i] = rom.program[i].hashPDigest ? 1n : 0n;
        pols.bin[i] = rom.program[i].bin ? 1n : 0n;
        pols.binOpcode[i] = rom.program[i].binOpcode ? BigInt(rom.program[i].binOpcode) : 0n;
        pols.assert[i] = rom.program[i].assert ? 1n : 0n;


        pols.line[i] = BigInt(i);

    }

    for (let i= rom.program.length; i<N; i++) {
        pols.CONST0[i] = F.zero;
        pols.CONST1[i] = F.zero;
        pols.CONST2[i] = F.zero;
        pols.CONST3[i] = F.zero;
        pols.CONST4[i] = F.zero;
        pols.CONST5[i] = F.zero;
        pols.CONST6[i] = F.zero;
        pols.CONST7[i] = F.zero;
        pols.offset[i] = F.zero;

        pols.inA[i] = F.zero;
        pols.inB[i] = F.zero;
        pols.inC[i] = F.zero;
        pols.inD[i] = F.zero;
        pols.inE[i] = F.zero;
        pols.inSR[i] = F.zero;
        pols.inCTX[i] = F.zero;
        pols.inSP[i] = F.zero;
        pols.inPC[i] = F.zero;
        pols.inMAXMEM[i] = F.zero;
        pols.inSTEP[i] = F.zero;
        pols.inFREE[i] = F.zero;
        pols.inGAS[i] = F.zero;
        pols.inRR[i] = F.zero;
        pols.inHASHPOS[i] = F.zero;
        pols.inROTL_C[i] = F.zero;

        pols.setA[i] = F.zero;
        pols.setB[i] = F.zero;
        pols.setC[i] = F.zero;
        pols.setD[i] = F.zero;
        pols.setE[i] = F.zero;
        pols.setSR[i] = F.zero;
        pols.setCTX[i] = F.zero;
        pols.setSP[i] = F.zero;
        pols.setPC[i] = F.zero;
        pols.setGAS[i] = F.zero;
        pols.setMAXMEM[i] = F.zero;
        pols.setRR[i] = F.zero;
        pols.setHASHPOS[i] = F.zero;

        pols.JMP[i] = F.zero;
        pols.JMPC[i] = F.zero;
        pols.JMPN[i] = F.zero;

        pols.incStack[i] = F.zero;
        pols.incCode[i] = F.zero;

        pols.isStack[i] = F.zero;
        pols.isCode[i] = F.zero;
        pols.isMem[i] = F.zero;
        pols.ind[i] = F.zero;
        pols.indRR[i] = F.zero;
        pols.useCTX[i] = F.zero;

        pols.mOp[i] = F.zero;
        pols.mWR[i] = F.zero;
        pols.sRD[i] = F.zero;
        pols.sWR[i] = F.zero;
        pols.arith[i] = F.zero;
        pols.arithEq0[i] = F.zero;
        pols.arithEq1[i] = F.zero;
        pols.arithEq2[i] = F.zero;
        pols.arithEq3[i] = F.zero;
        pols.memAlign[i] = F.zero;
        pols.memAlignWR[i] = F.zero;
        pols.memAlignWR8[i] = F.zero;
        pols.hashK[i] = F.zero;
        pols.hashKLen[i] = F.zero;
        pols.hashKDigest[i] = F.zero;
        pols.hashP[i] = F.zero;
        pols.hashPLen[i] = F.zero;
        pols.hashPDigest[i] = F.zero;
        pols.bin[i] = F.zero;
        pols.binOpcode[i] = F.zero;
        pols.assert[i] = F.zero;

        pols.line[i] = BigInt(i);
    }

}
4.1 以arith.zkasm示例 对应的rom常量多项式

以zkevm-proverjs/test/zkasm/counters/arith.zkasm为例：

start:

        STEP => A
        0 :ASSERT

        0 => A
        CNT_ARITH :ASSERT
        CNT_BINARY :ASSERT
        CNT_KECCAK_F: ASSERT
        CNT_MEM_ALIGN :ASSERT
        CNT_POSEIDON_G :ASSERT
        CNT_PADDING_PG :ASSERT

        0 => A,B,C,D    :ARITH

        CNT_ARITH => A
        1               :ASSERT

        CNT_ARITH => A
        1               :ASSERT

        0x2000000000000000000000000000000000000000000000000000000000000001n => A
        0x100    => B
        0x73     => C
        0x20    => D
        0x173   :ARITH


        2 => A
        CNT_ARITH :ASSERT

        0 => A
        CNT_KECCAK_F: ASSERT
        CNT_MEM_ALIGN :ASSERT
        CNT_POSEIDON_G :ASSERT
        CNT_PADDING_PG :ASSERT

end:
       0 => A,B,C,D,E,CTX, SP, PC, GAS, MAXMEM, SR

finalWait:
        ${beforeLast()}  : JMPN(finalWait)

                         : JMP(start)
opINVALID:

经const rom = await zkasm.compile(path.join(__dirname, "zkasm", zkasmFile)); zkasmcom 编译后的结果为：

{
 "program": [
  {
   "inSTEP": "1",
   "setA": 1,
   "line": 3,
   "fileName": "arith.zkasm",
   "lineStr": "        STEP => A"
  },
  {
   "CONST": "0",
   "assert": 1,
   "line": 4,
   "fileName": "arith.zkasm",
   "lineStr": "        0 :ASSERT"
  },
  {
   "CONST": "0",
   "setA": 1,
   "line": 6,
   "fileName": "arith.zkasm",
   "lineStr": "        0 => A"
  },
  {
   "inCntArith": "1",
   "assert": 1,
   "line": 7,
   "fileName": "arith.zkasm",
   "lineStr": "        CNT_ARITH :ASSERT"
  },
  {
   "inCntBinary": "1",
   "assert": 1,
   "line": 8,
   "fileName": "arith.zkasm",
   "lineStr": "        CNT_BINARY :ASSERT"
  },
  {
   "inCntKeccakF": "1",
   "assert": 1,
   "line": 9,
   "fileName": "arith.zkasm",
   "lineStr": "        CNT_KECCAK_F: ASSERT"
  },
  {
   "inCntMemAlign": "1",
   "assert": 1,
   "line": 10,
   "fileName": "arith.zkasm",
   "lineStr": "        CNT_MEM_ALIGN :ASSERT"
  },
  {
   "inCntPoseidonG": "1",
   "assert": 1,
   "line": 11,
   "fileName": "arith.zkasm",
   "lineStr": "        CNT_POSEIDON_G :ASSERT"
  },
  {
   "inCntPaddingPG": "1",
   "assert": 1,
   "line": 12,
   "fileName": "arith.zkasm",
   "lineStr": "        CNT_PADDING_PG :ASSERT"
  },
  {
   "CONST": "0",
   "setA": 1,
   "setB": 1,
   "setC": 1,
   "setD": 1,
   "arith": 1,
   "arithEq0": 1,
   "line": 14,
   "fileName": "arith.zkasm",
   "lineStr": "        0 => A,B,C,D    :ARITH"
  },
  {
   "inCntArith": "1",
   "setA": 1,
   "line": 16,
   "fileName": "arith.zkasm",
   "lineStr": "        CNT_ARITH => A"
  },
  {
   "CONST": "1",
   "assert": 1,
   "line": 17,
   "fileName": "arith.zkasm",
   "lineStr": "        1               :ASSERT"
  },
  {
   "inCntArith": "1",
   "setA": 1,
   "line": 19,
   "fileName": "arith.zkasm",
   "lineStr": "        CNT_ARITH => A"
  },
  {
   "CONST": "1",
   "assert": 1,
   "line": 20,
   "fileName": "arith.zkasm",
   "lineStr": "        1               :ASSERT"
  },
  {
  # CONSTL为0x2000000000000000000000000000000000000000000000000000000000000001n，以8个寄存器CONST0~CONST7表示，对应CONST7值为0x20000000=536870912,CONST0=1。
   "CONSTL": "14474011154664524427946373126085988481658748083205070504932198000989141204993",
   "setA": 1,
   "line": 22,
   "fileName": "arith.zkasm",
   "lineStr": "        0x2000000000000000000000000000000000000000000000000000000000000001n => A"
  },
  {
   "CONST": "256",
   "setB": 1,
   "line": 23,
   "fileName": "arith.zkasm",
   "lineStr": "        0x100    => B"
  },
  {
   "CONST": "115",
   "setC": 1,
   "line": 24,
   "fileName": "arith.zkasm",
   "lineStr": "        0x73     => C"
  },
  {
   "CONST": "32",
   "setD": 1,
   "line": 25,
   "fileName": "arith.zkasm",
   "lineStr": "        0x20    => D"
  },
  {
   "CONST": "371",
   "arith": 1,
   "arithEq0": 1,
   "line": 26,
   "fileName": "arith.zkasm",
   "lineStr": "        0x173   :ARITH"
  },
  {
   "CONST": "2",
   "setA": 1,
   "line": 29,
   "fileName": "arith.zkasm",
   "lineStr": "        2 => A"
  },
  {
   "inCntArith": "1",
   "assert": 1,
   "line": 30,
   "fileName": "arith.zkasm",
   "lineStr": "        CNT_ARITH :ASSERT"
  },
  {
   "CONST": "0",
   "setA": 1,
   "line": 32,
   "fileName": "arith.zkasm",
   "lineStr": "        0 => A"
  },
  {
   "inCntKeccakF": "1",
   "assert": 1,
   "line": 33,
   "fileName": "arith.zkasm",
   "lineStr": "        CNT_KECCAK_F: ASSERT"
  },
  {
   "inCntMemAlign": "1",
   "assert": 1,
   "line": 34,
   "fileName": "arith.zkasm",
   "lineStr": "        CNT_MEM_ALIGN :ASSERT"
  },
  {
   "inCntPoseidonG": "1",
   "assert": 1,
   "line": 35,
   "fileName": "arith.zkasm",
   "lineStr": "        CNT_POSEIDON_G :ASSERT"
  },
  {
   "inCntPaddingPG": "1",
   "assert": 1,
   "line": 36,
   "fileName": "arith.zkasm",
   "lineStr": "        CNT_PADDING_PG :ASSERT"
  },
  {
   "CONST": "0",
   "setA": 1,
   "setB": 1,
   "setC": 1,
   "setD": 1,
   "setE": 1,
   "setCTX": 1,
   "setSP": 1,
   "setPC": 1,
   "setGAS": 1,
   "setMAXMEM": 1,
   "setSR": 1,
   "line": 39,
   "fileName": "arith.zkasm",
   "lineStr": "       0 => A,B,C,D,E,CTX, SP, PC, GAS, MAXMEM, SR"
  },
  {
   "freeInTag": {
    "op": "functionCall",
    "funcName": "beforeLast",
    "params": []
   },
   "inFREE": "1",
   "JMPC": 0,
   "JMPN": 1,
   "offset": 27,
   "line": 42,
   "offsetLabel": "finalWait",
   "fileName": "arith.zkasm",
   "lineStr": "        ${beforeLast()}  : JMPN(finalWait)"
  },
  {
   "JMP": 1,
   "JMPC": 0,
   "JMPN": 0,
   "offset": 0,
   "line": 44,
   "offsetLabel": "start",
   "fileName": "arith.zkasm",
   "lineStr": "                         : JMP(start)"
  }
 ],
 "labels": {
  "start": 0,
  "end": 26,
  "finalWait": 27,
  "opINVALID": 29
 }
}

对应的各常量多项式的赋值为：

indexCONST0CONST1CONST2CONST3CONST4CONST5CONST6CONST7offsetincStackincCodeisStackisCodeisMemindindPRuseCTXmOpmWRsWRsRDaritharithEq0arithEq1arithEq2arithEq3memAlignmemAlignWRmemAlignWR8hashKhashKLenhashDigesthashPhashPLenhashPDigestbinbinOpcodeassertlineinAinBinCinROTL_CinDinEinSRinFREEinCTXinSPinPCinGASinMAXMEMinHASHPOSinSTEPinPRsetAsetBsetCsetDsetEsetSRsetCTXsetSPsetPCsetGASsetMAXMEMsetHASHPOSJMPJMPNJMPCsetPR
000000000000000000000000000000000000000000000000000000101000000000000000
100000000000000000000000000000000000001100000000000000000000000000000000
200000000000000000000000000000000000000200000000000000001000000000000000
300000000000000000000000000000000000001300000000000000000000000000000000
400000000000000000000000000000000000001400000000000000000000000000000000
500000000000000000000000000000000000001500000000000000000000000000000000
600000000000000000000000000000000000001600000000000000000000000000000000
700000000000000000000000000000000000001700000000000000000000000000000000
800000000000000000000000000000000000001800000000000000000000000000000000
900000000000000000000011000000000000000900000000000000001111000000000000
10000000000000000000000000000000000000001000000000000000001000000000000000
11100000000000000000000000000000000000011100000000000000000000000000000000
12000000000000000000000000000000000000001200000000000000001000000000000000
13100000000000000000000000000000000000011300000000000000000000000000000000
1410000005368709120000000000000000000000000000001400000000000000001000000000000000
1525600000000000000000000000000000000000001500000000000000000100000000000000
1611500000000000000000000000000000000000001600000000000000000010000000000000
173200000000000000000000000000000000000001700000000000000000001000000000000
1837100000000000000000000110000000000000001800000000000000000000000000000000
19200000000000000000000000000000000000001900000000000000001000000000000000
20000000000000000000000000000000000000012000000000000000000000000000000000
21000000000000000000000000000000000000002100000000000000001000000000000000
22000000000000000000000000000000000000012200000000000000000000000000000000
23000000000000000000000000000000000000012300000000000000000000000000000000
24000000000000000000000000000000000000012400000000000000000000000000000000
25000000000000000000000000000000000000012500000000000000000000000000000000
26000000000000000000000000000000000000002600000000000000001111111111100000
270000000027000000000000000000000000000002700000000000000000000000000000100
28000000000000000000000000000000000000002800000000000000000000000000001000
29000000000000000000000000000000000000002900000000000000000000000000000000
⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮
2 21 − 1 2^{21}-1 221−100000000000000000000000000000000000000 2 21 − 1 2^{21}-1 221−100000000000000000000000000000000
5. byte4.pil中的常量多项式

byte4.pil主要用于构建任意32-bit（4字节）数字，其具有常量多项式SET——奇数行为1，偶数行为0。

/*
This state machine is able to builds any number of 4 bytes (32 bits)


Example for building numbers: 0x00030007, 0x12345678, 0x00050009 and 0
        SET     freeIN  out        out'
w^0     1       3       0          3
w^1     0       7       3          0x00030007
w^2     1       0x1234  0x00030007 0x1234
w^3     0       0x5678  0x1234     0x12345678
w^4     1       5       0x12345678 5
w^5     0       9       5          0x50009
w^6     1       0       0x50009    0
w^7     0       0       0          0

*/

include "global.pil";

namespace Byte4(%N);
    /// Constant Polynomials
    pol constant SET;    // 1, 0, 1, 0, 1, 0 ......

    /// State Polynomials
    pol commit freeIN;
    pol commit out;

    freeIN in Global.BYTE2;  // 0, 1, 2,       , 65535

    out' = SET*freeIN +
           (1-SET)*(out * 2**16 + freeIN);
6. padding_kk.pil中的常量多项式

padding_kk.pil中的常量多项式有：

	/* Read Data output
        crLatch * crValid {addr, crOffset - crLen -1, crLen, crV0C, crV1C, crV2C, crV3C, crV4C, crV5C, crV6C, crV7C}
    */

    /* Read Len output
        lastHashLatch {addr, len}
    */

    /* Read Len digest
        lastHashLatch { addr, hash0, hash1, hash2, hash3, hash4, hash5, hash6, hash7 }
    */

namespace PaddingKK(%N);

    // Polynomials that are used to compute a hash chunk
    pol constant r8Id;
	
	pol constant lastBlock;
    pol constant lastBlockLatch;
    pol constant r8valid;
	
	pol constant sOutId;
	
	pol constant forceLastHash;
	
	pol constant k_crOffset, k_crF0, k_crF1, k_crF2, k_crF3, k_crF4, k_crF5, k_crF6, k_crF7;
	
	pol constant crValid;

具体的赋值逻辑为：

const BYTESPERBLOCK = 136;
const BlockSize = 158418;

module.exports.buildConstants = async function (pols) {
    const poseidon = await buildPoseidon();
    const F = poseidon.F;

    const N = pols.lastBlock.length;

    const nBlocks = 9*Math.floor((N-1)/BlockSize);

    let p =0;

    pols.k_crF = [];
    for (let i=0; i<8; i++) {
        pols.k_crF[i] = pols[`k_crF${i}`];
    }

    for (let i=0; i<nBlocks; i++) {
        const bytesBlock = 136;
        for (let j=0; j<bytesBlock; j++) {
            pols.lastBlock[p] = (j == bytesBlock-1) ? 1n : 0n;
            pols.lastBlockLatch[p] = (j == bytesBlock-1) ? 1n : 0n;
            pols.crValid[p] = F.one;
            pols.r8Id[p] = F.e(p);
            pols.sOutId[p] =  (j == bytesBlock-1) ? F.e(i) : F.zero;
            pols.forceLastHash[p] = ((j == bytesBlock-1)&&(i==nBlocks-1)) ? F.one : F.zero;
            pols.r8valid[p] = F.one;
            p += 1;
        }
    }

    for (let i=p; i<N; i++) {
        pols.crValid[i] = F.zero;
        pols.r8Id[i] = F.zero;    // Must repeat the first byte
        pols.lastBlock[i] = i<N-1 ? F.zero : F.one;
        pols.lastBlockLatch[i] = F.zero;
        pols.sOutId[i] =  F.zero;
        pols.forceLastHash[i] = i==N-1 ? F.one : F.zero;
        pols.r8valid[i] = F.zero;
    }

    for (let i=0; i<32; i++) {
        pols.k_crOffset[i] = BigInt(i);
        const acci = Math.floor(i / 4);
        const sh = BigInt((i % 4)*8);
        for (let k=0; k<8; k++) {
            pols.k_crF[k][i] = (k == acci) ? BigInt(1n << sh) : 0n;
        }
    }

    for (let i=32; i<N; i++) {
        pols.k_crOffset[i] = pols.k_crOffset[0];
        for (let k=0; k<8; k++) {
            pols.k_crF[k][i] =  pols.k_crF[k][0]
        }
    }

}
7. arith.pil中的常量多项式

arith.pil中的常量多项式有：

namespace Arith(%N);

    pol constant BYTE2_BIT19;
    pol constant SEL_BYTE2_BIT19;
    pol constant GL_SIGNED_4BITS_C0;
    pol constant GL_SIGNED_4BITS_C1;
    pol constant GL_SIGNED_4BITS_C2;
    pol constant GL_SIGNED_18BITS;
    pol constant CLK[32];      // 1 if CLK==0 and 0 if CLK!=0

相应的赋值逻辑为：

module.exports.buildConstants = async function (pols) {
    const N = pols.CLK[0].length;

    buildClocks(pols, N, 32);
    buildByte2Bits16(pols, N);
    buildRange(pols, N, 'GL_SIGNED_4BITS_C0', -16n, 16n);
    buildRange(pols, N, 'GL_SIGNED_4BITS_C1', -16n, 16n, 33);
    buildRange(pols, N, 'GL_SIGNED_4BITS_C2', -16n, 16n, 33*33);
    buildRange(pols, N, 'GL_SIGNED_18BITS', -(2n**18n), (2n**18n));
}

function buildByte2Bits16(pols, N) {
    const modB1 = (2 ** 16);
    const modB2 = (2 ** 19);
    const modBase = modB1 + modB2
    for (let i = 0; i < N; i++) {
        const value = i % modBase;
        pols.SEL_BYTE2_BIT19[i] = (i < modB1 ? 0n:1n);
        pols.BYTE2_BIT19[i] = BigInt(value);
    }
}

function buildClocks(pols, N, clocksByCycle) {
    for (let i = 0; i < clocksByCycle; i++) {
        for (let j = 0; j < N; ++j) {
            pols.CLK[i][j] = ((j + (clocksByCycle - i)) % clocksByCycle) == 0 ? 1n : 0n;
        }
    }
}

function buildRange(pols, N, name, fromValue, toValue, steps = 1) {
    let value = fromValue;
    let csteps = steps;
    for (let i = 0; i < N; i++) {
        pols[name][i] = value;
        csteps -= 1;
        if (csteps <= 0) {
            csteps = steps;
            if (value === toValue) value = fromValue;
            else value += 1n;
        }
    }
}

其中CLK[0]~CLK[31]常量多项式的赋值为：【对角线值为1，以32行为一个周期，循环重复】

indexCLK[0]CLK[1]CLK[2] ⋯ \cdots ⋯CLK[31]
0100 ⋯ \cdots ⋯0
1010 ⋯ \cdots ⋯0
2001 ⋯ \cdots ⋯0
⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮
31000 ⋯ \cdots ⋯1
32100 ⋯ \cdots ⋯0
33010 ⋯ \cdots ⋯0
34001 ⋯ \cdots ⋯0
⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮
63000 ⋯ \cdots ⋯1
⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮ ⋮ \vdots ⋮

SEL_BYTE2_BIT19常量多项式的取值为：

当 i < 2 16 i<2^{16} i<216，SEL_BYTE2_BIT19 [ i ] [i] [i]=0；当 i ≥ 2 16 i\geq 2^{16} i≥216，SEL_BYTE2_BIT19 [ i ] [i] [i]=1。

BYTE2_BIT19常量多项式的取值为：

BYTE2_BIT19 [ i ] = i   %   ( 2 16 + 2 19 ) [i]=i\ \% \ (2^{16}+2^{19}) [i]=i % (216+219)。

GL_SIGNED_4BITS_C0常量多项式的取值为：buildRange(pols, N, 'GL_SIGNED_4BITS_C0', -16n, 16n);

依次赋值： − 16 , − 15 , − 14 , − 13 , ⋯   , − 1 , 0 , 1 , 2 , ⋯   , 15 , 16 -16,-15,-14,-13,\cdots,-1,0,1,2,\cdots,15, 16 −16,−15,−14,−13,⋯,−1,0,1,2,⋯,15,16，不断重复该赋值。

GL_SIGNED_4BITS_C1常量多项式的取值为：buildRange(pols, N, 'GL_SIGNED_4BITS_C1', -16n, 16n, 33);

依次赋值：33个 − 16 -16 −16，33个 − 15 -15 −15，……，33个 0 0 0，……，33个 15 15 15，33个 16 16 16。这 33 ∗ 33 33*33 33∗33个数之后，重复该赋值。

GL_SIGNED_4BITS_C2常量多项式的取值为：buildRange(pols, N, 'GL_SIGNED_4BITS_C2', -16n, 16n, 33*33);

依次赋值： 33 ∗ 33 33*33 33∗33个 − 16 -16 −16， 33 ∗ 33 33*33 33∗33个 − 15 -15 −15，……， 33 ∗ 33 33*33 33∗33个 0 0 0，……， 33 ∗ 33 33*33 33∗33个 15 15 15， 33 ∗ 33 33*33 33∗33个 16 16 16。这 33 ∗ 33 ∗ 33 33*33*33 33∗33∗33个数之后，重复该赋值。

GL_SIGNED_18BITS常量多项式的取值为：buildRange(pols, N, 'GL_SIGNED_18BITS', -(2n**18n), (2n**18n));

依次赋值： − 2 18 , − 2 18 + 1 , − 2 18 + 2 , − 2 18 + 3 , ⋯   , − 1 , 0 , 1 , 2 , ⋯   , 2 18 − 1 , 2 18 -2^{18},-2^{18}+1,-2^{18}+2,-2^{18}+3,\cdots,-1,0,1,2,\cdots,2^{18}-1,2^{18} −218,−218+1,−218+2,−218+3,⋯,−1,0,1,2,⋯,218−1,218，不断重复该赋值。 8. binary.pil中的常量多项式

binary.pil中的常量多项式有：

	//  ##############################################################
    //  CONSTANT POLINOMIALS
    //  ##############################################################
    //  Plockup polinomials
    //  ==============================================================
    //  ==== IN ====
    //  P_OPCODE    (3  bits) Operation code
    //  P_CIN       (1  bits) Carry in
    //  P_LAST      (1  bits) Last byte
    //  P_A         (8  bits) Input A
    //  P_B         (8  bits) Input B
    //  ==== OUT ======
    //  P_C         (8 bits) Output C
    //  P_COUT      (1  bits) Carry out
    //  P_USE_CARRY (1  bits) Carry out
    //  ==== TOTAL ====
    //  3 + 1 + 1 + 8 + 8 = 21 bits
    //  ==============================================================
    //  NAME    | 0 | 1 | 2 | 3 | ... | 32 |
    //  ==============================================================
    //  RESET   | 1 | 0 | 0 | 0 | ... |  1 |
    //  FACTOR0 | 0x1 | 0x100 | 0x10000 | 0x1000000 | 0x0 | 0x0   | ... | 0x0 | 0x0   | 0x0     | 0x0       |
    //  FACTOR1 | 0x0 | 0x0   | 0x0     | 0x0       | 0x1 | 0x100 | ... | 0x0 | 0x0   | 0x0     | 0x0       |
    //  ...
    //  FACTOR7 | 0x0 | 0x0   | 0x0     | 0x0       | 0x0 | 0x0   | ... | 0x1 | 0x100 | 0x10000 | 0x1000000 |
    pol constant P_OPCODE, P_A, P_B, P_CIN, P_LAST, P_USE_CARRY;
    pol constant P_C, P_COUT;

    pol constant RESET;
    pol constant FACTOR[8];

Polygon zkEVM的Binary状态机中的运算是基于byte运行的，每个256-bit数字需以8个32-bit（4-byte）寄存器来表示。【let REGISTERS_NUM = 8; let BYTES_PER_REGISTER = 4;】
每32 cycle结束时，通过RESET寄存器来重置寄存器值，并使用FACTOR寄存器来进行正确更新，如：a0' = a0 * (1 - RESET) + freeInA * FACTOR[0];。
FACTOR[0]-FACTOR[7]常量多项式赋值为：

/*  =========
    FACTORS
    =========
    FACTOR0 => 0x1  0x100   0x10000 0x01000000  0x0  0x0    0x0     0x0         ... 0x0  0x0    0x0     0x0         0x1 0x100   0x10000 0x01000000  0x0  ...
    FACTOR1 => 0x0  0x0     0x0     0x0         0x1  0x100  0x10000 0x01000000  ... 0x0  0x0    0x0     0x0         0x0 0x0     0x0     0x0         0x0  ...
    ...
    FACTOR7 => 0x0  0x0     0x0     0x0         0x0  0x0     0x0     0x0        ... 0x1  0x100  0x10000 0x01000000  0x0 0x0     0x0     0x0         0x0  ...
*/

RESET常量多项式的赋值为：【第0、255、511……n*256-1 位置处的值为1，其它位置均为0】

/*  =========
    RESET
    =========
    1 0 0 ... { REGISTERS_NUM * BYTES_PER_REGISTER } ... 0 1 0 ... { REGISTERS_NUM * BYTES_PER_REGISTER } 0
    1 0 0 ... { REGISTERS_NUM * BYTES_PER_REGISTER } ... 0 1 0 ... { REGISTERS_NUM * BYTES_PER_REGISTER } 0
    ...
    1 0 0 ... { REGISTERS_NUM * BYTES_PER_REGISTER } ... 0 1 0 ... { REGISTERS_NUM * BYTES_PER_REGISTER } 0
*/

P_A常量多项式赋值为：【 2 8 ∗ 2 8 2^8*2^8 28∗28个0， 2 8 ∗ 2 8 2^8*2^8 28∗28个1，……， 2 8 ∗ 2 8 2^8*2^8 28∗28个15；然后一共重复该过程 N / ( 2 8 ∗ 2 8 ) N/(2^8*2^8) N/(28∗28)次。】

/*  ============
    A
    =========
    0 .. {size} .. 0 1 .. {size} .. 1 ... {size} ... 15 ... {size} ... 15 (size * size)
    0 .. {size} .. 0 1 .. {size} .. 1 ... {size} ... 15 ... {size} ... 15
    ...
    0 .. {size} .. 0 1 .. {size} .. 1 ... {size} ... 15 ... {size} ... 15
*/

P_B常量多项式赋值为：【0-15，重复 2 8 2^8 28次；再重复 N / ( 2 8 ∗ 2 8 ) N/(2^8*2^8) N/(28∗28)次。】

/*  =========
    B
    =========
    0 1 2 .. {size} .. 15 0 1 2 .. {size} .. 15 0 1 2 .. {size} .. 15 0 1 2 ... {size} ... 15 (size * size)
    0 1 2 .. {size} .. 15 0 1 2 .. {size} .. 15 0 1 2 .. {size} .. 15 0 1 2 ... {size} ... 15 (size * size)
    ...
    0 1 2 .. {size} .. 15 0 1 2 .. {size} .. 15 0 1 2 .. {size} .. 15 0 1 2 ... {size} ... 15 (size * size)
 */

P_CIN常量多项式赋值为：【 2 8 ∗ 2 8 2^8*2^8 28∗28个0， 2 8 ∗ 2 8 2^8*2^8 28∗28个1；重复该过程 N / ( 2 ∗ 2 8 ∗ 2 8 ) N/(2*2^8*2^8) N/(2∗28∗28)次。】

/*
    =========
    CIN
    =========
    0 0 0 ... {AccumulatedSize} ... 0 0 0 1 1 1 ... {AccumulatedSize} ... 1 1 1
    0 0 0 ... {AccumulatedSize} ... 0 0 0 1 1 1 ... {AccumulatedSize} ... 1 1 1
    ...
    0 0 0 ... {AccumulatedSize} ... 0 0 0 1 1 1 ... {AccumulatedSize} ... 1 1 1
 */

P_OPCODE常量多项式赋值为：【其中current_size为 2 8 ∗ 2 8 ∗ 2 1 ∗ 2 1 2^8*2^8*2^1*2^1 28∗28∗21∗21】

/*
    =========
    OPCODE
    =========
    0 0 0 ... {current_size} ... 0 0 0
    1 1 1 ... {current_size} ... 1 1 1
    2 2 2 ... {current_size} ... 2 2 2
    ...
 */

P_LAST常量多项式赋值为：【accumulated_size个0，accumulated_size个1；重复该过程N/(accumulated_size*2)次。其中accumulated_size为 2 8 ∗ 2 8 ∗ 2 1 2^8*2^8*2^1 28∗28∗21。】

P_C、P_COUT、P_USE_CARRY常量多项式赋值为：【其本质是为所支持的所有运算构建相应的plookup table。有约束：{last, opcode, freeInA, freeInB , cIn, useCarry ,freeInC, cOut} in {P_LAST, P_OPCODE, P_A, P_B, P_CIN, P_USE_CARRY, P_C, P_COUT};】

 	buildP_C_P_COUT_P_USE_CARRY(
        pols.P_A,
        pols.P_B,
        pols.P_CIN,
        pols.P_LAST,
        pols.P_OPCODE,
        pols.P_USE_CARRY,
        pols.P_C,
        pols.P_COUT,
        N);
/*
    =========
    C & COUT
    =========
    1 => ADD
        * Extract less signative byte -> C
        * Get the carry out -> COUT
    0 => AND
        * A & B -> C
        * 0 -> COUT (AND doesn't have carry)
    。。。。。。
    default
        * 0 -> C
        * 0 -> COUT
 */
9. mem.pil中的常量多项式

mem.pil中的常量多项式有：

pol constant INCS; // 1......N
pol constant ISNOTLAST; // 1, 1, 1, .........1, 1, 0

具体的赋值为：
INCS = ( 1 , 2 , 3 , … , N − 1 , N ⏟ N ) \texttt{INCS} = (\underbrace{1, 2, 3, \dots,N-1, N}_{N}) INCS=(N 1,2,3,…,N−1,N​​)
ISNOTLAST = ( 1 , 1 , 1 , … , 1 , 0 ⏟ N ) \texttt{ISNOTLAST} = (\underbrace{1, 1, 1, \dots,1, 0}_{N}) ISNOTLAST=(N 1,1,1,…,1,0​​)

10. mem_align.pil中的常量多项式

mem_align.pil中的常量多项式有：

	// BYTE2A = 0 (x256), 1 (x256), 2 (x256), ..., 255 (x256)
    pol constant BYTE2A;

    // BYTE2B = 0, 1, 2, 4, **, 255, 0, 1, ..., 255
    pol constant BYTE2B;

    pol constant BYTE_C3072;

    // FACTOR was same for all combinations of offset, wr8, wr256 is a f(step)
    // FACTOR[7] = 2**24, 2**16, 2**8, 1, 0 (x60)
    // FACTOR[6] = 0, 0, 0, 0, 2**24, 2**16, 2**8, 1, 0 (x56)
    // FACTOR[5] = 0, 0, 0, 0, 0, 0, 0, 0, 2**24, 2**16, 2**8, 1, 0 (x52)
    // :
    // FACTOR[0] = 0 (x28), 2**24, 2**16, 2**8, 1, 0 (x32)
    pol constant FACTOR[8];

    // FACTOR change according the combinations of offset, wr8, wr256 and step.
    pol constant FACTORV[8];

    // STEP = 0,1,2,...,62,63,0,1,2,...
    pol constant STEP;

    // STEP
    //    0 - 1023  WR256 = 0 WR8 = 0
    // 1024 - 2047  WR256 = 1 WR8 = 0
    // 2048 - 3071  WR256 = 0 WR8 = 1
    pol constant WR256;
    pol constant WR8;

    // OFFSET = 0 (x64), 1 (x64), ... , 31 (x64), 32 (x64), 0 (x64), 1 (x64), ...
    pol constant OFFSET; // 0 - 31

    // RESET = 1, 0 (x63), 1, 0 (x63)
    pol constant RESET;

    pol constant SELM1;
附录：Polygon Hermez 2.0 zkEVM系列博客 ZK-Rollups工作原理Polygon zkEVM——Hermez 2.0简介Polygon zkEVM网络节点Polygon zkEVM 基本概念Polygon zkEVM ProverPolygon zkEVM工具——PIL和CIRCOMPolygon zkEVM节点代码解析Polygon zkEVM的pil-stark Fibonacci状态机初体验Polygon zkEVM的pil-stark Fibonacci状态机代码解析Polygon zkEVM PIL编译器——pilcom 代码解析Polygon zkEVM Arithmetic状态机

欢迎分享，转载请注明来源：内存溢出

原文地址: https://outofmemory.cn/zaji/2991053.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
虚拟人生2秘籍 虚拟人生2秘籍 一级用户组
0 0
上一篇 2022-09-23
下一篇 2022-09-23

发表评论

登录后才能评论

评论列表（0条）

保存