本文主要對(duì)zkEVM STARK 證明過(guò)程進(jìn)行介紹，它是實(shí)現(xiàn)zkEVM 的關(guān)鍵組件瞬矩。
基礎(chǔ)知識(shí)
Permutation
Plookup
參考：https://eprint.iacr.org/2020/315.pdf
Connection check
image.png
注： 上圖有誤锡凝，S3第一行應(yīng)為, S1第四行應(yīng)用為：
.
connection check 計(jì)算實(shí)現(xiàn)可以參考Plonk 論文中的公式：
參考：https://eprint.iacr.org/2019/953.pdf
Goldiocks 域
Goldilocks 域?yàn)?祥款， 目前應(yīng)用在Polygon Miden, Plonky2, zkEVM 等多個(gè)項(xiàng)目中仑撞，
其中 的階為
, 即
, 即具有
次單元根聋袋，
的生成元為：
次根的單位元為：
= 1753635133440165772
Goldilocks 域能夠更好適配64位整數(shù)運(yùn)算。
Poseidon
Poseidon 是一種 zero-knowledge 友好的Hash函數(shù)腔稀，大概過(guò)程如下：
# 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 主要實(shí)現(xiàn)承諾多項(xiàng)式低度測(cè)試盆昙，參考 ：Vitalik blog 和 fri 介紹 羽历。
STARK 證明
本文以stark_all 為例，分析整個(gè)STARK 實(shí)現(xiàn)過(guò)程淡喜。
預(yù)處理
starkStruct
通過(guò)starkStruct 描述STARK 證明的一些參數(shù)信息：
const starkStruct = {
nBits: 10, // 基域位數(shù)秕磷，
nBitsExt: 11, // 擴(kuò)域域位數(shù)
nQueries: 8, // 查詢的個(gè)數(shù)
verificationHashType: "GL", // Hash函數(shù)使用Goldilocks 域數(shù)
steps: [
{ nBits: 11 }, // fri 第一輪域位數(shù)
{ nBits: 3 } // fri 第二輪域位數(shù)
]
};
上述主要定義基域?yàn)? , 擴(kuò)域?yàn)椋?
.
Goldilocks 三次擴(kuò)域構(gòu)建
定義三次擴(kuò)域的相關(guān)參數(shù)：
module.exports = class F3G {
constructor() {
this.p = 0xFFFFFFFF00000001n // 基礎(chǔ) 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; //代表三次擴(kuò)域
this.bitLength = 0;
for (let a =this.p; a>0n; a = a >> 1n) this.bitLength += 1; // 計(jì)算位數(shù)
buildSqrt(this); // 構(gòu)建平方根函數(shù)
buildFFT(this); // 生成 FFT 變換的參數(shù)
}
其中 buildFFT 主要是構(gòu)建各個(gè)子群的生成元，及其逆元素炼团。
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; // 長(zhǎng)度為33的數(shù)組澎嚣，每個(gè)元素對(duì)應(yīng)著相應(yīng)子群的生成元，例如w[32] 為2^32 子群的生成元瘟芝， 以此類推：
F.wi = fft.wi; // 長(zhǎng)度為33的數(shù)組易桃，每個(gè)元素對(duì)應(yīng)著相應(yīng)子群生成元的逆.
}
編譯PIL
PIL 定義了STARK 實(shí)現(xiàn)的約束描述，采用PIL編譯器可以將其轉(zhuǎn)換為json 描述锌俱，以stark_all 為例晤郑， 其PIL 定義為：
constant %N = 2**10;
namespace Global(%N);
pol constant L1; // 常量多項(xiàng)式
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; // 常量多項(xiàng)式
pol commit l1,l2; // 承諾多項(xiàng)式
pol l2c = l2; // l2c 為隱含多項(xiàng)式
public in1 = l2c(0); // 公開(kāi)輸入
public in2 = l1(0);
public out = l1(%N-1);
(l2' - l1)*(1-LLAST) = 0; // 多項(xiàng)式恒等約束
pol next = l1*l1 + l2*l2; // next 為隱含多項(xiàng)式
(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}; // 查找表約束
生成的對(duì)應(yīng)的json 為：
{
"nCommitments": 15, // 多項(xiàng)式承諾的總數(shù)
"nQ": 2, // Q多項(xiàng)式 總數(shù)
"nIm": 2, // 隱含變量個(gè)數(shù)
"nConstants": 9, // 常量多項(xiàng)式個(gè)數(shù)
"publics": [ // 表示 公開(kāi)輸入數(shù)組
{
"polType": "imP", // 引用多項(xiàng)式類型
"polId": 0, // 多項(xiàng)式 id 編號(hào)
"idx": 0, // index 索引， 可以當(dāng)用行號(hào)
"id": 0, // 公開(kāi)輸入的id
"name": "in1" // 公開(kāi)輸入的標(biāo)識(shí)符
},
....
],
"references": { // PIL 中的一些變量引用
"Global.L1": {
"type": "constP", // 類型
"id": 0, //在類型所在的編號(hào)
"polDeg": 1024, // 多項(xiàng)式次數(shù)
"isArray": false // 是否為數(shù)組
} ,
...
},
"expressions": [ // 定義了一些表達(dá)式
{ // 對(duì)應(yīng)著表達(dá)式 pol l2c = l2; 中的 l2
"op": "cm",
"deg": 1,
"id": 1,
"next": false
},
{ // 對(duì)應(yīng)著表達(dá)式： (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": [ // 對(duì)應(yīng)著恒等表達(dá)式
{
"e": 1, // 表未表達(dá)式(expressions)的編號(hào)
"fileName": "/Users/tron/test/polygon_zkevm/pil-stark/test/sm_fibonacci/fibonacci.pil",
"line": 13
},
...
],
"plookupIdentities": [ // 查詢表約束恒等關(guān)系
{
"f": [
19, // 表示表達(dá)式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": [ // 置換多項(xiàng)式恒等關(guān)系
{
"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": [ // 連接約束恒等關(guān)系
{
"pols": [
7, // 表示表達(dá)式(expressions)的編號(hào)
8,
9
],
"connections": [
10,
11,
12
],
"fileName": "/Users/tron/test/polygon_zkevm/pil-stark/test/sm_connection/connection.pil",
"line": 7
}
]
}
常量多項(xiàng)式賦值
主要對(duì)常量列進(jìn)行賦值嚼鹉，如
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 為例，主要對(duì)其中的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;
}
}
對(duì)Global, Plookup, Permutation, Connection 部分的常量多項(xiàng)式處理類似锚赤。
承諾多項(xiàng)式賦值
主要對(duì)承諾多項(xiàng)式進(jìn)行賦值，如下所示：
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 為例褐鸥，主要對(duì) l1 和 l2 分別賦值线脚，其中公開(kāi)輸入為[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];
}
對(duì) Plookup, Permutation, Connection 部分的常量多項(xiàng)式處理類似叫榕。
STARK setup
constTree 構(gòu)建
首先對(duì)常量多項(xiàng)式分別進(jìn)行FFT 變換浑侥，得到其在擴(kuò)展域上值；
然后構(gòu)建基于Goldilocks 域的Merkle Hash;
最后對(duì)擴(kuò)展域上的值構(gòu)建Merkle 樹(shù)晰绎，構(gòu)建時(shí)候?qū)⒍鄠€(gè)列合并寓落，生成一個(gè)Merkle樹(shù)，每個(gè)節(jié)點(diǎn)有4個(gè)域元素荞下。
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 的結(jié)構(gòu)為：
const tree = {
elements: buff, //保存所有葉子節(jié)點(diǎn)值伶选，包含所有常量列在擴(kuò)域上的值；
nodes: new BigUint64Array(this._getNNodes(height * 4)), // 所有中間節(jié)點(diǎn)的值尖昏，每個(gè)節(jié)點(diǎn)占用4個(gè)域元素, 最后四個(gè)元素為Merkle 樹(shù)根
width: width, // 常量多項(xiàng)式列的個(gè)數(shù)
height: height //最底層葉子點(diǎn)節(jié)個(gè)數(shù)
};
下面的過(guò)程主要用于構(gòu)建 starkInfo , 它包含了用于生成 stark 證明的所需要的各種信息仰税。
const res = {
varPolMap: [], //變量到多項(xiàng)式的映射
puCtx: [], // plookup
peCtx: [], // permutation
ciCtx: [] // connection
};
res.starkStruct = starkStruct; // stark 結(jié)構(gòu)體
res.nConstants = pil.nConstants; // 常量多項(xiàng)式個(gè)數(shù)
res.nPublics = pil.publics.length; // 公開(kāi)輸入個(gè)數(shù)
generatePublicCalculators
本步主要用于計(jì)算公開(kāi)輸入值。
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
}
}
}
首先對(duì)于imP 類型的公開(kāi)輸入抽诉，例如陨簇，如下所示：
{
"polType": "imP",
"polId": 0, // 其實(shí)表示 expression id
"idx": 0, // 對(duì)應(yīng)著索引值，可以當(dāng)用行號(hào)
"id": 0, // 公開(kāi)輸入的id
"name": "in1" // 公開(kāi)輸入的變量名
},
然后對(duì)pilCodeGen 將需要計(jì)算的表達(dá)式展開(kāi)成為基本的code (為二元運(yùn)算或基本運(yùn)算)迹淌，若表達(dá)式依賴其它表達(dá)式河绽，通過(guò)遞歸方式完全展開(kāi)己单。例如本例中生成的code 為：
{
"op": "copy", // 表示復(fù)制運(yùn)算
"dest": { // 復(fù)制的目標(biāo)
"type": "tmp",
"id": 0,
"dim": 1
},
"src": [ // 來(lái)源
{
"type": "cm", // 承諾多項(xiàng)式
"id": 1, // 承諾多項(xiàng)式 id
"prime": false,
"p": 2,
"dim": 1
}
]
}
再調(diào)用buildCode 將所有表達(dá)式的code 展開(kāi)，放到一個(gè)組數(shù)中葵姥，放到starkInfo的 publicsCode 組數(shù)中荷鼠。
對(duì)于每個(gè)公開(kāi)輸入，分別生成 first, i, last 三組code榔幸， 對(duì)應(yīng)不同的位置允乐，但目前只用了frist； i 和 last 沒(méi)有用削咆。
最后生成的publicsCode 會(huì)生成證明的時(shí)候用于計(jì)算公開(kāi)輸入的值牍疏。
res.nCm1 = pil.nCommitments; // 表示第一步中的承諾多項(xiàng)式個(gè)數(shù)
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; // 計(jì)算 t 表達(dá)式
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 表達(dá)式 id
tExp.keep = true;
pil.expressions.push(tExp);
fExp = null; // 計(jì)算 f 表達(dá)式
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 表達(dá)式id
fExp.keep = true;
pil.expressions.push(fExp);
pilCodeGen(ctx, puCtx.fExpId, false);
pilCodeGen(ctx, puCtx.tExpId, false);
puCtx.h1Id = pil.nCommitments++; // h1承諾多項(xiàng)式id
puCtx.h2Id = pil.nCommitments++; // h2 承諾多項(xiàng)式id
res.puCtx.push(puCtx);
}
res.step2prev = buildCode(ctx);
}
首先定義一個(gè)表達(dá)式類，表達(dá)式所包含的所有運(yùn)算主要有：add, sub, mul, const, q, challenge, number, eval, tmp, xDivXSubXi, xDivXSubWXi , x .
然后對(duì)PIL 中的每個(gè) plookup 運(yùn)算拨齐，循環(huán)進(jìn)行處理鳞陨，例如，如下所示：
"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
}
]
然后計(jì)算 t 表達(dá)式
若存在選擇子setT瞻惋， 則：
puCtx.tExpId 為 t 表達(dá)式id厦滤， 放入表達(dá)式列表中。
再計(jì)算f 表達(dá)式歼狼，和上面類似：
若存在選擇子setF掏导， 則：
puCtx.fExpId 為 f 表達(dá)式id， 放入表達(dá)式列表中羽峰。
然后分別對(duì)f 和 t 表達(dá)式調(diào)用pilCodeGen趟咆， 生成表達(dá)式計(jì)算的Code；
最后生成h1 和 h2 承諾多項(xiàng)式 id梅屉。
生成的 puCtx 的結(jié)構(gòu)為：
{
"tExpId": 27, // t 表達(dá)式 id
"fExpId": 28, // f 表達(dá)式 id
"h1Id": 15, // h1 承諾多項(xiàng)式id
"h2Id": 16, // h2 承諾多項(xiàng)式id
"zId": 17, // 下面幾個(gè)后續(xù)待計(jì)算
"c1Id": 31,
"numId": 32,
"denId": 33,
"c2Id": 34
}
當(dāng)所有的plookup 處理完后值纱，通過(guò)buildCode 將生成的所有code 放入 step2prev 中。
res.nCm2 為第2步承諾多項(xiàng)式的個(gè)數(shù)坯汤，賦值為：
res.nCm2 = pil.nCommitments - res.nCm1;
generateStep3
步驟3又分為三步虐唠，分別為：
generatePermutationLC
該步驟與步驟2類似，生成置換對(duì)應(yīng)的t 表達(dá)式和 f表達(dá)式惰聂，例如置換：
"permutationIdentities": [
{
"f": [ // f 表達(dá)式
13,
14
],
"t": [ // t 表達(dá)式
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
}
]
生成的對(duì)應(yīng)的peCtx 為：
"peCtx": [
{
"tExpId": 29, // t 表達(dá)式 id
"fExpId": 30, // f 表達(dá)式 id
"zId": 18, // 后面幾個(gè)后續(xù)待計(jì)算
"c1Id": 35,
"numId": 36,
"denId": 37,
"c2Id": 38
}
]
generatePlookupZ
本步驟主要生成plookup 的Z 多項(xiàng)式凿滤， 對(duì)于每個(gè) plookup 分別執(zhí)行以下步驟：
const puCtx = res.puCtx[i]; // 取出單個(gè)plookup
puCtx.zId = pil.nCommitments++; // z 承諾多項(xiàng)式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 多項(xiàng)式
const t = E.exp(puCtx.tExpId); // t 多項(xiàng)式
const tp = E.exp(puCtx.tExpId, true); // t'
const z = E.cm(puCtx.zId); // z 承諾
const zp = E.cm(puCtx.zId, true); // z'
計(jì)算c1 表達(dá)式：
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}); // 加入恒等多項(xiàng)式中
計(jì)算分子 numExp 表達(dá)式：
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);
計(jì)算分母denExp表達(dá)式：
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);
然后構(gòu)建 c2 約束表達(dá)式：
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}); // 加入恒等多項(xiàng)式中
最后分別構(gòu)建 num 和 den 表達(dá)式的code.
pilCodeGen(ctx, puCtx.numId, false);
pilCodeGen(ctx, puCtx.denId, false);
generatePermutationZ
此步驟主要生成置換的 Z 多項(xiàng)式。
首先取出每個(gè)置換個(gè)運(yùn)算：
peCtx = res.peCtx[i]; // 取出置換
peCtx.zId = pil.nCommitments++; // z 承諾多項(xiàng)式 id
const f = E.exp(peCtx.fExpId); // f 表達(dá)式
const t = E.exp(peCtx.tExpId); // t 表達(dá)式
const z = E.cm(peCtx.zId); // z 表達(dá)式
const zp = E.cm(peCtx.zId, true); //z' 表達(dá)式
然后計(jì)算c1 表達(dá)式：
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});
計(jì)算分子numExp 表達(dá)式：
const beta = E.challenge("beta");
const numExp = E.add( f, beta);
peCtx.numId = pil.expressions.length;
numExp.keep = true;
pil.expressions.push(numExp);
計(jì)算分母denExp 表達(dá)式：
const denExp = E.add( t, beta);
peCtx.denId = pil.expressions.length;
denExp.keep = true;
pil.expressions.push(denExp);
計(jì)算c2 表達(dá)式：
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});
最后通過(guò)pilCodeGen 分別構(gòu)建 num 和 den 的Code.
pilCodeGen(ctx, peCtx.numId, false);
pilCodeGen(ctx, peCtx.denId, false);
generateConnectionsZ
此次主要對(duì)了每個(gè)connection 運(yùn)算進(jìn)行處理：
首先取取出PIL 中每個(gè)connection, 如下所示：
const ci = pil.connectionIdentities[i];
const ciCtx = {};
每個(gè)ci 的結(jié)構(gòu)為：
"connectionIdentities": [
{
"pols": [
7, // 表達(dá)式 id
8,
9
],
"connections": [
10,
11,
12
],
"fileName": "/Users/tron/test/polygon_zkevm/pil-stark/test/sm_connection/connection.pil",
"line": 7
}
]
然后構(gòu)建numExp 和 denExp庶近，
ciCtx.zId = pil.nCommitments++; // z 承諾多項(xiàng)式 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);
}
分別對(duì)應(yīng)著以下公式：
[圖片上傳失敗...(image-3b3b75-1695281936283)]
構(gòu)建 c1 表達(dá)式：
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});
構(gòu)建c2 表達(dá)式：
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});
最后調(diào)用pilCodeGen 分別生成表達(dá)式num 和 den 的code.
pilCodeGen(ctx, ciCtx.numId, false);
pilCodeGen(ctx, ciCtx.denId, false);
res.ciCtx.push(ciCtx);
生成的ciCtx 結(jié)構(gòu)為：
"ciCtx": [
{
"zId": 19, // z 承諾多項(xiàng)式 id
"numId": 43, // num 表達(dá)式 id
"denId": 44, // den 表達(dá)式 id
"c1Id": 45, // c1 表達(dá)式 id
"c2Id": 46 // c2 表達(dá)式 id
}
]
buildCode
以上四步處理完成后翁脆，最終調(diào)用buildCode 將code 存入 res.step2prev 中。
res.step3prev = buildCode(ctx);
res.nCm2 表示第3步中承諾多項(xiàng)式的個(gè)數(shù)鼻种。
generateConstraintPolynomial
本步主要將前面生成的約束表達(dá)式組合在在一起反番，生成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);
}
然后對(duì)于idQ 類型的表達(dá)式，生成對(duì)應(yīng)的code. 對(duì)于evalQ 類型罢缸，需要額外添加2個(gè)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
}
})
最后將構(gòu)建的code 分別存于step4 和 step42ns 中篙贸。
nCm4 表示第4步中承諾多項(xiàng)式的個(gè)數(shù)，nQ 表示 q 多項(xiàng)式個(gè)數(shù)枫疆。
res.nCm4 = pil.nCommitments - res.nCm3 - res.nCm2 - res.nCm1;
res.nQ = pil.nQ;
generateConstraintPolynomialVerifier
主要對(duì)約束組合表達(dá)式生成驗(yàn)證的code, 代碼如下：
const ctxC = {
pil: pil,
calculated: {
exps: {},
expsPrime: {}
},
tmpUsed: 0,
code: []
};
pilCodeGen(ctxC, res.cExp, false, "correctQ");
res.verifierCode = buildCode(ctxC);
將生成的code 保存到verifierCode 中爵川。
對(duì)于correctQ ， 需要額外添加兩個(gè)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]
});
此時(shí)會(huì)將code 中 cm, q, const 類型更改為eval 類型息楔，并構(gòu)建 evIdex 到 evMap 的映射：
res.evIdx[r.type][p][r.id] = res.evMap.length;
evMap 對(duì)應(yīng)著 eval 類型的 id.
同時(shí)將exp 類型 更改變tmp 類型寝贡。
generateFRIPolynomial
本步驟主要生成 FRI 表達(dá)式：
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}}
$$
其中 和
分別表示 承諾多項(xiàng)式 和 q 多項(xiàng)式的個(gè)數(shù)。
然后分別計(jì)算 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;
}
}
其中 .
最后得到 的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;
}
生成 friExpId, 并構(gòu)建code. 放于step52ns中值依。
res.friExpId = pil.expressions.length;
friExp.keep2ns = true;
pil.expressions.push(friExp);
pilCodeGen(ctx2ns, res.friExpId);
res.step52ns = buildCode(ctx2ns);
注：最終得到的 的次數(shù)為
.
generateVerifierQuery
主要對(duì) fri 表達(dá)式生成用于查詢驗(yàn)證的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
主要構(gòu)建 各個(gè)section 的位置映射關(guān)系颇蜡，包含的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:[]
}
對(duì)nCm1 進(jìn)行處理：
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 的個(gè)數(shù)；
mapSectionN3: 各section 寬度為3的個(gè)數(shù)扮叨；
mapSectionN: 各section總寬度缤弦。
mapOffsets: 各section 在內(nèi)存中偏移
mapTotalN: 總共域（Goldilocks）元素個(gè)數(shù)；
mapDeg: 各 section 的個(gè)數(shù)甫匹。
然后調(diào)用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;
}
});
然后調(diào)用setCodeDimensions兵迅， 設(shè)置各種類型的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
預(yù)處理
首先對(duì)各個(gè)section 分配內(nèi)存空間薪贫，每個(gè)BigBuffer是一個(gè)uit64 類型數(shù)據(jù)恍箭。
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);
計(jì)算 和
，
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]);
}
其中
然后生成Zi:
其中 為偏移瞧省，
為基域總數(shù)扯夭，
為基域生成元，
為擴(kuò)域生成元,
為基域和擴(kuò)域擴(kuò)展位之間的子群的生成元鞍匾。
可以通過(guò)以下推導(dǎo)得到：
將常量多項(xiàng)式在基域和擴(kuò)域上進(jìn)行賦值交洗。
ctx.const_n = new BigBuffer(starkInfo.nConstants * ctx.N);
constPols.writeToBigBuffer(ctx.const_n, 0);
ctx.const_2ns = constTree.elements;
publics
本步驟主要計(jì)算公開(kāi)輸入的值，
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));
對(duì)于cmP 類型的公開(kāi)輸入橡淑，直接從cm1_n 中讀裙谷；
對(duì)于imP類型的公開(kāi)輸入，需要將表達(dá)通過(guò)compileCode生成函數(shù)置森，計(jì)算公開(kāi)輸入斗埂。例如本例中得到公開(kāi)輸入函數(shù)為：
(function anonymous(ctx,i
) {
ctx.tmp[0] = ctx.cm1_n[1 + i*15];
return ctx.tmp[0];
})
然后將cm_1 通過(guò)FFT擴(kuò)展到cm1_2ns， 然后生成Merkle 樹(shù) tree1凫海。
Caluculate plookups
第二步對(duì)應(yīng)的輸入和輸出分別為：
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";
}
通過(guò)調(diào)用compileCode 將第2步的 code 編譯成為計(jì)算函數(shù)呛凶，例如，本例中編譯的結(jié)果為：
? 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]); // 對(duì)應(yīng)著 t 表達(dá)式
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] ]); // 對(duì)應(yīng)著 f 表達(dá)式
}
然后計(jì)算 f 和 t 表達(dá)式行贪，再計(jì)算 h1 和 h2 , 將結(jié)果保存在 ctx.cm2_n 內(nèi)存中漾稀。
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);
}
然后將計(jì)算ctx.cm2_n 擴(kuò)展到cm2_2ns 擴(kuò)展域上，生成Merkle 樹(shù) 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";
}
通過(guò)調(diào)用compileCode 將第3步的 code 編譯成為計(jì)算函數(shù)县好，例如，本例中編譯的結(jié)果為：
(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]); // 對(duì)應(yīng) plookup pNum 計(jì)算
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]); // 對(duì)應(yīng)著 plookup pDen 計(jì)算
[ 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]); // 對(duì)應(yīng)著 permuation pNum 計(jì)算
[ 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]); // 對(duì)應(yīng)著 permutation pDen 計(jì)算
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]); // 對(duì)應(yīng)著 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]); // 對(duì)應(yīng)著 connection pDen
})
根據(jù)以上計(jì)算的plookup, permuation, connection 的 pNum 和 pDen暖混，計(jì)算其對(duì)應(yīng)的z 多項(xiàng)式缕贡，存放于ctx.cm3_n中。
最后再對(duì)ctx.cm3_n 通過(guò)FFT變換擴(kuò)展到擴(kuò)域上拣播，再生成Merkle 樹(shù)晾咪，得到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";
}
通過(guò)調(diào)用compileCode 將第step4 步的 code 編譯成為計(jì)算函數(shù)，例如贮配，本例中編譯的結(jié)果為：
(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 通過(guò)FFT變換擴(kuò)展到 ctx.exps_withq_2ns 上谍倦，然后再計(jì)算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";
}
通過(guò)調(diào)用compileCode 將第step42ns 步的 code 編譯成為計(jì)算函數(shù)，例如泪勒，本例中編譯的結(jié)果為：
(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]);
})
根據(jù)上述計(jì)算得到ctx.q_2ns 昼蛀， 然后得到Merkle 樹(shù) tree4。
Compute FRI Polynomial
Calculate Evals
首先選取兩個(gè)點(diǎn)：
const xis = F.div(ctx.challenges[7], F.shift);
const wxis = F.div(F.mul(ctx.challenges[7], F.w[nBits]), F.shift);
和
分別表示在Prime 為 faslse 和 true 情況下的選的點(diǎn)：
然后計(jì)算：
然后對(duì) 和
分別進(jìn)行IFFT變換圆存，得到對(duì)應(yīng)的Lagrange 基叼旋。
然后對(duì)evMap 的 中的多項(xiàng)式進(jìn)行計(jì)算估值，將結(jié)果保存在 ctx.evals 中沦辙。
Calculate xDivXSubXi, xDivXSubWXi
xDivXSubXi 和 xDivXWXi的計(jì)算公式分別為：
其中 為偏移夫植，
為基域生成元，
為擴(kuò)域生成元油讯，
详民。
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";
}
通過(guò)調(diào)用compileCode 將第step52ns 步的 code 編譯成為計(jì)算函數(shù)，例如陌兑，本例中編譯的結(jié)果為：
(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]); // 對(duì)應(yīng)著 fri 表達(dá)式計(jì)算
})
由此得到fri 表達(dá)式的列：
const friPol = getPol(ctx, starkInfo, starkInfo.exps_2ns[starkInfo.friExpId]);
friPol 為長(zhǎng)度為2048的數(shù)組沈跨，每個(gè)元素為width 為 3。
Calculate FRI proof
根據(jù) fri中steps 進(jìn)行多輪FRI 處理兔综。
"steps": [
{
"nBits": 11
},
{
"nBits": 3
}
]
對(duì)于第0輪饿凛，直接取fri 表達(dá)式的值隅俘。
if (si == 0) {
pol2_e[g] = pol[g];
}
然后，根據(jù)下一輪組的元素個(gè)數(shù)（本例為8）和 分組個(gè)數(shù)（本例為256）笤喳， 構(gòu)建Merkle 樹(shù)为居，width 為 768， height 為 8. 最后將merkle 樹(shù)的根保存在 proof 中杀狡。
if (si < this.steps.length - 1) {
const nGroups = 1 << this.steps[si + 1].nBits;
let groupSize = (1 << this.steps[si].nBits) / nGroups;
// 每間隔8個(gè)取一個(gè)蒙畴，重排
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]));
}
對(duì)于第1輪，計(jì)算如下參數(shù)：
const reductionBits = polBits - this.steps[si].nBits; // 計(jì)算約減位數(shù)呜象，本例為 11 -3 = 8
const pol2N = 1 << (polBits - reductionBits); // 計(jì)數(shù)pol2 的大小膳凝，本例為 2^3 = 8
const nX = pol.length / pol2N; // 計(jì)算分組個(gè)數(shù)，本例為256
const pol2_e = new Array(pol2N); // 用于保存pol2 的值恭陡。
let special_x = transcript.getField();
下面展示pol2_e 的計(jì)算過(guò)程：
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);
}
}
對(duì)于pol中的元素蹬音，每隔 pol2N (本例為8) 取一個(gè)， 得到ppar, 再進(jìn)行IFFT 變換休玩，得到 ppar_c著淆， 然后調(diào)整系數(shù)，再計(jì)算在special_x 點(diǎn)處的值拴疤。依次類推永部，得到pol2_e.
這部分實(shí)現(xiàn)原理參考：https://vitalik.ca/general/2017/11/22/starks_part_2.html
<img src="https://vitalik.ca/images/starks-part-2-files/fri7.png" alt="img" style="zoom:50%;" />
因?yàn)楸纠挥袃奢啠詈髮?code>pol2_e 保存到proof 中呐矾。
const lastPol = [];
for (let i = 0; i < pol.length; i++) {
lastPol.push(pol[i]);
}
proof.push(lastPol);
最后對(duì)所有生成的tree 的葉子節(jié)點(diǎn)進(jìn)行抽樣：
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 為選取葉子節(jié)點(diǎn)的的索引值苔埋。
第一輪從tree1, tree2, tree3, tree4, constTree， 根據(jù) ys 選取對(duì)應(yīng)葉子節(jié)點(diǎn)蜒犯，對(duì)應(yīng)的Merkle 路徑组橄；
后面，依次從生成的FRI 子樹(shù)罚随，根據(jù)ys 選取對(duì)應(yīng)葉子節(jié)點(diǎn)玉工，以及對(duì)應(yīng)的Merkle 路徑。
最終生成的證明即為：
proof: {
root1: MH.root(tree1), // tree1 的根
root2: MH.root(tree2),
root3: MH.root(tree3),
root4: MH.root(tree4),
evals: ctx.evals, // evMap 中多項(xiàng)式在xi或wxi的值
fri: friProof // 包含F(xiàn)RI 各輪的子樹(shù)根毫炉，以及隨機(jī)抽樣的葉子節(jié)點(diǎn)和對(duì)應(yīng)的Merkle路徑
},
publics: ctx.publics // 公開(kāi)輸入值
}
STARK verify
首先計(jì)算用到的挑戰(zhàn)的值：
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);
其中：
然后根據(jù) evals 點(diǎn)的值瓮栗，對(duì)組合多項(xiàng)式（verifierCode）進(jìn)行計(jì)算削罩，判斷結(jié)果是否為0瞄勾。
const res=executeCode(F, ctx, starkInfo.verifierCode.first);
此步驗(yàn)證所有約束條件滿足。
FRI 驗(yàn)證
首先計(jì)算 special_x 數(shù)組的值弥激，如下所示：
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]);
}
}
}
第一輪的時(shí)候进陡，對(duì)查詢點(diǎn)進(jìn)行Merkle 路徑驗(yàn)證，以及FRI多項(xiàng)式約束關(guān)系微服，汲及 和
(或
) 處估值趾疚；
第二輪對(duì)FRI 樹(shù)查詢點(diǎn)，及約束關(guān)系進(jìn)行驗(yàn)證。
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);
}
}
}
對(duì)最后一輪糙麦，進(jìn)行低度測(cè)試：
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
