Polygon zkEVM FFT和多项式evaluate计算的circom约束

1. 引言

前序博客：

• Polygon zkEVM中Goldilocks域元素circom约束

代码见：

• https://github.com/0xPolygonHermez/pil-stark/tree/main/circuits.gl

2. FFT运算的circom约束

const pgroup_c = F.ifft(pgroup_e);

// Adjustable parametees
const maxBlockBits = 16;
const minBlockBits = 12;
//const maxBlockBits = 2;
//const minBlockBits = 2;
const blocksPerThread = 8;
async function _fft(buffSrc, nPols, nBits, buffDst, inverse) {
    const n = 1 << nBits;
    const tmpBuff = new BigBuffer(n*nPols);
    const outBuff = buffDst;

    let bIn, bOut;

    const pool = workerpool.pool(__dirname + '/fft_worker.js');

    const idealNBlocks = pool.maxWorkers*blocksPerThread;
    let blockBits = log2(n*nPols/idealNBlocks);
    if (blockBits < minBlockBits) blockBits = minBlockBits;
    if (blockBits > maxBlockBits) blockBits = maxBlockBits;
    blockBits = Math.min(nBits, blockBits);
    const blockSize = 1 << blockBits;
    const nBlocks = n / blockSize;

    let nTrasposes;
    if (nBits == blockBits) {
        nTrasposes = 0;
    } else {
        nTrasposes = Math.floor((nBits-1) / blockBits)+1;
    }

    if (nTrasposes & 1) {
        bOut = tmpBuff;
        bIn = outBuff;
    } else {
        bOut = outBuff;
        bIn = tmpBuff;
    }

    if (inverse) {
        await invBitReverse(bOut, buffSrc, nPols, nBits);
    } else {
        await bitReverse(bOut, buffSrc, nPols, nBits);
    }
    [bIn, bOut] = [bOut, bIn];

    for (let i=0; i<nBits; i+= blockBits) {
        const sInc = Math.min(blockBits, nBits-i);
        const promisesFFT = [];

        // let results = [];
        for (j=0; j<nBlocks; j++) {
            const bb = bIn.slice(j*blockSize*nPols, (j+1)*blockSize*nPols);
            promisesFFT.push(pool.exec("fft_block", [bb, j*blockSize, nPols, nBits, i+sInc, blockBits, sInc]));

            // results[j] = await fft_block(bb, j*blockSize, nPols, nBits, i+sInc, blockBits, sInc);
        }
        const results = await Promise.all(promisesFFT);
        for (let i=0; i<results.length; i++) {
            bIn.set(results[i], i*blockSize*nPols)
        }
        if (sInc < nBits) {                // Do not transpose if it's the same
            await traspose(bOut, bIn, nPols, nBits, sInc);
            [bIn, bOut] = [bOut, bIn];
        }
    }

    await pool.terminate();
}

async function fft(buffSrc, nPols, nBits, buffDst) {
    await _fft(buffSrc, nPols, nBits, buffDst, false)
}

async function ifft(buffSrc, nPols, nBits, buffDst) {
    await _fft(buffSrc, nPols, nBits, buffDst, true)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

Goldilocks域 $p=2^{64}-2^{32}+1$。其支持最大FFT运算degree为32：【roots[i]对应为$2^i$-th root of unity。】

var roots[33] = [
        1,  // 2^0-th root of unity
        18446744069414584320, // 2^1-th root of unity
        281474976710656,  // 2^2-th root of unity
        18446744069397807105,
        17293822564807737345,
        70368744161280,
        549755813888,
        17870292113338400769,
        13797081185216407910,
        1803076106186727246,
        11353340290879379826,
        455906449640507599,
        17492915097719143606,
        1532612707718625687,
        16207902636198568418,
        17776499369601055404,
        6115771955107415310,
        12380578893860276750,
        9306717745644682924,
        18146160046829613826,
        3511170319078647661,
        17654865857378133588,
        5416168637041100469,
        16905767614792059275,
        9713644485405565297,
        5456943929260765144,
        17096174751763063430,
        1213594585890690845,
        6414415596519834757,
        16116352524544190054,
        9123114210336311365,
        4614640910117430873,
        1753635133440165772 // 2^{32}-th root of unity
    ];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

FFT(nBits, eSize, inv , shift)中inv为1表示iFFT，为0表示FFT。nBits表示对应$2^{\text{nBits}}-1$ degree多项式。eSize表示每个元素的宽度。shift表示偏移。

template FFT(nBits, eSize, inv , shift) {
    var n = 1<> 1;
        wm = roots(s);
        for (var k=0; k