FFT rust代码实现

Tani ·

更新时间:2024-11-14

· 525 次阅读

目前的实现主要有：
1）Halo中（https://github.com/ebfull/halo/blob/master/src/util.rs）在utils.rs中对两条新的曲线做了实现；
2）Zexe中，设计了单独的ff-fft模块，对pairing曲线（如Jubjub/mnt6等）做了实现；
3）Openzkp中（https://github.com/0xProject/OpenZKP/blob/master/algebra/primefield/src/fft.rs）在fft.rs 中对251-bit prime field 做了fft实现。

注意，其实在做polynomial commitment时，factor(p-1) = 2^s*t，其中的s值代表允许的多项式的最高阶数。generator=primitive_root(p)【generator为(p−1)(p-1)(p−1)-th root of unity，有限域内任意xxx，其x(p−1)=1x^{(p-1)}=1x(p−1)=1恒成立】，2s2^s2s-th root of unity的计算方式为power_mod(generator, t, p)。
对于curve25519来说，其Fr域内的s值仅为2且generator无返回（无论是基于magma还是sagemath）。所以在polynomial commitment时，其并不适用。
另外，考虑到vector commitment（如系数的commitment，需要用到scalar值乘以point）的结合，一般polynomial commitment都采用的是scalar field的值。
Zexe中的ff-fft模块中，会由2s2^s2s-th root of unity获得多项式阶数（提升到最近的2^k值，如下代码中的size值）对应的root of unity（对应如下代码中的group_gen值）：

		// Compute the size of our evaluation domain
        let size = num_coeffs.next_power_of_two() as u64;
        let log_size_of_group = size.trailing_zeros();
        if log_size_of_group >= F::Params::TWO_ADICITY {
            return None;
        }
        // Compute the generator for the multiplicative subgroup.
        // It should be 2^(log_size_of_group) root of unity.
        let mut group_gen = F::root_of_unity();
        for _ in log_size_of_group..F::Params::TWO_ADICITY {
            group_gen.square_in_place();
        }

作者：mutourend

fft rust

1024 个赞