Polygon zkEVM STARK证明解析

本文主要对zkEVM STARK 证明过程进行介绍，它是实现zkEVM 的关键组件。

基础知识

Permutation

Plookup

参考：https://eprint.iacr.org/2020/315.pdf

Connection check

image.png

注：上图有误，S3第一行应为 $w^3$ , S1第四行应用为： $w^2$ .

connection check 计算实现可以参考Plonk 论文中的公式：

参考：https://eprint.iacr.org/2019/953.pdf

Goldiocks 域

Goldilocks 域为 $p=2^{64}-2^{32} + 1$ ，目前应用在Polygon Miden, Plonky2, zkEVM 等多个项目中，

其中 $\mathbb{F}^*_p$ 的阶为 $p-1$ , 即 $2^{64}-2^{32} = 2^{32}\cdot 3\cdot \cdot 5 \cdot 17 \cdot 257 \cdot 65537$ , 即具有 $2^{32}$ 次单元根，

$\mathbb{F}^*_p$ 的生成元为： $g = 7$

$2^{32}$ 次根的单位元为： $g^{(p-1)/2^{32}}$ = 1753635133440165772

Goldilocks 域能够更好适配64位整数运算。

Poseidon

Poseidon 是一种 zero-knowledge 友好的Hash函数，大概过程如下：

# modular exponentiation
def sbox(field_element):
    field_element^5

# apply MDS matrix
def apply_mds(state):
    n = [0, 0, 0]
    n[0] = state[0] * mds[0][0] + state[1] * mds[0][1] + state[2] * mds[0][2]
    n[1] = state[0] * mds[1][0] + state[1] * mds[1][1] + state[2] * mds[1][2]
    n[2] = state[0] * mds[2][0] + state[1] * mds[2][1] + state[2] * mds[2][2]
    return n
    
# a round
def full_round(round, state):
    # sbox
    state[0] = sbox(state[0])
    state[1] = sbox(state[1])
    state[2] = sbox(state[2])

    # apply MDS matrix
    state = apply_mds(state)

    # add round constant
    constant = round_constants[round]
    state[0] += constant[0]
    state[1] += constant[1]
    state[2] += constant[2]

# poseidon is just a number of rounds with different round constants
def poseidon(state, rounds):
    # ARK_INITIAL is not used usually, but if used there's 
    round_offset = 0
    if ARK_INITIAL:
        constant = round_constants[0]
        state[0] += constant[0]
        state[1] += constant[1]
        state[2] += constant[2]
        round_offset = 1
        
    for round in range(round_offset, rounds + round_offset):
        full_round(round, state)

参考：https://o1-labs.github.io/proof-systems/specs/poseidon.html#pseudo-code

FRI 证明

Fri 主要实现承诺多项式低度测试，参考：Vitalik blog 和 fri 介绍。

STARK 证明

本文以stark_all 为例，分析整个STARK 实现过程。

预处理

starkStruct

通过starkStruct 描述STARK 证明的一些参数信息：

  const starkStruct = {
            nBits: 10,    // 基域位数，
            nBitsExt: 11,  // 扩域域位数
            nQueries: 8,   //  查询的个数
            verificationHashType: "GL",    // Hash函数使用Goldilocks 域数
            steps: [
                { nBits: 11 },   // fri 第一轮域位数
                { nBits: 3 }     // fri 第二轮域位数
            ]
        };

上述主要定义基域为: $2^{10}$ , 扩域为： $2^{11}$ .

Goldilocks 三次扩域构建

定义三次扩域的相关参数：

