本文以Fibonacci 為例，分析整個(gè)實(shí)現(xiàn)過(guò)程：
實(shí)現(xiàn)過(guò)程
/usr/local/bin/node --max-old-space-size=32000 src/main_pil2circom.js -p /Users/tron/test/polygon_zkevm/pil-stark/test/sm_fibonacci/fibonacci_main.pil -s /Users/tron/test/polygon_zkevm/pil-stark/test/sm_fibonacci/fibonacci.starkstruct.json -v /Users/tron/test/polygon_zkevm/pil-stark/tmp/fibonacci.verkey.json -o /Users/tron/test/polygon_zkevm/pil-stark/tmp/fibonacci.verifier.circom
輸入為：
- Fibonacci_main.pil
namespace Fibonacci(%N);
pol constant L1, LLAST;
pol commit l1,l2;
pol l2c = l2;
public in1 = l2c(0);
public in2 = l1(0);
public out = l1(%N-1);
(l2' - l1)*(1-LLAST) = 0;
pol next = l1*l1 + l2*l2;
(l1' - next)*(1-LLAST) = 0;
L1 * (l2 - :in1) = 0;
L1 * (l1 - :in2) = 0;
LLAST * (l1 - :out) = 0;
- Fibonacci.starkstruct.json
{
"nBits": 10,
"nBitsExt": 11,
"nQueries": 8,
"verificationHashType": "GL",
"steps": [
{"nBits": 11},
{"nBits": 7},
{"nBits": 3}
]
}
- Fibonacci.verkey.json
{
"constRoot": [
8072859658275330050,
6129740704102247485,
16008196867495226449,
2863018592730207411
]
}
輸出為生成的circom 電路：
Fibonacci.verifier.circom
主要采用 ejs 乡括，將Fibonacci 的信息注入stark 驗(yàn)證電路模板中黎泣，生成最后的Fibonacci stark 證明的驗(yàn)證電路。
const obj = {
F: F,
starkInfo: starkInfo,
starkStruct: starkStruct,
constRoot: constRoot,
pil: pil,
options: options
};
return ejs.render(template , obj);
verifier.circom
下面以fibonacci.verrifer.circom 過(guò)程為例坡椒，分析生成的用于驗(yàn)證STARK 證明的circom 電路涎永。
main 是 circom 程序的入口涯保，其中publics 聲明為公開(kāi)輸入。
component main {public [publics]}= StarkVerifier();
Merkle 樹(shù)
下面的代碼聲明驗(yàn)證需要用的Merkle 根：
signal input publics[3]; // Fibonacci中的三個(gè)公開(kāi)輸入
signal input root1[4]; // commit多項(xiàng)式對(duì)應(yīng)的Merkle 根
signal input root2[4]; // plookup 多項(xiàng)式對(duì)應(yīng)的Merkle 根
signal input root3[4]; // plookup/permutation/connection Z 多項(xiàng)式對(duì)應(yīng)的根
signal input root4[4]; // q多項(xiàng)式 約束對(duì)應(yīng)的Merkle 根
signal rootC[4]; // 常量多項(xiàng)式對(duì)應(yīng)的Merkle 根
rootC[0] <== 8072859658275330050; //從fibonacci.verkey.json 導(dǎo)入的常量根
rootC[1] <== 6129740704102247485;
rootC[2] <== 16008196867495226449;
rootC[3] <== 2863018592730207411;
以下涉及FRI 過(guò)程對(duì)應(yīng)的葉子節(jié)點(diǎn)和Merkle 路徑：
signal input evals[8][3]; // 對(duì)應(yīng)starkinfo 中 evMap中各個(gè)承諾多項(xiàng)式的值钞诡。
signal input s0_vals1[8][2]; // 8 表示查詢點(diǎn)的個(gè)數(shù)郑现，2表示commit多項(xiàng)式的個(gè)數(shù)（cm1_2ns）
signal input s0_vals4[8][4]; // 8 表示查詢點(diǎn)的個(gè)數(shù)湃崩，4表示q多項(xiàng)式的個(gè)數(shù)（q_2ns）
//注：Fibonacci s0_vals2, so_vals3對(duì)應(yīng)的約束不存在，所有沒(méi)有生成
signal input s0_valsC[8][2]; // 8 表示查詢點(diǎn)的個(gè)數(shù)接箫，2表示 常量多項(xiàng)式 的個(gè)數(shù)（q_2ns）
signal input s0_siblings1[8][11][4]; //s0_vals1對(duì)應(yīng)的Merkle 路徑攒读，有11層，每個(gè)節(jié)點(diǎn)由4個(gè)Goldilocks 元素組成
signal input s0_siblings4[8][11][4];
signal input s0_siblingsC[8][11][4];
signal input s1_root[4]; // fri step 1 root
signal input s2_root[4]; // fri step 2 root
signal input s1_vals[8][48]; // fri 1 tree對(duì)應(yīng)查詢點(diǎn)的葉子節(jié)點(diǎn)辛友，48為對(duì)應(yīng)葉子width, 即： (1 <<
// (starkStruct.steps[s-1].nBits - starkStruct.steps[s].nBits))*3
signal input s1_siblings[8][7][4]; // fri 1 tree 對(duì)應(yīng)的Merkle路徑
signal input s2_vals[8][48]; //與以上類似
signal input s2_siblings[8][3][4];
signal input finalPol[8][3]; // 最后一輪薄扁，每個(gè)都為寬度為3的值
FRI 參數(shù)
FRI 的相關(guān)參數(shù)值定義：
signal enable; // enable input
enable <== 1;
signal challenges[8][3]; // 固定的8個(gè)chanllenge 值
signal s0_specialX[3]; // fri計(jì)算過(guò)程中涉及到的special_x, 和fri的 steps 個(gè)數(shù)相等
signal s1_specialX[3];
signal s2_specialX[3];
signal ys[8][11]; // 查詢點(diǎn)索引值
FRI 相關(guān)參數(shù)值的計(jì)算：
component tcHahs_0 = Poseidon(12);
tcHahs_0.in[0] <== root1[0];
tcHahs_0.in[1] <== root1[1];
tcHahs_0.in[2] <== root1[2];
tcHahs_0.in[3] <== root1[3];
tcHahs_0.in[4] <== 0;
tcHahs_0.in[5] <== 0;
tcHahs_0.in[6] <== 0;
tcHahs_0.in[7] <== 0;
tcHahs_0.capacity[0] <== 0;
tcHahs_0.capacity[1] <== 0;
tcHahs_0.capacity[2] <== 0;
tcHahs_0.capacity[3] <== 0;
challenges[0][0] <== tcHahs_0.out[0];
challenges[0][1] <== tcHahs_0.out[1];
challenges[0][2] <== tcHahs_0.out[2];
challenges[1][0] <== tcHahs_0.out[3];
challenges[1][1] <== tcHahs_0.out[4];
challenges[1][2] <== tcHahs_0.out[5];
......
后續(xù)代碼類似，依次完成challenge, special_x, ys 計(jì)算過(guò)程废累。
約束多項(xiàng)式檢查
///////////
// Constrain polynomial check in vauations
///////////
component verifyEvaluations = VerifyEvaluations();
verifyEvaluations.enable <== enable;
for (var i=0; i<8; i++) {
for (var k=0; k<3; k++) {
verifyEvaluations.challenges[i][k] <== challenges[i][k];
}
}
for (var i=0; i<3; i++) {
verifyEvaluations.publics[i] <== publics[i];
}
for (var i=0; i<8; i++) {
for (var k=0; k<3; k++) {
verifyEvaluations.evals[i][k] <== evals[i][k];
}
}
FRI 表達(dá)式驗(yàn)證
///////////
// Step0 Check and evaluate queries
///////////
component verifyQueries[8];
component s0_merkle1[8];
component s0_merkle4[8];
component s0_merkleC[8];
component s0_lowValues[8];
...
FRI tree 1 驗(yàn)證
component s1_merkle[8];
component s1_fft[8];
component s1_evalPol[8];
component s1_lowValues[8];
signal s1_sx[8][7];
......
FRI tree 2 驗(yàn)證
component s2_merkle[8];
component s2_fft[8];
component s2_evalPol[8];
component s2_lowValues[8];
signal s2_sx[8][3];
...
低度測(cè)試
最后一輪的低度邓梅，判定最后的多項(xiàng)式次數(shù)小于4。
///////
// Check Degree last pol
///////
// Last FFT
component lastIFFT = FFT(3, 3, 1, 1 );
for (var k=0; k< 8; k++ ){
for (var e=0; e<3; e++) {
lastIFFT.in[k][e] <== finalPol[k][e];
}
}
for (var k= 4; k< 8; k++ ) {
for (var e=0; e<3; e++) {
enable * lastIFFT.out[k][e] === 0;
}
}
參考
https://github.com/0xPolygonHermez/pil-stark/blob/main/src/main_pil2circom.js
