有人知道怎么理解risc0中的fri fold的工程代码吗？

[nihaoqingtuan]

#include "fp.h"
#include "fp4.h"

constexpr size_t kFriFold = 16;

/// Compute `ceil(log_2(in))`, i.e. find the smallest value `out` such that `2^out >= in`.
__device__ inline constexpr size_t log2Ceil(size_t in) {
  size_t r = 0;
  while ((1 << r) < in) {
    r++;
  }
  return r;
}

extern "C" __global__
void fri_fold(Fp* out,
              const Fp* in,
              const Fp4& mix,
              const uint32_t count) {
  uint idx = blockIdx.x * blockDim.x + threadIdx.x;
  if (idx < count) {
    Fp4 tot;
    Fp4 curMix(1);
    for (uint32_t i = 0; i < kFriFold; i++) {
      size_t rev_i = __brev(i) >> (32 - log2Ceil(kFriFold));
      size_t rev_idx = rev_i * count + idx;
      Fp4 factor(in[0 * count * kFriFold + rev_idx],
                 in[1 * count * kFriFold + rev_idx],
                 in[2 * count * kFriFold + rev_idx],
                 in[3 * count * kFriFold + rev_idx]);
      tot += curMix * factor;
      curMix *= mix;
    }
    for (size_t i = 0; i < 4; i++) {
      out[count * i + idx] = tot.elems[i];
    }
  }
}

[nihaoqingtuan]

我贴的是它的cuda代码

[dajuguan]

这里做的是FRI的low degree testing，基本的原理就是对代码中的每个in(采用的FP4表示的，估计与机器最多是64位有关)，乘上一个随机数
$curMix =factor^n$, 最后输出结果out用于验证。
具体可参考如下解释:

参考文献:

• Dokchitser, Tim, and Alexandr Bulkin. "Zero Knowledge Virtual Machine step by step." Cryptology ePrint Archive (2023).
• Introduction to ZK-STARKs

[nihaoqingtuan]

感谢。我知道这是为了低度测试，只是看risc0文档的手写stark中，理论写的是将多项式分为奇偶项然后mix一下形成新的多项式。(https://dev.risczero.com/proof-system/stark-by-hand#round-1-of-fri-commit-phase)
但是我看这个工程代码，不是很能理解怎么做的分成两个多项式。这里采用的是点值表示来计算的吗？我看risc0的教程的Python实现，里面就是转成系数表示来分成奇偶两项操作。

python代码：
`def split(block, large_domain):
small_domain = large_domain.evaluation_domain_of_half_size
# Re-write block as a galois array
block = _finite_field_array(block)
evalmatrix_inv = np.linalg.inv(
_finite_field_array(large_domain.as_vandermonde_matrix())
)

# Given a block u, we construct smaller blocks v_0, v_1

# The defining relationship between u and v_i is easy to state in coefficient representation:
#   Writing u_bar as the coefficient form of u, and v_bar_i as the coefficient form of v_i, we write:
#   u_bar(x) = v_bar_0(x^2) + (x * v_bar_1(x^2))
# We compute the coefficients of v_bar_0 and v_bar_1 through the following matrix multiplication:
# _finite_field_array is the finite field of order _field_size:

# Computing coefficient form of input:
u_bar = evalmatrix_inv @ block

# Writing coefficients of output polynomials:
v_bar_0 = extendarray(
    [u_bar[2 * i] for i in range(len(u_bar) // 2)], len(small_domain.domain)
)
v_bar_1 = extendarray(
    [u_bar[1 + 2 * i] for i in range(len(u_bar) // 2)], len(small_domain.domain)
)

# Computing output blocks
v_0 = small_domain.evaluate(v_bar_0)
v_1 = small_domain.evaluate(v_bar_1)
return [v_0, v_1]`

[dajuguan]

我觉得这里只是提供了一个low level的API，实际上是奇偶分别fold的，参见代码

PS:提问时请注意格式，并附上链接，比如你提到的python实现和fold_fri的代码链接等，这样可以更快地让其他人定位到你的问题。我其实已经帮你修改了你的提问和comment哈

[nihaoqingtuan]

应该不是。我刚了解到这里的折叠因子是16，这个教程(https://dev.risczero.com/proof-system/stark-by-hand#round-1-of-fri-commit-phase)中的折叠因子是2，然后就以奇偶的方式来教学。实际工程的代码应该不是分奇偶。