Plonky3-fri 作业

[YangXiaoXue205]

以下问题三选一回答即可，这也是我对代码的疑问，有可能我的想法是有问题的，抛给小伙伴们帮我check
1.two_adic_pcs的open函数里预先计算alpha powers是否会更高效？即，open函数里，在遍历每一round的矩阵前，预先计算alpha powers到max length，然后在遍历到每一个矩阵的某一个open的点，计算reduced_ys以及reduced_row时按需取用预先计算的alpha powers。这样做是否会更高效？理由是？如果你觉得更高效，对代码做相应的优化并po出优化前后的效率对比。

2.two_adic_pcs的open函数里调用的计算inv_denoms的函数compute_inverse_denominators中，对应每一个open点z，都计算到了全局最大的高度max_log_height，我认为这是没有必要的，若是对应每一个open点z，都只计算到在该点处open的所有矩阵的最大高度即可。你赞同我的看法吗？理由是？

3.在“竖着卷”的过程中，两个多项式是直接相加的，这样是否足够安全？是否有必要乘以一个随机数之后再相加？如果要乘以一个随机数之后再相加应该如何修改代码？po出具体的修改

[keroro520]

3.在“竖着卷”的过程中，两个多项式是直接相加的，这样是否足够安全？是否有必要乘以一个随机数之后再相加？如果要乘以一个随机数之后再相加应该如何修改代码？po出具体的修改

代码改动: 乘以一个随机数之后再相加

prover commit_phase 改动如下：

diff --git a/fri/src/prover.rs b/fri/src/prover.rs
index 2113a90..a50769c 100644
--- a/fri/src/prover.rs
+++ b/fri/src/prover.rs
@@ -94,7 +94,7 @@ where
         let beta: Challenge = challenger.sample_ext_element();
         // We passed ownership of `current` to the MMCS, so get a reference to it
         let leaves = config.mmcs.get_matrices(&prover_data).pop().unwrap();
-        folded = g.fold_matrix(beta, leaves.as_view());
+        folded = g.fold_matrix(beta, leaves.as_view()).into_iter().map(|x| beta * x).collect_vec();
 
         commits.push(commit);
         data.push(prover_data);

verifier verify_query 改动如下：

diff --git a/fri/src/verifier.rs b/fri/src/verifier.rs
index 6553c29..a262434 100644
--- a/fri/src/verifier.rs
+++ b/fri/src/verifier.rs
@@ -133,7 +133,7 @@ where
 
         index = index_pair;
 
-        folded_eval = g.fold_row(index, log_folded_height, beta, evals.into_iter());
+        folded_eval = g.fold_row(index, log_folded_height, beta, evals.into_iter()) * beta;
     }

FRI 和 Plonky3 FRI

FRI 迭代式地将 $p(x)$ 二分展开成 $p_{even}(x)$ 和 $p_odd(x)$ ，再折叠成新的多项式 $p^{\star}(x)$ 。折叠时引入随机数 $\beta$ ，用以确保 prover 正确地展开 $p(x) = p_{even}(x^2) + x \cdot p_odd(x^2)$ ：

$$ \begin{aligned} \text{set } p(x) &= \text{ folded matrix} \\ p^\star(g^{2i}) &= p_{even}(g^{2i}) + \beta \cdot p_{odd}(g^{2i}) \end{aligned} $$

Plonky3 FRI 可以批量证明多个多项式，它在迭代过程中将折叠后的多项式跟输入中的小阶多项式组合到一起证明：

$$ \begin{aligned} \text{set } p(x) &= \text{ folded matrix} \\ \text{set } \text{unfolded}(x) &= \text{ unfolded matrix} \\ p^{\star}(g^{2i}) &= p_{even}(g^{2i}) + \beta \cdot p_{odd}(g^{2i}) \\ p^{\star\star}(g^{2i}) &= p^{\star}(g^{2i}) + \text{unfolded}(g^{2i}) \end{aligned} $$

上述代码改动后，折叠后的多项式先乘以 $\beta$ 再加上 $\text{unfolded}$ ：

$$ \begin{aligned} p^{\star\star}(g^{2i}) = \beta \cdot p^{\star}(g^{2i}) + \text{unfolded}(g^{2i}) \end{aligned} $$

引入 $\beta$ 做折叠的原因

