pil2circom 实现过程
2023-09-20 本文已影响0人
雪落无留痕
本文以Fibonacci 为例，分析整个实现过程：
实现过程
/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 验证电路模板中，生成最后的Fibonacci stark 证明的验证电路。
const obj = {
F: F,
starkInfo: starkInfo,
starkStruct: starkStruct,
constRoot: constRoot,
pil: pil,
options: options
};
return ejs.render(template , obj);
verifier.circom
下面以fibonacci.verrifer.circom 过程为例，分析生成的用于验证STARK 证明的circom 电路。
main 是 circom 程序的入口，其中publics 声明为公开输入。
component main {public [publics]}= StarkVerifier();
Merkle 树
下面的代码声明验证需要用的Merkle 根：
signal input publics[3]; // Fibonacci中的三个公开输入
signal input root1[4]; // commit多项式对应的Merkle 根
signal input root2[4]; // plookup 多项式对应的Merkle 根
signal input root3[4]; // plookup/permutation/connection Z 多项式对应的根
signal input root4[4]; // q多项式 约束对应的Merkle 根
signal rootC[4]; // 常量多项式对应的Merkle 根
rootC[0] <== 8072859658275330050; //从fibonacci.verkey.json 导入的常量根
rootC[1] <== 6129740704102247485;
rootC[2] <== 16008196867495226449;
rootC[3] <== 2863018592730207411;
以下涉及FRI 过程对应的叶子节点和Merkle 路径：
signal input evals[8][3]; // 对应starkinfo 中 evMap中各个承诺多项式的值。
signal input s0_vals1[8][2]; // 8 表示查询点的个数，2表示commit多项式的个数（cm1_2ns）
signal input s0_vals4[8][4]; // 8 表示查询点的个数，4表示q多项式的个数（q_2ns）
//注：Fibonacci s0_vals2, so_vals3对应的约束不存在，所有没有生成
signal input s0_valsC[8][2]; // 8 表示查询点的个数，2表示 常量多项式 的个数（q_2ns）
signal input s0_siblings1[8][11][4]; //s0_vals1对应的Merkle 路径，有11层，每个节点由4个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对应查询点的叶子节点，48为对应叶子width, 即： (1 <<
// (starkStruct.steps[s-1].nBits - starkStruct.steps[s].nBits))*3
signal input s1_siblings[8][7][4]; // fri 1 tree 对应的Merkle路径
signal input s2_vals[8][48]; //与以上类似
signal input s2_siblings[8][3][4];
signal input finalPol[8][3]; // 最后一轮，每个都为宽度为3的值
FRI 参数
FRI 的相关参数值定义：
signal enable; // enable input
enable <== 1;
signal challenges[8][3]; // 固定的8个chanllenge 值
signal s0_specialX[3]; // fri计算过程中涉及到的special_x, 和fri的 steps 个数相等
signal s1_specialX[3];
signal s2_specialX[3];
signal ys[8][11]; // 查询点索引值
FRI 相关参数值的计算：
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];
......
后续代码类似，依次完成challenge, special_x, ys 计算过程。
约束多项式检查
///////////
// 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 表达式验证
///////////
// 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 验证
component s1_merkle[8];
component s1_fft[8];
component s1_evalPol[8];
component s1_lowValues[8];
signal s1_sx[8][7];
......
FRI tree 2 验证
component s2_merkle[8];
component s2_fft[8];
component s2_evalPol[8];
component s2_lowValues[8];
signal s2_sx[8][3];
...
低度测试
最后一轮的低度，判定最后的多项式次数小于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
