本文以Plookup約束為例對PIL-STARK源碼進行分析。
1. 定義starkStruct
首先定義starkStruct 結構為：
const starkStruct = {
nBits: 3, // 基域 2**3 = 8
nBitsExt: 4, // 擴域：2**4 = 6
nQueries: 8,
verificationHashType: "GL", // 采用GoldLicks Hash
steps: [
{ nBits: 4 },
{ nBits: 2 }
]
};
2. 編譯PIL
Plookup 的PIL 代碼有兩個文件：
simple_plookup_main.pil為：
constant %N = 2**3;
namespace Global(%N);
pol constant L1; // Lagrange basis
include "simple_plookup.pil";
simple_plookup.pil 為：
namespace SimplePlookup(%N);
pol commit a; // commitment polynomia
pol constant A; // constant polynomial
pol constant ONE;
pol constant ZERO;
a in A; // plookup
對PIL 源碼進行編譯：
const pil = await compile(Fr, path.join(__dirname, "sm_simple_plookup", "simple_plookup_main.pil"));
得到PIL為：
{
"nCommitments": 1, //承諾多項式的個數(shù)
"nQ": 0,
"nIm": 0,
"nConstants": 4, //常量承諾多項式的個數(shù)
"publics": [],
"references": {
"Global.L1": {
"type": "constP", //常量承諾多項式類型
"id": 0, //在`constP` 的id
"polDeg": 8,
"isArray": false
},
"SimplePlookup.a": {
"type": "cmP", //承諾多項式類型
"id": 0, //在`cmP` 承諾中的id
"polDeg": 8,
"isArray": false
},
"SimplePlookup.A": {
"type": "constP",
"id": 1,
"polDeg": 8,
"isArray": false
},
"SimplePlookup.ONE": {
"type": "constP",
"id": 2,
"polDeg": 8,
"isArray": false
},
"SimplePlookup.ZERO": {
"type": "constP",
"id": 3,
"polDeg": 8,
"isArray": false
}
},
"expressions": [ // 包含兩個表達式
{
"op": "cm",
"deg": 1,
"id": 0,
"next": false
},
{
"op": "const",
"deg": 1,
"id": 1,
"next": false
}
],
"polIdentities": [],
"plookupIdentities": [
{
"f": [
0 // 表示式 id
],
"t": [
1 // 表達式 id
],
"selF": null,
"selT": null,
"fileName": "simple_plookup.pil",
"line": 10
}
],
"permutationIdentities": [],
"connectionIdentities": []
}
3. build constPols and cmPols
其中 N=8.
module.exports.buildConstants = async function (pols) {
const N = pols.A.length;
let p = 0;
for (let i = 0; i < N; i++) {
pols.A[i] = BigInt(i);
pols.ONE[i] = 1n;
pols.ZERO[i] = 0n;
}
}
module.exports.execute = async function (pols) {
const N = pols.a.length;
for (let i = 0; i < N; i++) {
pols.a[i] = BigInt(i);
}
}
4. StarkInfo 初始化
const res = { // 用于保存最終的StarkInfo 的結果
varPolMap: [],
puCtx: [],
peCtx: [],
ciCtx: []
};
res.starkStruct = starkStruct;
res.nConstants = pil.nConstants;
res.nPublics = pil.publics.length;
generatePublicCalculators(res, pil); // 處理公開輸入
res.nCm1 = pil.nCommitments;
const ctx = {
pil: pil,
calculated: {
exps: {},
expsPrime: {}
},
tmpUsed: 0,
code: []
};
const ctx2ns = {
pil: pil,
calculated: {
exps: {},
expsPrime: {}
},
tmpUsed: 0,
code: []
};
5. generateStep2
主要的代碼如下：
module.exports = function generateStep2(res, pil, ctx) {
const E = new ExpressionOps(); //用于表達式的運算
for (let i=0; i<pil.plookupIdentities.length; i++) { //循環(huán)結構， 對PIL的每個plookup， 分別處理
const puCtx = {};
const pi = pil.plookupIdentities[i];
// 計算 t 表達式
let tExp = null;
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; //Q 可能表示 Quadraic， 二次的
pil.nQ++;
}
puCtx.tExpId = pil.expressions.length;
tExp.keep = true;
pil.expressions.push(tExp);
// 計算 f 表達式
fExp = null;
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;
fExp.keep = true;
pil.expressions.push(fExp);
pilCodeGen(ctx, puCtx.fExpId, false);
pilCodeGen(ctx, puCtx.tExpId, false);
puCtx.h1Id = pil.nCommitments++; // 每個plookup 新添加h1和h2 兩個承諾：
puCtx.h2Id = pil.nCommitments++;
res.puCtx.push(puCtx);
}
res.step2prev = buildCode(ctx);
}
pil.expressions 數(shù)組目前變?yōu)?個表達式：
0:{op: 'cm', deg: 1, id: 0, next: false}
1:{op: 'const', deg: 1, id: 1, next: false}
2:{op: 'exp', id: 1, next: false, keep: true} // tExp: id 1 指向第 1 個表達式
3:{op: 'exp', id: 0, next: false, keep: true} // fExp: id 0 指向第 0 個表達式
對 fExp 執(zhí)行 pilCodeGen 操作后，
pilCodeGen(ctx, puCtx.fExpId, false);
ctx 添加2兩個code：
// 第0個code, 執(zhí)行復制操作 cm0 -> exp 0
0:{expId: 0, prime: false, code: Array(1), idQ: undefined}
code:(1) [{…}]
0:{op: 'copy', dest: {…}, src: Array(1)}
dest:{type: 'exp', prime: false, id: 0}
op:'copy'
src:(1) [{…}]
0:{type: 'cm', id: 0, prime: false}
// 第 1 個 code, 執(zhí)行復制操作 exp 0 -> exp3
1:{expId: 3, prime: false, code: Array(1), idQ: undefined}
code:(1) [{…}]
0:{op: 'copy', dest: {…}, src: Array(1)}
dest:{type: 'exp', prime: false, id: 3}
id:3
prime:false
type:'exp'
op:'copy'
src:(1) [{…}]
0:{type: 'exp', id: 0, prime: false}
對tExp 執(zhí)行 pilCodeGen 運算：
pilCodeGen(ctx, puCtx.tExpId, false);
ctx 再次添加兩個code, 分別：
// 第2個code, 執(zhí)行復制操作 const 1 -> exp 1
2:{expId: 1, prime: false, code: Array(1), idQ: undefined}
code:(1) [{…}]
0:{op: 'copy', dest: {…}, src: Array(1)}
length:1
expId:1
dest:{type: 'exp', prime: false, id: 1}
op:'copy'
src:(1) [{…}]
0:{type: 'const', id: 1, prime: false}
// 第3個code, 執(zhí)行復制操作 exp 1 -> exp 2
3:{expId: 2, prime: false, code: Array(1), idQ: undefined}
code:(1) [{…}]
0:{op: 'copy', dest: {…}, src: Array(1)}
dest:{type: 'exp', prime: false, id: 2}
op:'copy'
src:(1) [{…}]
0:{type: 'exp', id: 1, prime: false}
生成puCtx的 結構為：
{tExpId: 2, fExpId: 3, h1Id: 1, h2Id: 2}
fExpId:3 // f 表達式 id
h1Id:1 // h1 承諾(cm) id
h2Id:2 // h2 承諾 id
tExpId:2 // t 表達式 id
buildCode 整合所有的code， 共4個，分別放于first, i, last 中：
res.step2prev = buildCode(ctx);
和上述的code 順序對應：
first:(4) [{…}, {…}, {…}, {…}]
0:{op: 'copy', dest: {…}, src: Array(1)}
dest:{type: 'exp', prime: false, id: 0}
op:'copy'
src:(1) [{…}]
0:{type: 'cm', id: 0, prime: false}
1:{op: 'copy', dest: {…}, src: Array(1)}
dest:{type: 'exp', prime: false, id: 3}
op:'copy'
src:(1) [{…}]
0:{type: 'exp', id: 0, prime: false}
2:{op: 'copy', dest: {…}, src: Array(1)}
dest:{type: 'exp', prime: false, id: 1}
op:'copy'
src:(1) [{…}]
0:{type: 'const', id: 1, prime: false}
3:{op: 'copy', dest: {…}, src: Array(1)}
dest:{type: 'exp', prime: false, id: 2}
op:'copy'
src:(1) [{…}]
0:{type: 'exp', id: 1, prime: false}
nCm2 表示為第2步的承諾個數(shù)。
res.nCm2 = pil.nCommitments - res.nCm1;
6. generateStep3
generatePermutationsLC
對置換進行處理，本例不需要，略過；
generatePlookupZ
對查找表進行處理。
下面的計算對應著Plooup 算法：
function generatePlookupZ(res, pil, ctx) {
const E = new ExpressionOps();
for (let i=0; i<pil.plookupIdentities.length; i++) { // 循環(huán)，對每個plookup操作分別處理
const puCtx = res.puCtx[i];
puCtx.zId = pil.nCommitments++; // 添加一個承諾
const h1 = E.cm(puCtx.h1Id); // 生成承諾表達式
const h2 = E.cm(puCtx.h2Id); // 生成承諾表達式
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 表達式下一步
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))); // 對應 z(g) = 1 約束條件
c1.deg=2;
puCtx.c1Id = pil.expressions.length; // 表達式的 id
pil.expressions.push(c1);
pil.polIdentities.push({e: puCtx.c1Id}); // 最終表達式放于polIdentities 中
const gamma = E.challenge("gamma");
const beta = E.challenge("beta");
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; // 分子表達式id
numExp.keep = true;
pil.expressions.push(numExp);
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; // 分母表達式 id
denExp.keep = true;
pil.expressions.push(denExp);
const num = E.exp(puCtx.numId);
const den = E.exp(puCtx.denId);
const c2 = E.sub( E.mul(zp, den), E.mul(z, num) ); // 對就上文公式 4（b）表達
c2.deg=2;
puCtx.c2Id = pil.expressions.length; // c2 表達式 id
pil.expressions.push(c2);
pil.polIdentities.push({e: puCtx.c2Id}); // 表達式約束放入poldIdentities中。
pilCodeGen(ctx, puCtx.numId, false); // 生成分子表達式的code
pilCodeGen(ctx, puCtx.denId, false); // 生成分母表達式的code
}
}
得到的puCtx 結構為：
{
"tExpId": 2, // t 表達式id
"fExpId": 3, // f 表達式id
"h1Id": 1, // h1 承諾id
"h2Id": 2, // h2 承諾id
"zId": 3, // z 承諾id
"c1Id": 4, // c1 表達式id
"numId": 5, // num 表達式id
"denId": 6, // den 表達式id
"c2Id": 7 // c2 表達式 id
}
generatePermutationZ
生成置換多項式Z， 本例不需要，略過
generateConnectionZ
生成ConnectinsZ， 本例不需要，略過
最后生成第code, 如下所示：
res.step3prev = buildCode(ctx);
計算第三步的承諾個數(shù)：
res.nCm3 = pil.nCommitments - res.nCm1 - res.nCm2;
7. generateConstraintPolynomial
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; // 組合表達式的 id
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);
}
參考
https://github.com/0xPolygonHermez/pil-stark/blob/main/test/stark_simple_plookup.test.js