module.exports = class F3G {

    constructor() {
        this.p = 0xFFFFFFFF00000001n  // 基础 p
        this.zero = 0n;       
        this.one = 1n;
        this.nqr = 7n;      // Fp* 生成元
        this.shift = 49n;   // shift 偏移
        this.shiftInv = this.inv(this.shift);  // shift 的逆
        this.half = 0xFFFFFFFF00000001n >> 1n;   // p/2
        this.negone = 0xFFFFFFFF00000000n;       // -1
        this.k = 12275445934081160404n;  // 7^(2^32) => Generetor of the group 3x5x17x257x65537
        this.s = 32;     
        this.t = (this.p-1n) / BigInt(2**this.s); // 表示3x5x17x257x65537
        this.n8 = 8;
        this.n32 = 2;
        this.n64 = 1;

        this.m = 3;   //代表三次扩域

        this.bitLength = 0;
        for (let a =this.p; a>0n; a = a >> 1n) this.bitLength += 1;  // 计算位数

        buildSqrt(this);    // 构建平方根函数

        buildFFT(this);   // 生成 FFT 变换的参数 
    }

其中 buildFFT 主要是构建各个子群的生成元，及其逆元素。

module.exports = function buildFFT(F) {
    const fft = new FFT(F, F, F.mul.bind(F));
    F.fft = fft.fft.bind(fft);   // fft 变换
    F.ifft = fft.ifft.bind(fft);   //ifft 变换
    F.w = fft.w;  // 长度为33的数组，每个元素对应着相应子群的生成元，例如w[32] 为2^32 子群的生成元， 以此类推：
    F.wi = fft.wi; // 长度为33的数组，每个元素对应着相应子群生成元的逆.
}

编译PIL

PIL 定义了STARK 实现的约束描述，采用PIL编译器可以将其转换为json 描述，以stark_all 为例，其PIL 定义为：

constant %N = 2**10;

namespace Global(%N);
    pol constant L1;   // 常量多项式

include "../sm_fibonacci/fibonacci.pil";
include "../sm_connection/connection.pil";
include "../sm_permutation/permutation.pil";
include "../sm_plookup/plookup.pil";



// fibonacci.pil
namespace Fibonacci(%N);

    pol constant L1, LLAST;   // 常量多项式
    pol commit l1,l2;        // 承诺多项式

    pol l2c = l2;   // l2c 为隐含多项式

    public in1 = l2c(0);   // 公开输入
    public in2 = l1(0);
    public out = l1(%N-1);

    (l2' - l1)*(1-LLAST) = 0;    // 多项式恒等约束

    pol next = l1*l1 + l2*l2;  // next 为隐含多项式

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

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

// connection.pil
namespace Connection(%N);
    pol constant S1, S2, S3;
    pol commit a,b,c;

    {a, b, c} connect {S1, S2, S3};   // 连接约束
    
    
// permutation.pil    
namespace Permutation(%N);

    pol commit a, b;
    pol commit c, d;
    pol commit selC, selD;

    selC {c, c} is selD {d, d};     // 置换约束
    

// plookup.pil
namespace Plookup(%N);

    pol commit sel, a, b;

    pol constant SEL, A, B;
    pol commit cc;

    sel {a, b', a*b'} in SEL { A, B, cc};  // 查找表约束

生成的对应的json 为：

{
 "nCommitments": 15,   // 多项式承诺的总数
 "nQ": 2,     // Q多项式 总数
 "nIm": 2,      // 隐含变量个数
 "nConstants": 9,     // 常量多项式个数
 "publics": [   // 表示 公开输入数组
  {
   "polType": "imP",   // 引用多项式类型
   "polId": 0,         // 多项式 id  编号
   "idx": 0,          // index 索引， 可以当用行号
   "id": 0,           // 公开输入的id 
   "name": "in1"     // 公开输入的标识符
  },
   
  ....
   
 ],
 "references": { // PIL 中的一些变量引用
  "Global.L1": {
   "type": "constP",   // 类型
   "id": 0,            //在类型所在的编号
   "polDeg": 1024,     // 多项式次数
   "isArray": false    // 是否为数组
  } ,
 
  ...
   
 },
 "expressions": [  // 定义了一些表达式
  {            // 对应着表达式 pol l2c = l2; 中的 l2 
   "op": "cm",
   "deg": 1,
   "id": 1,
   "next": false
  },
  {    // 对应着表达式：  (l2' - l1)*(1-LLAST) = 0;    
   "op": "sub",
   "deg": 2,
   "values": [
    {
     "op": "mul",
     "deg": 2,
     "values": [
      {
       "op": "sub",
       "deg": 1,
       "values": [
        {
         "op": "cm",
         "deg": 1,
         "id": 1,
         "next": true
        },
        {
         "op": "cm",
         "deg": 1,
         "id": 0,
         "next": false
        }
       ]
      },
      {
       "op": "sub",
       "deg": 1,
       "values": [
        {
         "op": "number",
         "deg": 0,
         "value": "1"
        },
        {
         "op": "const",
         "deg": 1,
         "id": 2,
         "next": false
        }
       ]
      }
     ]
    },
    {
     "op": "number",
     "deg": 0,
     "value": "0"
    }
   ]
  },
    
   ...
     
 ],
 "polIdentities": [  // 对应着恒等表达式
  {
   "e": 1,  // 表未表达式(expressions)的编号
   "fileName": "/Users/tron/test/polygon_zkevm/pil-stark/test/sm_fibonacci/fibonacci.pil",
   "line": 13
  },

  ... 
  
 ],
 "plookupIdentities": [   // 查询表约束恒等关系
  {
   "f": [
    19,     // 表示表达式id, 以下类同
    20,
    21
   ],
   "t": [
    23,
    24,
    25
   ],
   "selF": 22,
   "selT": 26,
   "fileName": "/Users/tron/test/polygon_zkevm/pil-stark/test/sm_plookup/plookup.pil",
   "line": 9
  }
 ],
 "permutationIdentities": [  // 置换多项式恒等关系
  {
   "f": [
    13,     // 表示exid
    14
   ],
   "t": [
    16,
    17
   ],
   "selF": 15,
   "selT": 18,
   "fileName": "/Users/tron/test/polygon_zkevm/pil-stark/test/sm_permutation/permutation.pil",
   "line": 9
  }
 ],
 "connectionIdentities": [   // 连接约束恒等关系
  {
   "pols": [
    7,      // 表示表达式(expressions)的编号
    8,
    9
   ],
   "connections": [
    10,
    11,
    12
   ],
   "fileName": "/Users/tron/test/polygon_zkevm/pil-stark/test/sm_connection/connection.pil",
   "line": 7
  }
 ]
}

常量多项式赋值

主要对常量列进行赋值，如

        const constPols = newConstantPolsArray(pil);

        await smGlobal.buildConstants(constPols.Global);
        await smPlookup.buildConstants(constPols.Plookup);
        await smFibonacci.buildConstants(constPols.Fibonacci);
        await smPermutation.buildConstants(constPols.Permutation);
        await smConnection.buildConstants(constPols.Connection);

以Fibonacci 为例，主要对其中的L1 和LLAST 例赋值，如下所示：

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

    const N = pols.L1.length;


    for ( let i=0; i<N; i++) {
        pols.L1[i] = (i == 0) ? 1n : 0n;
        pols.LLAST[i] = (i == N-1) ? 1n : 0n;
    }
}

对Global, Plookup, Permutation, Connection 部分的常量多项式处理类似。

承诺多项式赋值

主要对承诺多项式进行赋值，如下所示：

        const cmPols = newCommitPolsArray(pil);

        await smPlookup.execute(cmPols.Plookup);
        await smFibonacci.execute(cmPols.Fibonacci, [1, 2]);
        await smPermutation.execute(cmPols.Permutation);
        await smConnection.execute(cmPols.Connection);

以 Fibonacci 为例，主要对 l1 和 l2 分别赋值，其中公开输入为[1,2]。

module.exports.execute = async function (pols, input) {

    const N = pols.l1.length;

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

    pols.l2[0] = BigInt(input[0]);
    pols.l1[0] = BigInt(input[1]);

    for (let i=1; i<N; i++) {
        pols.l2[i] =pols.l1[i-1];
        pols.l1[i] =Fr.add(Fr.square(pols.l2[i-1]), Fr.square(pols.l1[i-1]));
    }

    return pols.l1[N-1];
}

对 Plookup, Permutation, Connection 部分的常量多项式处理类似。

STARK setup

constTree 构建

首先对常量多项式分别进行FFT 变换，得到其在扩展域上值；

然后构建基于Goldilocks 域的Merkle Hash;

最后对扩展域上的值构建Merkle 树，构建时候将多个列合并，生成一个Merkle树，每个节点有4个域元素。

    const constBuff = constPols.writeToBuff();
    await interpolate(constBuff, pil.nConstants, nBits, constPolsArrayE, nBitsExt);

    let MH;
    if (starkStruct.verificationHashType == "GL") {
        MH = await buildMerklehashGL();
    } else if (starkStruct.verificationHashType == "BN128") {
        MH = await buildMerklehashBN128();
    } else {
        throw new Error("Invalid Hash Type: " + starkStruct.verificationHashType);
    }

    const constTree = await MH.merkelize(constPolsArrayE, pil.nConstants, nExt);

constTree 的结构为：

   const tree = {
            elements: buff,  //保存所有叶子节点值，包含所有常量列在扩域上的值；
            nodes: new BigUint64Array(this._getNNodes(height * 4)), // 所有中间节点的值，每个节点占用4个域元素, 最后四个元素为Merkle 树根
            width: width,  // 常量多项式列的个数
            height: height  //最底层叶子点节个数
        };

下面的过程主要用于构建 starkInfo , 它包含了用于生成 stark 证明的所需要的各种信息。

    const res = {
        varPolMap: [],  //变量到多项式的映射
        puCtx: [],    // plookup    
        peCtx: [],    // permutation
        ciCtx: []     // connection 
    };

    res.starkStruct = starkStruct;    //   stark 结构体
    res.nConstants = pil.nConstants;   //  常量多项式个数
    res.nPublics = pil.publics.length;  // 公开输入个数

generatePublicCalculators

本步主要用于计算公开输入值。

module.exports = function generatePublicCalculators(res, pil) {
    res.publicsCode = [];
    for (let i=0; i<pil.publics.length; i++) {
        if (pil.publics[i].polType == "imP") {
            const ctx = {
                pil: pil,
                calculated: {
                    exps: {},
                    expsPrime: {}
                },
                tmpUsed: 0,
                code: []
            };
            pilCodeGen(ctx, pil.publics[i].polId, false);
            res.publicsCode[i] = buildCode(ctx);
            const ctxF = {};
            ctxF.expMap = [{}, {}];
            ctxF.code = res.publicsCode[i];
            iterateCode(res.publicsCode[i], function fixRef(r, ctx) {
                const p = r.prime ? 1 : 0;
                if (r.type === "exp") {
                    if (typeof ctx.expMap[p][r.id] === "undefined") {
                        ctx.expMap[p][r.id] = ctx.code.tmpUsed ++;
                    }
                    delete r.prime;
                    r.type= "tmp";
                    r.id= ctx.expMap[p][r.id];
                }
            }, ctxF);
            ctx.calculated =  { exps: {}, expsPrime: {} }  // Public inputs expressions are caculated at a single point, so they cannot be considered as calculated
        }
    }
}

首先对于imP 类型的公开输入，例如，如下所示：

  {
   "polType": "imP",
   "polId": 0,   // 其实表示 expression id
   "idx": 0,     // 对应着索引值，可以当用行号 
   "id": 0,      // 公开输入的id 
   "name": "in1"   // 公开输入的变量名
  },

然后对pilCodeGen 将需要计算的表达式展开成为基本的code (为二元运算或基本运算)，若表达式依赖其它表达式，通过递归方式完全展开。例如本例中生成的code 为：

    {
     "op": "copy",    // 表示复制运算
     "dest": {        // 复制的目标
      "type": "tmp",
      "id": 0,
      "dim": 1
     },
     "src": [         // 来源
      {
       "type": "cm",      // 承诺多项式
       "id": 1,           // 承诺多项式 id
       "prime": false,
       "p": 2,
       "dim": 1
      }
     ]
    }

再调用buildCode 将所有表达式的code 展开，放到一个组数中，放到starkInfo的 publicsCode 组数中。

对于每个公开输入，分别生成 first, i, last 三组code，对应不同的位置，但目前只用了frist； i 和 last 没有用。

最后生成的publicsCode 会生成证明的时候用于计算公开输入的值。

res.nCm1 = pil.nCommitments;   // 表示第一步中的承诺多项式个数

generateStep2

步骤2的主要代码如下：

module.exports = function generateStep2(res, pil, ctx) {

    const E = new ExpressionOps();

    for (let i = 0; i < pil.plookupIdentities.length; i++) {  
        const puCtx = {};
        const pi = pil.plookupIdentities[i];   // 取出plookup

        let tExp = null;  // 计算 t 表达式 
        const u = E.challenge("u");
        const defVal = E.challenge("defVal");
        for (let j = 0; j < pi.t.length; j++) {
            const e = E.exp(pi.t[j]);
            if (tExp) {
                tExp = E.add(E.mul(u, tExp), e);
            } else {
                tExp = e;
            }
        }
        if (pi.selT !== null) {
            tExp = E.sub(tExp, defVal);
            tExp = E.mul(tExp, E.exp(pi.selT));
            tExp = E.add(tExp, defVal);

            tExp.idQ = pil.nQ;
            pil.nQ++;       // 
        }

        puCtx.tExpId = pil.expressions.length; // t 表达式 id
        tExp.keep = true;
        pil.expressions.push(tExp);


        fExp = null; // 计算 f 表达式
        for (let j = 0; j < pi.f.length; j++) {
            const e = E.exp(pi.f[j]);
            if (fExp) {
                fExp = E.add(E.mul(fExp, u), e);
            } else {
                fExp = e;
            }
        }
        if (pi.selF !== null) {
            fExp = E.sub(fExp, E.exp(puCtx.tExpId));
            fExp = E.mul(fExp, E.exp(pi.selF));
            fExp = E.add(fExp, E.exp(puCtx.tExpId));

            fExp.idQ = pil.nQ;
            pil.nQ++;
        }

        puCtx.fExpId = pil.expressions.length;  //f 表达式id
        fExp.keep = true;
        pil.expressions.push(fExp);

        pilCodeGen(ctx, puCtx.fExpId, false);
        pilCodeGen(ctx, puCtx.tExpId, false);

        puCtx.h1Id = pil.nCommitments++; // h1承诺多项式id
        puCtx.h2Id = pil.nCommitments++;  // h2 承诺多项式id

        res.puCtx.push(puCtx);
    }

    res.step2prev = buildCode(ctx);
}

首先定义一个表达式类，表达式所包含的所有运算主要有：add, sub, mul, const, q, challenge, number, eval, tmp, xDivXSubXi, xDivXSubWXi , x .

然后对PIL 中的每个 plookup 运算，循环进行处理，例如，如下所示：

"plookupIdentities": [
  {
   "f": [
    19,
    20,
    21
   ],
   "t": [
    23,
    24,
    25
   ],
   "selF": 22,
   "selT": 26,
   "fileName": "/Users/tron/test/polygon_zkevm/pil-stark/test/sm_plookup/plookup.pil",
   "line": 9
  }
 ]

然后计算 t 表达式
$t_{exp} = u^{n-1}e_0 + u^{n-2} e_1 + \cdots u e_{n-2} + e_{n-1}$
若存在选择子setT，则：
$t_{exp} = e_{selT} * (t_{exp} - defVal) + defVal$
puCtx.tExpId 为 t 表达式id，放入表达式列表中。

再计算f 表达式，和上面类似：
$f_{exp} = u^{n-1}f_0 + u^{n-2} f_1 + \cdots u f_{n-2} + f_{n-1}$
若存在选择子setF，则：
$f_{exp} = e_{selF} * (f_{exp} - t_{exp}) + t_{exp}$
puCtx.fExpId 为 f 表达式id，放入表达式列表中。

然后分别对f 和 t 表达式调用pilCodeGen，生成表达式计算的Code；

最后生成h1 和 h2 承诺多项式 id。

生成的 puCtx 的结构为：

 {
   "tExpId": 27,   // t 表达式 id
   "fExpId": 28,   // f 表达式 id
   "h1Id": 15,   // h1 承诺多项式id
   "h2Id": 16,   // h2 承诺多项式id
   "zId": 17,    // 下面几个后续待计算
   "c1Id": 31,
   "numId": 32,
   "denId": 33,
   "c2Id": 34
  }

当所有的plookup 处理完后，通过buildCode 将生成的所有code 放入 step2prev 中。

res.nCm2 为第2步承诺多项式的个数，赋值为：

res.nCm2 = pil.nCommitments - res.nCm1;

generateStep3

步骤3又分为三步，分别为：

generatePermutationLC

该步骤与步骤2类似，生成置换对应的t 表达式和 f表达式，例如置换：

 "permutationIdentities": [
  {
   "f": [  // f 表达式
    13,
    14
   ],
   "t": [   // t 表达式
    16,
    17
   ],
   "selF": 15, // f selector
   "selT": 18,   // t selector
   "fileName": "/Users/tron/test/polygon_zkevm/pil-stark/test/sm_permutation/permutation.pil",
   "line": 9
  }
 ]

生成的对应的peCtx 为：

 "peCtx": [
  {
   "tExpId": 29,  // t 表达式 id
   "fExpId": 30,  // f 表达式 id
   "zId": 18,    // 后面几个后续待计算
   "c1Id": 35,
   "numId": 36,
   "denId": 37,
   "c2Id": 38
  }
 ]

generatePlookupZ

本步骤主要生成plookup 的Z 多项式，对于每个 plookup 分别执行以下步骤：

        const puCtx = res.puCtx[i];  // 取出单个plookup
        puCtx.zId = pil.nCommitments++;   // z 承诺多项式id


        const h1 = E.cm(puCtx.h1Id);    // h1 承诺 
        const h2 =  E.cm(puCtx.h2Id);    // h2 承诺  
        const h1p = E.cm(puCtx.h1Id, true);   // h1'
        const f = E.exp(puCtx.fExpId);       // f 多项式 
        const t = E.exp(puCtx.tExpId);       // t 多项式
        const tp = E.exp(puCtx.tExpId, true); // t' 
        const z = E.cm(puCtx.zId);             // z 承诺
        const zp = E.cm(puCtx.zId, true);      // z'

计算c1 表达式：

        const c1 = E.mul(l1,  E.sub(z, E.number(1)));
        c1.deg=2;
        puCtx.c1Id = pil.expressions.length;
        pil.expressions.push(c1);
        pil.polIdentities.push({e: puCtx.c1Id}); // 加入恒等多项式中

$c1 = L_1 * (z-1)$

计算分子 numExp 表达式：

        const numExp = E.mul(
            E.mul(
                E.add(f, gamma),
                E.add(
                    E.add(
                        t,
                        E.mul(
                            tp,
                            beta
                        )
                    ),
                    E.mul(gamma,E.add(E.number(1), beta))
                )
            ),
            E.add(E.number(1), beta)
        );
        numExp.idQ = pil.nQ++;
        puCtx.numId = pil.expressions.length;
        numExp.keep = true;
        pil.expressions.push(numExp);

$numExp = ((f+\gamma)((t + t'\beta)+(\gamma (1+\beta))))(1+\beta) \\ = (1+\beta)(f+\gamma)(\gamma(1+\beta)+ t +\beta t')$

计算分母denExp表达式：

        const denExp = E.mul(
            E.add(
                E.add(
                    h1,
                    E.mul(
                        h2,
                        beta
                    )
                ),
                E.mul(gamma,E.add(E.number(1), beta))
            ),
            E.add(
                E.add(
                    h2,
                    E.mul(
                        h1p,
                        beta
                    )
                ),
                E.mul(gamma,E.add(E.number(1), beta))
            )
        );
        denExp.idQ = pil.nQ++;
        puCtx.denId = pil.expressions.length;
        denExp.keep = true;
        pil.expressions.push(denExp);

$denExp = (\gamma(1+\beta) + h_1 +\beta h_2)(\gamma(1+\beta)+h_2+\beta h_1')$

然后构建 c2 约束表达式：

        const num = E.exp(puCtx.numId);
        const den = E.exp(puCtx.denId);

        const c2 = E.sub(  E.mul(zp, den), E.mul(z, num)  );
        c2.deg=2;
        puCtx.c2Id = pil.expressions.length;
        pil.expressions.push(c2);
        pil.polIdentities.push({e: puCtx.c2Id});  // 加入恒等多项式中

$c_2 = z'\cdot den - z \cdot num$

最后分别构建 num 和 den 表达式的code.

        pilCodeGen(ctx, puCtx.numId, false);
        pilCodeGen(ctx, puCtx.denId, false);

generatePermutationZ

此步骤主要生成置换的 Z 多项式。

首先取出每个置换个运算：

        peCtx = res.peCtx[i];  // 取出置换

        peCtx.zId = pil.nCommitments++;   // z 承诺多项式 id

        const f = E.exp(peCtx.fExpId);    // f 表达式
        const t = E.exp(peCtx.tExpId);    // t 表达式
        const z = E.cm(peCtx.zId);       // z 表达式
        const zp = E.cm(peCtx.zId, true); //z' 表达式

然后计算c1 表达式：


        const l1 = E.const(pil.references["Global.L1"].id);

        const c1 = E.mul(l1,  E.sub(z, E.number(1)));
        c1.deg=2;
        peCtx.c1Id = pil.expressions.length;
        pil.expressions.push(c1);
        pil.polIdentities.push({e: peCtx.c1Id});

$c1 = L_1 * (z-1)$

计算分子numExp 表达式：

        const beta = E.challenge("beta");

        const numExp = E.add( f, beta);
        peCtx.numId = pil.expressions.length;
        numExp.keep = true;
        pil.expressions.push(numExp);

$numExp = f + \beta$

计算分母denExp 表达式：

        const denExp = E.add( t, beta);
        peCtx.denId = pil.expressions.length;
        denExp.keep = true;
        pil.expressions.push(denExp);

$denExp = t + \beta$

计算c2 表达式：

        const c2 = E.sub(  E.mul(zp,  E.exp( peCtx.denId )), E.mul(z, E.exp( peCtx.numId )));
        c2.deg=2;
        peCtx.c2Id = pil.expressions.length;
        pil.expressions.push(c2);
        pil.polIdentities.push({e: peCtx.c2Id});

$c2 = z' \cdot den - z \cdot num$

最后通过pilCodeGen 分别构建 num 和 den 的Code.

        pilCodeGen(ctx, peCtx.numId, false);
        pilCodeGen(ctx, peCtx.denId, false);

generateConnectionsZ

此次主要对了每个connection 运算进行处理：

首先取取出PIL 中每个connection, 如下所示：

        const ci = pil.connectionIdentities[i];
        const ciCtx = {};

每个ci 的结构为：

 "connectionIdentities": [
  {
   "pols": [   
    7,  // 表达式 id
    8,
    9
   ],
   "connections": [
    10,
    11,
    12
   ],
   "fileName": "/Users/tron/test/polygon_zkevm/pil-stark/test/sm_connection/connection.pil",
   "line": 7
  }
 ]

然后构建numExp 和 denExp，

        ciCtx.zId = pil.nCommitments++;    // z 承诺多项式 id

        const beta = E.challenge("beta");
        const gamma = E.challenge("gamma");

        let numExp = E.add(
            E.add(
                E.exp(ci.pols[0]),
                E.mul(beta, E.x())
            ), gamma);

        let denExp = E.add(
            E.add(
                E.exp(ci.pols[0]),
                E.mul(beta, E.exp(ci.connections[0]))
            ), gamma);

        ciCtx.numId = pil.expressions.length;
        numExp.keep = true;
        pil.expressions.push(numExp);

        ciCtx.denId = pil.expressions.length;
        denExp.keep = true;
        pil.expressions.push(denExp);

        let ks = getKs(F, ci.pols.length-1);
        for (let i=1; i<ci.pols.length; i++) {
            const numExp =
                E.mul(
                    E.exp(ciCtx.numId),
                    E.add(
                        E.add(
                            E.exp(ci.pols[i]),
                            E.mul(E.mul(beta, E.number(ks[i-1])), E.x())
                        ),
                        gamma
                    )
                );
            numExp.idQ = pil.nQ++;

            const denExp =
                E.mul(
                    E.exp(ciCtx.denId),
                    E.add(
                        E.add(
                            E.exp(ci.pols[i]),
                            E.mul(beta, E.exp(ci.connections[i]))
                        ),
                        gamma
                    )
                );
            denExp.idQ = pil.nQ++;

            ciCtx.numId = pil.expressions.length;
            pil.expressions.push(numExp);

            ciCtx.denId = pil.expressions.length;
            pil.expressions.push(denExp);
        }

分别对应着以下公式：

[图片上传失败...(image-3b3b75-1695281936283)]

构建 c1 表达式：

        const z = E.cm(ciCtx.zId);
        const zp = E.cm(ciCtx.zId, true);

        if ( typeof pil.references["Global.L1"] === "undefined") throw new Error("Global.L1 must be defined");

        const l1 = E.const(pil.references["Global.L1"].id);

        const c1 = E.mul(l1,  E.sub(z, E.number(1)));
        c1.deg=2;
        ciCtx.c1Id = pil.expressions.length;
        pil.expressions.push(c1);
        pil.polIdentities.push({e: ciCtx.c1Id});

$c1 = L1 *(z-1)$

构建c2 表达式：

        const c2 = E.sub(  E.mul(zp,  E.exp( ciCtx.denId )), E.mul(z, E.exp( ciCtx.numId )));
        c2.deg=2;
        ciCtx.c2Id = pil.expressions.length;
        pil.expressions.push(c2);
        pil.polIdentities.push({e: ciCtx.c2Id});

$c2 = z' \cdot den - z \cdot num$

最后调用pilCodeGen 分别生成表达式num 和 den 的code.

        pilCodeGen(ctx, ciCtx.numId, false);
        pilCodeGen(ctx, ciCtx.denId, false);

        res.ciCtx.push(ciCtx);

生成的ciCtx 结构为：

 "ciCtx": [
  {
   "zId": 19,     // z 承诺多项式 id
   "numId": 43,   // num 表达式 id
   "denId": 44,   // den 表达式 id
   "c1Id": 45,    // c1 表达式 id
   "c2Id": 46     // c2 表达式 id
  }
 ]

buildCode

以上四步处理完成后，最终调用buildCode 将code 存入 res.step2prev 中。

    res.step3prev = buildCode(ctx);

res.nCm2 表示第3步中承诺多项式的个数。

generateConstraintPolynomial

本步主要将前面生成的约束表达式组合在在一起，生成cExp ，如下所示：

module.exports = function generateConstraintPolynomial(res, pil, ctx, ctx2ns) {

    const E = new ExpressionOps();

    const vc = E.challenge("vc");
    let cExp = null;
    for (let i=0; i<pil.polIdentities.length; i++) {
        const e = E.exp(pil.polIdentities[i].e);
        if (cExp) {
            cExp = E.add(E.mul(vc, cExp), e);
        } else {
            cExp = e;
        }
    }
    cExp.idQ = pil.nQ++;
    res.cExp = pil.expressions.length;
    pil.expressions.push(cExp);

    for (let i=0; i<pil.expressions.length; i++) {
        if (typeof pil.expressions[i].idQ != "undefined") {
            pilCodeGen(ctx, i);   
            pilCodeGen(ctx2ns, i, false, "evalQ");
        }
    }

    res.step4 = buildCode(ctx);
    res.step42ns = buildCode(ctx2ns);
}

$c_{exp} = vc^{n-1}e_0 + vc^{n-2} e_1 + \cdots vc\cdot e_{n-2} + e_{n-1}$

然后对于idQ 类型的表达式，生成对应的code. 对于evalQ 类型，需要额外添加2个code, 如下所示:

        const rqz = {
            type: "tmp",
            id: codeCtx.tmpUsed++
        };
        codeCtx.code.push({
            op: "sub",
            src: [retRef, {
                type: "exp",
                prime: prime,
                id: expId
            }],
            dest: rqz
        });
        codeCtx.code.push({
            op: "mul",
            src: [{
                type: "Zi",
            }, rqz],
            dest: {
                type: "q",
                id: ctx.pil.expressions[expId].idQ,
                prime: prime
            }
        })

最后将构建的code 分别存于step4 和 step42ns 中。

nCm4 表示第4步中承诺多项式的个数，nQ 表示 q 多项式个数。

    res.nCm4 = pil.nCommitments - res.nCm3 - res.nCm2 - res.nCm1;
    res.nQ = pil.nQ;

generateConstraintPolynomialVerifier

主要对约束组合表达式生成验证的code, 代码如下：

    const ctxC = {
        pil: pil,
        calculated: {
            exps: {},
            expsPrime: {}
        },
        tmpUsed: 0,
        code: []
    };

    pilCodeGen(ctxC, res.cExp, false, "correctQ");

    res.verifierCode = buildCode(ctxC);

将生成的code 保存到verifierCode 中。

对于correctQ ，需要额外添加两个code, 如下所示：

       const rqz = {
            type: "tmp",
            id: codeCtx.tmpUsed++
        };
        codeCtx.code.push({
            op: "mul",
            dest: rqz,
            src: [
                {
                    type: "q",
                    id: ctx.pil.expressions[expId].idQ,
                    prime: prime
                },
                {
                    type: "Z",
                    prime: prime
                }
            ]
        });
        codeCtx.code.push({
            op: "sub",
            dest: {
                type: "exp",
                prime: prime,
                id: expId
            },
            src: [retRef, rqz]
        });

此时会将code 中 cm, q, const 类型更改为eval 类型，并构建 evIdex 到 evMap 的映射：

    res.evIdx[r.type][p][r.id] = res.evMap.length;

evMap 对应着 eval 类型的 id.

同时将exp 类型更改变tmp 类型。

generateFRIPolynomial

本步骤主要生成 FRI 表达式：

    let friExp = null;
    for (let i=0; i<pil.nCommitments; i++) {
        if (friExp) {
            friExp = E.add(E.mul(vf1, friExp), E.cm(i));
        } else {
            friExp = E.cm(i);
        }
    }
    for (let i=0; i<pil.nQ; i++) {
        if (friExp) {
            friExp = E.add(E.mul(vf1, friExp), E.q(i));
        } else {
            friExp = E.q(i);
        }
    }

$$
friExp = vf_1^{n_{cm} + n_q-1}e_{cm_0} + vf_1^{n_{cm} + n_q-2} e_{cm_1} + \cdots vf_1^{n_q} e_{cm_{n-2}} + vf_1^{n_q} e_{cm_{n-1}} \

vf_1^{n_q-1}e_{q_0} + vf_1^{n_q-2} e_{q_1} + \cdots vf_1 e_{q_{n-2}} + e_{q_{n-1}}
$$

其中 $n_{cm}$ 和 $n_q$ 分别表示承诺多项式和 q 多项式的个数。

然后分别计算 fri1Exp 和 fri2Exp 分别表示evMap 的为非Prime和Prime的情形：

    let fri1exp = null;
    let fri2exp = null;
    const xi = E.challenge("xi");
    for (let i=0; i<res.evMap.length; i++) {
        const ev = res.evMap[i];
        let friExp = ev.prime ? fri2exp : fri1exp;
        const e = E[ev.type](ev.id);
        if (friExp) {
            friExp = E.add(E.mul(friExp, vf2), E.sub(e,  E.eval(i)));
        } else {
            friExp = E.sub(e,  E.eval(i));
        }
        if (ev.prime) {
            fri2exp = friExp;
        } else {
            fri1exp = friExp;
        }
    }

$fri_i = vf_2^{n_i-1}(e_0-e_{val_0}) + vf_2^{n_i-2}(e_1-e_{val_1})+ \cdots + (e_{n_i-1}-e_{val_{n_i-1}})$

其中 $i = 1,2$ .

最后得到的friExp 为

    fri1exp = E.mul(fri1exp, E.xDivXSubXi() );
    if (friExp) {
        friExp = E.add(E.mul(vf1, friExp),  fri1exp );
    } else {
        friExp = fri1exp;
    }

    fri2exp =  E.mul(fri2exp, E.xDivXSubWXi() );
    if (friExp) {
        friExp = E.add(E.mul(vf1, friExp),  fri2exp );
    } else {
        friExp = fri2exp;
    }

$friExp = vf_1\cdot friExp + fri_1\cdot e_{xDivXSubXi} \\ friExp = vf_1 \cdot friExp + fri_2\cdot e_{xDivXSubWXi}$

生成 friExpId, 并构建code. 放于step52ns中。

    res.friExpId = pil.expressions.length;
    friExp.keep2ns = true;
    pil.expressions.push(friExp);

    pilCodeGen(ctx2ns, res.friExpId);
    res.step52ns = buildCode(ctx2ns);

注：最终得到的 $friExp$ 的次数为 $2^{nBits}-1$ .

generateVerifierQuery

主要对 fri 表达式生成用于查询验证的code，保存在verifierQueryCode中。

    const ctxFri = {
        pil: pil,
        calculated: {
            exps: {},
            expsPrime: {}
        },
        tmpUsed: 0,
        code: []
    };

    pilCodeGen(ctxFri, res.friExpId);
    res.verifierQueryCode = buildCode(ctxFri);
    res.nExps = pil.expressions.length;

需要把code 中的exp 类型更改为 tmp 类型。

map

主要构建各个section 的位置映射关系，包含的section 有：

res.mapSections = {
        cm1_n: [],
        cm1_2ns: [],
        cm2_n:[],
        cm2_2ns:[],
        cm3_n:[],
        cm3_2ns:[],
        q_2ns:[],
        exps_withq_n:[],
        exps_withq_2ns:[],
        exps_withoutq_n:[],
        exps_withoutq_2ns:[]
    }

对nCm1 进行处理：

    pil.cmDims = [];
    for (let i=0; i<res.nCm1; i++) {
        const pp_n = addPol({  // 添加到valPolMap中
            section: "cm1_n",
            dim:1
        });
        const pp_2ns = addPol({
            section: "cm1_2ns",
            dim:1
        });
        res.cm_n.push(pp_n);      // cm_n -> valPolMap
        res.cm_2ns.push(pp_2ns);            //cm_2ns -> valPolMap上
        res.mapSections.cm1_n.push(pp_n);     // cm1_n -> valPolMap 上
        res.mapSections.cm1_2ns.push(pp_2ns);   // cm1_2ns -> valPolMap 上
        pil.cmDims[i] = 1;
    }

其它各部分类似，得到cm1_n, cm1_2ns, cm2_n, cm2_2ns, cm3_n, cm3_2ns, q_2ns, exps_withq_n, exps_withq_2ns, exps_withoutq_n, exps_withoutq_2ns，都是映射到valPolMap 中。

mapSectionN1: 各section宽度 1 的个数；

mapSectionN3: 各section 宽度为3的个数；

mapSectionN: 各section总宽度。

mapOffsets: 各section 在内存中偏移

mapTotalN: 总共域（Goldilocks）元素个数；

mapDeg: 各 section 的个数。

然后调用fixProverCode ，主要在Code中添加 p, 表示在 section中的索引。

然后更新verifierQueryCode, 如下：

    iterateCode(res.verifierQueryCode, function fixRef(r, ctx) {
        if (r.type == "cm") {
            const p1 = res.varPolMap[res.cm_2ns[r.id]];
            switch (p1.section) {
                case "cm1_2ns": r.type = "tree1"; break;
                case "cm2_2ns": r.type = "tree2"; break;
                case "cm3_2ns": r.type = "tree3"; break;
                default: throw new Error("Invalid cm section");
            }
            r.treePos = p1.sectionPos;
            r.dim = p1.dim;
        } else if (r.type == "q") {
            const p2 = res.varPolMap[res.qs[r.id]];
            r.type = "tree4";
            r.treePos = p2.sectionPos;
            r.dim = p2.dim;
        }
    });

然后调用setCodeDimensions，设置各种类型的dim值，如下所示：

    function _getExpDim(exp) {
        switch (exp.op) {
            case "add":
            case "sub":
            case "mul":
            case "addc":
            case "mulc":
            case "neg":
                let md = 1;
                for (let i = 0; i < exp.values.length; i++) {
                    const d = _getExpDim(exp.values[i]);
                    if (d > md) md = d;
                }
                return md;
            case "cm": return pil.cmDims[exp.id];
            case "const": return 1;
            case "exp": return _getExpDim(pil.expressions[exp.id]);
            case "q": return _getExpDim(pil.expressions[pil.q2exp[exp.id]]);
            case "number": return 1;
            case "public": return 1;
            case "challenge": return 3;
            case "eval": return 3;
            case "xDivXSubXi": return 3;
            case "xDivXSubWXi": return 3;
            case "x": return 1;
            default: throw new Error("Exp op not defined: " + exp.op);
        }

STARK gen

预处理

首先对各个section 分配内存空间，每个BigBuffer是一个uit64 类型数据。

    ctx.cm1_n = new BigBuffer(starkInfo.mapSectionsN.cm1_n * ctx.N);
    cmPols.writeToBigBuffer(ctx.cm1_n, 0);
    ctx.cm2_n = new BigBuffer(starkInfo.mapSectionsN.cm2_n * ctx.N);
    ctx.cm3_n = new BigBuffer(starkInfo.mapSectionsN.cm3_n * ctx.N);
    ctx.exps_withq_n = new BigBuffer(starkInfo.mapSectionsN.exps_withq_n * ctx.N);
    ctx.exps_withoutq_n = new BigBuffer(starkInfo.mapSectionsN.exps_withoutq_n * ctx.N);
    ctx.cm1_2ns = new BigBuffer(starkInfo.mapSectionsN.cm1_n * ctx.Next);
    ctx.cm2_2ns = new BigBuffer(starkInfo.mapSectionsN.cm2_n * ctx.Next);
    ctx.cm3_2ns = new BigBuffer(starkInfo.mapSectionsN.cm3_n * ctx.Next);
    ctx.q_2ns = new BigBuffer(starkInfo.mapSectionsN.q_2ns * ctx.Next);
    ctx.exps_withq_2ns = new BigBuffer(starkInfo.mapSectionsN.exps_withq_2ns * ctx.Next);
    ctx.exps_withoutq_2ns = new BigBuffer(starkInfo.mapSectionsN.exps_withoutq_2ns * ctx.Next);

计算 $x_n$ 和 $x_{2ns}$ ，

    ctx.x_n = new BigBuffer(N);
    let xx = F.one;
    for (let i = 0; i < N; i++) {
        ctx.x_n.setElement(i, xx);
        xx = F.mul(xx, F.w[nBits])
    }

    ctx.x_2ns = new BigBuffer(N << extendBits);
    xx = F.shift;
    for (let i = 0; i < (N << extendBits); i++) {
        ctx.x_2ns.setElement(i, xx);
        xx = F.mul(xx, F.w[nBits + extendBits]);
    }

其中
$x_n = (1, w, \cdots, w^{N-1}) \\ x_{2ns} = (shfit, shift\cdot w_e,\cdots,shift\cdot w_e^{N_e-1})$
然后生成Zi:
$Z(i) = \frac{1}{shift^{2^N}w_{extend}^i-1}$
其中 $shift$ 为偏移， $2^N$ 为基域总数， $w$ 为基域生成元， $w_e$ 为扩域生成元, $w_{extend}$ 为基域和扩域扩展位之间的子群的生成元。

$Z(i)$ 可以通过以下推导得到：
$Z(x) = \frac{1}{x^{2^N}-1} \\ Z(i) = \frac{1}{(shift\cdot w_e^i)^{2^N}-1} \\ = \frac{1}{shift^{2^N}\cdot (w_e^{2^N})^i-1} \\ = \frac{1}{shift^{2^N}\cdot w_{extend}^i-1} \\$

将常量多项式在基域和扩域上进行赋值。

   ctx.const_n = new BigBuffer(starkInfo.nConstants * ctx.N);
   constPols.writeToBigBuffer(ctx.const_n, 0);

   ctx.const_2ns = constTree.elements;

publics

本步骤主要计算公开输入的值，

    ctx.publics = [];
    for (let i = 0; i < starkInfo.publics.length; i++) {
        if (starkInfo.publics[i].polType == "cmP") {
            ctx.publics[i] = ctx.cm1_n.getElement(starkInfo.publics[i].idx * starkInfo.mapSectionsN.cm1_n + starkInfo.publics[i].polId);
        } else if (starkInfo.publics[i].polType == "imP") {
            // EDU: Do not implement this in the firs version.
            //      we will not use it.
            ctx.publics[i] = calculateExpAtPoint(ctx, starkInfo.publicsCode[i], starkInfo.publics[i].idx);
            //            ctx.publics[i] = ctx.exps[starkInfo.publics[i].polId][starkInfo.publics[i].idx];
        } else {
            throw new Error(`Invalid public type: ${polType.type}`);
        }
    }

    console.log("Merkelizing 1....");
    const tree1 = await extendAndMerkelize(MH, ctx.cm1_n, ctx.cm1_2ns, starkInfo.mapSectionsN.cm1_n, ctx.nBits, ctx.nBitsExt);
    transcript.put(MH.root(tree1));

对于cmP 类型的公开输入，直接从cm1_n 中读取；

对于imP类型的公开输入，需要将表达通过compileCode生成函数，计算公开输入。例如本例中得到公开输入函数为：

(function anonymous(ctx,i
) {
  ctx.tmp[0] = ctx.cm1_n[1 + i*15];
  return ctx.tmp[0];
})

然后将cm_1 通过FFT扩展到cm1_2ns，然后生成Merkle 树 tree1。

Caluculate plookups

第二步对应的输入和输出分别为：

if (execPart == "step2prev") {
        execInfo.inputSections.push({ name: "cm1_n" });   // 输入
        execInfo.inputSections.push({ name: "const_n" });   // 输入  
        execInfo.outputSections.push({ name: "exps_withq_n" });   // 输出
        execInfo.outputSections.push({ name: "exps_withoutq_n" });  
        execInfo.outputSections.push({ name: "cm2_n" });    
        dom = "n";
    }

通过调用compileCode 将第2步的 code 编译成为计算函数，例如，本例中编译的结果为：

ƒ anonymous(ctx,i
) {
  ctx.tmp[12] = ctx.cm1_n[12 + i*15];
  ctx.tmp[13] = ctx.cm1_n[13 + ((i + 1)%1024)*15];
  ctx.exps_withq_n[1 + i*35] = ctx.F.mul(ctx.cm1_n[12 + i*15], ctx.cm1_n[13 + ((i + 1)%1024)*15]);
  ctx.tmp[14] = ctx.const_n[7 + i*9];
  ctx.tmp[15] = ctx.const_n[8 + i*9];
  ctx.tmp[16] = ctx.cm1_n[14 + i*15];
  ctx.tmp[17] = ctx.const_n[6 + i*9];
  ctx.tmp[0] = ctx.F.mul(ctx.challenges[0], ctx.tmp[14]);
  ctx.tmp[1] = ctx.F.add(ctx.tmp[0], ctx.tmp[15]);
  ctx.tmp[2] = ctx.F.mul(ctx.challenges[0], ctx.tmp[1]);
  ctx.tmp[3] = ctx.F.add(ctx.tmp[2], ctx.tmp[16]);
  ctx.tmp[4] = ctx.F.sub(ctx.tmp[3], ctx.challenges[1]);
  ctx.tmp[5] = ctx.F.mul(ctx.tmp[4], ctx.tmp[17]);
  [ ctx.exps_withq_n[2 + i*35] , ctx.exps_withq_n[2 + i*35 + 1] , ctx.exps_withq_n[2 + i*35 + 2] ] = ctx.F.add(ctx.tmp[5], ctx.challenges[1]);   // 对应着 t 表达式
  ctx.tmp[18] = ctx.cm1_n[11 + i*15];
  ctx.tmp[6] = ctx.F.mul(ctx.tmp[12], ctx.challenges[0]);
  ctx.tmp[7] = ctx.F.add(ctx.tmp[6], ctx.tmp[13]);
  ctx.tmp[8] = ctx.F.mul(ctx.tmp[7], ctx.challenges[0]);
  ctx.tmp[9] = ctx.F.add(ctx.tmp[8], ctx.exps_withq_n[1 + i*35]);
  ctx.tmp[10] = ctx.F.sub(ctx.tmp[9], [ ctx.exps_withq_n[2 + i*35] , ctx.exps_withq_n[2 + i*35 + 1] , ctx.exps_withq_n[2 + i*35 + 2] ]);
  ctx.tmp[11] = ctx.F.mul(ctx.tmp[10], ctx.tmp[18]);
  [ ctx.exps_withq_n[5 + i*35] , ctx.exps_withq_n[5 + i*35 + 1] , ctx.exps_withq_n[5 + i*35 + 2] ] = ctx.F.add(ctx.tmp[11], [ ctx.exps_withq_n[2 + i*35] , ctx.exps_withq_n[2 + i*35 + 1] , ctx.exps_withq_n[2 + i*35 + 2] ]);   // 对应着 f  表达式
}

然后计算 f 和 t 表达式，再计算 h1 和 h2 , 将结果保存在 ctx.cm2_n 内存中。

    for (let i = 0; i < starkInfo.puCtx.length; i++) {
        const puCtx = starkInfo.puCtx[i];
        const fPol = getPol(ctx, starkInfo, starkInfo.exps_n[puCtx.fExpId]);
        const tPol = getPol(ctx, starkInfo, starkInfo.exps_n[puCtx.tExpId]);
        const [h1, h2] = calculateH1H2(F, fPol, tPol);
        setPol(ctx, starkInfo, starkInfo.cm_n[nCm++], h1);
        setPol(ctx, starkInfo, starkInfo.cm_n[nCm++], h2);
    }

然后将计算ctx.cm2_n 扩展到cm2_2ns 扩展域上，生成Merkle 树 tree2。

    console.log("Merkelizing 2....");
    const tree2 = await extendAndMerkelize(MH, ctx.cm2_n, ctx.cm2_2ns, starkInfo.mapSectionsN.cm2_n, ctx.nBits, ctx.nBitsExt);
    transcript.put(MH.root(tree2));

Compute Z polynomials

第三步的输入输出分别为：

if (execPart == "step3prev") {
        execInfo.inputSections.push({ name: "exps_withq_n" });
        execInfo.inputSections.push({ name: "exps_withoutq_n" });
        execInfo.inputSections.push({ name: "cm1_n" });
        execInfo.inputSections.push({ name: "cm2_n" });
        execInfo.inputSections.push({ name: "const_n" });
        execInfo.inputSections.push({ name: "x_n" });
        execInfo.outputSections.push({ name: "exps_withq_n" });
        execInfo.outputSections.push({ name: "exps_withoutq_n" });
        execInfo.outputSections.push({ name: "cm3_n" });
        dom = "n";
    }

通过调用compileCode 将第3步的 code 编译成为计算函数，例如，本例中编译的结果为：

(function anonymous(ctx,i
) {
  ctx.tmp[62] = ctx.cm1_n[7 + i*15];
  ctx.tmp[63] = ctx.cm1_n[7 + i*15];
  ctx.tmp[64] = ctx.cm1_n[9 + i*15];
  ctx.tmp[12] = ctx.F.mul(ctx.tmp[62], ctx.challenges[0]);
  ctx.tmp[13] = ctx.F.add(ctx.tmp[12], ctx.tmp[63]);
  ctx.tmp[14] = ctx.F.sub(ctx.tmp[13], ctx.challenges[1]);
  ctx.tmp[15] = ctx.F.mul(ctx.tmp[14], ctx.tmp[64]);
  [ ctx.exps_withq_n[11 + i*35] , ctx.exps_withq_n[11 + i*35 + 1] , ctx.exps_withq_n[11 + i*35 + 2] ] = ctx.F.add(ctx.tmp[15], ctx.challenges[1]);
  ctx.tmp[65] = ctx.cm1_n[8 + i*15];
  ctx.tmp[66] = ctx.cm1_n[8 + i*15];
  ctx.tmp[67] = ctx.cm1_n[10 + i*15];
  ctx.tmp[16] = ctx.F.mul(ctx.challenges[0], ctx.tmp[65]);
  ctx.tmp[17] = ctx.F.add(ctx.tmp[16], ctx.tmp[66]);
  ctx.tmp[18] = ctx.F.sub(ctx.tmp[17], ctx.challenges[1]);
  ctx.tmp[19] = ctx.F.mul(ctx.tmp[18], ctx.tmp[67]);
  [ ctx.exps_withq_n[8 + i*35] , ctx.exps_withq_n[8 + i*35 + 1] , ctx.exps_withq_n[8 + i*35 + 2] ] = ctx.F.add(ctx.tmp[19], ctx.challenges[1]);
  ctx.tmp[68] = ctx.const_n[7 + ((i+1)%1024)*9 ];
  ctx.tmp[69] = ctx.const_n[8 + ((i+1)%1024)*9 ];
  ctx.tmp[70] = ctx.cm1_n[14 + ((i + 1)%1024)*15];
  ctx.tmp[71] = ctx.const_n[6 + ((i+1)%1024)*9 ];
  ctx.tmp[20] = ctx.F.mul(ctx.challenges[0], ctx.tmp[68]);
  ctx.tmp[21] = ctx.F.add(ctx.tmp[20], ctx.tmp[69]);
  ctx.tmp[22] = ctx.F.mul(ctx.challenges[0], ctx.tmp[21]);
  ctx.tmp[23] = ctx.F.add(ctx.tmp[22], ctx.tmp[70]);
  ctx.tmp[24] = ctx.F.sub(ctx.tmp[23], ctx.challenges[1]);
  ctx.tmp[25] = ctx.F.mul(ctx.tmp[24], ctx.tmp[71]);
  [ ctx.exps_withq_n[2 + ((i + 1)%1024)*35] , ctx.exps_withq_n[2 + ((i + 1)%1024)*35 + 1], ctx.exps_withq_n[2 + ((i + 1)%1024)*35 + 2] ] = ctx.F.add(ctx.tmp[25], ctx.challenges[1]);
  ctx.tmp[26] = ctx.F.add([ ctx.exps_withq_n[5 + i*35] , ctx.exps_withq_n[5 + i*35 + 1] , ctx.exps_withq_n[5 + i*35 + 2] ], ctx.challenges[2]);
  ctx.tmp[27] = ctx.F.mul([ ctx.exps_withq_n[2 + ((i + 1)%1024)*35] , ctx.exps_withq_n[2 + ((i + 1)%1024)*35 + 1], ctx.exps_withq_n[2 + ((i + 1)%1024)*35 + 2] ], ctx.challenges[3]);
  ctx.tmp[28] = ctx.F.add([ ctx.exps_withq_n[2 + i*35] , ctx.exps_withq_n[2 + i*35 + 1] , ctx.exps_withq_n[2 + i*35 + 2] ], ctx.tmp[27]);
  ctx.tmp[29] = ctx.F.add(1n, ctx.challenges[3]);
  ctx.tmp[30] = ctx.F.mul(ctx.challenges[2], ctx.tmp[29]);
  ctx.tmp[31] = ctx.F.add(ctx.tmp[28], ctx.tmp[30]);
  ctx.tmp[32] = ctx.F.mul(ctx.tmp[26], ctx.tmp[31]);
  ctx.tmp[33] = ctx.F.add(1n, ctx.challenges[3]);
  [ ctx.exps_withq_n[14 + i*35] , ctx.exps_withq_n[14 + i*35 + 1] , ctx.exps_withq_n[14 + i*35 + 2] ] = ctx.F.mul(ctx.tmp[32], ctx.tmp[33]);   // 对应 plookup pNum 计算
  ctx.tmp[34] = ctx.F.mul([ ctx.cm2_n[3 + i*6] , ctx.cm2_n[3 + i*6 + 1] , ctx.cm2_n[3 + i*6 + 2] ], ctx.challenges[3]);
  ctx.tmp[35] = ctx.F.add([ ctx.cm2_n[0 + i*6] , ctx.cm2_n[0 + i*6 + 1] , ctx.cm2_n[0 + i*6 + 2] ], ctx.tmp[34]);
  ctx.tmp[36] = ctx.F.add(1n, ctx.challenges[3]);
  ctx.tmp[37] = ctx.F.mul(ctx.challenges[2], ctx.tmp[36]);
  ctx.tmp[38] = ctx.F.add(ctx.tmp[35], ctx.tmp[37]);
  ctx.tmp[39] = ctx.F.mul([ ctx.cm2_n[0 + ((i + 1)%1024)*6] , ctx.cm2_n[0 + ((i + 1)%1024)*6 + 1], ctx.cm2_n[0 + ((i + 1)%1024)*6 + 2] ], ctx.challenges[3]);
  ctx.tmp[40] = ctx.F.add([ ctx.cm2_n[3 + i*6] , ctx.cm2_n[3 + i*6 + 1] , ctx.cm2_n[3 + i*6 + 2] ], ctx.tmp[39]);
  ctx.tmp[41] = ctx.F.add(1n, ctx.challenges[3]);
  ctx.tmp[42] = ctx.F.mul(ctx.challenges[2], ctx.tmp[41]);
  ctx.tmp[43] = ctx.F.add(ctx.tmp[40], ctx.tmp[42]);
  [ ctx.exps_withq_n[17 + i*35] , ctx.exps_withq_n[17 + i*35 + 1] , ctx.exps_withq_n[17 + i*35 + 2] ] = ctx.F.mul(ctx.tmp[38], ctx.tmp[43]);   // 对应着 plookup pDen 计算
  [ ctx.exps_withoutq_n[0 + i*12] , ctx.exps_withoutq_n[0 + i*12 + 1] , ctx.exps_withoutq_n[0 + i*12 + 2] ] = ctx.F.add([ ctx.exps_withq_n[11 + i*35] , ctx.exps_withq_n[11 + i*35 + 1] , ctx.exps_withq_n[11 + i*35 + 2] ], ctx.challenges[3]);    // 对应着 permuation pNum 计算
  [ ctx.exps_withoutq_n[3 + i*12] , ctx.exps_withoutq_n[3 + i*12 + 1] , ctx.exps_withoutq_n[3 + i*12 + 2] ] = ctx.F.add([ ctx.exps_withq_n[8 + i*35] , ctx.exps_withq_n[8 + i*35 + 1] , ctx.exps_withq_n[8 + i*35 + 2] ], ctx.challenges[3]);      // 对应着 permutation pDen 计算
  ctx.tmp[72] = ctx.cm1_n[2 + i*15];
  ctx.tmp[44] = ctx.F.mul(ctx.challenges[3], ctx.x_n[i]);
  ctx.tmp[45] = ctx.F.add(ctx.tmp[72], ctx.tmp[44]);
  [ ctx.exps_withoutq_n[6 + i*12] , ctx.exps_withoutq_n[6 + i*12 + 1] , ctx.exps_withoutq_n[6 + i*12 + 2] ] = ctx.F.add(ctx.tmp[45], ctx.challenges[2]);
  ctx.tmp[73] = ctx.cm1_n[3 + i*15];
  ctx.tmp[46] = ctx.F.mul(ctx.challenges[3], 12275445934081160404n);
  ctx.tmp[47] = ctx.F.mul(ctx.tmp[46], ctx.x_n[i]);
  ctx.tmp[48] = ctx.F.add(ctx.tmp[73], ctx.tmp[47]);
  ctx.tmp[49] = ctx.F.add(ctx.tmp[48], ctx.challenges[2]);
  [ ctx.exps_withq_n[20 + i*35] , ctx.exps_withq_n[20 + i*35 + 1] , ctx.exps_withq_n[20 + i*35 + 2] ] = ctx.F.mul([ ctx.exps_withoutq_n[6 + i*12] , ctx.exps_withoutq_n[6 + i*12 + 1] , ctx.exps_withoutq_n[6 + i*12 + 2] ], ctx.tmp[49]);
  ctx.tmp[74] = ctx.cm1_n[4 + i*15];
  ctx.tmp[50] = ctx.F.mul(ctx.challenges[3], 4756475762779100925n);
  ctx.tmp[51] = ctx.F.mul(ctx.tmp[50], ctx.x_n[i]);
  ctx.tmp[52] = ctx.F.add(ctx.tmp[74], ctx.tmp[51]);
  ctx.tmp[53] = ctx.F.add(ctx.tmp[52], ctx.challenges[2]);
  [ ctx.exps_withq_n[26 + i*35] , ctx.exps_withq_n[26 + i*35 + 1] , ctx.exps_withq_n[26 + i*35 + 2] ] = ctx.F.mul([ ctx.exps_withq_n[20 + i*35] , ctx.exps_withq_n[20 + i*35 + 1] , ctx.exps_withq_n[20 + i*35 + 2] ], ctx.tmp[53]);  // 对应着 connection pNum
  ctx.tmp[75] = ctx.const_n[3 + i*9];
  ctx.tmp[54] = ctx.F.mul(ctx.challenges[3], ctx.tmp[75]);
  ctx.tmp[55] = ctx.F.add(ctx.tmp[72], ctx.tmp[54]);
  [ ctx.exps_withoutq_n[9 + i*12] , ctx.exps_withoutq_n[9 + i*12 + 1] , ctx.exps_withoutq_n[9 + i*12 + 2] ] = ctx.F.add(ctx.tmp[55], ctx.challenges[2]);
  ctx.tmp[76] = ctx.const_n[4 + i*9];
  ctx.tmp[56] = ctx.F.mul(ctx.challenges[3], ctx.tmp[76]);
  ctx.tmp[57] = ctx.F.add(ctx.tmp[73], ctx.tmp[56]);
  ctx.tmp[58] = ctx.F.add(ctx.tmp[57], ctx.challenges[2]);
  [ ctx.exps_withq_n[23 + i*35] , ctx.exps_withq_n[23 + i*35 + 1] , ctx.exps_withq_n[23 + i*35 + 2] ] = ctx.F.mul([ ctx.exps_withoutq_n[9 + i*12] , ctx.exps_withoutq_n[9 + i*12 + 1] , ctx.exps_withoutq_n[9 + i*12 + 2] ], ctx.tmp[58]);
  ctx.tmp[77] = ctx.const_n[5 + i*9];
  ctx.tmp[59] = ctx.F.mul(ctx.challenges[3], ctx.tmp[77]);
  ctx.tmp[60] = ctx.F.add(ctx.tmp[74], ctx.tmp[59]);
  ctx.tmp[61] = ctx.F.add(ctx.tmp[60], ctx.challenges[2]);
  [ ctx.exps_withq_n[29 + i*35] , ctx.exps_withq_n[29 + i*35 + 1] , ctx.exps_withq_n[29 + i*35 + 2] ] = ctx.F.mul([ ctx.exps_withq_n[23 + i*35] , ctx.exps_withq_n[23 + i*35 + 1] , ctx.exps_withq_n[23 + i*35 + 2] ], ctx.tmp[61]);   // 对应着 connection pDen 
})

根据以上计算的plookup, permuation, connection 的 pNum 和 pDen，计算其对应的z 多项式，存放于ctx.cm3_n中。

最后再对ctx.cm3_n 通过FFT变换扩展到扩域上，再生成Merkle 树，得到tree3.

Compute C Polynomial

step4 的输入和输出分别为：

if (execPart == "step4") {
        execInfo.inputSections.push({ name: "exps_withq_n" });  // 输入
        execInfo.inputSections.push({ name: "exps_withoutq_n" });
        execInfo.inputSections.push({ name: "cm1_n" });
        execInfo.inputSections.push({ name: "cm2_n" });
        execInfo.inputSections.push({ name: "cm3_n" });
        execInfo.inputSections.push({ name: "x_n" });
        execInfo.inputSections.push({ name: "const_n" });
        execInfo.outputSections.push({ name: "exps_withq_n" });  // 输出
        dom = "n";
    }

通过调用compileCode 将第step4 步的 code 编译成为计算函数，例如，本例中编译的结果为：

(function anonymous(ctx,i
) {
  ctx.tmp[62] = ctx.F.mul(ctx.cm1_n[0 + i*15], ctx.cm1_n[0 + i*15]);
  ctx.tmp[63] = ctx.F.mul(ctx.cm1_n[1 + i*15], ctx.cm1_n[1 + i*15]);
  ctx.exps_withq_n[0 + i*35] = ctx.F.add(ctx.tmp[62], ctx.tmp[63]);
  ctx.tmp[64] = ctx.F.sub(ctx.cm1_n[1 + ((i + 1)%1024)*15], ctx.cm1_n[0 + i*15]);
  ctx.tmp[65] = ctx.F.sub(1n, ctx.const_n[2 + i*9]);
  ctx.tmp[66] = ctx.F.mul(ctx.tmp[64], ctx.tmp[65]);
  ctx.tmp[104] = ctx.F.sub(ctx.tmp[66], 0n);
  ctx.tmp[67] = ctx.F.sub(ctx.cm1_n[0 + ((i + 1)%1024)*15], ctx.exps_withq_n[0 + i*35]);
  ctx.tmp[68] = ctx.F.sub(1n, ctx.const_n[2 + i*9]);
  ctx.tmp[69] = ctx.F.mul(ctx.tmp[67], ctx.tmp[68]);
  ctx.tmp[105] = ctx.F.sub(ctx.tmp[69], 0n);
  ctx.tmp[70] = ctx.F.sub(ctx.cm1_n[1 + i*15], ctx.publics[0]);
  ctx.tmp[71] = ctx.F.mul(ctx.const_n[1 + i*9], ctx.tmp[70]);
  ctx.tmp[106] = ctx.F.sub(ctx.tmp[71], 0n);
  ctx.tmp[72] = ctx.F.sub(ctx.cm1_n[0 + i*15], ctx.publics[1]);
  ctx.tmp[73] = ctx.F.mul(ctx.const_n[1 + i*9], ctx.tmp[72]);
  ctx.tmp[107] = ctx.F.sub(ctx.tmp[73], 0n);
  ctx.tmp[74] = ctx.F.sub(ctx.cm1_n[0 + i*15], ctx.publics[2]);
  ctx.tmp[75] = ctx.F.mul(ctx.const_n[2 + i*9], ctx.tmp[74]);
  ctx.tmp[108] = ctx.F.sub(ctx.tmp[75], 0n);
  ctx.tmp[76] = ctx.F.sub([ ctx.cm3_n[0 + i*9] , ctx.cm3_n[0 + i*9 + 1] , ctx.cm3_n[0 + i*9 + 2] ], 1n);
  ctx.tmp[109] = ctx.F.mul(ctx.const_n[0 + i*9], ctx.tmp[76]);
  ctx.tmp[77] = ctx.F.mul([ ctx.cm3_n[0 + ((i + 1)%1024)*9] , ctx.cm3_n[0 + ((i + 1)%1024)*9 + 1], ctx.cm3_n[0 + ((i + 1)%1024)*9 + 2] ], [ ctx.exps_withq_n[17 + i*35] , ctx.exps_withq_n[17 + i*35 + 1] , ctx.exps_withq_n[17 + i*35 + 2] ]);
  ctx.tmp[78] = ctx.F.mul([ ctx.cm3_n[0 + i*9] , ctx.cm3_n[0 + i*9 + 1] , ctx.cm3_n[0 + i*9 + 2] ], [ ctx.exps_withq_n[14 + i*35] , ctx.exps_withq_n[14 + i*35 + 1] , ctx.exps_withq_n[14 + i*35 + 2] ]);
  ctx.tmp[110] = ctx.F.sub(ctx.tmp[77], ctx.tmp[78]);
  ctx.tmp[79] = ctx.F.sub([ ctx.cm3_n[3 + i*9] , ctx.cm3_n[3 + i*9 + 1] , ctx.cm3_n[3 + i*9 + 2] ], 1n);
  ctx.tmp[111] = ctx.F.mul(ctx.const_n[0 + i*9], ctx.tmp[79]);
  ctx.tmp[80] = ctx.F.mul([ ctx.cm3_n[3 + ((i + 1)%1024)*9] , ctx.cm3_n[3 + ((i + 1)%1024)*9 + 1], ctx.cm3_n[3 + ((i + 1)%1024)*9 + 2] ], [ ctx.exps_withoutq_n[3 + i*12] , ctx.exps_withoutq_n[3 + i*12 + 1] , ctx.exps_withoutq_n[3 + i*12 + 2] ]);
  ctx.tmp[81] = ctx.F.mul([ ctx.cm3_n[3 + i*9] , ctx.cm3_n[3 + i*9 + 1] , ctx.cm3_n[3 + i*9 + 2] ], [ ctx.exps_withoutq_n[0 + i*12] , ctx.exps_withoutq_n[0 + i*12 + 1] , ctx.exps_withoutq_n[0 + i*12 + 2] ]);
  ctx.tmp[112] = ctx.F.sub(ctx.tmp[80], ctx.tmp[81]);
  ctx.tmp[82] = ctx.F.sub([ ctx.cm3_n[6 + i*9] , ctx.cm3_n[6 + i*9 + 1] , ctx.cm3_n[6 + i*9 + 2] ], 1n);
  ctx.tmp[113] = ctx.F.mul(ctx.const_n[0 + i*9], ctx.tmp[82]);
  ctx.tmp[83] = ctx.F.mul([ ctx.cm3_n[6 + ((i + 1)%1024)*9] , ctx.cm3_n[6 + ((i + 1)%1024)*9 + 1], ctx.cm3_n[6 + ((i + 1)%1024)*9 + 2] ], [ ctx.exps_withq_n[29 + i*35] , ctx.exps_withq_n[29 + i*35 + 1] , ctx.exps_withq_n[29 + i*35 + 2] ]);
  ctx.tmp[84] = ctx.F.mul([ ctx.cm3_n[6 + i*9] , ctx.cm3_n[6 + i*9 + 1] , ctx.cm3_n[6 + i*9 + 2] ], [ ctx.exps_withq_n[26 + i*35] , ctx.exps_withq_n[26 + i*35 + 1] , ctx.exps_withq_n[26 + i*35 + 2] ]);
  ctx.tmp[114] = ctx.F.sub(ctx.tmp[83], ctx.tmp[84]);
  ctx.tmp[85] = ctx.F.mul(ctx.challenges[4], ctx.tmp[104]);
  ctx.tmp[86] = ctx.F.add(ctx.tmp[85], ctx.tmp[105]);
  ctx.tmp[87] = ctx.F.mul(ctx.challenges[4], ctx.tmp[86]);
  ctx.tmp[88] = ctx.F.add(ctx.tmp[87], ctx.tmp[106]);
  ctx.tmp[89] = ctx.F.mul(ctx.challenges[4], ctx.tmp[88]);
  ctx.tmp[90] = ctx.F.add(ctx.tmp[89], ctx.tmp[107]);
  ctx.tmp[91] = ctx.F.mul(ctx.challenges[4], ctx.tmp[90]);
  ctx.tmp[92] = ctx.F.add(ctx.tmp[91], ctx.tmp[108]);
  ctx.tmp[93] = ctx.F.mul(ctx.challenges[4], ctx.tmp[92]);
  ctx.tmp[94] = ctx.F.add(ctx.tmp[93], ctx.tmp[109]);
  ctx.tmp[95] = ctx.F.mul(ctx.challenges[4], ctx.tmp[94]);
  ctx.tmp[96] = ctx.F.add(ctx.tmp[95], ctx.tmp[110]);
  ctx.tmp[97] = ctx.F.mul(ctx.challenges[4], ctx.tmp[96]);
  ctx.tmp[98] = ctx.F.add(ctx.tmp[97], ctx.tmp[111]);
  ctx.tmp[99] = ctx.F.mul(ctx.challenges[4], ctx.tmp[98]);
  ctx.tmp[100] = ctx.F.add(ctx.tmp[99], ctx.tmp[112]);
  ctx.tmp[101] = ctx.F.mul(ctx.challenges[4], ctx.tmp[100]);
  ctx.tmp[102] = ctx.F.add(ctx.tmp[101], ctx.tmp[113]);
  ctx.tmp[103] = ctx.F.mul(ctx.challenges[4], ctx.tmp[102]);
  [ ctx.exps_withq_n[32 + i*35] , ctx.exps_withq_n[32 + i*35 + 1] , ctx.exps_withq_n[32 + i*35 + 2] ] = ctx.F.add(ctx.tmp[103], ctx.tmp[114]);
})

然后将ctx.exps_withq_n 通过FFT变换扩展到 ctx.exps_withq_2ns 上，然后再计算step42ns.

step42ns 的输入和输出分别为：

if (execPart == "step42ns") {
        execInfo.inputSections.push({ name: "cm1_2ns" });  // 输入
        execInfo.inputSections.push({ name: "cm2_2ns" });
        execInfo.inputSections.push({ name: "cm3_2ns" });
        execInfo.inputSections.push({ name: "const_2ns" });
        execInfo.inputSections.push({ name: "x_2ns" });
        execInfo.inputSections.push({ name: "exps_withq_2ns" });
        execInfo.outputSections.push({ name: "q_2ns" });           // 输出
        dom = "2ns";
    }

通过调用compileCode 将第step42ns 步的 code 编译成为计算函数，例如，本例中编译的结果为：

(function anonymous(ctx,i
) {
  ctx.tmp[0] = ctx.F.mul(ctx.cm1_2ns[0 + i*15], ctx.cm1_2ns[0 + i*15]);
  ctx.tmp[1] = ctx.F.mul(ctx.cm1_2ns[1 + i*15], ctx.cm1_2ns[1 + i*15]);
  ctx.tmp[2] = ctx.F.add(ctx.tmp[0], ctx.tmp[1]);
  ctx.tmp[3] = ctx.F.sub(ctx.tmp[2], ctx.exps_withq_2ns[0 + i*35]);
  ctx.q_2ns[0 + i*35] = ctx.F.mul(ctx.Zi(i), ctx.tmp[3]); 
  ctx.tmp[4] = ctx.F.mul(ctx.cm1_2ns[12 + i*15], ctx.cm1_2ns[13 + ((i + 2)%2048)*15]);
  ctx.tmp[5] = ctx.F.sub(ctx.tmp[4], ctx.exps_withq_2ns[1 + i*35]);
  ctx.q_2ns[1 + i*35] = ctx.F.mul(ctx.Zi(i), ctx.tmp[5]);  // a * b'
  ctx.tmp[124] = ctx.const_2ns[7 + i*9];
  ctx.tmp[125] = ctx.const_2ns[8 + i*9];
  ctx.tmp[126] = ctx.cm1_2ns[14 + i*15];
  ctx.tmp[127] = ctx.const_2ns[6 + i*9];
  ctx.tmp[6] = ctx.F.mul(ctx.challenges[0], ctx.tmp[124]);
  ctx.tmp[7] = ctx.F.add(ctx.tmp[6], ctx.tmp[125]);
  ctx.tmp[8] = ctx.F.mul(ctx.challenges[0], ctx.tmp[7]);
  ctx.tmp[9] = ctx.F.add(ctx.tmp[8], ctx.tmp[126]);
  ctx.tmp[10] = ctx.F.sub(ctx.tmp[9], ctx.challenges[1]);
  ctx.tmp[11] = ctx.F.mul(ctx.tmp[10], ctx.tmp[127]);
  ctx.tmp[12] = ctx.F.add(ctx.tmp[11], ctx.challenges[1]);
  ctx.tmp[13] = ctx.F.sub(ctx.tmp[12], [ ctx.exps_withq_2ns[2 + i*35] , ctx.exps_withq_2ns[2 + i*35 + 1] , ctx.exps_withq_2ns[2 + i*35 + 2] ]);
  [ ctx.q_2ns[2 + i*35] , ctx.q_2ns[2 + i*35 + 1] , ctx.q_2ns[2 + i*35 + 2] ] = ctx.F.mul(ctx.Zi(i), ctx.tmp[13]); // plookup t 
  ctx.tmp[128] = ctx.cm1_2ns[12 + i*15];
  ctx.tmp[129] = ctx.cm1_2ns[13 + ((i + 2)%2048)*15];
  ctx.tmp[130] = ctx.cm1_2ns[11 + i*15];
  ctx.tmp[14] = ctx.F.mul(ctx.tmp[128], ctx.challenges[0]);
  ctx.tmp[15] = ctx.F.add(ctx.tmp[14], ctx.tmp[129]);
  ctx.tmp[16] = ctx.F.mul(ctx.tmp[15], ctx.challenges[0]);
  ctx.tmp[17] = ctx.F.add(ctx.tmp[16], ctx.exps_withq_2ns[1 + i*35]);
  ctx.tmp[18] = ctx.F.sub(ctx.tmp[17], [ ctx.exps_withq_2ns[2 + i*35] , ctx.exps_withq_2ns[2 + i*35 + 1] , ctx.exps_withq_2ns[2 + i*35 + 2] ]);
  ctx.tmp[19] = ctx.F.mul(ctx.tmp[18], ctx.tmp[130]);
  ctx.tmp[20] = ctx.F.add(ctx.tmp[19], [ ctx.exps_withq_2ns[2 + i*35] , ctx.exps_withq_2ns[2 + i*35 + 1] , ctx.exps_withq_2ns[2 + i*35 + 2] ]);
  ctx.tmp[21] = ctx.F.sub(ctx.tmp[20], [ ctx.exps_withq_2ns[5 + i*35] , ctx.exps_withq_2ns[5 + i*35 + 1] , ctx.exps_withq_2ns[5 + i*35 + 2] ]);
  [ ctx.q_2ns[5 + i*35] , ctx.q_2ns[5 + i*35 + 1] , ctx.q_2ns[5 + i*35 + 2] ] = ctx.F.mul(ctx.Zi(i), ctx.tmp[21]);  // plookup f 
  ctx.tmp[131] = ctx.cm1_2ns[8 + i*15];
  ctx.tmp[132] = ctx.cm1_2ns[8 + i*15];
  ctx.tmp[133] = ctx.cm1_2ns[10 + i*15];
  ctx.tmp[22] = ctx.F.mul(ctx.challenges[0], ctx.tmp[131]);
  ctx.tmp[23] = ctx.F.add(ctx.tmp[22], ctx.tmp[132]);
  ctx.tmp[24] = ctx.F.sub(ctx.tmp[23], ctx.challenges[1]);
  ctx.tmp[25] = ctx.F.mul(ctx.tmp[24], ctx.tmp[133]);
  ctx.tmp[26] = ctx.F.add(ctx.tmp[25], ctx.challenges[1]);
  ctx.tmp[27] = ctx.F.sub(ctx.tmp[26], [ ctx.exps_withq_2ns[8 + i*35] , ctx.exps_withq_2ns[8 + i*35 + 1] , ctx.exps_withq_2ns[8 + i*35 + 2] ]);
  [ ctx.q_2ns[8 + i*35] , ctx.q_2ns[8 + i*35 + 1] , ctx.q_2ns[8 + i*35 + 2] ] = ctx.F.mul(ctx.Zi(i), ctx.tmp[27]);
  ctx.tmp[134] = ctx.cm1_2ns[7 + i*15];
  ctx.tmp[135] = ctx.cm1_2ns[7 + i*15];
  ctx.tmp[136] = ctx.cm1_2ns[9 + i*15];
  ctx.tmp[28] = ctx.F.mul(ctx.tmp[134], ctx.challenges[0]);
  ctx.tmp[29] = ctx.F.add(ctx.tmp[28], ctx.tmp[135]);
  ctx.tmp[30] = ctx.F.sub(ctx.tmp[29], ctx.challenges[1]);
  ctx.tmp[31] = ctx.F.mul(ctx.tmp[30], ctx.tmp[136]);
  ctx.tmp[32] = ctx.F.add(ctx.tmp[31], ctx.challenges[1]);
  ctx.tmp[33] = ctx.F.sub(ctx.tmp[32], [ ctx.exps_withq_2ns[11 + i*35] , ctx.exps_withq_2ns[11 + i*35 + 1] , ctx.exps_withq_2ns[11 + i*35 + 2] ]);
  [ ctx.q_2ns[11 + i*35] , ctx.q_2ns[11 + i*35 + 1] , ctx.q_2ns[11 + i*35 + 2] ] = ctx.F.mul(ctx.Zi(i), ctx.tmp[33]);
  ctx.tmp[34] = ctx.F.add([ ctx.exps_withq_2ns[5 + i*35] , ctx.exps_withq_2ns[5 + i*35 + 1] , ctx.exps_withq_2ns[5 + i*35 + 2] ], ctx.challenges[2]);
  ctx.tmp[35] = ctx.F.mul([ ctx.exps_withq_2ns[2 + ((i + 2)%2048)*35] , ctx.exps_withq_2ns[2 + ((i + 2)%2048)*35 + 1], ctx.exps_withq_2ns[2 + ((i + 2)%2048)*35 + 2] ], ctx.challenges[3]);
  ctx.tmp[36] = ctx.F.add([ ctx.exps_withq_2ns[2 + i*35] , ctx.exps_withq_2ns[2 + i*35 + 1] , ctx.exps_withq_2ns[2 + i*35 + 2] ], ctx.tmp[35]);
  ctx.tmp[37] = ctx.F.add(1n, ctx.challenges[3]);
  ctx.tmp[38] = ctx.F.mul(ctx.challenges[2], ctx.tmp[37]);
  ctx.tmp[39] = ctx.F.add(ctx.tmp[36], ctx.tmp[38]);
  ctx.tmp[40] = ctx.F.mul(ctx.tmp[34], ctx.tmp[39]);
  ctx.tmp[41] = ctx.F.add(1n, ctx.challenges[3]);
  ctx.tmp[42] = ctx.F.mul(ctx.tmp[40], ctx.tmp[41]);
  ctx.tmp[43] = ctx.F.sub(ctx.tmp[42], [ ctx.exps_withq_2ns[14 + i*35] , ctx.exps_withq_2ns[14 + i*35 + 1] , ctx.exps_withq_2ns[14 + i*35 + 2] ]);
  [ ctx.q_2ns[14 + i*35] , ctx.q_2ns[14 + i*35 + 1] , ctx.q_2ns[14 + i*35 + 2] ] = ctx.F.mul(ctx.Zi(i), ctx.tmp[43]);
  ctx.tmp[44] = ctx.F.mul([ ctx.cm2_2ns[3 + i*6] , ctx.cm2_2ns[3 + i*6 + 1] , ctx.cm2_2ns[3 + i*6 + 2] ], ctx.challenges[3]);
  ctx.tmp[45] = ctx.F.add([ ctx.cm2_2ns[0 + i*6] , ctx.cm2_2ns[0 + i*6 + 1] , ctx.cm2_2ns[0 + i*6 + 2] ], ctx.tmp[44]);
  ctx.tmp[46] = ctx.F.add(1n, ctx.challenges[3]);
  ctx.tmp[47] = ctx.F.mul(ctx.challenges[2], ctx.tmp[46]);
  ctx.tmp[48] = ctx.F.add(ctx.tmp[45], ctx.tmp[47]);
  ctx.tmp[49] = ctx.F.mul([ ctx.cm2_2ns[0 + ((i + 2)%2048)*6] , ctx.cm2_2ns[0 + ((i + 2)%2048)*6 + 1], ctx.cm2_2ns[0 + ((i + 2)%2048)*6 + 2] ], ctx.challenges[3]);
  ctx.tmp[50] = ctx.F.add([ ctx.cm2_2ns[3 + i*6] , ctx.cm2_2ns[3 + i*6 + 1] , ctx.cm2_2ns[3 + i*6 + 2] ], ctx.tmp[49]);
  ctx.tmp[51] = ctx.F.add(1n, ctx.challenges[3]);
  ctx.tmp[52] = ctx.F.mul(ctx.challenges[2], ctx.tmp[51]);
  ctx.tmp[53] = ctx.F.add(ctx.tmp[50], ctx.tmp[52]);
  ctx.tmp[54] = ctx.F.mul(ctx.tmp[48], ctx.tmp[53]);
  ctx.tmp[55] = ctx.F.sub(ctx.tmp[54], [ ctx.exps_withq_2ns[17 + i*35] , ctx.exps_withq_2ns[17 + i*35 + 1] , ctx.exps_withq_2ns[17 + i*35 + 2] ]);
  [ ctx.q_2ns[17 + i*35] , ctx.q_2ns[17 + i*35 + 1] , ctx.q_2ns[17 + i*35 + 2] ] = ctx.F.mul(ctx.Zi(i), ctx.tmp[55]);
  ctx.tmp[137] = ctx.cm1_2ns[2 + i*15];
  ctx.tmp[56] = ctx.F.mul(ctx.challenges[3], ctx.x_2ns[i]);
  ctx.tmp[57] = ctx.F.add(ctx.tmp[137], ctx.tmp[56]);
  ctx.tmp[138] = ctx.F.add(ctx.tmp[57], ctx.challenges[2]);
  ctx.tmp[139] = ctx.cm1_2ns[3 + i*15];
  ctx.tmp[58] = ctx.F.mul(ctx.challenges[3], 12275445934081160404n);
  ctx.tmp[59] = ctx.F.mul(ctx.tmp[58], ctx.x_2ns[i]);
  ctx.tmp[60] = ctx.F.add(ctx.tmp[139], ctx.tmp[59]);
  ctx.tmp[61] = ctx.F.add(ctx.tmp[60], ctx.challenges[2]);
  ctx.tmp[62] = ctx.F.mul(ctx.tmp[138], ctx.tmp[61]);
  ctx.tmp[63] = ctx.F.sub(ctx.tmp[62], [ ctx.exps_withq_2ns[20 + i*35] , ctx.exps_withq_2ns[20 + i*35 + 1] , ctx.exps_withq_2ns[20 + i*35 + 2] ]);
  [ ctx.q_2ns[20 + i*35] , ctx.q_2ns[20 + i*35 + 1] , ctx.q_2ns[20 + i*35 + 2] ] = ctx.F.mul(ctx.Zi(i), ctx.tmp[63]);
  ctx.tmp[140] = ctx.const_2ns[3 + i*9];
  ctx.tmp[64] = ctx.F.mul(ctx.challenges[3], ctx.tmp[140]);
  ctx.tmp[65] = ctx.F.add(ctx.tmp[137], ctx.tmp[64]);
  ctx.tmp[141] = ctx.F.add(ctx.tmp[65], ctx.challenges[2]);
  ctx.tmp[142] = ctx.const_2ns[4 + i*9];
  ctx.tmp[66] = ctx.F.mul(ctx.challenges[3], ctx.tmp[142]);
  ctx.tmp[67] = ctx.F.add(ctx.tmp[139], ctx.tmp[66]);
  ctx.tmp[68] = ctx.F.add(ctx.tmp[67], ctx.challenges[2]);
  ctx.tmp[69] = ctx.F.mul(ctx.tmp[141], ctx.tmp[68]);
  ctx.tmp[70] = ctx.F.sub(ctx.tmp[69], [ ctx.exps_withq_2ns[23 + i*35] , ctx.exps_withq_2ns[23 + i*35 + 1] , ctx.exps_withq_2ns[23 + i*35 + 2] ]);
  [ ctx.q_2ns[23 + i*35] , ctx.q_2ns[23 + i*35 + 1] , ctx.q_2ns[23 + i*35 + 2] ] = ctx.F.mul(ctx.Zi(i), ctx.tmp[70]);
  ctx.tmp[143] = ctx.cm1_2ns[4 + i*15];
  ctx.tmp[71] = ctx.F.mul(ctx.challenges[3], 4756475762779100925n);
  ctx.tmp[72] = ctx.F.mul(ctx.tmp[71], ctx.x_2ns[i]);
  ctx.tmp[73] = ctx.F.add(ctx.tmp[143], ctx.tmp[72]);
  ctx.tmp[74] = ctx.F.add(ctx.tmp[73], ctx.challenges[2]);
  ctx.tmp[75] = ctx.F.mul([ ctx.exps_withq_2ns[20 + i*35] , ctx.exps_withq_2ns[20 + i*35 + 1] , ctx.exps_withq_2ns[20 + i*35 + 2] ], ctx.tmp[74]);
  ctx.tmp[76] = ctx.F.sub(ctx.tmp[75], [ ctx.exps_withq_2ns[26 + i*35] , ctx.exps_withq_2ns[26 + i*35 + 1] , ctx.exps_withq_2ns[26 + i*35 + 2] ]);
  [ ctx.q_2ns[26 + i*35] , ctx.q_2ns[26 + i*35 + 1] , ctx.q_2ns[26 + i*35 + 2] ] = ctx.F.mul(ctx.Zi(i), ctx.tmp[76]);
  ctx.tmp[144] = ctx.const_2ns[5 + i*9];
  ctx.tmp[77] = ctx.F.mul(ctx.challenges[3], ctx.tmp[144]);
  ctx.tmp[78] = ctx.F.add(ctx.tmp[143], ctx.tmp[77]);
  ctx.tmp[79] = ctx.F.add(ctx.tmp[78], ctx.challenges[2]);
  ctx.tmp[80] = ctx.F.mul([ ctx.exps_withq_2ns[23 + i*35] , ctx.exps_withq_2ns[23 + i*35 + 1] , ctx.exps_withq_2ns[23 + i*35 + 2] ], ctx.tmp[79]);
  ctx.tmp[81] = ctx.F.sub(ctx.tmp[80], [ ctx.exps_withq_2ns[29 + i*35] , ctx.exps_withq_2ns[29 + i*35 + 1] , ctx.exps_withq_2ns[29 + i*35 + 2] ]);
  [ ctx.q_2ns[29 + i*35] , ctx.q_2ns[29 + i*35 + 1] , ctx.q_2ns[29 + i*35 + 2] ] = ctx.F.mul(ctx.Zi(i), ctx.tmp[81]);
  ctx.tmp[82] = ctx.F.sub(ctx.cm1_2ns[1 + ((i + 2)%2048)*15], ctx.cm1_2ns[0 + i*15]);
  ctx.tmp[83] = ctx.F.sub(1n, ctx.const_2ns[2 + i*9]);
  ctx.tmp[84] = ctx.F.mul(ctx.tmp[82], ctx.tmp[83]);
  ctx.tmp[145] = ctx.F.sub(ctx.tmp[84], 0n);
  ctx.tmp[85] = ctx.F.sub(ctx.cm1_2ns[0 + ((i + 2)%2048)*15], ctx.exps_withq_2ns[0 + i*35]);
  ctx.tmp[86] = ctx.F.sub(1n, ctx.const_2ns[2 + i*9]);
  ctx.tmp[87] = ctx.F.mul(ctx.tmp[85], ctx.tmp[86]);
  ctx.tmp[146] = ctx.F.sub(ctx.tmp[87], 0n);
  ctx.tmp[88] = ctx.F.sub(ctx.cm1_2ns[1 + i*15], ctx.publics[0]);
  ctx.tmp[89] = ctx.F.mul(ctx.const_2ns[1 + i*9], ctx.tmp[88]);
  ctx.tmp[147] = ctx.F.sub(ctx.tmp[89], 0n);
  ctx.tmp[90] = ctx.F.sub(ctx.cm1_2ns[0 + i*15], ctx.publics[1]);
  ctx.tmp[91] = ctx.F.mul(ctx.const_2ns[1 + i*9], ctx.tmp[90]);
  ctx.tmp[148] = ctx.F.sub(ctx.tmp[91], 0n);
  ctx.tmp[92] = ctx.F.sub(ctx.cm1_2ns[0 + i*15], ctx.publics[2]);
  ctx.tmp[93] = ctx.F.mul(ctx.const_2ns[2 + i*9], ctx.tmp[92]);
  ctx.tmp[149] = ctx.F.sub(ctx.tmp[93], 0n);
  ctx.tmp[94] = ctx.F.sub([ ctx.cm3_2ns[0 + i*9] , ctx.cm3_2ns[0 + i*9 + 1] , ctx.cm3_2ns[0 + i*9 + 2] ], 1n);
  ctx.tmp[150] = ctx.F.mul(ctx.const_2ns[0 + i*9], ctx.tmp[94]);
  ctx.tmp[95] = ctx.F.mul([ ctx.cm3_2ns[0 + ((i + 2)%2048)*9] , ctx.cm3_2ns[0 + ((i + 2)%2048)*9 + 1], ctx.cm3_2ns[0 + ((i + 2)%2048)*9 + 2] ], [ ctx.exps_withq_2ns[17 + i*35] , ctx.exps_withq_2ns[17 + i*35 + 1] , ctx.exps_withq_2ns[17 + i*35 + 2] ]);
  ctx.tmp[96] = ctx.F.mul([ ctx.cm3_2ns[0 + i*9] , ctx.cm3_2ns[0 + i*9 + 1] , ctx.cm3_2ns[0 + i*9 + 2] ], [ ctx.exps_withq_2ns[14 + i*35] , ctx.exps_withq_2ns[14 + i*35 + 1] , ctx.exps_withq_2ns[14 + i*35 + 2] ]);
  ctx.tmp[151] = ctx.F.sub(ctx.tmp[95], ctx.tmp[96]);
  ctx.tmp[97] = ctx.F.sub([ ctx.cm3_2ns[3 + i*9] , ctx.cm3_2ns[3 + i*9 + 1] , ctx.cm3_2ns[3 + i*9 + 2] ], 1n);
  ctx.tmp[152] = ctx.F.mul(ctx.const_2ns[0 + i*9], ctx.tmp[97]);
  ctx.tmp[153] = ctx.F.add([ ctx.exps_withq_2ns[8 + i*35] , ctx.exps_withq_2ns[8 + i*35 + 1] , ctx.exps_withq_2ns[8 + i*35 + 2] ], ctx.challenges[3]);
  ctx.tmp[154] = ctx.F.add([ ctx.exps_withq_2ns[11 + i*35] , ctx.exps_withq_2ns[11 + i*35 + 1] , ctx.exps_withq_2ns[11 + i*35 + 2] ], ctx.challenges[3]);
  ctx.tmp[98] = ctx.F.mul([ ctx.cm3_2ns[3 + ((i + 2)%2048)*9] , ctx.cm3_2ns[3 + ((i + 2)%2048)*9 + 1], ctx.cm3_2ns[3 + ((i + 2)%2048)*9 + 2] ], ctx.tmp[153]);
  ctx.tmp[99] = ctx.F.mul([ ctx.cm3_2ns[3 + i*9] , ctx.cm3_2ns[3 + i*9 + 1] , ctx.cm3_2ns[3 + i*9 + 2] ], ctx.tmp[154]);
  ctx.tmp[155] = ctx.F.sub(ctx.tmp[98], ctx.tmp[99]);
  ctx.tmp[100] = ctx.F.sub([ ctx.cm3_2ns[6 + i*9] , ctx.cm3_2ns[6 + i*9 + 1] , ctx.cm3_2ns[6 + i*9 + 2] ], 1n);
  ctx.tmp[156] = ctx.F.mul(ctx.const_2ns[0 + i*9], ctx.tmp[100]);
  ctx.tmp[101] = ctx.F.mul([ ctx.cm3_2ns[6 + ((i + 2)%2048)*9] , ctx.cm3_2ns[6 + ((i + 2)%2048)*9 + 1], ctx.cm3_2ns[6 + ((i + 2)%2048)*9 + 2] ], [ ctx.exps_withq_2ns[29 + i*35] , ctx.exps_withq_2ns[29 + i*35 + 1] , ctx.exps_withq_2ns[29 + i*35 + 2] ]);
  ctx.tmp[102] = ctx.F.mul([ ctx.cm3_2ns[6 + i*9] , ctx.cm3_2ns[6 + i*9 + 1] , ctx.cm3_2ns[6 + i*9 + 2] ], [ ctx.exps_withq_2ns[26 + i*35] , ctx.exps_withq_2ns[26 + i*35 + 1] , ctx.exps_withq_2ns[26 + i*35 + 2] ]);
  ctx.tmp[157] = ctx.F.sub(ctx.tmp[101], ctx.tmp[102]);
  ctx.tmp[103] = ctx.F.mul(ctx.challenges[4], ctx.tmp[145]);
  ctx.tmp[104] = ctx.F.add(ctx.tmp[103], ctx.tmp[146]);
  ctx.tmp[105] = ctx.F.mul(ctx.challenges[4], ctx.tmp[104]);
  ctx.tmp[106] = ctx.F.add(ctx.tmp[105], ctx.tmp[147]);
  ctx.tmp[107] = ctx.F.mul(ctx.challenges[4], ctx.tmp[106]);
  ctx.tmp[108] = ctx.F.add(ctx.tmp[107], ctx.tmp[148]);
  ctx.tmp[109] = ctx.F.mul(ctx.challenges[4], ctx.tmp[108]);
  ctx.tmp[110] = ctx.F.add(ctx.tmp[109], ctx.tmp[149]);
  ctx.tmp[111] = ctx.F.mul(ctx.challenges[4], ctx.tmp[110]);
  ctx.tmp[112] = ctx.F.add(ctx.tmp[111], ctx.tmp[150]);
  ctx.tmp[113] = ctx.F.mul(ctx.challenges[4], ctx.tmp[112]);
  ctx.tmp[114] = ctx.F.add(ctx.tmp[113], ctx.tmp[151]);
  ctx.tmp[115] = ctx.F.mul(ctx.challenges[4], ctx.tmp[114]);
  ctx.tmp[116] = ctx.F.add(ctx.tmp[115], ctx.tmp[152]);
  ctx.tmp[117] = ctx.F.mul(ctx.challenges[4], ctx.tmp[116]);
  ctx.tmp[118] = ctx.F.add(ctx.tmp[117], ctx.tmp[155]);
  ctx.tmp[119] = ctx.F.mul(ctx.challenges[4], ctx.tmp[118]);
  ctx.tmp[120] = ctx.F.add(ctx.tmp[119], ctx.tmp[156]);
  ctx.tmp[121] = ctx.F.mul(ctx.challenges[4], ctx.tmp[120]);
  ctx.tmp[122] = ctx.F.add(ctx.tmp[121], ctx.tmp[157]);
  ctx.tmp[123] = ctx.F.sub(ctx.tmp[122], [ ctx.exps_withq_2ns[32 + i*35] , ctx.exps_withq_2ns[32 + i*35 + 1] , ctx.exps_withq_2ns[32 + i*35 + 2] ]);
  [ ctx.q_2ns[32 + i*35] , ctx.q_2ns[32 + i*35 + 1] , ctx.q_2ns[32 + i*35 + 2] ] = ctx.F.mul(ctx.Zi(i), ctx.tmp[123]);
})

根据上述计算得到ctx.q_2ns ，然后得到Merkle 树 tree4。

Compute FRI Polynomial

Calculate Evals

首先选取两个点：

    const xis = F.div(ctx.challenges[7], F.shift);
    const wxis = F.div(F.mul(ctx.challenges[7], F.w[nBits]), F.shift);

$xis = \frac{xi}{shift} \\ wxis = \frac{w\cdot xi}{shift} \\$

$xis$ 和 $wxis$ 分别表示在Prime 为 faslse 和 true 情况下的选的点：

然后计算：
$LEv = (1, xis, xis^2, \cdots, xis^{N-1}) \\ LpEv = (1, wxis, wxis^2, \cdots, wxis^{N-1})$
然后对 $LEv$ 和 $LpEv$ 分别进行IFFT变换，得到对应的Lagrange 基。

然后对evMap 的中的多项式进行计算估值，将结果保存在 ctx.evals 中。

Calculate xDivXSubXi, xDivXSubWXi

xDivXSubXi 和 xDivXWXi的计算公式分别为：
$xDivXsubXi = \frac{shift\cdot w_e^i}{shift\cdot w_e^i-xi} \\ xDivXsubWXi = \frac{shift\cdot w_e^i}{shift \cdot w_e^i-w\cdot xi}$
其中 $shift$ 为偏移， $w$ 为基域生成元， $w_e$ 为扩域生成元， $i\in [0, N_e-1]$ 。

Calculate FRI

step52ns 的输入和输出分别为：

if (execPart == "step52ns") {
        execInfo.inputSections.push({ name: "cm1_2ns" });
        execInfo.inputSections.push({ name: "cm2_2ns" });
        execInfo.inputSections.push({ name: "cm3_2ns" });
        execInfo.inputSections.push({ name: "const_2ns" });
        execInfo.inputSections.push({ name: "q_2ns" });
        execInfo.inputSections.push({ name: "xDivXSubXi" });
        execInfo.inputSections.push({ name: "xDivXSubWXi" });
        execInfo.outputSections.push({ name: "exps_withoutq_2ns" });
        dom = "2ns";
    }

通过调用compileCode 将第step52ns 步的 code 编译成为计算函数，例如，本例中编译的结果为：

(function anonymous(ctx,i
) {
  ctx.tmp[124] = ctx.F.mul(ctx.challenges[5], ctx.cm1_2ns[0 + i*15]);
  ctx.tmp[125] = ctx.F.add(ctx.tmp[124], ctx.cm1_2ns[1 + i*15]);
  ctx.tmp[126] = ctx.F.mul(ctx.challenges[5], ctx.tmp[125]);
  ctx.tmp[127] = ctx.F.add(ctx.tmp[126], ctx.cm1_2ns[2 + i*15]);
  ctx.tmp[128] = ctx.F.mul(ctx.challenges[5], ctx.tmp[127]);
  ctx.tmp[129] = ctx.F.add(ctx.tmp[128], ctx.cm1_2ns[3 + i*15]);
  ctx.tmp[130] = ctx.F.mul(ctx.challenges[5], ctx.tmp[129]);
  ctx.tmp[131] = ctx.F.add(ctx.tmp[130], ctx.cm1_2ns[4 + i*15]);
  ctx.tmp[132] = ctx.F.mul(ctx.challenges[5], ctx.tmp[131]);
  ctx.tmp[133] = ctx.F.add(ctx.tmp[132], ctx.cm1_2ns[5 + i*15]);
  ctx.tmp[134] = ctx.F.mul(ctx.challenges[5], ctx.tmp[133]);
  ctx.tmp[135] = ctx.F.add(ctx.tmp[134], ctx.cm1_2ns[6 + i*15]);
  ctx.tmp[136] = ctx.F.mul(ctx.challenges[5], ctx.tmp[135]);
  ctx.tmp[137] = ctx.F.add(ctx.tmp[136], ctx.cm1_2ns[7 + i*15]);
  ctx.tmp[138] = ctx.F.mul(ctx.challenges[5], ctx.tmp[137]);
  ctx.tmp[139] = ctx.F.add(ctx.tmp[138], ctx.cm1_2ns[8 + i*15]);
  ctx.tmp[140] = ctx.F.mul(ctx.challenges[5], ctx.tmp[139]);
  ctx.tmp[141] = ctx.F.add(ctx.tmp[140], ctx.cm1_2ns[9 + i*15]);
  ctx.tmp[142] = ctx.F.mul(ctx.challenges[5], ctx.tmp[141]);
  ctx.tmp[143] = ctx.F.add(ctx.tmp[142], ctx.cm1_2ns[10 + i*15]);
  ctx.tmp[144] = ctx.F.mul(ctx.challenges[5], ctx.tmp[143]);
  ctx.tmp[145] = ctx.F.add(ctx.tmp[144], ctx.cm1_2ns[11 + i*15]);
  ctx.tmp[146] = ctx.F.mul(ctx.challenges[5], ctx.tmp[145]);
  ctx.tmp[147] = ctx.F.add(ctx.tmp[146], ctx.cm1_2ns[12 + i*15]);
  ctx.tmp[148] = ctx.F.mul(ctx.challenges[5], ctx.tmp[147]);
  ctx.tmp[149] = ctx.F.add(ctx.tmp[148], ctx.cm1_2ns[13 + i*15]);
  ctx.tmp[150] = ctx.F.mul(ctx.challenges[5], ctx.tmp[149]);
  ctx.tmp[151] = ctx.F.add(ctx.tmp[150], ctx.cm1_2ns[14 + i*15]);
  ctx.tmp[152] = ctx.F.mul(ctx.challenges[5], ctx.tmp[151]);
  ctx.tmp[153] = ctx.F.add(ctx.tmp[152], [ ctx.cm2_2ns[0 + i*6] , ctx.cm2_2ns[0 + i*6 + 1] , ctx.cm2_2ns[0 + i*6 + 2] ]);
  ctx.tmp[154] = ctx.F.mul(ctx.challenges[5], ctx.tmp[153]);
  ctx.tmp[155] = ctx.F.add(ctx.tmp[154], [ ctx.cm2_2ns[3 + i*6] , ctx.cm2_2ns[3 + i*6 + 1] , ctx.cm2_2ns[3 + i*6 + 2] ]);
  ctx.tmp[156] = ctx.F.mul(ctx.challenges[5], ctx.tmp[155]);
  ctx.tmp[157] = ctx.F.add(ctx.tmp[156], [ ctx.cm3_2ns[0 + i*9] , ctx.cm3_2ns[0 + i*9 + 1] , ctx.cm3_2ns[0 + i*9 + 2] ]);
  ctx.tmp[158] = ctx.F.mul(ctx.challenges[5], ctx.tmp[157]);
  ctx.tmp[159] = ctx.F.add(ctx.tmp[158], [ ctx.cm3_2ns[3 + i*9] , ctx.cm3_2ns[3 + i*9 + 1] , ctx.cm3_2ns[3 + i*9 + 2] ]);
  ctx.tmp[160] = ctx.F.mul(ctx.challenges[5], ctx.tmp[159]);
  ctx.tmp[161] = ctx.F.add(ctx.tmp[160], [ ctx.cm3_2ns[6 + i*9] , ctx.cm3_2ns[6 + i*9 + 1] , ctx.cm3_2ns[6 + i*9 + 2] ]);
  ctx.tmp[162] = ctx.F.mul(ctx.challenges[5], ctx.tmp[161]);
  ctx.tmp[163] = ctx.F.add(ctx.tmp[162], ctx.q_2ns[0 + i*35]);
  ctx.tmp[164] = ctx.F.mul(ctx.challenges[5], ctx.tmp[163]);
  ctx.tmp[165] = ctx.F.add(ctx.tmp[164], ctx.q_2ns[1 + i*35]);
  ctx.tmp[166] = ctx.F.mul(ctx.challenges[5], ctx.tmp[165]);
  ctx.tmp[167] = ctx.F.add(ctx.tmp[166], [ ctx.q_2ns[2 + i*35] , ctx.q_2ns[2 + i*35 + 1] , ctx.q_2ns[2 + i*35 + 2] ]);
  ctx.tmp[168] = ctx.F.mul(ctx.challenges[5], ctx.tmp[167]);
  ctx.tmp[169] = ctx.F.add(ctx.tmp[168], [ ctx.q_2ns[5 + i*35] , ctx.q_2ns[5 + i*35 + 1] , ctx.q_2ns[5 + i*35 + 2] ]);
  ctx.tmp[170] = ctx.F.mul(ctx.challenges[5], ctx.tmp[169]);
  ctx.tmp[171] = ctx.F.add(ctx.tmp[170], [ ctx.q_2ns[8 + i*35] , ctx.q_2ns[8 + i*35 + 1] , ctx.q_2ns[8 + i*35 + 2] ]);
  ctx.tmp[172] = ctx.F.mul(ctx.challenges[5], ctx.tmp[171]);
  ctx.tmp[173] = ctx.F.add(ctx.tmp[172], [ ctx.q_2ns[11 + i*35] , ctx.q_2ns[11 + i*35 + 1] , ctx.q_2ns[11 + i*35 + 2] ]);
  ctx.tmp[174] = ctx.F.mul(ctx.challenges[5], ctx.tmp[173]);
  ctx.tmp[175] = ctx.F.add(ctx.tmp[174], [ ctx.q_2ns[14 + i*35] , ctx.q_2ns[14 + i*35 + 1] , ctx.q_2ns[14 + i*35 + 2] ]);
  ctx.tmp[176] = ctx.F.mul(ctx.challenges[5], ctx.tmp[175]);
  ctx.tmp[177] = ctx.F.add(ctx.tmp[176], [ ctx.q_2ns[17 + i*35] , ctx.q_2ns[17 + i*35 + 1] , ctx.q_2ns[17 + i*35 + 2] ]);
  ctx.tmp[178] = ctx.F.mul(ctx.challenges[5], ctx.tmp[177]);
  ctx.tmp[179] = ctx.F.add(ctx.tmp[178], [ ctx.q_2ns[20 + i*35] , ctx.q_2ns[20 + i*35 + 1] , ctx.q_2ns[20 + i*35 + 2] ]);
  ctx.tmp[180] = ctx.F.mul(ctx.challenges[5], ctx.tmp[179]);
  ctx.tmp[181] = ctx.F.add(ctx.tmp[180], [ ctx.q_2ns[23 + i*35] , ctx.q_2ns[23 + i*35 + 1] , ctx.q_2ns[23 + i*35 + 2] ]);
  ctx.tmp[182] = ctx.F.mul(ctx.challenges[5], ctx.tmp[181]);
  ctx.tmp[183] = ctx.F.add(ctx.tmp[182], [ ctx.q_2ns[26 + i*35] , ctx.q_2ns[26 + i*35 + 1] , ctx.q_2ns[26 + i*35 + 2] ]);
  ctx.tmp[184] = ctx.F.mul(ctx.challenges[5], ctx.tmp[183]);
  ctx.tmp[185] = ctx.F.add(ctx.tmp[184], [ ctx.q_2ns[29 + i*35] , ctx.q_2ns[29 + i*35 + 1] , ctx.q_2ns[29 + i*35 + 2] ]);
  ctx.tmp[186] = ctx.F.mul(ctx.challenges[5], ctx.tmp[185]);
  ctx.tmp[187] = ctx.F.add(ctx.tmp[186], [ ctx.q_2ns[32 + i*35] , ctx.q_2ns[32 + i*35 + 1] , ctx.q_2ns[32 + i*35 + 2] ]);
  ctx.tmp[188] = ctx.F.mul(ctx.challenges[5], ctx.tmp[187]);
  ctx.tmp[189] = ctx.F.sub(ctx.cm1_2ns[0 + i*15], ctx.evals[1]);
  ctx.tmp[190] = ctx.F.mul(ctx.tmp[189], ctx.challenges[6]);
  ctx.tmp[191] = ctx.F.sub(ctx.const_2ns[2 + i*9], ctx.evals[2]);
  ctx.tmp[192] = ctx.F.add(ctx.tmp[190], ctx.tmp[191]);
  ctx.tmp[193] = ctx.F.mul(ctx.tmp[192], ctx.challenges[6]);
  ctx.tmp[194] = ctx.F.sub(ctx.cm1_2ns[1 + i*15], ctx.evals[3]);
  ctx.tmp[195] = ctx.F.add(ctx.tmp[193], ctx.tmp[194]);
  ctx.tmp[196] = ctx.F.mul(ctx.tmp[195], ctx.challenges[6]);
  ctx.tmp[197] = ctx.F.sub(ctx.q_2ns[0 + i*35], ctx.evals[4]);
  ctx.tmp[198] = ctx.F.add(ctx.tmp[196], ctx.tmp[197]);
  ctx.tmp[199] = ctx.F.mul(ctx.tmp[198], ctx.challenges[6]);
  ctx.tmp[200] = ctx.F.sub(ctx.const_2ns[1 + i*9], ctx.evals[6]);
  ctx.tmp[201] = ctx.F.add(ctx.tmp[199], ctx.tmp[200]);
  ctx.tmp[202] = ctx.F.mul(ctx.tmp[201], ctx.challenges[6]);
  ctx.tmp[203] = ctx.F.sub([ ctx.cm3_2ns[0 + i*9] , ctx.cm3_2ns[0 + i*9 + 1] , ctx.cm3_2ns[0 + i*9 + 2] ], ctx.evals[7]);
  ctx.tmp[204] = ctx.F.add(ctx.tmp[202], ctx.tmp[203]);
  ctx.tmp[205] = ctx.F.mul(ctx.tmp[204], ctx.challenges[6]);
  ctx.tmp[206] = ctx.F.sub(ctx.const_2ns[0 + i*9], ctx.evals[8]);
  ctx.tmp[207] = ctx.F.add(ctx.tmp[205], ctx.tmp[206]);
  ctx.tmp[208] = ctx.F.mul(ctx.tmp[207], ctx.challenges[6]);
  ctx.tmp[209] = ctx.F.sub([ ctx.cm2_2ns[3 + i*6] , ctx.cm2_2ns[3 + i*6 + 1] , ctx.cm2_2ns[3 + i*6 + 2] ], ctx.evals[9]);
  ctx.tmp[210] = ctx.F.add(ctx.tmp[208], ctx.tmp[209]);
  ctx.tmp[211] = ctx.F.mul(ctx.tmp[210], ctx.challenges[6]);
  ctx.tmp[212] = ctx.F.sub([ ctx.cm2_2ns[0 + i*6] , ctx.cm2_2ns[0 + i*6 + 1] , ctx.cm2_2ns[0 + i*6 + 2] ], ctx.evals[10]);
  ctx.tmp[213] = ctx.F.add(ctx.tmp[211], ctx.tmp[212]);
  ctx.tmp[214] = ctx.F.mul(ctx.tmp[213], ctx.challenges[6]);
  ctx.tmp[215] = ctx.F.sub([ ctx.q_2ns[17 + i*35] , ctx.q_2ns[17 + i*35 + 1] , ctx.q_2ns[17 + i*35 + 2] ], ctx.evals[12]);
  ctx.tmp[216] = ctx.F.add(ctx.tmp[214], ctx.tmp[215]);
  ctx.tmp[217] = ctx.F.mul(ctx.tmp[216], ctx.challenges[6]);
  ctx.tmp[218] = ctx.F.sub(ctx.cm1_2ns[12 + i*15], ctx.evals[13]);
  ctx.tmp[219] = ctx.F.add(ctx.tmp[217], ctx.tmp[218]);
  ctx.tmp[220] = ctx.F.mul(ctx.tmp[219], ctx.challenges[6]);
  ctx.tmp[221] = ctx.F.sub(ctx.q_2ns[1 + i*35], ctx.evals[15]);
  ctx.tmp[222] = ctx.F.add(ctx.tmp[220], ctx.tmp[221]);
  ctx.tmp[223] = ctx.F.mul(ctx.tmp[222], ctx.challenges[6]);
  ctx.tmp[224] = ctx.F.sub(ctx.const_2ns[7 + i*9], ctx.evals[16]);
  ctx.tmp[225] = ctx.F.add(ctx.tmp[223], ctx.tmp[224]);
  ctx.tmp[226] = ctx.F.mul(ctx.tmp[225], ctx.challenges[6]);
  ctx.tmp[227] = ctx.F.sub(ctx.const_2ns[8 + i*9], ctx.evals[17]);
  ctx.tmp[228] = ctx.F.add(ctx.tmp[226], ctx.tmp[227]);
  ctx.tmp[229] = ctx.F.mul(ctx.tmp[228], ctx.challenges[6]);
  ctx.tmp[230] = ctx.F.sub(ctx.cm1_2ns[14 + i*15], ctx.evals[18]);
  ctx.tmp[231] = ctx.F.add(ctx.tmp[229], ctx.tmp[230]);
  ctx.tmp[232] = ctx.F.mul(ctx.tmp[231], ctx.challenges[6]);
  ctx.tmp[233] = ctx.F.sub(ctx.const_2ns[6 + i*9], ctx.evals[19]);
  ctx.tmp[234] = ctx.F.add(ctx.tmp[232], ctx.tmp[233]);
  ctx.tmp[235] = ctx.F.mul(ctx.tmp[234], ctx.challenges[6]);
  ctx.tmp[236] = ctx.F.sub([ ctx.q_2ns[2 + i*35] , ctx.q_2ns[2 + i*35 + 1] , ctx.q_2ns[2 + i*35 + 2] ], ctx.evals[20]);
  ctx.tmp[237] = ctx.F.add(ctx.tmp[235], ctx.tmp[236]);
  ctx.tmp[238] = ctx.F.mul(ctx.tmp[237], ctx.challenges[6]);
  ctx.tmp[239] = ctx.F.sub(ctx.cm1_2ns[11 + i*15], ctx.evals[21]);
  ctx.tmp[240] = ctx.F.add(ctx.tmp[238], ctx.tmp[239]);
  ctx.tmp[241] = ctx.F.mul(ctx.tmp[240], ctx.challenges[6]);
  ctx.tmp[242] = ctx.F.sub([ ctx.q_2ns[5 + i*35] , ctx.q_2ns[5 + i*35 + 1] , ctx.q_2ns[5 + i*35 + 2] ], ctx.evals[22]);
  ctx.tmp[243] = ctx.F.add(ctx.tmp[241], ctx.tmp[242]);
  ctx.tmp[244] = ctx.F.mul(ctx.tmp[243], ctx.challenges[6]);
  ctx.tmp[245] = ctx.F.sub([ ctx.q_2ns[14 + i*35] , ctx.q_2ns[14 + i*35 + 1] , ctx.q_2ns[14 + i*35 + 2] ], ctx.evals[28]);
  ctx.tmp[246] = ctx.F.add(ctx.tmp[244], ctx.tmp[245]);
  ctx.tmp[247] = ctx.F.mul(ctx.tmp[246], ctx.challenges[6]);
  ctx.tmp[248] = ctx.F.sub([ ctx.cm3_2ns[3 + i*9] , ctx.cm3_2ns[3 + i*9 + 1] , ctx.cm3_2ns[3 + i*9 + 2] ], ctx.evals[30]);
  ctx.tmp[249] = ctx.F.add(ctx.tmp[247], ctx.tmp[248]);
  ctx.tmp[250] = ctx.F.mul(ctx.tmp[249], ctx.challenges[6]);
  ctx.tmp[251] = ctx.F.sub(ctx.cm1_2ns[8 + i*15], ctx.evals[31]);
  ctx.tmp[252] = ctx.F.add(ctx.tmp[250], ctx.tmp[251]);
  ctx.tmp[253] = ctx.F.mul(ctx.tmp[252], ctx.challenges[6]);
  ctx.tmp[254] = ctx.F.sub(ctx.cm1_2ns[10 + i*15], ctx.evals[32]);
  ctx.tmp[255] = ctx.F.add(ctx.tmp[253], ctx.tmp[254]);
  ctx.tmp[256] = ctx.F.mul(ctx.tmp[255], ctx.challenges[6]);
  ctx.tmp[257] = ctx.F.sub([ ctx.q_2ns[8 + i*35] , ctx.q_2ns[8 + i*35 + 1] , ctx.q_2ns[8 + i*35 + 2] ], ctx.evals[33]);
  ctx.tmp[258] = ctx.F.add(ctx.tmp[256], ctx.tmp[257]);
  ctx.tmp[259] = ctx.F.mul(ctx.tmp[258], ctx.challenges[6]);
  ctx.tmp[260] = ctx.F.sub(ctx.cm1_2ns[7 + i*15], ctx.evals[34]);
  ctx.tmp[261] = ctx.F.add(ctx.tmp[259], ctx.tmp[260]);
  ctx.tmp[262] = ctx.F.mul(ctx.tmp[261], ctx.challenges[6]);
  ctx.tmp[263] = ctx.F.sub(ctx.cm1_2ns[9 + i*15], ctx.evals[35]);
  ctx.tmp[264] = ctx.F.add(ctx.tmp[262], ctx.tmp[263]);
  ctx.tmp[265] = ctx.F.mul(ctx.tmp[264], ctx.challenges[6]);
  ctx.tmp[266] = ctx.F.sub([ ctx.q_2ns[11 + i*35] , ctx.q_2ns[11 + i*35 + 1] , ctx.q_2ns[11 + i*35 + 2] ], ctx.evals[36]);
  ctx.tmp[267] = ctx.F.add(ctx.tmp[265], ctx.tmp[266]);
  ctx.tmp[268] = ctx.F.mul(ctx.tmp[267], ctx.challenges[6]);
  ctx.tmp[269] = ctx.F.sub([ ctx.cm3_2ns[6 + i*9] , ctx.cm3_2ns[6 + i*9 + 1] , ctx.cm3_2ns[6 + i*9 + 2] ], ctx.evals[38]);
  ctx.tmp[270] = ctx.F.add(ctx.tmp[268], ctx.tmp[269]);
  ctx.tmp[271] = ctx.F.mul(ctx.tmp[270], ctx.challenges[6]);
  ctx.tmp[272] = ctx.F.sub(ctx.cm1_2ns[2 + i*15], ctx.evals[39]);
  ctx.tmp[273] = ctx.F.add(ctx.tmp[271], ctx.tmp[272]);
  ctx.tmp[274] = ctx.F.mul(ctx.tmp[273], ctx.challenges[6]);
  ctx.tmp[275] = ctx.F.sub(ctx.const_2ns[3 + i*9], ctx.evals[40]);
  ctx.tmp[276] = ctx.F.add(ctx.tmp[274], ctx.tmp[275]);
  ctx.tmp[277] = ctx.F.mul(ctx.tmp[276], ctx.challenges[6]);
  ctx.tmp[278] = ctx.F.sub(ctx.cm1_2ns[3 + i*15], ctx.evals[41]);
  ctx.tmp[279] = ctx.F.add(ctx.tmp[277], ctx.tmp[278]);
  ctx.tmp[280] = ctx.F.mul(ctx.tmp[279], ctx.challenges[6]);
  ctx.tmp[281] = ctx.F.sub(ctx.const_2ns[4 + i*9], ctx.evals[42]);
  ctx.tmp[282] = ctx.F.add(ctx.tmp[280], ctx.tmp[281]);
  ctx.tmp[283] = ctx.F.mul(ctx.tmp[282], ctx.challenges[6]);
  ctx.tmp[284] = ctx.F.sub([ ctx.q_2ns[23 + i*35] , ctx.q_2ns[23 + i*35 + 1] , ctx.q_2ns[23 + i*35 + 2] ], ctx.evals[43]);
  ctx.tmp[285] = ctx.F.add(ctx.tmp[283], ctx.tmp[284]);
  ctx.tmp[286] = ctx.F.mul(ctx.tmp[285], ctx.challenges[6]);
  ctx.tmp[287] = ctx.F.sub(ctx.cm1_2ns[4 + i*15], ctx.evals[44]);
  ctx.tmp[288] = ctx.F.add(ctx.tmp[286], ctx.tmp[287]);
  ctx.tmp[289] = ctx.F.mul(ctx.tmp[288], ctx.challenges[6]);
  ctx.tmp[290] = ctx.F.sub(ctx.const_2ns[5 + i*9], ctx.evals[45]);
  ctx.tmp[291] = ctx.F.add(ctx.tmp[289], ctx.tmp[290]);
  ctx.tmp[292] = ctx.F.mul(ctx.tmp[291], ctx.challenges[6]);
  ctx.tmp[293] = ctx.F.sub([ ctx.q_2ns[29 + i*35] , ctx.q_2ns[29 + i*35 + 1] , ctx.q_2ns[29 + i*35 + 2] ], ctx.evals[46]);
  ctx.tmp[294] = ctx.F.add(ctx.tmp[292], ctx.tmp[293]);
  ctx.tmp[295] = ctx.F.mul(ctx.tmp[294], ctx.challenges[6]);
  ctx.tmp[296] = ctx.F.sub([ ctx.q_2ns[20 + i*35] , ctx.q_2ns[20 + i*35 + 1] , ctx.q_2ns[20 + i*35 + 2] ], ctx.evals[47]);
  ctx.tmp[297] = ctx.F.add(ctx.tmp[295], ctx.tmp[296]);
  ctx.tmp[298] = ctx.F.mul(ctx.tmp[297], ctx.challenges[6]);
  ctx.tmp[299] = ctx.F.sub([ ctx.q_2ns[26 + i*35] , ctx.q_2ns[26 + i*35 + 1] , ctx.q_2ns[26 + i*35 + 2] ], ctx.evals[48]);
  ctx.tmp[300] = ctx.F.add(ctx.tmp[298], ctx.tmp[299]);
  ctx.tmp[301] = ctx.F.mul(ctx.tmp[300], ctx.challenges[6]);
  ctx.tmp[302] = ctx.F.sub([ ctx.q_2ns[32 + i*35] , ctx.q_2ns[32 + i*35 + 1] , ctx.q_2ns[32 + i*35 + 2] ], ctx.evals[50]);
  ctx.tmp[303] = ctx.F.add(ctx.tmp[301], ctx.tmp[302]);
  ctx.tmp[304] = ctx.F.mul(ctx.tmp[303], [ctx.xDivXSubXi[3*i], ctx.xDivXSubXi[3*i+1], ctx.xDivXSubXi[3*i+2]]);
  ctx.tmp[305] = ctx.F.add(ctx.tmp[188], ctx.tmp[304]);
  ctx.tmp[306] = ctx.F.mul(ctx.challenges[5], ctx.tmp[305]);
  ctx.tmp[307] = ctx.F.sub(ctx.cm1_2ns[1 + i*15], ctx.evals[0]);
  ctx.tmp[308] = ctx.F.mul(ctx.tmp[307], ctx.challenges[6]);
  ctx.tmp[309] = ctx.F.sub(ctx.cm1_2ns[0 + i*15], ctx.evals[5]);
  ctx.tmp[310] = ctx.F.add(ctx.tmp[308], ctx.tmp[309]);
  ctx.tmp[311] = ctx.F.mul(ctx.tmp[310], ctx.challenges[6]);
  ctx.tmp[312] = ctx.F.sub([ ctx.cm2_2ns[0 + i*6] , ctx.cm2_2ns[0 + i*6 + 1] , ctx.cm2_2ns[0 + i*6 + 2] ], ctx.evals[11]);
  ctx.tmp[313] = ctx.F.add(ctx.tmp[311], ctx.tmp[312]);
  ctx.tmp[314] = ctx.F.mul(ctx.tmp[313], ctx.challenges[6]);
  ctx.tmp[315] = ctx.F.sub(ctx.cm1_2ns[13 + i*15], ctx.evals[14]);
  ctx.tmp[316] = ctx.F.add(ctx.tmp[314], ctx.tmp[315]);
  ctx.tmp[317] = ctx.F.mul(ctx.tmp[316], ctx.challenges[6]);
  ctx.tmp[318] = ctx.F.sub(ctx.const_2ns[7 + i*9], ctx.evals[23]);
  ctx.tmp[319] = ctx.F.add(ctx.tmp[317], ctx.tmp[318]);
  ctx.tmp[320] = ctx.F.mul(ctx.tmp[319], ctx.challenges[6]);
  ctx.tmp[321] = ctx.F.sub(ctx.const_2ns[8 + i*9], ctx.evals[24]);
  ctx.tmp[322] = ctx.F.add(ctx.tmp[320], ctx.tmp[321]);
  ctx.tmp[323] = ctx.F.mul(ctx.tmp[322], ctx.challenges[6]);
  ctx.tmp[324] = ctx.F.sub(ctx.cm1_2ns[14 + i*15], ctx.evals[25]);
  ctx.tmp[325] = ctx.F.add(ctx.tmp[323], ctx.tmp[324]);
  ctx.tmp[326] = ctx.F.mul(ctx.tmp[325], ctx.challenges[6]);
  ctx.tmp[327] = ctx.F.sub(ctx.const_2ns[6 + i*9], ctx.evals[26]);
  ctx.tmp[328] = ctx.F.add(ctx.tmp[326], ctx.tmp[327]);
  ctx.tmp[329] = ctx.F.mul(ctx.tmp[328], ctx.challenges[6]);
  ctx.tmp[330] = ctx.F.sub([ ctx.q_2ns[2 + i*35] , ctx.q_2ns[2 + i*35 + 1] , ctx.q_2ns[2 + i*35 + 2] ], ctx.evals[27]);
  ctx.tmp[331] = ctx.F.add(ctx.tmp[329], ctx.tmp[330]);
  ctx.tmp[332] = ctx.F.mul(ctx.tmp[331], ctx.challenges[6]);
  ctx.tmp[333] = ctx.F.sub([ ctx.cm3_2ns[0 + i*9] , ctx.cm3_2ns[0 + i*9 + 1] , ctx.cm3_2ns[0 + i*9 + 2] ], ctx.evals[29]);
  ctx.tmp[334] = ctx.F.add(ctx.tmp[332], ctx.tmp[333]);
  ctx.tmp[335] = ctx.F.mul(ctx.tmp[334], ctx.challenges[6]);
  ctx.tmp[336] = ctx.F.sub([ ctx.cm3_2ns[3 + i*9] , ctx.cm3_2ns[3 + i*9 + 1] , ctx.cm3_2ns[3 + i*9 + 2] ], ctx.evals[37]);
  ctx.tmp[337] = ctx.F.add(ctx.tmp[335], ctx.tmp[336]);
  ctx.tmp[338] = ctx.F.mul(ctx.tmp[337], ctx.challenges[6]);
  ctx.tmp[339] = ctx.F.sub([ ctx.cm3_2ns[6 + i*9] , ctx.cm3_2ns[6 + i*9 + 1] , ctx.cm3_2ns[6 + i*9 + 2] ], ctx.evals[49]);
  ctx.tmp[340] = ctx.F.add(ctx.tmp[338], ctx.tmp[339]);
  ctx.tmp[341] = ctx.F.mul(ctx.tmp[340], [ctx.xDivXSubWXi[3*i], ctx.xDivXSubWXi[3*i+1], ctx.xDivXSubWXi[3*i+2]]);
  [ ctx.exps_withoutq_2ns[0 + i*3] , ctx.exps_withoutq_2ns[0 + i*3 + 1] , ctx.exps_withoutq_2ns[0 + i*3 + 2] ] = ctx.F.add(ctx.tmp[306], ctx.tmp[341]);  // 对应着 fri 表达式计算
})

由此得到fri 表达式的列：

const friPol = getPol(ctx, starkInfo, starkInfo.exps_2ns[starkInfo.friExpId]);

friPol 为长度为2048的数组，每个元素为width 为 3。

Calculate FRI proof

根据 fri中steps 进行多轮FRI 处理。

  "steps": [
   {
    "nBits": 11
   },
   {
    "nBits": 3
   }
  ]

对于第0轮，直接取fri 表达式的值。

if (si == 0) {
  pol2_e[g] = pol[g];
}

然后，根据下一轮组的元素个数（本例为8）和分组个数（本例为256），构建Merkle 树，width 为 768， height 为 8. 最后将merkle 树的根保存在 proof 中。

           if (si < this.steps.length - 1) {
                const nGroups = 1 << this.steps[si + 1].nBits;

                let groupSize = (1 << this.steps[si].nBits) / nGroups;

                // 每间隔8个取一个，重排
                const pol2_etb = getTransposedBuffer(pol2_e, this.steps[si + 1].nBits);

                tree[si] = await this.MH.merkelize(pol2_etb, 3 * groupSize, nGroups);

                proof[si + 1].root = this.MH.root(tree[si]);
                transcript.put(this.MH.root(tree[si]));
          }

对于第1轮，计算如下参数：

            const reductionBits = polBits - this.steps[si].nBits;   // 计算约减位数，本例为 11 -3 = 8

            const pol2N = 1 << (polBits - reductionBits);   // 计数pol2 的大小，本例为 2^3 = 8
            const nX = pol.length / pol2N;    // 计算分组个数，本例为256

            const pol2_e = new Array(pol2N);   // 用于保存pol2 的值。

            let special_x = transcript.getField();

下面展示pol2_e 的计算过程：

            let sinv = shiftInv;
            const wi = F.inv(F.w[polBits]);
            for (let g = 0; g < pol.length / nX; g++) {
                if (si == 0) {     // 可忽略  
                    pol2_e[g] = pol[g];  // 
                } else {
                    const ppar = new Array(nX);
                    for (let i = 0; i < nX; i++) {
                        ppar[i] = pol[(i * pol2N) + g];
                    }
                    const ppar_c = F.ifft(ppar);
                    polMulAxi(F, ppar_c, F.one, sinv);    // Multiplies coefs by 1, shiftInv, shiftInv^2, shiftInv^3, ......

                    pol2_e[g] = evalPol(F, ppar_c, special_x);
                    sinv = F.mul(sinv, wi);
                }
            }

对于pol中的元素，每隔 pol2N (本例为8) 取一个，得到ppar, 再进行IFFT 变换，得到 ppar_c，然后调整系数，再计算在special_x 点处的值。依次类推，得到pol2_e.

这部分实现原理参考：https://vitalik.ca/general/2017/11/22/starks_part_2.html

因为本例只有两轮，最后将pol2_e 保存到proof 中。

        const lastPol = [];
        for (let i = 0; i < pol.length; i++) {
            lastPol.push(pol[i]);
        }
        proof.push(lastPol);

最后对所有生成的tree 的叶子节点进行抽样：

        const ys = transcript.getPermutations(this.nQueries, this.steps[0].nBits);

        for (let si = 0; si < this.steps.length; si++) {

            proof[si].polQueries = [];
            for (let i = 0; i < ys.length; i++) {
                const gIdx =
                    proof[si].polQueries.push(queryPol(ys[i]));
            }


            if (si < this.steps.length - 1) {
                queryPol = (idx) => {
                    return self.MH.getGroupProof(tree[si], idx);
                }

                for (let i = 0; i < ys.length; i++) {
                    ys[i] = ys[i] % (1 << this.steps[si + 1].nBits);
                }
            }
        }

其中ys 为选取叶子节点的的索引值。

第一轮从tree1, tree2, tree3, tree4, constTree，根据 ys 选取对应叶子节点，对应的Merkle 路径；

后面，依次从生成的FRI 子树，根据ys 选取对应叶子节点，以及对应的Merkle 路径。

最终生成的证明即为：

        proof: {
            root1: MH.root(tree1),  // tree1 的根
            root2: MH.root(tree2),   
            root3: MH.root(tree3),
            root4: MH.root(tree4),
            evals: ctx.evals, // evMap 中多项式在xi或wxi的值
            fri: friProof  //  包含FRI 各轮的子树根，以及随机抽样的叶子节点和对应的Merkle路径
        },
        publics: ctx.publics  // 公开输入值
    }

STARK verify

首先计算用到的挑战的值：

    ctx = {
        challenges: [],
        evals: proof.evals,
        publics: publics
    };
    transcript.put(proof.root1);
    ctx.challenges[0] = transcript.getField(); // u
    ctx.challenges[1] = transcript.getField(); // defVal
    transcript.put(proof.root2);
    ctx.challenges[2] = transcript.getField(); // gamma
    ctx.challenges[3] = transcript.getField(); // beta

    transcript.put(proof.root3);
    ctx.challenges[4] = transcript.getField(); // vc

    transcript.put(proof.root4);
    ctx.challenges[5] = transcript.getField(); // v1
    ctx.challenges[6] = transcript.getField(); // v2
    ctx.challenges[7] = transcript.getField(); // xi

    ctx.Z = F.sub(F.exp(ctx.challenges[7], N), 1n);
    ctx.Zp = F.sub(F.exp(F.mul(ctx.challenges[7], F.w[nBits]), N), 1n);

其中：
$Z = xi^N-1 \\ Z_p = (w\cdot xi)^N-1$
然后根据 evals 点的值，对组合多项式（verifierCode）进行计算，判断结果是否为0。

 const res=executeCode(F, ctx, starkInfo.verifierCode.first);

此步验证所有约束条件满足。

FRI 验证

首先计算 special_x 数组的值，如下所示：

        let special_x = [];

        for (let si = 0; si < this.steps.length; si++) {
            special_x[si] = transcript.getField();

            if (si < this.steps.length - 1) {
                const nGroups = 1 << this.steps[si + 1].nBits;

                let groupSize = (1 << this.steps[si].nBits) / nGroups;
                transcript.put(proof[si + 1].root);
            } else {
                for (let i = 0; i < proof[proof.length - 1].length; i++) {
                    transcript.put(proof[proof.length - 1][i]);
                }
            }
        }

第一轮的时候，对查询点进行Merkle 路径验证，以及FRI多项式约束关系，汲及 $shift \cdot w_e^i$ 和 $xi$ (或 $w\cdot xi$ ) 处估值；

第二轮对FRI 树查询点，及约束关系进行验证。

        const nQueries = this.nQueries;
        const ys = transcript.getPermutations(this.nQueries, this.steps[0].nBits);

        let polBits = this.inNBits;
        let shift = F.shift;
        for (let si = 0; si < this.steps.length; si++) {

            const proofItem = proof[si];

            const reductionBits = polBits - this.steps[si].nBits;

            for (let i = 0; i < nQueries; i++) {
                const pgroup_e = checkQuery(proofItem.polQueries[i], ys[i]);
                if (!pgroup_e) return false;

                const pgroup_c = F.ifft(pgroup_e);
                const sinv = F.inv(F.mul(shift, F.exp(F.w[polBits], ys[i])));
                //                polMulAxi(F, pgroup_c, F.one, sinv);    // Multiplies coefs by 1, shiftInv, shiftInv^2, shiftInv^3, ......
                //                const ev = evalPol(F, pgroup_c, special_x[si]);
                const ev = evalPol(F, pgroup_c, F.mul(special_x[si], sinv));

                if (si < this.steps.length - 1) {
                    const nextNGroups = 1 << this.steps[si + 1].nBits
                    const groupIdx = Math.floor(ys[i] / nextNGroups);
                    if (!F.eq(get3(proof[si + 1].polQueries[i][0], groupIdx), ev)) return false;
                } else {
                    if (!F.eq(proof[si + 1][ys[i]], ev)) return false;
                }
            }

            checkQuery = (query, idx) => {
                const res = self.MH.verifyGroupProof(proof[si + 1].root, query[1], idx, query[0]);
                if (!res) return false;
                return split3(query[0]);
            }

            polBits = this.steps[si].nBits;
            for (let j = 0; j < reductionBits; j++) shift = F.mul(shift, shift);

            if (si < this.steps.length - 1) {
                for (let i = 0; i < ys.length; i++) {
                    ys[i] = ys[i] % (1 << this.steps[si + 1].nBits);
                }
            }

        }

对最后一轮，进行低度测试：

        const lastPol_e = proof[proof.length - 1];

        let maxDeg;
        if ((polBits - (this.inNBits - this.maxDegNBits)) < 0) {
            maxDeg = 0;
        } else {
            maxDeg = 1 << (polBits - (this.inNBits - this.maxDegNBits));
        }

        const lastPol_c = F.ifft(lastPol_e);
        // We don't need to divide by shift as we just need to check for zeros

        for (let i = maxDeg + 1; i < lastPol_c.length; i++) {
            if (!F.isZero(lastPol_c[i])) return false;
        }

参考

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

https://www.youtube.com/watch?v=0IZ8-tYaNJM

https://www.youtube.com/watch?v=T2fH1NlHnAc

https://www.youtube.com/watch?v=-9TJa1hVsKA

https://blog.csdn.net/mutourend/article/details/126407028?spm=1001.2014.3001.5501

https://eprint.iacr.org/2019/953.pdf

最后编辑于：2023.09.21 17:04:18

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 214,837评论 6赞 496
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 91,551评论 3赞 389
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 160,417评论 0赞 350
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 57,448评论 1赞 288
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 66,524评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 50,554评论 1赞 293
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,569评论 3赞 414
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,316评论 0赞 270
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,766评论 1赞 307
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,077评论 2赞 330
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,240评论 1赞 343
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,912评论 5赞 338
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,560评论 3赞 322
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,176评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,425评论 1赞 268
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,114评论 2赞 366
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,114评论 2赞 352