本文以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, //承诺多项式的个数
"nQ": 0,
"nIm": 0,
"nConstants": 4, //常量承诺多项式的个数
"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++) { //循环结构， 对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 数组目前变为4个表达式：
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 执行 pilCodeGen 操作后，
pilCodeGen(ctx, puCtx.fExpId, false);
ctx 添加2两个code：
// 第0个code, 执行复制操作 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, 执行复制操作 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 执行 pilCodeGen 运算：
pilCodeGen(ctx, puCtx.tExpId, false);
ctx 再次添加两个code, 分别：
// 第2个code, 执行复制操作 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, 执行复制操作 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步的承诺个数。
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++) { // 循环，对每个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);
计算第三步的承诺个数：
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