在回答 “是否有必要再引入一个新的随机数来组合 $\text{unfoled}(x)$ ” 之前，我想先理解 “为什么要引入 $\beta$ 来折叠”？

FRI 一轮迭代的顺序过程是：

1. commit $[p(x)]$
2. add $[p(x)]$ into channel and then sample $\beta$ from channel
3. linear combination using $\beta$ and then commit $[p^{\star}(x)]$

我的理解是，以 $[p(x)]$ 作为随机数因子而产生的随机数 $\beta$ ，
使得 $p$ 和 $p^{\star}$ 的线性关系不可预测，
所以 prover 无法提前预测和提前构建 $p^{\star}$ ，
这样就约束了 prover 只能按约定来构建 $p^{\star}$ 。

反之，如果没有随机数折叠带来的不可预测的线性关系，那么对 prover 的约束力就比较低，prover 就可以提前构建 false positive 的多项式。

不知道我的这番理解有没有问题，求指正。

Plonky3 是否有必要再引入一个新的随机数来组合

$p^{\star\star}$ 由 $p^{\star}$ 和 $\text{unfolded}$ 组合而成，

• $p^{\star}$ 已经由 $\beta$ 约束住；
• $\text{unfolded}$ 已经由 commitment $[\text{unfolded}(x)]$ 约束（这是输入数据，应该在算术化阶段就承诺了，不在 FRI 范畴）。

二者无需额外约束，所以没有必要在引入新的随机数来组合。

[keroro520]

2.two_adic_pcs的open函数里调用的计算inv_denoms的函数compute_inverse_denominators中，对应每一个open点z，都计算到了全局最大的高度max_log_height，我认为这是没有必要的，若是对应每一个open点z，都只计算到在该点处open的所有矩阵的最大高度即可。你赞同我的看法吗？理由是？

我理解源代码就是如后者所述的 “只计算到在该点处open的所有矩阵的最大高度即可”。

