如何从零开始编写FRI代码
- lambdaclass
- 发布于 2023-08-19 17:35
- 阅读 7
本文深入探讨了FRI（快速Reed-Solomon交互式Oracle证明）协议，该协议用于证明某个函数接近于低阶多项式，这在构建STARKs等证明系统中非常有用。文章详细解释了FRI协议的原理、实现过程，包括多项式的随机折叠、使用Merkle树进行承诺，以及验证过程，并讨论了该协议的安全性依赖于有限域的大小、哈希函数的安全性以及查询的数量。
介绍
STARKs（可扩展透明知识论证）近年来受到广泛关注，因为它们能够帮助扩展以太坊和其他 L1s。它们提供了一种通过加密证据来保证由不可信方进行的计算的完整性。这种证明的验证速度远快于计算的简单检查，即其他方重新运行整个计算。关键思想是，整个计算可以表示为一个值表和一组必须满足的多项式约束。这组约束可以转换为多项式的商的随机线性组合（形式为，我们将不详细讨论这一转化。有关介绍，请参见 Stark-101 或 我们的博客）
p0(x)=∑kαkck(x)zk(x)p0(x)=∑kαkck(x)zk(x)
其中 ck(x)ck(x) 和 zk(x)zk(x) 是多项式。如果 p0(x)p0(x) 是一个多项式（如果不是，它将是一个有理函数），并且当每个 ck(x)ck(x) 被可整除对应的 zk(x)zk(x) 时，这种情况就会发生。我们如何能够快速地说服验证者，上述的 p0(x)p0(x) 是一个多项式？关键成分是 FRI 协议，下面的部分将涵盖这一点。所展示的代码来自 Stark Platinum Prover。
如果你想了解更多关于 FRI 协议及其属性的信息，我们建议你阅读原始的 STARKs 论文和关于 FRI 低度测试的总结。我们想要感谢 Eli Ben-Sasson 和出色的 Starkware 团队，帮助我们学习该协议并开发证明者。
FRI 背后的想法
FRI 代表快速的 Reed-Solomon 交互式 oracle 接近性证明。它允许我们证明在某个域 D0D0 上给定函数 pp 的评估对应于低度多项式的评估（相对于 D0D0 的大小）。这有什么用？
假设我们想说服某人，我们有一个度为 NN 的多项式 p0p0。我们可以传递 N+1N+1 个系数的所有值或 N+1N+1 个多项式在某个集合上的评估。问题是我们必须传递 N+1N+1 个数字（在 STARKs 中，度 NN 可能很大），证明和验证不会很简短。我们可以通过某种适当的变换来降低多项式的度数，做得更好。我们可以将多项式拆分为奇数和偶数度的幂（我们假设 NN 是奇数，但这并不重要），
p0(x)=p0,e(x2)+xp0,o(x2)p0(x)=p0,e(x2)+xp0,o(x2)
其中
p0,e(x2)=a0+a2x2+a4x4+...+aN−1xN−1p0,e(x2)=a0+a2x2+a4x4+...+aN−1xN−1
和
p0,o(x2)=a1+a3x2+a5x4+...+aNxN−1p0,o(x2)=a1+a3x2+a5x4+...+aNxN−1
我们可以随机折叠这两个部分，得到一个随机的 β0β0，生成度为 (N−1)/2(N−1)/2 的多项式，
p1(y)=(a0+β0a1)+(a2+β0a3)y+...+(aN−1+β0aN)y(N−1)/2p1(y)=(a0+β0a1)+(a2+β0a3)y+...+(aN−1+β0aN)y(N−1)/2
我们可以通过传递所有 (N+1)/2(N+1)/2 个 p1(y)p1(y) 的系数以及一些 p0(x)p0(x) 的评估来证明我们有一个多项式，以表明我们从 p0(x)p0(x) 正确推导出 p1(y)p1(y)。
当然，为什么我们要停在 (N+1)/2(N+1)/2 个系数上，而不可以通过重复相同的策略进一步减少系数数量呢？
p1(y)=p1,e(y2)+yp1,o(y2)p1(y)=p1,e(y2)+yp1,o(y2)
其中
p1,e(y2)=b0+b2y2+b4y4+...+bMyM−1p1,e(y2)=b0+b2y2+b4y4+...+bMyM−1
和
p1,o(y2)=b1+b3y2+b5y4+...+bMyM−1p1,o(y2)=b1+b3y2+b5y4+...+bMyM−1
然后，我们随机采样 β1β1 并折叠
p2(z)=(b0+β1b1)+(b2+β1b3)z+...+(bM−1+β1aM)z(M−1)/2p2(z)=(b0+β1b1)+(b2+β1b3)z+...+(bM−1+β1aM)z(M−1)/2
我们可以这样操作，并在每一步将多项式的度数减半。经过 log2(N)log2(N) 次步骤后，我们到达一个常数多项式，只需传递该值。如果我们能够进行这些折叠并最终到达最后的常数值，我们就可以被说服，认为我们得到了一个多项式。
以下是用于在 Lambdaworks 中折叠多项式的 Rust 代码：
pub fn fold_polynomial<F>(
poly: &Polynomial<FieldElement<F>>,
beta: &FieldElement<F>,
) -> Polynomial<FieldElement<F>>
where
F: IsField,
{
let coef = poly.coefficients();
let even_coef: Vec<FieldElement<F>> = coef.iter().step_by(2).cloned().collect();
// poly 的奇数系数乘以 beta
let odd_coef_mul_beta: Vec<FieldElement<F>> = coef
.iter()
.skip(1)
.step_by(2)
.map(|v| (v.clone()) * beta)
.collect();
let (even_poly, odd_poly) = Polynomial::pad_with_zero_coefficients(
&Polynomial::new(&even_coef),
&Polynomial::new(&odd_coef_mul_beta),
);
even_poly + odd_poly
}
多项式 poly 是一个变量，包含作为字段元素向量的多项式系数。在第 9 行中，我们收集偶数度系数的值，在第 12 到 17 行中，我们取所有奇数度系数并将它们乘以 ββ（我们还可以通过压缩迭代器来提高效率，避免收集结果，然后再次迭代数组以添加值）。
问题是我们需要确保多项式不能被改变以生成随机值。将我们绑定到多项式的一种方式是根据在适当域上的多项式评估构建一个 Merkle tree（这就是 Reed-Solomon 代码发挥作用的部分）。我们取域 D0=ω,ωg,ωg2,...,ωgαN−1D0=ω,ωg,ωg2,...,ωgαN−1，其中 gg 是 αNαN 的单位根的生成元素，ωω 是在 gg 的幂产生的集合之外的一个元素。这样，我们被迫仅提供树中的值；该方案的安全性依赖于用于构建树的哈希函数的碰撞抗性。在每个折叠步骤中，我们都将创建一层，包含多项式评估的值及其对应的 Merkle tree。使用 D0D0 作为域的一个优势是，当我们考虑域 D1D1 对于 y=x2y=x2 时，其大小恰好是 D0D0 大小的一半。因此，p1(y)p1(y) 的树的大小将小于对应于 p0(x)p0(x) 的树的大小（这是单位根的一个属性，当 nn 是 2 的幂时。如果 x0x0 在集合中，那么 −x0−x0 也在，且 x20=(−x0)2=x20x02=(−x0)2=x02，因此我们只有 n/2n/2 个不同元素）。
FRI 还可用于使用 Merkle trees 创建多项式的承诺方案。如果我们想向某人表明我们有一个低度多项式 p(x)p(x)，使得 p(z)=vp(z)=v，我们可以评估以下商，
q(x)=p(x)−vx−zq(x)=p(x)−vx−z
并对该商应用 FRI 协议，以表明它确实是一个低度多项式。
创建 FRI 层
如前所述，我们需要将自己提交给我们的多项式，我们将通过在适当域上的评估创建 Merkle tree 来做到这一点。下面我们提供 FriLayer 的基本结构：一个评估向量和一个 Merkle tree（我们添加 coset 偏移量 ωω 和域大小仅为方便）。
#[derive(Clone)]
pub struct FriLayer<F>
where
F: IsField,
FieldElement<F>: ByteConversion,
{
pub evaluation: Vec<FieldElement<F>>,
pub merkle_tree: FriMerkleTree<F>,
pub coset_offset: FieldElement<F>,
pub domain_size: usize,
}
impl<F> FriLayer<F>
where
F: IsField + IsFFTField,
FieldElement<F>: ByteConversion,
{
pub fn new(
poly: &Polynomial<FieldElement<F>>,
coset_offset: &FieldElement<F>,
domain_size: usize,
) -> Self {
let evaluation = poly
.evaluate_offset_fft(1, Some(domain_size), coset_offset)
.unwrap();
let merkle_tree = FriMerkleTree::build(&evaluation);
Self {
evaluation,
merkle_tree,
coset_offset: coset_offset.clone(),
domain_size,
}
}
}
我们还提供了一种根据多项式、域大小和域偏移量创建层的方法。稍后将与折叠函数结合以创建新多项式并获取不同层。
给定多项式，我们可以使用 FFT 高效地评估它（由于我们使用的特定结构）并获得字段元素的向量，如第 23 行所示。在第 27 行，我们根据评估向量构建 Merkle tree（如果你想了解更多关于 Merkle tree 背后的工作原理，请参见这里）。在下一部分中，我们将展示如何构建并提交所有 FRI 层。在此阶段之后，我们可以证明我们已承诺给一个低度多项式。
FRI 承诺阶段
现在我们能够折叠多项式并构建层，我们可以对每一层进行承诺，并获取 FRI 协议的第一部分。承诺阶段将给我们一个层的向量和 FRI 协议的最终值（当我们到达零度多项式时）。该函数需要接收层的数量（可以从多项式的度数中获得）、以系数形式表示的多项式、协议的记录（我们将在此处附加 Merkle trees 的根，并使用此生成 Fiat-Shamir 转换的随机挑战）、偏移量和域大小（我们可以给出域 D0D0，而不是这最后两个）。域大小决定单位根组的大小，而偏移量则允许我们移动该组。
pub fn fri_commit_phase<F: IsField + IsFFTField, T: Transcript>(
number_layers: usize,
p_0: Polynomial<FieldElement<F>>,
transcript: &mut T,
coset_offset: &FieldElement<F>,
domain_size: usize,
) -> (FieldElement<F>, Vec<FriLayer<F>>)
where
FieldElement<F>: ByteConversion,
{
let mut domain_size = domain_size;
let mut fri_layer_list = Vec::with_capacity(number_layers);
let mut current_layer = FriLayer::new(&p_0, coset_offset, domain_size);
fri_layer_list.push(current_layer.clone());
let mut current_poly = p_0;
// >>>> 发送承诺: [p₀]
transcript.append(¤t_layer.merkle_tree.root);
let mut coset_offset = coset_offset.clone();
for _ in 1..number_layers {
// <<<< 接收挑战 𝜁ₖ₋₁
let zeta = transcript_to_field(transcript);
coset_offset = coset_offset.square();
domain_size /= 2;
// 计算层多项式和域
current_poly = fold_polynomial(¤t_poly, &zeta);
current_layer = FriLayer::new(¤t_poly, &coset_offset, domain_size);
let new_data = ¤t_layer.merkle_tree.root;
fri_layer_list.push(current_layer.clone()); // TODO: 移除此 clone
// >>>> 发送承诺: [pₖ]
transcript.append(new_data);
}
// <<<< 接收挑战: 𝜁ₙ₋₁
let zeta = transcript_to_field(transcript);
let last_poly = fold_polynomial(¤t_poly, &zeta);
let last_value = last_poly
.coefficients()
.get(0)
.unwrap_or(&FieldElement::zero())
.clone();
// >>>> 发送值: pₙ
transcript.append(&last_value.to_bytes_be());
(last_value, fri_layer_list)
}
我们首先创建第一个多项式的层（在 STARK 证明者的上下文中，这是 DEEP 组合多项式），位于第 14 行。然后，我们通过附加根到交换记录中来承诺多项式评估，使用 Merkle tree 进行承诺（第 18 行）。
之后，我们继续进行 FRI 的递归部分：我们抽样随机系数（代码中的 ζζ，第 24 行），我们平方偏移量并减少域大小（这样我们就可以生成下一个评估域），并在第 29 行中折叠多项式。我们获得新层（第 30 行），将根添加到交换记录中（以便我们承诺新多项式的评估），并将新层添加到 FriLayers 向量中。在我们经过递归部分之后，我们再折叠一次，以到达零度多项式并获取最终值，我们也将其附加到交换记录中（第 50 行）。
FRI 解承诺
现在我们创建了所有的承诺，我们需要生成证明，以便验证者可以检查一切是否正确。我们能传递给验证者的唯一是通过使用 Merkle trees 承诺的值。树中的任何评估都可以通过先前层中树内的评估来计算。我们可以看到：
p0,e(x)=p0(x)+p0(−x)2p0,e(x)=p0(x)+p0(−x)2
和
p0,o(x)=p0(x)−p0(−x)2xp0,o(x)=p0(x)−p0(−x)2x
幸运的是，如果 p0(x0)p0(x0) 在 Merkle tree 中，则 p0(−x0)p0(−x0) 也在，因为我们选择了域 D0D0 的方式。我们可以看到，
p1(x20)=p0(x0)+p0(−x0)2+β0(p0(x0)−p0(−x0))2x0p1(x02)=p0(x0)+p0(−x0)2+β0(p0(x0)−p0(−x0))2x0
同样，
pk(w20)=pk−1(w0)+pk−1(−w0)2+β0(pk−1(w0)−pk−1(−w0))2w0pk(w02)=pk−1(w0)+pk−1(−w0)2+β0(pk−1(w0)−pk−1(−w0))2w0
因此，如果我们传递来自前一层树中的两个值（这些必须是正确的对，得益于评估域的结构，它们总是按树的大小的一半分开），我们就可以检查树中的一个值。
我们将让验证者选择 Merkle tree 中的索引 p0(x)p0(x)。我们将为验证者提供 p0(x0)p0(x0) 的值（其中 x0x0 是与验证者选择的索引对应的域中的点）和 p0(−x0)p0(−x0)、p1(x20)p1(x02)、p1(−(x20))p1(−(x02)、p2(x40)p2(x04)、p2(−(x40))p2(−(x04))，一直到 pN−1(x2N−10)pN−1(x02N−1)、pN−1(−(x2N−10))pN−1(−(x02N−1))。通过这种方式，验证者可以从第一个多项式到最终值，并检查我们是否正确执行了一切。我们还必须向他展示我们传递的值属于其相应的 Merkle tree。我们将通过为每个值提供包含证明来做到这一点。若包含证明和层间的计算通过，验证者将相信我们在一个点上正确进行了操作。然而，仅通过一个点的测试并不意味着函数确实是一个多项式，因为 FRI 具有统计性质。当然，验证者可以选择更多的点，如果对于所有点测试通过，验证者可以以高概率相信函数确实是一个多项式。我们将称每个验证者选择的点为查询（查询的数量越多，证明者被抓到欺诈的可能性越大）。
为了更好地处理每个查询，我们将拥有一个 FriDecommitment 结构，包含所有评估对（layers_evaluations 和 layers_evaluations_sym）和每个的认证路径（layers_auth_paths 和 layers_auth_paths_sym）。
pub struct FriDecommitment<F: IsPrimeField> {
pub layers_auth_paths_sym: Vec<Proof<Commitment>>,
pub layers_evaluations_sym: Vec<FieldElement<F>>,
pub layers_auth_paths: Vec<Proof<Commitment>>,
pub layers_evaluations: Vec<FieldElement<F>>,
}
我们现在可以跳到协议的查询阶段，并获得 FRI 协议的证明。由于我们希望协议是非交互式的，我们需要记录（通过 Fiat-Shamir 转换来模拟验证者），所有来自 FriLayers 的信息，和其他参数，例如查询的数量（包含在 air 中）。
pub fn fri_query_phase<F, A, T>(
air: &A,
domain_size: usize,
fri_layers: &Vec<FriLayer<F>>,
transcript: &mut T,
) -> (Vec<FriDecommitment<F>>, Vec<usize>)
where
F: IsFFTField,
A: AIR<Field = F>,
T: Transcript,
FieldElement<F>: ByteConversion,
{
if !fri_layers.is_empty() {
let number_of_queries = air.options().fri_number_of_queries;
let iotas = (0..number_of_queries)
.map(|_| (transcript_to_u32(transcript) as usize) % domain_size)
.collect::<Vec<usize>>();
let query_list = iotas
.iter()
.map(|iota_s| {
// <<<< 接收挑战 𝜄ₛ (iota_s)
let mut layers_auth_paths_sym = vec![];
let mut layers_evaluations_sym = vec![];
let mut layers_evaluations = vec![];
let mut layers_auth_paths = vec![];
for layer in fri_layers {
// 对称元素
let index = iota_s % layer.domain_size;
let index_sym = (iota_s + layer.domain_size / 2) % layer.domain_size;
let evaluation_sym = layer.evaluation[index_sym].clone();
let auth_path_sym = layer.merkle_tree.get_proof_by_pos(index_sym).unwrap();
let evaluation = layer.evaluation[index].clone();
let auth_path = layer.merkle_tree.get_proof_by_pos(index).unwrap();
layers_auth_paths_sym.push(auth_path_sym);
layers_evaluations_sym.push(evaluation_sym);
layers_evaluations.push(evaluation);
layers_auth_paths.push(auth_path);
}
FriDecommitment {
layers_auth_paths_sym,
layers_evaluations_sym,
layers_evaluations,
layers_auth_paths,
}
})
.collect();
(query_list, iotas)
} else {
(vec![], vec![])
}
}
在第 15 行中，我们对属于 p0(x)p0(x) 的 Merkle tree 进行所有索引的抽样。我们通过域大小进行规范化，以确保查询落在范围内。一旦我们获取所有查询的索引，我们就可以按行 18 进行迭代（在这种情况下，我们也可以并行执行）。对于每个索引，我们将遍历每个 FriLayer 并获取 pk(u)pk(u) 和 pk(−u)pk(−u) 的索引（这是通过计算当前索引和 FriLayer 的域大小之间的余数来完成的），如第 29 行和第 30 行，然后获取 Merkle tree 中叶子的值（第 31 行和第 33 行），以及相应的认证路径（第 32 行和第 34 行）。然后我们将每个添加到包含评估和每个查询的认证路径的向量中。最后，我们获得完整的查询列表和所有必要的值。
验证
如果验证者想检查我们的工作，他需要执行包含证明（以查看所有值是否属于 Merkle trees）以及每一层是从前一层中获取的，直到我们达到零度。由于该协议是以非交互方式完成的，验证者必须重放所有随机的 βkβk。我们将仅专注于 FRI 部分，但请记住，在一般的 STARK 证明者中，我们在此之前还有更多的工作：
let merkle_roots = &proof.fri_layers_merkle_roots;
let zetas = merkle_roots
.iter()
.map(|root| {
// <<<< 接收承诺: [pₖ] （第一个是 [p₀]）
transcript.append(root);
// >>>> 发送挑战 𝜁ₖ
transcript_to_field(transcript)
})
.collect::<Vec<FieldElement<F>>>();
// <<<< 接收值: pₙ
transcript.append(&proof.fri_last_value.to_bytes_be());
// 接收磨光值
// 1) 从交换记录接收挑战
let transcript_challenge = transcript.challenge();
let nonce = proof.nonce;
let leading_zeros_count =
hash_transcript_with_int_and_get_leading_zeros(&transcript_challenge, nonce);
transcript.append(&nonce.to_be_bytes());
// FRI 查询阶段
// <<<< 发送挑战 𝜄ₛ (iota_s)
let iota_max: usize = 2_usize.pow(domain.lde_root_order);
let iotas: Vec<usize> = (0..air.options().fri_number_of_queries)
.map(|_| (transcript_to_u32(transcript) as usize) % iota_max)
.collect();
验证者逐一将每个 Merkle tree 的根附加到交换记录中，并获取 βkβk 的值（第 2 到 11 行）。然后，验证者添加 FRI 协议的最终值（第 14 行）；如果有工作证明，在验证者检查提供的 nonce 是否正确（在前面完成）后，他将其添加到交换记录并抽样所有索引。
通过这样，验证者可以继续检查所有查询，
fn verify_fri<F, A>(
proof: &StarkProof<F>,
domain: &Domain<F>,
challenges: &Challenges<F, A>,
) -> bool
where
F: IsFFTField,
FieldElement<F>: ByteConversion,
A: AIR<Field = F>,
{
// 验证 FRI
let two_inv = &FieldElement::from(2).inv();
let mut evaluation_point_inverse = challenges
.iotas
.iter()
.map(|iota| &domain.lde_roots_of_unity_coset[*iota])
.cloned()
.collect::<Vec<FieldElement<F>>>();
FieldElement::inplace_batch_inverse(&mut evaluation_point_inverse);
proof
.query_list
.iter()
.zip(&challenges.iotas)
.zip(evaluation_point_inverse)
.fold(true, |mut result, ((proof_s, iota_s), eval)| {
//这是常数时间完成的
result &= verify_query_and_sym_openings(
proof,
&challenges.zetas,
*iota_s,
proof_s,
domain,
eval,
two_inv,
);
result
})
}
在这个函数中，验证者接收所有的 FriDecommitment（包含在 StarkProof 中），域 D0D0（其中包含所有评估点）和通过重放证明者行为采样的挑战（索引）。第 12 至 19 行仅是性能优化，验证者以批量计算评估点的逆（这样计算除法会更高效）。然后，验证者检查每个查询。函数 verify_query_and_sym_openings 有以下代码：
fn verify_query_and_sym_openings<F: IsField + IsFFTField>(
proof: &StarkProof<F>,
zetas: &[FieldElement<F>],
iota: usize,
fri_decommitment: &FriDecommitment<F>,
domain: &Domain<F>,
evaluation_point: FieldElement<F>,
two_inv: &FieldElement<F>,
) -> bool
where
FieldElement<F>: ByteConversion,
{
let fri_layers_merkle_roots = &proof.fri_layers_merkle_roots;
let evaluation_point_vec: Vec<FieldElement<F>> =
core::iter::successors(Some(evaluation_point), |evaluation_point| {
Some(evaluation_point.square())
})
.take(fri_layers_merkle_roots.len())
.collect();
let mut v = fri_decommitment.layers_evaluations[0].clone();
// 对每个 fri layer merkle proof 进行检查：
// 验证每个 merkle 路径
// 使用 fiat shamir 抽样 beta
// 计算 v = [P_i(z_i) + P_i(-z_i)] / 2 + beta * [P_i(z_i) - P_i(-z_i)] / (2 * z_i)
// 其中 P_i 是第 i 的 fiat shamir 轮次的折叠多项式
// z_i 通过已知计算从第一个 z （通过 Fiat-Shamir 推导）获得
// 计算是给定索引，index % length_of_evaluation_domain
// 检查 v = P_{i+1}(z_i)
// 对于每个 (merkle_root, merkle_auth_path) / 折叠
// 认证路径包含该元素，证明其存在
fri_layers_merkle_roots
.iter()
.enumerate()
.zip(&fri_decommitment.layers_auth_paths)
.zip(&fri_decommitment.layers_evaluations)
.zip(&fri_decommitment.layers_auth_paths_sym)
.zip(&fri_decommitment.layers_evaluations_sym)
.zip(evaluation_point_vec)
.fold(
true,
|result,
(
(((((k, merkle_root), auth_path), evaluation), auth_path_sym), evaluation_sym),
evaluation_point_inv,
)| {
let domain_length = 1 << (domain.lde_root_order - k as u32);
let layer_evaluation_index_sym = (iota + domain_length / 2) % domain_length;
// 由于我们总是从前一层派生当前层
// 我们从第二层开始跳过第一层，因此前一层是第一层
// 当前层的评估域长度。
// 我们需要知道当前层的解承诺索引，以便可以在正确索引处检查 Merkle 路径。
// 验证打开 Open(pₖ(Dₖ), −𝜐ₛ^(2ᵏ))
let auth_sym = &auth_path_sym.verify::<FriMerkleTreeBackend<F>>(
merkle_root,
layer_evaluation_index_sym,
evaluation_sym,
);
// 验证打开 Open(pₖ(Dₖ), 𝜐ₛ)
let auth_point =
auth_path.verify::<FriMerkleTreeBackend<F>>(merkle_root, iota, evaluation);
let beta = &zetas[k];
// v 是共线性检查计算出的元素
v = (&v + evaluation_sym) * two_inv
+ beta * (&v - evaluation_sym) * two_inv * evaluation_point_inv;
// 检查下一个值是否由证明者提供
if k < fri_decommitment.layers_evaluations.len() - 1 {
let next_layer_evaluation = &fri_decommitment.layers_evaluations[k + 1];
result & (v == *next_layer_evaluation) & auth_point & auth_sym
} else {
result & (v == proof.fri_last_value) & auth_point & auth_sym
}
},
)
}
每一步，我们必须除以 x2k0x02k，这与乘以（乘法）逆相同。我们之前预先计算了 x−10x0−1，所有其他的逆可以通过反复平方法来计算（第 14 行到 19 行）。然后，验证者可以遍历所有的 FriLayers。我们将使用折叠迭代器以实现常时间实现（第 35 行到 43 行）。如果任何检查为假，则证明将失败。验证者为当前层采样索引（第 51 行）。然后，验证者检查这些值的包含证明（第 59 行和第 65 行）。接着，验证者计算来自当前层的下一个层的值（第 69-70 行）。如果我们不在最后一层，验证者检查计算出的值与下一个层的解承诺中的值是否相等（第 73-75 行）；如果未通过该测试，测试将失败。如果是最后一层，验证者将计算值与 FRI 协议的最后值进行比较。
安全性
FRI 的安全性取决于有限域的大小、哈希函数的安全性和查询的数量。让我们逐一讨论每个方面：
- 有限域的大小应远大于多项式的度数（在 STARK 证明者中与轨迹长度相关）。为了实现 128 位的安全性，域大小应至少为 21282128。如果最大轨迹长度为 230230，则域大小应至少为 21582158。如果基域大小不够大，我们可以在随机挑战采样时处理扩展。一些常见的选择是 StarkPrime 252，素数 264−232+1264−232+1（通常被误称为 MiniGoldilocks，使用度数为 3 的扩展域），BabyBear 或 Mersenne 31（231−1231−1，使用度数为 6 的扩展）。
- 哈希函数提供的安全性应至少达到我们目标的安全级别。对于 SHA2、SHA3、Blake2、Blake3 和 Poseidon 等哈希函数，安全性简单地是摘要（哈希）大小除以二。因此，使用 32 字节（256 位）的摘要可以达到所需的安全级别。如果我们想保护自己免受量子计算机的 Grover 算法攻击，我们需要将摘要大小加倍到 64 字节（512 位）。这会增加证明的大小。
- 查询的数量。每个查询提供一定量的安全位，具体取决于使用的膨胀因子。通过在证明者协议中引入工作证明，可以减少查询数量，从而增加生成虚假证明的成本。在所使用的膨胀因子（这将增加证明者的工作和内存使用）与查询数量（这将增加证明大小和验证者的工作）之间存在权衡。
有关 FRI 安全性的更多讨论，请参见 EthSTARK、关于 FRI 低度测试的总结和FRI 的 Fiat-Shamir 安全性。
总结
FRI 是一个接近性测试，允许我们展示特定函数接近于低度多项式，这是构建证明系统（如 STARKs 或 Plonky2）的有用工具。
在这篇文章中，我们介绍了如何从头编码协议（除了必要的 Merkle trees 和有限域算术）以及如何验证 FRI 证明。该协议包括随机折叠多项式并通过使用 Merkle trees 对适当域上的多项式评估进行承诺，直到得到零度多项式。为了表明协议正确执行，证明者必须提供每个多项式的评估并证明这些值在 Merkle tree 中。该协议的安全性依赖于哈希函数的特性，并依赖于域的大小、摘要的大小和使用的查询数量。
我们采访了开发 Iroh 的团队，Iroh 是一个运行良好的 Rust 点对点库。
简介\ \ 交互式证明是两方之间的协议，证明者 PP 和验证者 VV，证明者尝试说服验证者某个陈述的有效性。通过利用随机性和交互，验证者可以比完全做所有事情更有效地检查该陈述。
- 原文链接： blog.lambdaclass.com/how...
- 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～
