pil2circom 实现过程

本文以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

https://docs.circom.io/