1. 遍历 open z 点所涉及的 matrices，过滤出其中的最大高度 "max log height for z" ，其中 max_log_height_for_point 存储着 #{z => max log height for z} 的对应关系。

                if let Some(lh) = max_log_height_for_point.get_mut(&z) {
                    *lh = core::cmp::max(*lh, log_height);

2. 对于点 z，只算 batch_multiplicative_inverse([ (x-z) for x in [0..2^(max_log_height_for_z)] )

    max_log_height_for_point
        .into_iter()
        .map(|(z, log_height)| {
            (
                z,
                batch_multiplicative_inverse(
                    &subgroup[..(1 << log_height)]
                        .iter()
                        .map(|&x| EF::from_base(x) - z)
                        .collect_vec(),
                ),
            )
        })

[keroro520]

1.two_adic_pcs的open函数里预先计算alpha powers是否会更高效？即，open函数里，在遍历每一round的矩阵前，预先计算alpha powers到max length，然后在遍历到每一个矩阵的某一个open的点，计算reduced_ys以及reduced_row时按需取用预先计算的alpha powers。这样做是否会更高效？理由是？如果你觉得更高效，对代码做相应的优化并po出优化前后的效率对比。

我没有做到很精确的对比，只是对比了两种方案的 open() 耗时，以及写了单元测试单独比较两种方案。

我的结论是，改动后有优化效果，只是优化效果微小。优化效果取决于程序实际执行了多少次乘法运算，乘法运算的次数取决于 「打开的z点数量」 、「matrix数量」和「max_log_height」。

原代码通过调用 alpha.exp_u64(pow) 来计算 a^pow，执行的乘法运算的次数是 log2(pow)，那么实际调用的乘法运算次数为 打开的z点数量 * SUM_{pow=1}{matrix数量 * max_log_height}{log2(pow)}

如果改为提前计算 alpha pows， alpha.powers().take(max_log_height * matrices.len()) ，调用了 matrix数量 * max_log_height 次乘法运算。

代入实际情况的 max_log_height 约为 16，matrices 的数量约为 16，z 点数量 1，实际上减少的乘法运算的次数并没有多少，优化效果很小。实测两种方案对于 open() 的影响是比较小的。

下面是一个单元测试用例，可以在 release mode 下运行来对比两种方案的耗时。

// Run in release mode:
// ```
// cargo test --release  --package p3-fri --test pcs -- bench_alpha_pow --exact --show-output
// ```
fn bench_alpha_pow() {
    use p3_field::AbstractField;
    let alpha = BinomialExtensionField::<p3_mersenne_31::Mersenne31, 3>::from_canonical_u64(12);

    let bench = |max_power: usize| {
        println!("");
        println!("For max_power: {}", max_power);

        let start_time = std::time::Instant::now();
        let alpha_pows = alpha.powers().take(max_power).collect_vec();
        (0..max_power).for_each(|power| { let _ = alpha_pows[power] ; });
        println!("    time taken to precompute alpha_pows  : {:?}", start_time.elapsed());

        let start_time = std::time::Instant::now();
        (0..max_power).for_each(|power| { let _ = alpha.exp_u64(power as u64); });
        println!("    time taken to compute alpha.exp_u64(): {:?}", start_time.elapsed());
    };
    bench(16*16);
    bench(16*160);
}

输出:

For max_power: 256
    time taken to precompute alpha_pows  : 31.668µs
    time taken to compute alpha.exp_u64(): 115.783µs

For max_power: 2560
    time taken to precompute alpha_pows  : 269.458µs
    time taken to compute alpha.exp_u64(): 1.292716ms

[Einstellung]

抱歉，我有点疑惑，这一条说的是什么地方。是在讨论这块的代码吗？

let alpha_pow_offset = alpha.exp_u64(num_reduced[log_height] as u64);
let reduced_ys: Challenge = dot_product(alpha.powers(), ys.iter().copied());

这个power来自

#[must_use]
fn powers(&self) -> Powers<Self> {
	self.shifted_powers(Self::one())
}

fn shifted_powers(&self, start: Self) -> Powers<Self> {
	Powers {
		base: self.clone(),
		current: start,
	}
}

pub struct Powers<F> {
    pub base: F,
    pub current: F,
}

impl<AF: AbstractField> Iterator for Powers<AF> {
    type Item = AF;

    fn next(&mut self) -> Option<AF> {
        let result = self.current.clone();
        self.current *= self.base.clone();
        Some(result)
    }
}

本身就是一个迭代器，按需加载。大家是在讨论重复计算的问题吗？从下面代码中看到对传入的current再做进一步计算，好像并没有重复计算。

fn exp_u64(&self, power: u64) -> Self {
	Self::F::exp_u64_generic(self.clone(), power)
}

pub fn exp_u64_by_squaring<AF: AbstractField>(val: AF, power: u64) -> AF {
    let mut current = val;
    let mut product = AF::one();

    for j in 0..bits_u64(power) {
        if (power >> j & 1) != 0 {
            product *= current.clone();
        }
        current = current.square();
    }
    product
}

[keroro520]

1. 我之前只看到 alpha_pow_offset = alpha.exp_u64(num_reduced[log_height] as u64);，忽略掉下面调用 reduced_ys: Challenge = dot_product(alpha.powers(), ys.iter().copied()) 了。
2. 我理解的 “重复计算” 是说，这段代码 嵌套了三个循环，从全局的角度看，计算 alpha.exp_u64() 和 alpha.powers() 是有重复工作的。比如改成下面这样能省一些乘法运算：

        // 预先计算的alpha powers
        let alpha_pows = alpha.powers().take(log_global_max_height + 1).collect_vec();
        for (mats, points) in mats_and_points {
            ...
            for (mat, points_for_mat) in izip!(mats, points) {
                for &point in points_for_mat {
                    // 按需取用
                    let alpha_pow_offset = alpha_pows[num_reduced[log_height]]
                    // 按需取用
                    let reduced_ys: Challenge = dot_product(alpha_pows[..ys.len()].iter().cloned(), ys.iter().copied());

[Einstellung]

懂了，确实，不同round之间计算会有重复问题，改一下能提高性能，不知道实际业务中会不会有超级多的round要去算。

[justinzjj]

针对问题2，我认为这是合理的，是可以一定程度的减少资源的浪费。因为对于每个open点来说，通常只有部分矩阵达到较高的高度，全局最大高度可能远超过多数open点的需求。减少这些冗余计算可以降低存储和计算开销。
只需要计算在two_adic_pcs.rs中第469-末尾中提到的即可