首届Lambda-Ingo ZK CTF：使用LambdaWorks的ZK挑战

lambdaclass
发布于 2023-07-31 11:52
阅读 10

本文介绍了在Lambda-Ingo ZK CTF比赛中提出的挑战及其解决方案，包括Plonk中的常见攻击（frozen heart和缺乏blinding polynomials）以及利用FRI生成伪造证明或从witness中恢复信息。作者还提到将在Lambdaworks exercises repo中添加更多练习和案例研究，以便人们学习构建证明系统以及在实现中可能出现的一些常见陷阱和漏洞。

## 介绍

从 7 月 14 日到 16 日，我们与 [Ingonyama](https://www.ingonyama.com/) 合作组织了 [首届 Lambda-Ingo ZK 夺旗赛](https://ctf.ingonyama.com/) (CTF)， 超过 60 支队伍和 160 人参与。CTF 涉及多个与零知识证明（使用 [Lambdaworks](https://github.com/lambdaclass/lambdaworks)）和全同态加密相关的挑战。我们对整个经历感到非常兴奋，尤其是我们与 Ingonyama 的第二次合作以及巴黎 Lambda ZK 周的所有赞助商。

这些挑战旨在作为示例练习，以学习如何使用 Lambdaworks（尤其是 [Starknet Stack](https://github.com/lambdaclass/starknet_stack_prover_lambdaworks) 和 [Plonk](https://github.com/lambdaclass/lambdaworks_plonk_prover) prover)），并了解这些系统中可能出现的不同漏洞和错误。如果你想了解更多关于库的开发信息或希望做出贡献，请加入我们的 [telegram 群组](https://t.me/+98Whlzql7Hs0MDZh)。

这篇文章将介绍我们为 CTF 提交的挑战，并解释如何解决这些挑战。

## Plonk 挑战

有两个与 Plonk 和可能的漏洞相关的挑战：[frozen heart](https://blog.trailofbits.com/2022/04/18/the-frozen-heart-vulnerability-in-plonk/) 和缺少 blinding polynomials。

### Obi-Wan 的搜索

#### 挑战

为了阻止西斯的威胁，Obi-Wan Kenobi 找到了一个（西斯）holocron，它提供了一个关于存在西斯银河铸造厂的零知识证明（使用银河 Plonk）。

据说这个地方包含一些可以帮助银河共和国进行战争的文物。位置由 (x,h,y)(x,h,y) 给出，满足等式 y=x×h+by=x×h+b。

经过一些研究，Obi-Wan 找到了 yy 和 bb 的值（属于西斯传说）。唯一的问题是，即使有了这些知识，他可能也需要很长时间才能找到这个神秘的星球，而共和国的局势已经岌岌可危。

他还与 Holocron 一起，找到了包含用于生成证明的 SRS、prover 和所用电路描述的第二个物品。

他能在为时过晚之前找到铸造厂的位置吗？

所有其他信息都在这个 [repo](https://github.com/lambdaclass/obi_wan_search) 中。

FLAG 格式：XXXX........XXXX flag 由 x 和 h 连接并以十六进制写入组成（例如，x=0x123, h=0x789，flag=123789）

#### 解决方法

这个挑战是找到 witness 变量 xx 和 hh，给定值 yy 和 bb。通常，由于 Plonk 系统具有零知识特性，我们无法访问这些值。但是，在这种情况下，prover 存在一个错误：没有 blinding polynomials，我们可以利用此漏洞来恢复未知数。

PLONK 的第一轮读取如下：

```
用 T 在域 H 上各列的插值多项式计算多项式 a',b',c'。
对 b_1, b_2, b_3, b_4, b_5, b_6 抽样。
设

a := (b_1X + b_2)Z_H + a'

b := (b_3X + b_4)Z_H + b'

c := (b_5X + b_6)Z_H + c'

计算 [a]_1, [b]_1, [c]_1 并将它们添加到 transcript 中。
```

添加到 a′,b′,c′a′,b′,c′ 的 ZHZH 的倍数称为 blindings。在随后的几轮中，多项式 a,b,ca,b,c 在 verifier 选择的点处打开。

多项式 ZHZH 是插值域上的 vanishing polynomials；它们在集合 HH 中的每个点处都等于零。因此，添加该多项式（或任何组合）不会更改 a′a′、b′b′ 和 c′c′ 多项式的值，它们必须满足电路方程。但是，在任何其他点，它们都会添加一些随机性并有助于隐藏这些值。

通过检查挑战的代码，参与者可以在 `circuit.rs` 中找到以下内容。

```rust
/// 电路 `ASSERT y == x * h + b` 的 Witness 生成器
pub fn circuit_witness(
    b: &FrElement,
    y: &FrElement,
    h: &FrElement,
    x: &FrElement,
) -> Witness<FrField> {
    let z = x * h;
    let w = &z + b;
    let empty = b.clone();
    Witness {
        a: vec![
            b.clone(),
            y.clone(),
            x.clone(),
            b.clone(),
            w.clone(),
            empty.clone(),
            empty.clone(),
            empty.clone(),
        ],
        ...
```

此代码表明 prover 构造 VV 矩阵的方式是

| A | B | C |
|---|---|---|
| b | - | - |
| y | - | - |
| x | h | z |
| b | z | w |
| w | y | - |
| - | - | - |
| - | - | - |
| - | - | - |

其中 `-` 是空值。`lambdaworks-plonk` 的 PLONK 实现要求用第一个公共输入填充空值。因此，在本例中，值 `-` 将被 bb 替换。可以直接从挑战的代码中看到这一点。

因此，多项式 a′a′ 是列 `A` 的插值

a′=bL1+yL2+xL3+bL4+wL5+bL6+bL7+bL8,a′=bL1+yL2+xL3+bL4+wL5+bL6+bL7+bL8,

其中 LiLi 是 Lagrange 基的第 ii 个多项式。此外，值 ww 等于 yy。这可以从代码以及 VV 矩阵的最后一行对应于断言电路的实际输出等于声明的输出 yy 这一事实中看出。

在证明过程中，verifier 发送一个 challenge ζζ，prover 会打开多项式 aa 在 ζζ 处的值（及其他值）。由于挑战的实现省略了 blindings，a(ζ)=a′(ζ)a(ζ)=a′(ζ)，我们得到

a(ζ)=bL1(ζ)+yL2(ζ)+xL3(ζ)+bL4(ζ)+yL5(ζ)+bL6(ζ)+bL7(ζ)+bL8(ζ).a(ζ)=bL1(ζ)+yL2(ζ)+xL3(ζ)+bL4(ζ)+yL5(ζ)+bL6(ζ)+bL7(ζ)+bL8(ζ).

此表达式中的所有项对于参与者都是已知的，除了 xx，可以从等式中清除。为此，参与者需要知道如何恢复 challenge 以获得 ζζ，以及如何计算在它处评估的 Lagrange 多项式。

第二个私有输入 hh 可以计算为 h=(y−b)/xh=(y−b)/x。以下代码段恢复 challenge ζζ，计算在 ζζ 处的 Lagrange 多项式，并恢复 xx 和 hh：

```rust=
fn compute_private_input<F, CS>(
    proof: &Proof<F, CS>,
    vk: &VerificationKey<CS::Commitment>,
    public_input: &[FieldElement<F>],
    common_preprocessed_input: &CommonPreprocessedInput<F>,
) -> (FieldElement<F>, FieldElement<F>)
where
    F: IsField,
    CS: IsCommitmentScheme<F>,
    CS::Commitment: Serializable,
    FieldElement<F>: ByteConversion,
{
    // 重新播放交互以恢复 challenge。我们只对 \zeta 感兴趣
    let mut transcript = new_strong_fiat_shamir_transcript::<F, CS>(vk, public_input);
    transcript.append(&proof.a_1.serialize());
    transcript.append(&proof.b_1.serialize());
    transcript.append(&proof.c_1.serialize());
    let _beta = FieldElement::from_bytes_be(&transcript.challenge()).unwrap();
    let _gamma = FieldElement::from_bytes_be(&transcript.challenge()).unwrap();

transcript.append(&proof.z_1.serialize());
    let _alpha = FieldElement::from_bytes_be(&transcript.challenge()).unwrap();

transcript.append(&proof.t_lo_1.serialize());
    transcript.append(&proof.t_mid_1.serialize());
    transcript.append(&proof.t_hi_1.serialize());
    let zeta = FieldElement::from_bytes_be(&transcript.challenge()).unwrap();

// 计算 `x` 和 `h`
    let [b, y] = [&public_input[0], &public_input[1]];
    let n = common_preprocessed_input.n as u64;
    let omega = &common_preprocessed_input.omega;
    let domain = &common_preprocessed_input.domain;
    // 计算 L_1(\zeta)。此多项式在域中的每个点都等于零，
    // 除了第一个点，它等于 unity
    let l1_zeta =
        (zeta.pow(n) - FieldElement::one()) / (&zeta - FieldElement::one()) / FieldElement::from(n);

let mut li_zeta = l1_zeta;
    let mut lagrange_basis_zeta = Vec::new();
    lagrange_basis_zeta.push(li_zeta.clone());
    // 使用它们之间的关系计算所有其他 Lagrange 多项式
    for i in 1..domain.len() {
        li_zeta = omega * &li_zeta * ((&zeta - &domain[i - 1]) / (&zeta - &domain[i]));
        lagrange_basis_zeta.push(li_zeta.clone());
    }
    // 通过关联 \zeta 处的 a 和公共输入来恢复 x

let x = (&proof.a_zeta
        - b * &lagrange_basis_zeta[3]
        - y * &lagrange_basis_zeta[4]
        - b * &lagrange_basis_zeta[0]
        - y * &lagrange_basis_zeta[1]
        - b * &lagrange_basis_zeta[5]
        - b * &lagrange_basis_zeta[6]
        - b * &lagrange_basis_zeta[7])
        / &lagrange_basis_zeta[2];
    // 假设 x 已知，则恢复 h
    let h = (y - b) / &x;
    (x, h)
}
```

坐标的解决方案是：

1. `x: "2194826651b32ca1055614fc6e2f2de86eab941d2c55bd467268e9"`,
2. `h: "432904cca36659420aac29f8dc5e5bd0dd57283a58ab7a8ce4d1ca"`.

flag 是两者的连接：`FLAG: 2194826651b32ca1055614fc6e2f2de86eab941d2c55bd467268e9432904cca36659420aac29f8dc5e5bd0dd57283a58ab7a8ce4d1ca`

### Loki 的活板门

#### 挑战

成功闯入 Loki 的金库并获得他最珍贵的宝藏和武器后，你发现地毯下有一个小活板门。

活板门被锁住，里面装有一个带有 PLONK prover 的设备。上面写着：证明点 (1,y)(1,y) 属于椭圆曲线 y2=x3+4y2=x3+4。

你看到为了证明这一点，你需要 y2−x3−4y2−x3−4 等于零，这对应于 Loki 提供的 prover 电路。

你能打开活板门吗？

nc 44.203.113.160 4000

其他信息在此 [repo](https://github.com/ingonyama-zk/ZKCTF-lokis-trapdoor)。

FLAG 格式：ZKCTF{XXX...XXX}

#### 解决方法

这个挑战利用了 frozen heart 漏洞，当 Fiat-Shamir 转换未正确实现时会出现此漏洞。主要问题是 (1,y)(1,y) 不是属于 BLS12-381 椭圆曲线的点。如果是这样，y2=13+4=5y2=13+4=5，但 55 不是 BLS12-381 素数的二次剩余。因此，解决挑战的方法必须是创建虚假证明。

电路是：

```
公共输入：x
公共输入：y

ASSERT 0 == y^2 - x^3 - 4
```

它是在 `BLS12 381` 标量域上实例化的。

该漏洞源于 strong Fiat-Shamir 实现中的一个错误。正确的实现应将所有公共输入添加到初始化时的 transcript 中（及其他内容）。如果未将公共输入添加到 transcript 中并且受攻击者控制，他们可以伪造虚假证明。修复 `x=1` 会将 `y` 留给用户控制。我们可以看到 Fiat-Shamir transcript 没有包含公共输入，如 [此处](https://github.com/ingonyama-zk/ZKCTF-lokis-trapdoor/blob/69eba0d41d56a7831b4532d5adc2c21720764885/lambdaworks_plonk_prover/src/setup.rs#L70C1-L73C23) 所示

```rust
pub fn new_strong_fiat_shamir_transcript<F, CS>(
    vk: &VerificationKey<CS::Commitment>,
    _public_input: &[FieldElement<F>],
) -> DefaultTranscript
```

[弱 Fiat-Shamir 对现代证明系统的攻击](https://eprint.iacr.org/2023/691.pdf) 的第 V 节描述了该攻击。

以下是攻击的摘要：

![](https://img.learnblockchain.cn/2026/01/01/B10en9A93.png)

当前的解决方案没有采用随机多项式（步骤 (1) 到 (7)），而是采用 `x=0`、`y=2` 对的有效证明，并使用它为 `x=1` 伪造一个与原始证明兼容的 `y`。

```rust=
##[allow(unused)]
fn forge_y_for_valid_proof<F: IsField, CS: IsCommitmentScheme<F>>(
    proof: &Proof<F, CS>,
    vk: &VerificationKey<CS::Commitment>,
    common_preprocessed_input: CommonPreprocessedInput<F>,
) -> FieldElement<F>
where
    CS::Commitment: Serializable,
    FieldElement<F>: ByteConversion,
{
    // 像 verifier 一样重播交互
    let mut transcript = new_strong_fiat_shamir_transcript::<F, CS>(vk, &[]);

transcript.append(&proof.a_1.serialize());
    transcript.append(&proof.b_1.serialize());
    transcript.append(&proof.c_1.serialize());
    let beta = FieldElement::from_bytes_be(&transcript.challenge()).unwrap();
    let gamma = FieldElement::from_bytes_be(&transcript.challenge()).unwrap();

transcript.append(&proof.z_1.serialize());
    let alpha = FieldElement::from_bytes_be(&transcript.challenge()).unwrap();

transcript.append(&proof.t_lo_1.serialize());
    transcript.append(&proof.t_mid_1.serialize());
    transcript.append(&proof.t_hi_1.serialize());
    let zeta = &FieldElement::from_bytes_be(&transcript.challenge()).unwrap();

// 伪造公共输入
    let zh_zeta = zeta.pow(common_preprocessed_input.n) - FieldElement::one();

let omega = &common_preprocessed_input.omega;
    let n = common_preprocessed_input.n as u64;
    let one = &FieldElement::one();

let l1_zeta = ((zeta.pow(n) - one) / (zeta - one)) / FieldElement::from(n);

let l2_zeta = omega * &l1_zeta * (zeta - one) / (zeta - omega);

let mut p_constant_zeta = &alpha
        * &proof.z_zeta_omega
        * (&proof.c_zeta + &gamma)
        * (&proof.a_zeta + &beta * &proof.s1_zeta + &gamma)
        * (&proof.b_zeta + &beta * &proof.s2_zeta + &gamma);
    p_constant_zeta = p_constant_zeta - &l1_zeta * &alpha * &alpha;

let p_zeta = p_constant_zeta + &proof.p_non_constant_zeta;
    -(p_zeta + l1_zeta * one - (&zh_zeta * &proof.t_zeta)) / l2_zeta
}
```

## STARKs 挑战

### 挑战

早上好，黑客。

如果你正在阅读此内容，则日期应为 2023 年 7 月 7 日，并且你应该正在查看 Lambda-Ingoyama CTF 挑战站点。

希望我们能够劫持该站点，并且你现在正在阅读此内容。我们不允许说太多，但你必须知道赢得这一挑战至关重要。

因此，我们决定提供帮助。不用担心；这应该很容易。我们找到了正确的漏洞来解决，并将解决方案转发给你。

如果出现问题，我们会留下一些我们收集的其他数据。我们不知道是否有帮助，但我们希望它可以提供帮助。

现在由你来获取 flag。祝你好运。

[https://github.com/ingonyama-zk/ZKCTF-ch3-client](https://github.com/ingonyama-zk/ZKCTF-ch3-client)

FLAG 格式：ZKCTF{XXX...XXX}

### 解决方法

这里的关键是 STARK prover 只进行一次查询，这使得可靠性错误非常重要。此漏洞出现在 Lambdaworks 的早期实现中（请参阅此 [PR](https://github.com/lambdaclass/starknet_stack_prover_lambdaworks/pull/66)）， 并由 [Michael Carilli](https://github.com/mcarilli) 发现（我们对此深表感谢）。

第一步是将数据发送到服务器的端点，服务器应回复类似“Expired proof.”的内容。之后，下一步是检查证明。大多数数据将不相关。统计查询次数，我们意识到只有 1 个。现在仍然要看看如何利用它。

需要使用一些额外的数据，例如偏移量、约束和 blowup factor。数据中暗示了偏移量和约束。可以猜测或暗示 blowup factor。

我们现在可以利用 FRI 可靠性错误（对于一个查询来说非常大）来打破 STARK 协议。我们必须首先通过组成多项式和 trace 多项式之间在域外点 zz 处的*一致性检查*。verifier 在 [步骤 2](https://github.com/lambdaclass/starknet_stack_prover_lambdaworks/blob/23eb9df082ec4de4f1d44c6760be4b7a13ea24b1/src/starks/verifier.rs#L208) 中执行此检查。如果我们直接从 trace 多项式计算多项式的值，我们可以自动通过此测试：

```rust
pub fn composition_poly_ood_evaluation_exact_from_trace<F: IsFFTField, A: AIR<Field = F>>(
    air: &A,
    trace_ood_frame_evaluations: &Frame<F>,
    domain: &Domain<F>,
    z: &FieldElement<F>,
    rap_challenges: &A::RAPChallenges,
    boundary_coeffs: &[(FieldElement<F>, FieldElement<F>)],
    transition_coeffs: &[(FieldElement<F>, FieldElement<F>)],
) -> FieldElement<F> {
    let _public_input = air.pub_inputs();
    let boundary_constraints = air.boundary_constraints(rap_challenges);

let n_trace_cols = air.context().trace_columns;

let boundary_constraint_domains =
        boundary_constraints.generate_roots_of_unity(&domain.trace_primitive_root, &[n_trace_cols]);

let values = boundary_constraints.values(&[n_trace_cols]);

// 遵循 https://www.notamonadtutorial.com/diving-deep-fri/ 的命名约定
    let mut boundary_c_i_evaluations = Vec::with_capacity(n_trace_cols);
    let mut boundary_quotient_degrees = Vec::with_capacity(n_trace_cols);

for trace_idx in 0..n_trace_cols {
        let trace_evaluation = &trace_ood_frame_evaluations.get_row(0)[trace_idx];
        let boundary_constraints_domain = &boundary_constraint_domains[trace_idx];
        let boundary_interpolating_polynomial =
            &Polynomial::interpolate(boundary_constraints_domain, &values[trace_idx])
                .expect("xs and ys have equal length and xs are unique");

let boundary_zerofier =
            boundary_constraints.compute_zerofier(&domain.trace_primitive_root, trace_idx);

let boundary_quotient_ood_evaluation = (trace_evaluation
            - boundary_interpolating_polynomial.evaluate(z))
            / boundary_zerofier.evaluate(z);

let boundary_quotient_degree = air.trace_length() - boundary_zerofier.degree() - 1;

boundary_c_i_evaluations.push(boundary_quotient_ood_evaluation);
        boundary_quotient_degrees.push(boundary_quotient_degree);
    }

let trace_length = air.trace_length();

let boundary_term_degree_adjustment = air.composition_poly_degree_bound() - trace_length;

let boundary_quotient_ood_evaluations: Vec<FieldElement<F>> = boundary_c_i_evaluations
        .iter()
        .zip(boundary_coeffs)
        .map(|(poly_eval, (alpha, beta))| {
            poly_eval * (alpha * &z.pow(boundary_term_degree_adjustment) + beta)
        })
        .collect();

let boundary_quotient_ood_evaluation = boundary_quotient_ood_evaluations
        .iter()
        .fold(FieldElement::<F>::zero(), |acc, x| acc + x);

let transition_ood_frame_evaluations =
        air.compute_transition(trace_ood_frame_evaluations, rap_challenges);

let transition_exemptions = air.transition_exemptions();

let x_n = Polynomial::new_monomial(FieldElement::<F>::one(), trace_length);
    let x_n_1 = x_n - FieldElement::<F>::one();

let divisors = transition_exemptions
        .into_iter()
        .map(|exemption| x_n_1.clone() / exemption)
        .collect::<Vec<Polynomial<FieldElement<F>>>>();

let mut denominators = Vec::with_capacity(divisors.len());
    for divisor in divisors.iter() {
        denominators.push(divisor.evaluate(z));
    }
    FieldElement::inplace_batch_inverse(&mut denominators);

let mut degree_adjustments = Vec::with_capacity(divisors.len());
    for transition_degree in air.context().transition_degrees().iter() {
        let degree_adjustment =
            air.composition_poly_degree_bound() - (air.trace_length() * (transition_degree - 1));
        degree_adjustments.push(z.pow(degree_adjustment));
    }
    let transition_c_i_evaluations_sum =
        ConstraintEvaluator::<F, A>::compute_constraint_composition_poly_evaluations_sum(
            &transition_ood_frame_evaluations,
            &denominators,
            &degree_adjustments,
            transition_coeffs,
        );

&boundary_quotient_ood_evaluation + transition_c_i_evaluations_sum
}
```

prover 将组成多项式拆分为*偶次*和*奇次*项，H1(z2)H1(z2) 和 H2(z2)H2(z2)。verifier 必须从 trace 多项式计算 H(z)H(z)，然后检查

H(z)=H1(z2)+zH2(z2)H(z)=H1(z2)+zH2(z2)

我们可以通过确保 verifier 得到 H1(z2)=H(z)H1(z2)=H(z) 和 H2(z2)=0H2(z2)=0 来强制执行此检查。当然，这会在 verifier 的其他部分产生一些问题，例如 DEEP 组成多项式。DEEP 组成多项式允许我们检查所有多项式是否已在 zz 处得到适当评估，

P0(x)=∑jγjtj(x)−tj(z)x−z+∑jγ′jtj(x)−tj(gz)x−gz+γH1(x)−H1(z2)x−z2+γ′H2(x)−H2(z2)x−z2P0(x)=∑jγjtj(x)−tj(z)x−z+∑jγj′tj(x)−tj(gz)x−gz+γH1(x)−H1(z2)x−z2+γ′H2(x)−H2(z2)x−z2

当然，如果我们发送多项式 H1(x2)H1(x2) 和 H2(x2)H2(x2) 的虚假评估，则最后一项将不是低次多项式，并且不应满足 FRI 测试。但是，我们可以精确地评估 (Hk(ωj)−Hk(z2))/(ωj−z2)(Hk(ωj)−Hk(z2))/(ωj−z2) 的值，并通过插值创建一个通过低次测试允许的尽可能多的评估（即 trace 长度）的多项式。以下函数计算 DEEP 组成多项式

```rust=
fn compute_deep_composition_poly_evil<A: AIR, F: IsFFTField>(
    air: &A,
    domain: &Domain<F>,
    trace_polys: &[Polynomial<FieldElement<F>>],
    round_2_result: &Round2<F>,
    round_3_result: &Round3<F>,
    z: &FieldElement<F>,
    primitive_root: &FieldElement<F>,
    composition_poly_gammas: &[FieldElement<F>; 2],
    trace_terms_gammas: &[FieldElement<F>],
) -> Polynomial<FieldElement<F>>
where
    lambdaworks_math::field::element::FieldElement<F>: lambdaworks_math::traits::ByteConversion,
{
    // 计算 deep 组成多项式的组成多项式项。
    let h_1 = &round_2_result.composition_poly_even;
    let h_1_z2 = &round_3_result.composition_poly_even_ood_evaluation;
    let h_2 = &round_2_result.composition_poly_odd;
    let h_2_z2 = &round_3_result.composition_poly_odd_ood_evaluation;
    let gamma = &composition_poly_gammas[0];
    let gamma_p = &composition_poly_gammas[1];
    let z_squared = z.square();

// 𝛾 ( H₁ − H₁(z²) ) / ( X − z² )
    let h_1_term = {
        let x = Polynomial::new_monomial(FieldElement::one(), 1);
        let h_1_num = gamma * (h_1 - h_1_z2);
        let h_1_denom = &x - &z_squared;
        interp_from_num_denom(&h_1_num, &h_1_denom, domain)
    };

// 𝛾' ( H₂ − H₂(z²) ) / ( X − z² )
    let h_2_term = {
        let x = Polynomial::new_monomial(FieldElement::one(), 1);
        let h_2_num = gamma_p * (h_2 - h_2_z2);
        let h_2_denom = &x - &z_squared;
        interp_from_num_denom(&h_2_num, &h_2_denom, domain)
    };

// 获取 deep 组成多项式 trace 项所需的 trace 评估
    let transition_offsets = &air.context().transition_offsets;
    let trace_frame_evaluations = &round_3_result.trace_ood_evaluations;

// 计算所有 deep 组成多项式 trace 项的总和。
    // 对于 trace 多项式中的每个 trace 和帧中的每一行，都有一项。
    // ∑ ⱼₖ [ 𝛾ₖ ( tⱼ − tⱼ(z) ) / ( X − zgᵏ )]

let mut trace_terms = Polynomial::zero();
    for (i, t_j) in trace_polys.iter().enumerate() {
        let i_times_trace_frame_evaluation = i * trace_frame_evaluations.len();
        let iter_trace_gammas = trace_terms_gammas
            .iter()
            .skip(i_times_trace_frame_evaluation);
        for ((evaluations, offset), elemen_trace_gamma) in trace_frame_evaluations
            .iter()
            .zip(transition_offsets)
            .zip(iter_trace_gammas)
        {

let t_j_z = evaluations[i].clone();

let z_shifted = z * primitive_root.pow(*offset);

let mut poly = t_j - t_j_z;
            poly.ruffini_division_inplace(&z_shifted);
            trace_terms = trace_terms + poly * elemen_trace_gamma;
        }
    }

h_1_term + h_2_term + trace_terms
}
```

它使用以下函数进行插值

```rust
pub fn interp_from_num_denom<F: IsFFTField>(
    num: &Polynomial<FieldElement<F>>,
    denom: &Polynomial<FieldElement<F>>,
    domain: &Domain<F>,
) -> Polynomial<FieldElement<F>> {
    let target_deg = domain.lde_roots_of_unity_coset.len() / domain.blowup_factor;
    let num_evals = evaluate_polynomial_on_lde_domain(
        num,
        domain.blowup_factor,
        domain.interpolation_domain_size,
        &domain.coset_offset,
    )
    .unwrap();
    let denom_evals = evaluate_polynomial_on_lde_domain(
        denom,
        domain.blowup_factor,
        domain.interpolation_domain_size,
        &domain.coset_offset,
    )
    .unwrap();
    let evals: Vec<_> = num_evals
        .iter()
        .zip(denom_evals)
        .map(|(num, denom)| num / denom)
        .collect();

Polynomial::interpolate(
        &domain.lde_roots_of_unity_coset[..target_deg],
        &evals[..target_deg],
    )
    .unwrap()
}
```

这样，我们可以选择 nn 个点，假 DEEP 组成多项式将在这些点通过所有测试。由于 verifier 可以在 βnβn 个点中进行选择，因此 prover 有 1/β1/β 的机会通过测试。

我们现在可以创建一个恶意 prover，即使他使用虚假的执行 trace，它也可能会通过 verifier 的检查。修改 Step\_2 以计算精确的组成多项式：
```rust=
fn step_2_evil_eval<F: IsFFTField, A: AIR<Field = F>>(
    air: &A,
    domain: &Domain<F>,
    transition_coeffs: &[(FieldElement<F>, FieldElement<F>)],
    boundary_coeffs: &[(FieldElement<F>, FieldElement<F>)],
    rap_challenges: &A::RAPChallenges,
    z: &FieldElement<F>,
    trace_ood_frame_evaluations: &Frame<F>,
) -> FieldElement<F> {
    // BEGIN TRACE <-> 组合多项式一致性评估检查
    // 这些是 H_1(z^2) 和 H_2(z^2)

let boundary_constraints = air.boundary_constraints(rap_challenges);

//let n_trace_cols = air.context().trace_columns;
    // 特例。
    let trace_length = air.trace_length();
    let composition_poly_degree_bound = air.composition_poly_degree_bound();
    let boundary_term_degree_adjustment = composition_poly_degree_bound - trace_length;
    let number_of_b_constraints = boundary_constraints.constraints.len();

// 遵循来自 https://www.notamonadtutorial.com/diving-deep-fri/ 的命名约定
    let (boundary_c_i_evaluations_num, mut boundary_c_i_evaluations_den): (
        Vec<FieldElement<F>>,
        Vec<FieldElement<F>>,
    ) = (0..number_of_b_constraints)
        .map(|index| {
            let step = boundary_constraints.constraints[index].step;
            let point = &domain.trace_primitive_root.pow(step as u64);
            let trace_idx = boundary_constraints.constraints[index].col;
            let trace_evaluation = &trace_ood_frame_evaluations.get_row(0)[trace_idx];
            let boundary_zerofier_challenges_z_den = z - point;

let boundary_quotient_ood_evaluation_num =
                trace_evaluation - &boundary_constraints.constraints[index].value;

(
                boundary_quotient_ood_evaluation_num,
                boundary_zerofier_challenges_z_den,
            )
        })
        .collect::<Vec<_>>()
        .into_iter()
        .unzip();

FieldElement::inplace_batch_inverse(&mut boundary_c_i_evaluations_den);

let boundary_degree_z = z.pow(boundary_term_degree_adjustment);
    let boundary_quotient_ood_evaluation: FieldElement<F> = boundary_c_i_evaluations_num
        .iter()
        .zip(&boundary_c_i_evaluations_den)
        .zip(boundary_coeffs)
        .map(|((num, den), (alpha, beta))| num * den * (alpha * &boundary_degree_z + beta))
        .fold(FieldElement::<F>::zero(), |acc, x| acc + x);

let transition_ood_frame_evaluations =
        air.compute_transition(trace_ood_frame_evaluations, rap_challenges);

let divisor_x_n = (z.pow(trace_length) - FieldElement::<F>::one()).inv();

let denominators = air
        .transition_exemptions_verifier()
        .iter()
        .map(|poly| poly.evaluate(z) * &divisor_x_n)
        .collect::<Vec<FieldElement<F>>>();

let degree_adjustments = air
        .context()
        .transition_degrees()
        .iter()
        .map(|transition_degree| {
            let degree_adjustment =
                composition_poly_degree_bound - (trace_length * (transition_degree - 1));
            z.pow(degree_adjustment)
        })
        .collect::<Vec<FieldElement<F>>>();

let transition_c_i_evaluations_sum =
        ConstraintEvaluator::<F, A>::compute_constraint_composition_poly_evaluations_sum(
            &transition_ood_frame_evaluations,
            &denominators,
            &degree_adjustments,
            transition_coeffs,
        );

&boundary_quotient_ood_evaluation + transition_c_i_evaluations_sum
}
```

然后，step\_3 更改为

```rust=
fn round_3_evil<F: IsFFTField, A: AIR<Field = F>>(
    air: &A,
    domain: &Domain<F>,
    round_1_result: &Round1<F, A>,
    z: &FieldElement<F>,
    boundary_coeffs: &[(FieldElement<F>, FieldElement<F>)],
    transition_coeffs: &[(FieldElement<F>, FieldElement<F>)],
) -> Round3<F>
where
    FieldElement<F>: ByteConversion,
{
    let trace_ood_evaluations = Frame::get_trace_evaluations(
        &round_1_result.trace_polys,
        z,
        &air.context().transition_offsets,
        &domain.trace_primitive_root,
    );

let (composition_poly_even_ood_evaluation, composition_poly_odd_ood_evaluation) = {
        let trace_ood_frame_evaluations = Frame::new(
            trace_ood_evaluations.iter().flatten().cloned().collect(),
            round_1_result.trace_polys.len(),
        );

let hz_exact_from_trace = step_2_evil_eval(
            air,
            domain,
            transition_coeffs,
            boundary_coeffs,
            &round_1_result.rap_challenges,
            z,
            &trace_ood_frame_evaluations,
        );

(hz_exact_from_trace, FieldElement::<F>::from(0))
    };

Round3 {
        trace_ood_evaluations,
        composition_poly_even_ood_evaluation,
        composition_poly_odd_ood_evaluation,
    }
}
```

最后，round\_4 是

```rust=
fn round_4_evil<F: IsFFTField, A: AIR<Field = F>, T: Transcript>(
    air: &A,
    domain: &Domain<F>,
    round_1_result: &Round1<F, A>,
    round_2_result: &Round2<F>,
    round_3_result: &Round3<F>,
    z: &FieldElement<F>,
    transcript: &mut T,
) -> Round4<F>
where
    FieldElement<F>: ByteConversion,
{
    let coset_offset_u64 = air.context().proof_options.coset_offset;
    let coset_offset = FieldElement::<F>::from(coset_offset_u64);

// <<<< 接收 challenges: 𝛾, 𝛾'
    let composition_poly_coeffients = [\
        transcript_to_field(transcript),\
        transcript_to_field(transcript),\
    ];
    // <<<< 接收 challenges: 𝛾ⱼ, 𝛾ⱼ'
    let trace_poly_coeffients = batch_sample_challenges::<F, T>(
        air.context().transition_offsets.len() * air.context().trace_columns,
        transcript,
    );

// 计算 p₀ (deep composition polynomial)
    let deep_composition_poly = compute_deep_composition_poly_evil(
        air,
        domain,
        &round_1_result.trace_polys,
        round_2_result,
        round_3_result,
        z,
        &domain.trace_primitive_root,
        &composition_poly_coeffients,
        &trace_poly_coeffients,
    );

let domain_size = domain.lde_roots_of_unity_coset.len();

// FRI 提交和查询阶段
    let (fri_last_value, fri_layers) = fri_commit_phase(
        domain.root_order as usize,
        deep_composition_poly,
        transcript,
        &coset_offset,
        domain_size,
    );
    let (query_list, iotas) = fri_query_phase(air, domain_size, &fri_layers, transcript);
    let fri_layers_merkle_roots: Vec<_> = fri_layers
        .iter()
        .map(|layer| layer.merkle_tree.root)
        .collect();

let deep_poly_openings =
        open_deep_composition_poly(domain, round_1_result, round_2_result, &iotas);

// grinding: 生成 nonce 并将其附加到 transcript
    let grinding_factor = air.context().proof_options.grinding_factor;
    let transcript_challenge = transcript.challenge();
    let nonce = generate_nonce_with_grinding(&transcript_challenge, grinding_factor)
        .expect("nonce not found");
    transcript.append(&nonce.to_be_bytes());

Round4 {
        fri_last_value,
        fri_layers_merkle_roots,
        deep_poly_openings,
        query_list,
        nonce,
    }
}
```

这样，我们生成了一个证明，该证明将始终通过 out-of-domain point 一致性检查，并将有很高的概率通过低度测试。

## 总结

这篇文章涵盖了我们在首届 Lambda-Ingo ZK CTF 中提出的挑战及其解决方案。这些挑战涉及对 Plonk 的一些常见攻击（冻结的心脏和缺少 blinding 多项式）和 FRI，以生成虚假证明或从 witness 中恢复信息。我们将在 [Lambdaworks exercises repo](https://github.com/lambdaclass/lambdaworks_exercises/tree/main) 中添加更多练习和案例研究，以便任何人都可以学习如何构建证明系统以及其实现中可能出现的一些常见陷阱和漏洞。我们要再次感谢 Ingonyama 的出色工作以及巴黎 LambdaZK 周的所有赞助商。请继续关注 ZK 的更多挑战！

>- 原文链接： [blog.lambdaclass.com/fir...](https://blog.lambdaclass.com/first-lambda-ingo-zk-ctf-zk-challenges-using-lambdaworks)
>- 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～

介绍

从 7 月 14 日到 16 日，我们与 Ingonyama 合作组织了首届 Lambda-Ingo ZK 夺旗赛 (CTF)，超过 60 支队伍和 160 人参与。CTF 涉及多个与零知识证明（使用 Lambdaworks）和全同态加密相关的挑战。我们对整个经历感到非常兴奋，尤其是我们与 Ingonyama 的第二次合作以及巴黎 Lambda ZK 周的所有赞助商。

这些挑战旨在作为示例练习，以学习如何使用 Lambdaworks（尤其是 Starknet Stack 和 Plonk prover)），并了解这些系统中可能出现的不同漏洞和错误。如果你想了解更多关于库的开发信息或希望做出贡献，请加入我们的 telegram 群组。

这篇文章将介绍我们为 CTF 提交的挑战，并解释如何解决这些挑战。

Plonk 挑战

有两个与 Plonk 和可能的漏洞相关的挑战：frozen heart 和缺少 blinding polynomials。

Obi-Wan 的搜索

挑战

为了阻止西斯的威胁，Obi-Wan Kenobi 找到了一个（西斯）holocron，它提供了一个关于存在西斯银河铸造厂的零知识证明（使用银河 Plonk）。

据说这个地方包含一些可以帮助银河共和国进行战争的文物。位置由 (x,h,y)(x,h,y) 给出，满足等式 y=x×h+by=x×h+b。

他还与 Holocron 一起，找到了包含用于生成证明的 SRS、prover 和所用电路描述的第二个物品。

他能在为时过晚之前找到铸造厂的位置吗？

所有其他信息都在这个 repo 中。

FLAG 格式：XXXX........XXXX flag 由 x 和 h 连接并以十六进制写入组成（例如，x=0x123, h=0x789，flag=123789）

解决方法

PLONK 的第一轮读取如下：

用 T 在域 H 上各列的插值多项式计算多项式 a',b',c'。
对 b_1, b_2, b_3, b_4, b_5, b_6 抽样。
设

a := (b_1X + b_2)Z_H + a'

b := (b_3X + b_4)Z_H + b'

c := (b_5X + b_6)Z_H + c'

计算 [a]_1, [b]_1, [c]_1 并将它们添加到 transcript 中。

添加到 a′,b′,c′a′,b′,c′ 的 ZHZH 的倍数称为 blindings。在随后的几轮中，多项式 a,b,ca,b,c 在 verifier 选择的点处打开。

通过检查挑战的代码，参与者可以在 circuit.rs 中找到以下内容。

/// 电路 `ASSERT y == x * h + b` 的 Witness 生成器
pub fn circuit_witness(
    b: &FrElement,
    y: &FrElement,
    h: &FrElement,
    x: &FrElement,
) -> Witness&lt;FrField> {
    let z = x * h;
    let w = &z + b;
    let empty = b.clone();
    Witness {
        a: vec![
            b.clone(),
            y.clone(),
            x.clone(),
            b.clone(),
            w.clone(),
            empty.clone(),
            empty.clone(),
            empty.clone(),
        ],
        ...

此代码表明 prover 构造 VV 矩阵的方式是

A	B	C
b	-	-
y	-	-
x	h	z
b	z	w
w	y	-
-	-	-
-	-	-
-	-	-

其中 - 是空值。lambdaworks-plonk 的 PLONK 实现要求用第一个公共输入填充空值。因此，在本例中，值 - 将被 bb 替换。可以直接从挑战的代码中看到这一点。

因此，多项式 a′a′ 是列 A 的插值

a′=bL1+yL2+xL3+bL4+wL5+bL6+bL7+bL8,a′=bL1+yL2+xL3+bL4+wL5+bL6+bL7+bL8,

a(ζ)=bL1(ζ)+yL2(ζ)+xL3(ζ)+bL4(ζ)+yL5(ζ)+bL6(ζ)+bL7(ζ)+bL8(ζ).a(ζ)=bL1(ζ)+yL2(ζ)+xL3(ζ)+bL4(ζ)+yL5(ζ)+bL6(ζ)+bL7(ζ)+bL8(ζ).

第二个私有输入 hh 可以计算为 h=(y−b)/xh=(y−b)/x。以下代码段恢复 challenge ζζ，计算在 ζζ 处的 Lagrange 多项式，并恢复 xx 和 hh：

fn compute_private_input&lt;F, CS>(
    proof: &Proof&lt;F, CS>,
    vk: &VerificationKey&lt;CS::Commitment>,
    public_input: &[FieldElement&lt;F>],
    common_preprocessed_input: &CommonPreprocessedInput&lt;F>,
) -> (FieldElement&lt;F>, FieldElement&lt;F>)
where
    F: IsField,
    CS: IsCommitmentScheme&lt;F>,
    CS::Commitment: Serializable,
    FieldElement&lt;F>: ByteConversion,
{
    // 重新播放交互以恢复 challenge。我们只对 \zeta 感兴趣
    let mut transcript = new_strong_fiat_shamir_transcript::&lt;F, CS>(vk, public_input);
    transcript.append(&proof.a_1.serialize());
    transcript.append(&proof.b_1.serialize());
    transcript.append(&proof.c_1.serialize());
    let _beta = FieldElement::from_bytes_be(&transcript.challenge()).unwrap();
    let _gamma = FieldElement::from_bytes_be(&transcript.challenge()).unwrap();

    transcript.append(&proof.z_1.serialize());
    let _alpha = FieldElement::from_bytes_be(&transcript.challenge()).unwrap();

    transcript.append(&proof.t_lo_1.serialize());
    transcript.append(&proof.t_mid_1.serialize());
    transcript.append(&proof.t_hi_1.serialize());
    let zeta = FieldElement::from_bytes_be(&transcript.challenge()).unwrap();

    // 计算 `x` 和 `h`
    let [b, y] = [&public_input[0], &public_input[1]];
    let n = common_preprocessed_input.n as u64;
    let omega = &common_preprocessed_input.omega;
    let domain = &common_preprocessed_input.domain;
    // 计算 L_1(\zeta)。此多项式在域中的每个点都等于零，
    // 除了第一个点，它等于 unity
    let l1_zeta =
        (zeta.pow(n) - FieldElement::one()) / (&zeta - FieldElement::one()) / FieldElement::from(n);

    let mut li_zeta = l1_zeta;
    let mut lagrange_basis_zeta = Vec::new();
    lagrange_basis_zeta.push(li_zeta.clone());
    // 使用它们之间的关系计算所有其他 Lagrange 多项式
    for i in 1..domain.len() {
        li_zeta = omega * &li_zeta * ((&zeta - &domain[i - 1]) / (&zeta - &domain[i]));
        lagrange_basis_zeta.push(li_zeta.clone());
    }
    // 通过关联 \zeta 处的 a 和公共输入来恢复 x

    let x = (&proof.a_zeta
        - b * &lagrange_basis_zeta[3]
        - y * &lagrange_basis_zeta[4]
        - b * &lagrange_basis_zeta[0]
        - y * &lagrange_basis_zeta[1]
        - b * &lagrange_basis_zeta[5]
        - b * &lagrange_basis_zeta[6]
        - b * &lagrange_basis_zeta[7])
        / &lagrange_basis_zeta[2];
    // 假设 x 已知，则恢复 h
    let h = (y - b) / &x;
    (x, h)
}

坐标的解决方案是：

x: "2194826651b32ca1055614fc6e2f2de86eab941d2c55bd467268e9",
h: "432904cca36659420aac29f8dc5e5bd0dd57283a58ab7a8ce4d1ca".

flag 是两者的连接：FLAG: 2194826651b32ca1055614fc6e2f2de86eab941d2c55bd467268e9432904cca36659420aac29f8dc5e5bd0dd57283a58ab7a8ce4d1ca

Loki 的活板门

挑战

成功闯入 Loki 的金库并获得他最珍贵的宝藏和武器后，你发现地毯下有一个小活板门。

活板门被锁住，里面装有一个带有 PLONK prover 的设备。上面写着：证明点 (1,y)(1,y) 属于椭圆曲线 y2=x3+4y2=x3+4。

你看到为了证明这一点，你需要 y2−x3−4y2−x3−4 等于零，这对应于 Loki 提供的 prover 电路。

你能打开活板门吗？

nc 44.203.113.160 4000

其他信息在此 repo。

FLAG 格式：ZKCTF{XXX...XXX}

解决方法

电路是：

公共输入：x
公共输入：y

ASSERT 0 == y^2 - x^3 - 4

它是在 BLS12 381 标量域上实例化的。

该漏洞源于 strong Fiat-Shamir 实现中的一个错误。正确的实现应将所有公共输入添加到初始化时的 transcript 中（及其他内容）。如果未将公共输入添加到 transcript 中并且受攻击者控制，他们可以伪造虚假证明。修复 x=1 会将 y 留给用户控制。我们可以看到 Fiat-Shamir transcript 没有包含公共输入，如此处所示

pub fn new_strong_fiat_shamir_transcript&lt;F, CS>(
    vk: &VerificationKey&lt;CS::Commitment>,
    _public_input: &[FieldElement&lt;F>],
) -> DefaultTranscript

弱 Fiat-Shamir 对现代证明系统的攻击的第 V 节描述了该攻击。

以下是攻击的摘要：

当前的解决方案没有采用随机多项式（步骤 (1) 到 (7)），而是采用 x=0、y=2 对的有效证明，并使用它为 x=1 伪造一个与原始证明兼容的 y。

##[allow(unused)]
fn forge_y_for_valid_proof&lt;F: IsField, CS: IsCommitmentScheme&lt;F>>(
    proof: &Proof&lt;F, CS>,
    vk: &VerificationKey&lt;CS::Commitment>,
    common_preprocessed_input: CommonPreprocessedInput&lt;F>,
) -> FieldElement&lt;F>
where
    CS::Commitment: Serializable,
    FieldElement&lt;F>: ByteConversion,
{
    // 像 verifier 一样重播交互
    let mut transcript = new_strong_fiat_shamir_transcript::&lt;F, CS>(vk, &[]);

    transcript.append(&proof.a_1.serialize());
    transcript.append(&proof.b_1.serialize());
    transcript.append(&proof.c_1.serialize());
    let beta = FieldElement::from_bytes_be(&transcript.challenge()).unwrap();
    let gamma = FieldElement::from_bytes_be(&transcript.challenge()).unwrap();

    transcript.append(&proof.z_1.serialize());
    let alpha = FieldElement::from_bytes_be(&transcript.challenge()).unwrap();

    transcript.append(&proof.t_lo_1.serialize());
    transcript.append(&proof.t_mid_1.serialize());
    transcript.append(&proof.t_hi_1.serialize());
    let zeta = &FieldElement::from_bytes_be(&transcript.challenge()).unwrap();

    // 伪造公共输入
    let zh_zeta = zeta.pow(common_preprocessed_input.n) - FieldElement::one();

    let omega = &common_preprocessed_input.omega;
    let n = common_preprocessed_input.n as u64;
    let one = &FieldElement::one();

    let l1_zeta = ((zeta.pow(n) - one) / (zeta - one)) / FieldElement::from(n);

    let l2_zeta = omega * &l1_zeta * (zeta - one) / (zeta - omega);

    let mut p_constant_zeta = &alpha
        * &proof.z_zeta_omega
        * (&proof.c_zeta + &gamma)
        * (&proof.a_zeta + &beta * &proof.s1_zeta + &gamma)
        * (&proof.b_zeta + &beta * &proof.s2_zeta + &gamma);
    p_constant_zeta = p_constant_zeta - &l1_zeta * &alpha * &alpha;

    let p_zeta = p_constant_zeta + &proof.p_non_constant_zeta;
    -(p_zeta + l1_zeta * one - (&zh_zeta * &proof.t_zeta)) / l2_zeta
}

STARKs 挑战

挑战

早上好，黑客。

如果你正在阅读此内容，则日期应为 2023 年 7 月 7 日，并且你应该正在查看 Lambda-Ingoyama CTF 挑战站点。

希望我们能够劫持该站点，并且你现在正在阅读此内容。我们不允许说太多，但你必须知道赢得这一挑战至关重要。

因此，我们决定提供帮助。不用担心；这应该很容易。我们找到了正确的漏洞来解决，并将解决方案转发给你。

如果出现问题，我们会留下一些我们收集的其他数据。我们不知道是否有帮助，但我们希望它可以提供帮助。

现在由你来获取 flag。祝你好运。

https://github.com/ingonyama-zk/ZKCTF-ch3-client

FLAG 格式：ZKCTF{XXX...XXX}

解决方法

这里的关键是 STARK prover 只进行一次查询，这使得可靠性错误非常重要。此漏洞出现在 Lambdaworks 的早期实现中（请参阅此 PR），并由 Michael Carilli 发现（我们对此深表感谢）。

需要使用一些额外的数据，例如偏移量、约束和 blowup factor。数据中暗示了偏移量和约束。可以猜测或暗示 blowup factor。

我们现在可以利用 FRI 可靠性错误（对于一个查询来说非常大）来打破 STARK 协议。我们必须首先通过组成多项式和 trace 多项式之间在域外点 zz 处的一致性检查。verifier 在步骤 2 中执行此检查。如果我们直接从 trace 多项式计算多项式的值，我们可以自动通过此测试：

pub fn composition_poly_ood_evaluation_exact_from_trace&lt;F: IsFFTField, A: AIR&lt;Field = F>>(
    air: &A,
    trace_ood_frame_evaluations: &Frame&lt;F>,
    domain: &Domain&lt;F>,
    z: &FieldElement&lt;F>,
    rap_challenges: &A::RAPChallenges,
    boundary_coeffs: &[(FieldElement&lt;F>, FieldElement&lt;F>)],
    transition_coeffs: &[(FieldElement&lt;F>, FieldElement&lt;F>)],
) -> FieldElement&lt;F> {
    let _public_input = air.pub_inputs();
    let boundary_constraints = air.boundary_constraints(rap_challenges);

    let n_trace_cols = air.context().trace_columns;

    let boundary_constraint_domains =
        boundary_constraints.generate_roots_of_unity(&domain.trace_primitive_root, &[n_trace_cols]);

    let values = boundary_constraints.values(&[n_trace_cols]);

    // 遵循 https://www.notamonadtutorial.com/diving-deep-fri/ 的命名约定
    let mut boundary_c_i_evaluations = Vec::with_capacity(n_trace_cols);
    let mut boundary_quotient_degrees = Vec::with_capacity(n_trace_cols);

    for trace_idx in 0..n_trace_cols {
        let trace_evaluation = &trace_ood_frame_evaluations.get_row(0)[trace_idx];
        let boundary_constraints_domain = &boundary_constraint_domains[trace_idx];
        let boundary_interpolating_polynomial =
            &Polynomial::interpolate(boundary_constraints_domain, &values[trace_idx])
                .expect("xs and ys have equal length and xs are unique");

        let boundary_zerofier =
            boundary_constraints.compute_zerofier(&domain.trace_primitive_root, trace_idx);

        let boundary_quotient_ood_evaluation = (trace_evaluation
            - boundary_interpolating_polynomial.evaluate(z))
            / boundary_zerofier.evaluate(z);

        let boundary_quotient_degree = air.trace_length() - boundary_zerofier.degree() - 1;

        boundary_c_i_evaluations.push(boundary_quotient_ood_evaluation);
        boundary_quotient_degrees.push(boundary_quotient_degree);
    }

    let trace_length = air.trace_length();

    let boundary_term_degree_adjustment = air.composition_poly_degree_bound() - trace_length;

    let boundary_quotient_ood_evaluations: Vec&lt;FieldElement&lt;F>> = boundary_c_i_evaluations
        .iter()
        .zip(boundary_coeffs)
        .map(|(poly_eval, (alpha, beta))| {
            poly_eval * (alpha * &z.pow(boundary_term_degree_adjustment) + beta)
        })
        .collect();

    let boundary_quotient_ood_evaluation = boundary_quotient_ood_evaluations
        .iter()
        .fold(FieldElement::&lt;F>::zero(), |acc, x| acc + x);

    let transition_ood_frame_evaluations =
        air.compute_transition(trace_ood_frame_evaluations, rap_challenges);

    let transition_exemptions = air.transition_exemptions();

    let x_n = Polynomial::new_monomial(FieldElement::&lt;F>::one(), trace_length);
    let x_n_1 = x_n - FieldElement::&lt;F>::one();

    let divisors = transition_exemptions
        .into_iter()
        .map(|exemption| x_n_1.clone() / exemption)
        .collect::&lt;Vec&lt;Polynomial&lt;FieldElement&lt;F>>>>();

    let mut denominators = Vec::with_capacity(divisors.len());
    for divisor in divisors.iter() {
        denominators.push(divisor.evaluate(z));
    }
    FieldElement::inplace_batch_inverse(&mut denominators);

    let mut degree_adjustments = Vec::with_capacity(divisors.len());
    for transition_degree in air.context().transition_degrees().iter() {
        let degree_adjustment =
            air.composition_poly_degree_bound() - (air.trace_length() * (transition_degree - 1));
        degree_adjustments.push(z.pow(degree_adjustment));
    }
    let transition_c_i_evaluations_sum =
        ConstraintEvaluator::&lt;F, A>::compute_constraint_composition_poly_evaluations_sum(
            &transition_ood_frame_evaluations,
            &denominators,
            &degree_adjustments,
            transition_coeffs,
        );

    &boundary_quotient_ood_evaluation + transition_c_i_evaluations_sum
}

prover 将组成多项式拆分为偶次和奇次项，H1(z2)H1(z2) 和 H2(z2)H2(z2)。verifier 必须从 trace 多项式计算 H(z)H(z)，然后检查

H(z)=H1(z2)+zH2(z2)H(z)=H1(z2)+zH2(z2)

fn compute_deep_composition_poly_evil&lt;A: AIR, F: IsFFTField>(
    air: &A,
    domain: &Domain&lt;F>,
    trace_polys: &[Polynomial&lt;FieldElement&lt;F>>],
    round_2_result: &Round2&lt;F>,
    round_3_result: &Round3&lt;F>,
    z: &FieldElement&lt;F>,
    primitive_root: &FieldElement&lt;F>,
    composition_poly_gammas: &[FieldElement&lt;F>; 2],
    trace_terms_gammas: &[FieldElement&lt;F>],
) -> Polynomial&lt;FieldElement&lt;F>>
where
    lambdaworks_math::field::element::FieldElement&lt;F>: lambdaworks_math::traits::ByteConversion,
{
    // 计算 deep 组成多项式的组成多项式项。
    let h_1 = &round_2_result.composition_poly_even;
    let h_1_z2 = &round_3_result.composition_poly_even_ood_evaluation;
    let h_2 = &round_2_result.composition_poly_odd;
    let h_2_z2 = &round_3_result.composition_poly_odd_ood_evaluation;
    let gamma = &composition_poly_gammas[0];
    let gamma_p = &composition_poly_gammas[1];
    let z_squared = z.square();

    // 𝛾 ( H₁ − H₁(z²) ) / ( X − z² )
    let h_1_term = {
        let x = Polynomial::new_monomial(FieldElement::one(), 1);
        let h_1_num = gamma * (h_1 - h_1_z2);
        let h_1_denom = &x - &z_squared;
        interp_from_num_denom(&h_1_num, &h_1_denom, domain)
    };

    // 𝛾' ( H₂ − H₂(z²) ) / ( X − z² )
    let h_2_term = {
        let x = Polynomial::new_monomial(FieldElement::one(), 1);
        let h_2_num = gamma_p * (h_2 - h_2_z2);
        let h_2_denom = &x - &z_squared;
        interp_from_num_denom(&h_2_num, &h_2_denom, domain)
    };

    // 获取 deep 组成多项式 trace 项所需的 trace 评估
    let transition_offsets = &air.context().transition_offsets;
    let trace_frame_evaluations = &round_3_result.trace_ood_evaluations;

    // 计算所有 deep 组成多项式 trace 项的总和。
    // 对于 trace 多项式中的每个 trace 和帧中的每一行，都有一项。
    // ∑ ⱼₖ [ 𝛾ₖ ( tⱼ − tⱼ(z) ) / ( X − zgᵏ )]

    let mut trace_terms = Polynomial::zero();
    for (i, t_j) in trace_polys.iter().enumerate() {
        let i_times_trace_frame_evaluation = i * trace_frame_evaluations.len();
        let iter_trace_gammas = trace_terms_gammas
            .iter()
            .skip(i_times_trace_frame_evaluation);
        for ((evaluations, offset), elemen_trace_gamma) in trace_frame_evaluations
            .iter()
            .zip(transition_offsets)
            .zip(iter_trace_gammas)
        {

            let t_j_z = evaluations[i].clone();

            let z_shifted = z * primitive_root.pow(*offset);

            let mut poly = t_j - t_j_z;
            poly.ruffini_division_inplace(&z_shifted);
            trace_terms = trace_terms + poly * elemen_trace_gamma;
        }
    }

    h_1_term + h_2_term + trace_terms
}

它使用以下函数进行插值

pub fn interp_from_num_denom&lt;F: IsFFTField>(
    num: &Polynomial&lt;FieldElement&lt;F>>,
    denom: &Polynomial&lt;FieldElement&lt;F>>,
    domain: &Domain&lt;F>,
) -> Polynomial&lt;FieldElement&lt;F>> {
    let target_deg = domain.lde_roots_of_unity_coset.len() / domain.blowup_factor;
    let num_evals = evaluate_polynomial_on_lde_domain(
        num,
        domain.blowup_factor,
        domain.interpolation_domain_size,
        &domain.coset_offset,
    )
    .unwrap();
    let denom_evals = evaluate_polynomial_on_lde_domain(
        denom,
        domain.blowup_factor,
        domain.interpolation_domain_size,
        &domain.coset_offset,
    )
    .unwrap();
    let evals: Vec&lt;_> = num_evals
        .iter()
        .zip(denom_evals)
        .map(|(num, denom)| num / denom)
        .collect();

    Polynomial::interpolate(
        &domain.lde_roots_of_unity_coset[..target_deg],
        &evals[..target_deg],
    )
    .unwrap()
}

我们现在可以创建一个恶意 prover，即使他使用虚假的执行 trace，它也可能会通过 verifier 的检查。修改 Step_2 以计算精确的组成多项式：

fn step_2_evil_eval&lt;F: IsFFTField, A: AIR&lt;Field = F>>(
    air: &A,
    domain: &Domain&lt;F>,
    transition_coeffs: &[(FieldElement&lt;F>, FieldElement&lt;F>)],
    boundary_coeffs: &[(FieldElement&lt;F>, FieldElement&lt;F>)],
    rap_challenges: &A::RAPChallenges,
    z: &FieldElement&lt;F>,
    trace_ood_frame_evaluations: &Frame&lt;F>,
) -> FieldElement&lt;F> {
    // BEGIN TRACE &lt;-> 组合多项式一致性评估检查
    // 这些是 H_1(z^2) 和 H_2(z^2)

    let boundary_constraints = air.boundary_constraints(rap_challenges);

    //let n_trace_cols = air.context().trace_columns;
    // 特例。
    let trace_length = air.trace_length();
    let composition_poly_degree_bound = air.composition_poly_degree_bound();
    let boundary_term_degree_adjustment = composition_poly_degree_bound - trace_length;
    let number_of_b_constraints = boundary_constraints.constraints.len();

    // 遵循来自 https://www.notamonadtutorial.com/diving-deep-fri/ 的命名约定
    let (boundary_c_i_evaluations_num, mut boundary_c_i_evaluations_den): (
        Vec&lt;FieldElement&lt;F>>,
        Vec&lt;FieldElement&lt;F>>,
    ) = (0..number_of_b_constraints)
        .map(|index| {
            let step = boundary_constraints.constraints[index].step;
            let point = &domain.trace_primitive_root.pow(step as u64);
            let trace_idx = boundary_constraints.constraints[index].col;
            let trace_evaluation = &trace_ood_frame_evaluations.get_row(0)[trace_idx];
            let boundary_zerofier_challenges_z_den = z - point;

            let boundary_quotient_ood_evaluation_num =
                trace_evaluation - &boundary_constraints.constraints[index].value;

            (
                boundary_quotient_ood_evaluation_num,
                boundary_zerofier_challenges_z_den,
            )
        })
        .collect::&lt;Vec&lt;_>>()
        .into_iter()
        .unzip();

    FieldElement::inplace_batch_inverse(&mut boundary_c_i_evaluations_den);

    let boundary_degree_z = z.pow(boundary_term_degree_adjustment);
    let boundary_quotient_ood_evaluation: FieldElement&lt;F> = boundary_c_i_evaluations_num
        .iter()
        .zip(&boundary_c_i_evaluations_den)
        .zip(boundary_coeffs)
        .map(|((num, den), (alpha, beta))| num * den * (alpha * &boundary_degree_z + beta))
        .fold(FieldElement::&lt;F>::zero(), |acc, x| acc + x);

    let transition_ood_frame_evaluations =
        air.compute_transition(trace_ood_frame_evaluations, rap_challenges);

    let divisor_x_n = (z.pow(trace_length) - FieldElement::&lt;F>::one()).inv();

    let denominators = air
        .transition_exemptions_verifier()
        .iter()
        .map(|poly| poly.evaluate(z) * &divisor_x_n)
        .collect::&lt;Vec&lt;FieldElement&lt;F>>>();

    let degree_adjustments = air
        .context()
        .transition_degrees()
        .iter()
        .map(|transition_degree| {
            let degree_adjustment =
                composition_poly_degree_bound - (trace_length * (transition_degree - 1));
            z.pow(degree_adjustment)
        })
        .collect::&lt;Vec&lt;FieldElement&lt;F>>>();

    let transition_c_i_evaluations_sum =
        ConstraintEvaluator::&lt;F, A>::compute_constraint_composition_poly_evaluations_sum(
            &transition_ood_frame_evaluations,
            &denominators,
            &degree_adjustments,
            transition_coeffs,
        );

    &boundary_quotient_ood_evaluation + transition_c_i_evaluations_sum
}

然后，step_3 更改为

fn round_3_evil&lt;F: IsFFTField, A: AIR&lt;Field = F>>(
    air: &A,
    domain: &Domain&lt;F>,
    round_1_result: &Round1&lt;F, A>,
    z: &FieldElement&lt;F>,
    boundary_coeffs: &[(FieldElement&lt;F>, FieldElement&lt;F>)],
    transition_coeffs: &[(FieldElement&lt;F>, FieldElement&lt;F>)],
) -> Round3&lt;F>
where
    FieldElement&lt;F>: ByteConversion,
{
    let trace_ood_evaluations = Frame::get_trace_evaluations(
        &round_1_result.trace_polys,
        z,
        &air.context().transition_offsets,
        &domain.trace_primitive_root,
    );

    let (composition_poly_even_ood_evaluation, composition_poly_odd_ood_evaluation) = {
        let trace_ood_frame_evaluations = Frame::new(
            trace_ood_evaluations.iter().flatten().cloned().collect(),
            round_1_result.trace_polys.len(),
        );

        let hz_exact_from_trace = step_2_evil_eval(
            air,
            domain,
            transition_coeffs,
            boundary_coeffs,
            &round_1_result.rap_challenges,
            z,
            &trace_ood_frame_evaluations,
        );

        (hz_exact_from_trace, FieldElement::&lt;F>::from(0))
    };

    Round3 {
        trace_ood_evaluations,
        composition_poly_even_ood_evaluation,
        composition_poly_odd_ood_evaluation,
    }
}

最后，round_4 是

fn round_4_evil&lt;F: IsFFTField, A: AIR&lt;Field = F>, T: Transcript>(
    air: &A,
    domain: &Domain&lt;F>,
    round_1_result: &Round1&lt;F, A>,
    round_2_result: &Round2&lt;F>,
    round_3_result: &Round3&lt;F>,
    z: &FieldElement&lt;F>,
    transcript: &mut T,
) -> Round4&lt;F>
where
    FieldElement&lt;F>: ByteConversion,
{
    let coset_offset_u64 = air.context().proof_options.coset_offset;
    let coset_offset = FieldElement::&lt;F>::from(coset_offset_u64);

    // &lt;&lt;&lt;&lt; 接收 challenges: 𝛾, 𝛾'
    let composition_poly_coeffients = [\
        transcript_to_field(transcript),\
        transcript_to_field(transcript),\
    ];
    // &lt;&lt;&lt;&lt; 接收 challenges: 𝛾ⱼ, 𝛾ⱼ'
    let trace_poly_coeffients = batch_sample_challenges::&lt;F, T>(
        air.context().transition_offsets.len() * air.context().trace_columns,
        transcript,
    );

    // 计算 p₀ (deep composition polynomial)
    let deep_composition_poly = compute_deep_composition_poly_evil(
        air,
        domain,
        &round_1_result.trace_polys,
        round_2_result,
        round_3_result,
        z,
        &domain.trace_primitive_root,
        &composition_poly_coeffients,
        &trace_poly_coeffients,
    );

    let domain_size = domain.lde_roots_of_unity_coset.len();

    // FRI 提交和查询阶段
    let (fri_last_value, fri_layers) = fri_commit_phase(
        domain.root_order as usize,
        deep_composition_poly,
        transcript,
        &coset_offset,
        domain_size,
    );
    let (query_list, iotas) = fri_query_phase(air, domain_size, &fri_layers, transcript);
    let fri_layers_merkle_roots: Vec&lt;_> = fri_layers
        .iter()
        .map(|layer| layer.merkle_tree.root)
        .collect();

    let deep_poly_openings =
        open_deep_composition_poly(domain, round_1_result, round_2_result, &iotas);

    // grinding: 生成 nonce 并将其附加到 transcript
    let grinding_factor = air.context().proof_options.grinding_factor;
    let transcript_challenge = transcript.challenge();
    let nonce = generate_nonce_with_grinding(&transcript_challenge, grinding_factor)
        .expect("nonce not found");
    transcript.append(&nonce.to_be_bytes());

    Round4 {
        fri_last_value,
        fri_layers_merkle_roots,
        deep_poly_openings,
        query_list,
        nonce,
    }
}

这样，我们生成了一个证明，该证明将始终通过 out-of-domain point 一致性检查，并将有很高的概率通过低度测试。

总结

这篇文章涵盖了我们在首届 Lambda-Ingo ZK CTF 中提出的挑战及其解决方案。这些挑战涉及对 Plonk 的一些常见攻击（冻结的心脏和缺少 blinding 多项式）和 FRI，以生成虚假证明或从 witness 中恢复信息。我们将在 Lambdaworks exercises repo 中添加更多练习和案例研究，以便任何人都可以学习如何构建证明系统以及其实现中可能出现的一些常见陷阱和漏洞。我们要再次感谢 Ingonyama 的出色工作以及巴黎 LambdaZK 周的所有赞助商。请继续关注 ZK 的更多挑战！

原文链接： blog.lambdaclass.com/fir...

登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～

本文参与登链社区写作激励计划，好文好收益，欢迎正在阅读的你也加入。

首届Lambda-Ingo ZK CTF：使用LambdaWorks的ZK挑战

介绍

Plonk 挑战

Obi-Wan 的搜索

挑战

解决方法

Loki 的活板门

挑战

解决方法

STARKs 挑战

挑战

解决方法

总结

0 条评论

文章目录