拆解ZK Hack V中的难题

zellic
发布于 2025-01-30 15:36
阅读 19

Zellic加密团队在ZK Hack V竞赛中成功解决了三道删除题目，其中包括基于Rust和halo2框架的密码学应用。文章详细总结了每个挑战的描述、解决方案和关键思路，强调了解释攻击的意图，展示了对相关技术的深刻理解。

泽利克加密团队的成员（Malte Leip 和 Avi Weinstock）参加了最近的 ZK Hack 竞赛，[ZK Hack V↗](https://zkhack.dev/zkhackV/)，总共有三个谜题。我们很高兴能赢得第二和第三个谜题，而在第一个谜题中仅以第四名错过了前三名的排名。

![](https://img.learnblockchain.cn/2025/04/05/le-two-winner-5334c1bdf8e22b403ce09fe826724897.png)

ZK Hack Puzzle V-2 结果

![](https://img.learnblockchain.cn/2025/04/05/-three-winner-48c9b2ac4263ba696301d2fce0fd9d8d.png)

ZK Hack Puzzle V-3 结果

与去年的 [ZK Hack IV↗](https://www.zellic.io/blog/zellic-wins-second-place-in-zkhack-iv/) 竞赛一样，为了解决 ZK Hack V 的谜题，需要使用小型加密应用。所有谜题结合了通常在围绕 ZK 项目中使用的加密原语，但在每个谜题中也引入了一种漏洞。任务是理解提供的代码，找到漏洞，并实施利用发现的漏洞的解决方案。与 ZK Hack IV 相比，本届比赛在使用的语言和框架上提供了更大的多样性，谜题围绕 Rust 和 [halo2↗](https://github.com/zcash/halo2)，纯 Rust，以及 [Noir↗](https://noir-lang.org/)。

在这篇文章中，我们总结了谜题及其解决方案。关于解决方案，我们专注于描述如何快速解决这些挑战，而无需熟悉全部背景。因此，它们是从熟悉一般加密原理但对挑战所构建的精确协议不熟悉的人的角度撰写的。每个谜题都有多个其他说明文档在 [ZK Hack V 网站↗](https://zkhack.dev/zkhackV/) 中，某些情况下包含有关各种协议的更多信息。

### 谜题 1: Zeitgeist

这个挑战是使用 Rust 编写并使用 halo2 框架，需要深入到 PLONK 证明的层面来解决。最终，我们遇到了一些障碍，延迟了我们的进展，这些障碍与挑战本身无直接关系，而是与解析和提取数据有关。

#### 理解任务

谜题的描述如下：

> 几年前，Bob 注册了 SuperCoolAirdrop™。这个过程很简单：提供你的私钥的哈希值进行注册，当你的空投准备好了之后，你会收到通知。今天，Bob 终于收到了来自 SuperCoolAirdrop™ 的通知。是时候领取他的空投了！
>
> 过程很简单，他只需要提供一个证明，证明他知道与多年前所做的承诺相关的私钥。为了防止重放攻击，SuperCoolAirdrop™ 实施了一个无效化系统：除了证明他知道私钥，用户还必须创建一个秘密随机数并生成一个公共无效因子。一旦 SuperCoolAirdrop™ 服务器验证了证明并记录了无效因子，该证明将无法重用。
>
> 所以 Bob 随机选择了一个随机数，他最喜欢的证明系统并提交了证明。证明被拒绝了……真奇怪。他又采样了一个新的随机数再试一次。一次又一次，证明依然被拒绝。
>
> 突然他恍然大悟。SuperCoolAirdrop™ 是合法的吗？这是试图窃取他的私钥吗？

这个挑战随附 64 个承诺、证明和无效因子文件。所有的承诺都是相同的。

`main.rs` 中的 `main` 函数包含我们将要添加攻击的地方，代码如下：

```
pub fn main() {
    welcome();
    puzzle(PUZZLE_DESCRIPTION);

/* 此处为序列化证明、无效因子和承诺的创建方式。 */
    // serialize();

/* 在这里实现你的攻击，以找到加密消息的索引 */

let secret = Fr::from(0u64);
    let secret_commitment = poseidon_base::primitives::Hash::<
        _,
        P128Pow5T3Compact<Fr>,
        ConstantLength<2>,
        WIDTH,
        RATE,
    >::init()
    .hash([secret, Fr::from(0u64)]);
    for i in 0..64 {
        let (_, _, commitment) = from_serialized(i);
        assert_eq!(secret_commitment, commitment);
    }
    /* 攻击结束 */
}
```

所以承诺都是私钥的 Poseidon 哈希值，我们必须找到这个秘钥。我们可以假设这 64 个证明与无效因子都是使用相同的秘钥生成的。

#### 电路的功能是什么？

让我们检查一下最后创建这些证明的 `create_proof` 函数：

```
pub fn create_proof<
    'params,
    Scheme: CommitmentScheme<Scalar = halo2curves::bn256::Fr>,
    P: Prover<'params, Scheme>,
    E: EncodedChallenge<Scheme::Curve>,
    R: RngCore,
    T: TranscriptWriterBuffer<Vec<u8>, Scheme::Curve, E>,
>(
    rng: R,
    params: &'params Scheme::ParamsProver,
    pk: &ProvingKey<Scheme::Curve>,
) -> (Vec<u8>, Fr, Fr)
where
    Scheme::Scalar: Ord + WithSmallOrderMulGroup<3> + FromUniformBytes<64>,
{
    let n_rng = OsRng;
    let witness = Fr::from_str_vartime(
        "0", /* 这只是创建证明的一种示例，在这里运气不好找到了它！ */
    )
    .unwrap();
    let nonce = Fr::random(n_rng);

let msg = [witness, nonce];
    let nullifier = poseidon_base::primitives::Hash::<
        _,
        P128Pow5T3Compact<Fr>,
        ConstantLength<2>,
        WIDTH,
        RATE,
    >::init()
    .hash(msg);

let msg = [witness, Fr::from(0u64)];
    let commitment = poseidon_base::primitives::Hash::<
        _,
        P128Pow5T3Compact<Fr>,
        ConstantLength<2>,
        WIDTH,
        RATE,
    >::init()
    .hash(msg);

let circuit = MyCircuit {
        witness: Value::known(witness),
        nonce: Value::known(nonce),
    };

let public_inputs = vec![nullifier, commitment];
    let mut transcript = T::init(vec![]);

create_plonk_proof::<Scheme, P, _, _, _, _>(
        params,
        pk,
        &[circuit],
        &[&[&public_inputs.clone()]],
        rng,
        &mut transcript,
    )
    .expect("证明生成不应失败");

(transcript.finalize(), nullifier, commitment)
}
```

我们看到秘钥是一个单独的字段元素，而 nonce 是随机生成的字段元素。承诺是秘钥的哈希，无效因子是秘钥和 nonce 的哈希，承诺和无效因子都是证明的公共输入。我们可以从这推测，电路很可能确保恰好有这样的关系。检查电路实现确认了这个假设。

#### 缺乏盲因子

在这个谜题的展示中提到，这个谜题涉及何时使用未针对零知识进行配置的证明方案，以及依赖于证明的小的大小作为攻击者提取秘密的障碍。

因此，值得看看 `create_proof` 函数中调用的 `create_plonk_proof` 函数。稍微令人困惑的是，这个函数也叫 `create_proof`，由于名称冲突，因此只以 `create_plonk_proof` 导入。它位于库的 halo2/halo2_proofs/src/plonk/prover.rs 中。挑战库中包含 halo2 的副本而不是仅作为依赖项，这已经可以看作是修改了某些内容的迹象。当寻找引用添加零知识或盲因子的地方时，以下段落似乎很有趣：

```
// 将盲因子添加到建议列
for advice_values in &mut advice_values {
    //for cell in &mut advice_values[unusable_rows_start..] {
    //*cell = C::Scalar::random(&mut rng);
    //*cell = C::Scalar::one();
    //}
    let idx = advice_values.len() - 1;
    advice_values[idx] = Scheme::Scalar::ONE;
}
```

评论表明，将盲因子添加到建议列的底部，但最后一行仅添加了一个值 `1`，而用来添加随机盲值的代码被注释掉了。与未修改版本的 halo2 对照检查，我们发现这个代码段应该如下所示：

```
// 将盲因子添加到建议列
for advice in &mut advice {
    for cell in &mut advice[unusable_rows_start..] {
        *cell = C::Scalar::random(&mut rng);
    }
}
```

所以看起来将填充了随机值的行添加到表底的过程被禁用了。

#### 找到有趣的列

从这里继续，测试在证明过程中发生了什么并输出一些相关数据是非常有用的。为了能够在输出中识别秘钥，建议将 `create_proof` 中的秘钥值从 `0` 更改为更易于识别的值，例如 `0x2a = 42`。`create_proof` 需要一些参数，但幸运的是，`main.rs` 中已经有一个不带参数的 `shplonk` 函数，做了所有调用 `create_proof` 所需的事情，返回证明、无效因子和承诺。因此我们可以在 `main` 函数中添加以下内容进行测试：

```
let (proof, nullifier, commitment) = shplonk();
println!("nullifier = {:?}", nullifier);
println!("commitment = {:?}", commitment);
```

然后我们想要检查在证明生成过程中表格的列的值，以帮助弄清楚如何利用缺乏盲因子。在 halo2 的 `create_proof` 函数中，`advice_values` 向量应该填充盲因子的内容，但没有，将保存到一些 `advice` 变量中，如下所示，在引述的代码片段前面有几行：

```
for ((column_index, advice_values), blind) in
    column_indices.iter().zip(advice_values).zip(blinds)
{
    advice.advice_polys[*column_index] = advice_values;
    advice.advice_blinds[*column_index] = blind;
}
```

有了这些信息，我们可以构建以下代码，将其放置在处理所有建议列的大循环之后，打印出每一列的内容：

```
for zellic_i in 0..advice[0].advice_polys.len() {
    println!("");
    for zellic_j in 0..advice[0].advice_polys[zellic_i].len() {
        println!("advice_polys[{}][{}] = {:?}", zellic_i, zellic_j, advice[0].advice_polys[zellic_i][zellic_j])
    }
}
```

运行一次，我们可以看到，例如第一列包含秘钥，然后是 nonce，最后只有零（除了最后的条目是 `1`，如前所述）：

```
advice_polys[0][0] = 0x000000000000000000000000000000000000000000000000000000000000002a
advice_polys[0][1] = 0x28d6b056ad8c883722d5d617d4b2f9062a183a6f67389c4d5c30a08be28126bf
advice_polys[0][2] = 0x0000000000000000000000000000000000000000000000000000000000000000
advice_polys[0][3] = 0x0000000000000000000000000000000000000000000000000000000000000000
advice_polys[0][4] = 0x0000000000000000000000000000000000000000000000000000000000000000
...
```

由于 nonce 每次运行证明时都是不同的随机值，所以检查哪些值发生改变哪些不发生改变是非常有趣的。保存两个运行的输出并差异比较，我们可以看到第 `0` 列在两个运行中保持不变，除了索引 `1` 部分是符合预期。此外，第 `1` 列到第 `4` 列在两个运行之间没有任何差异，因此它们显然不依赖于 nonce。从第 `5` 列开始，两次运行之间存在许多差异。对我们来说最有用的是包含秘钥的列。通过筛选包含秘钥的列，我们找到以下内容：

```
% cargo run --release  | grep "0x000000000000000000000000000000000000000000000000000000000000002a"
...
advice_polys[0][0] = 0x000000000000000000000000000000000000000000000000000000000000002a
advice_polys[1][2] = 0x000000000000000000000000000000000000000000000000000000000000002a
advice_polys[1][3] = 0x000000000000000000000000000000000000000000000000000000000000002a
advice_polys[1][4] = 0x000000000000000000000000000000000000000000000000000000000000002a
advice_polys[5][2] = 0x000000000000000000000000000000000000000000000000000000000000002a
advice_polys[5][3] = 0x000000000000000000000000000000000000000000000000000000000000002a
advice_polys[5][4] = 0x000000000000000000000000000000000000000000000000000000000000002a
```

列号 `1` 因此似乎最具希望：在每次运行中相同，并且在三处地方包含秘钥。

#### 我们掌握了什么信息？

可以推测的是，盲因子的缺失意味着这条证明泄露了有关分配的信息（包括我们需要的秘钥）到证明中。为了更快地找到代码中发生此事的地方，我们来看看这一证明包含的数据。`shplonk` 函数将证明作为第一个参数并以同样的方式从主函数中获取它：

```
let (proof, nullifier, commitment) =
create_proof::<_, ProverSHPLONK<_>, _, _, Blake2bWrite<_, _, Challenge255<_>>>(
    rng, &params, &pk,
);
```

检查该函数，我们可以看到证明由成绩单组成：

```
let mut transcript = T::init(vec![]);

create_plonk_proof::<Scheme, P, _, _, _, _>(
    params,
    pk,
    &[circuit],
    &[&[&public_inputs.clone()]],
    rng,
    &mut transcript,
)
.expect("证明生成不应失败");

(transcript.finalize(), nullifier, commitment)
```

回到 halo2/halo2_proofs/src/plonk/prover.rs 中的 `create_proof` 函数，在相同的 transcript 参数中，我们可以搜索这个词，略读代码，检查数据写入成绩单的地方。

#### 多项式评估

在此，我们找到以下代码段，在其中 `advice.advice_polys` 被使用（里面包含我们想要的数据），向 `transcript` 写入数据（收集我们实际上拥有的数据）：

```
// 计算并哈希每个电路实例的建议评估
for advice in advice.iter() {
    // 在 omega^i x 处评估多项式
    let advice_evals: Vec<_> = meta
        .advice_queries
        .iter()
        .map(|&(column, at)| {
            eval_polynomial(
                &advice.advice_polys[column.index()],
                domain.rotate_omega(*x, at),
            )
        })
        .collect();

// 哈希每个建议列的评估
    for eval in advice_evals.iter() {
        transcript.write_scalar(*eval)?;
    }
}
```

这个代码片段似乎将 `advice.advice_polys[column.index()]` 视为一个多项式，在某点处进行评估，将结果写入成绩单。

为了弄明白发生了什么，让我们将之前的打印语句更改为仅打印感兴趣的列，并将其打印只在此评估代码段之前以及进行评估的点和结果：

```
println!("Just before evaluation:");
for zellic_j in 0..advice[0].advice_polys[1].len() {
    println!("advice_polys[{}][{}] = {:?}", 1, zellic_j, advice[0].advice_polys[1][zellic_j])
}
// 计算并哈希每个电路实例的建议评估
for advice in advice.iter() {
    // 在 omega^i x 处评估多项式
    let advice_evals: Vec<_> = meta
        .advice_queries
        .iter()
        .map(|&(column, at)| {
            let zellic_eval_point = domain.rotate_omega(*x, at);
            let zellic_result = eval_polynomial(
                &advice.advice_polys[column.index()],
                zellic_eval_point,
            );
            if column.index() == 1 {
                println!("Evaluation at: {:?} with result {:?}", zellic_eval_point, zellic_result);
            }
            zellic_result
        })
        .collect();

// 哈希每个建议列的评估
    for eval in advice_evals.iter() {
        transcript.write_scalar(*eval)?;
    }
}
```

我们将获得如下输出（缩短）：

```
advice_polys[1][0] = 0x0000000000000000000000000000000000000000000000000000000000000000
advice_polys[1][1] = 0x0000000000000000000000000000000000000000000000000000000000000000
advice_polys[1][2] = 0x000000000000000000000000000000000000000000000000000000000000002a
advice_polys[1][3] = 0x000000000000000000000000000000000000000000000000000000000000002a
advice_polys[1][4] = 0x000000000000000000000000000000000000000000000000000000000000002a
advice_polys[1][5] = 0x08a62974fc6977295bf2283add4b3efb12fa85ff0cb70e26bc638bdac6d9bb3f
advice_polys[1][6] = 0x0cebe9b6b698c395b4a481c0f8766654a3885aaeee0fc03ff4271977f5caf56f
advice_polys[1][7] = 0x060da602f6da0624cd4ae8820e65eaf26d457e5609a7bb0d01a0608be81d1172
...
Just before evaluation:
advice_polys[1][0] = 0x0047b0bc6bbc49ddcc506fcc5bbb81e206c84506ccca9dc08392d26a11205c14
advice_polys[1][1] = 0x06be2f5f221c5e1f0e2a8aa8f3a7291881e5b312180d758baf42e22fb5564178
advice_polys[1][2] = 0x14e2da0bdbb6f13ea757bbc47e30931a3d437b0d668abb1d191a93664bc87f42
advice_polys[1][3] = 0x2bc488b432b21f6dd20172156de40fabb66187197f05ef774f2b54332d718d9d
advice_polys[1][4] = 0x14f880531ff79a8135dfa79591a5ccedf2228f77e0cb0eeb0be3ab518ce7c258
advice_polys[1][5] = 0x276d2d2370684496b1e47d75b683bcb4d59379a0cdeba9ec60660d3650160b8f
advice_polys[1][6] = 0x13e283c1275092e6ae3495fa7f8ab315db082c16ce763ae72807496a935bb7e4
advice_polys[1][7] = 0x2c06bd7148e6fb37f6f344cd03a615925c9d588b089c96c7cfb902417b3a4b22
...
Evaluation at: 0x2e41c57b0b55f6c28fe3400a1ef0dec2aa51f185e1156f285e78dda24c102bf5 with result 0x17fc29532cb3c0aa587c283328270d76b99f50c0f038e9e66431438bdacc8ad3
Evaluation at: 0x1b36a3314892fc220c1c3558d692f0d17cdea0359317ea9ba05f7af557592553 with result 0x08a3c5b002343a928d7a81021399b78723bd72fd3beba19d9e7bdafca4fc753d
Evaluation at: 0x0f7821cf94df9c91b51d3ce6cb7cb34c590c7997a59537cb59bb677400e86f81 with result 0x30545dd7c357e8584beb0913f43cdb5596a8e60184dd10ba69bb2fb70b70acf6
```

我们可以立即做出两个观察。第一个是 `advice[0].advice_polys[1]` 在我们打印它的前后发生了变化，我们需要理解是什么让他发生了变化。第二个是，实际上不止一个而是三个对列 `1` 的评估。如果我们再运行程序，我们注意到 `advice[0].advice_polys[1]` 的值在第一次打印和第二次评估之间是相同的，这表明它们保持不变，但是所评估的点不同。

#### `advice_polys` 是如何被修改的？

检查 `advice[0].advice_polys[1]` 在两个打印位置之间可能被修改的地方，我们发现如下代码段：

```
    // 计算建议多项式
    let advice: Vec<AdviceSingle<Scheme::Curve, Coeff>> = advice
        .into_iter()
        .map(
            |AdviceSingle {
                 advice_polys,
                 advice_blinds,
             }| {
                AdviceSingle {
                    advice_polys: advice_polys
                        .into_iter()
                        .map(|poly| domain.lagrange_to_coeff(poly))
                        .collect::<Vec<_>>(),
                    advice_blinds,
                }
            },
        )
        .collect();
```

这表明原始数据被视为某个域上的多项式评估（因此多项式是以拉格朗日形式给出的），然后被替换成该多项式的系数（通过执行 [拉格朗日插值↗](https://en.wikipedia.org/wiki/Lagrange_polynomial)）。

`domain` 变量的类型是

```
/// 该结构包含执行相关操作所需的预计算常数及其他详细信息
/// 在大小为 $2^k$ 的评估域上和大小为 $2^{k} * j$ 的扩展域上的操作, $j \neq 0$。
##[derive(Clone, Debug)]
pub struct EvaluationDomain<F: Field> {
    n: u64,
    k: u32,
    extended_k: u32,
    omega: F,
    omega_inv: F,
    extended_omega: F,
    extended_omega_inv: F,
    g_coset: F,
    g_coset_inv: F,
    quotient_poly_degree: u64,
    ifft_divisor: F,
    extended_ifft_divisor: F,
    t_evaluations: Vec<F>,
    barycentric_weight: F,
}
```

并在 `create_proof` 函数开始的地方生成如下：`let domain = &pk.vk.domain;`。`lagrange_to_coeff` 函数的实现使用某种逆傅里叶变换函数，所以通过阅读代码来确认它具体做了什么（例如它正在插值的精确点）可能需要花费很长时间。

相反，我们可以尝试猜测并检查猜测是否正确。通过结构体及其注释，我们可以猜测 `omega` 很可能是乘法阶为 `2^k` 的一个域元素，并且 `extended_omega` 是一个阶为 `2^k \cdot j` 的元素（其中 $j$取非零），拉格朗日插值所使用的域可能是 `1, omega, omega^2, ...` 或 `1, extended_omega, extended_omega^2, ...` — 或 `g_coset, g_coset*omega, g_coset*omega^2, ...` 或类似的（也许 `omega`、`extended_omega` 或 `g_coset` 的逆也可能使用）。我们可以通过打印 `advice[0].advice_polys[1]` 在被更改后的评估来检查这些：

首先检查序列中的常数因子。它是 `1`，`g_coset`，`g_coset_inv`，还是 none？

```
println!("After advice was replaced by doing lagrange_to_coeff.");
println!("Evaluation of advice[0].advice_polys[1] at 1: {:?}",
    eval_polynomial(&advice[0].advice_polys[1], 1.try_into().unwrap() ,));
println!("Evaluation of advice[0].advice_polys[1] at g_coset: {:?}",
    eval_polynomial(&advice[0].advice_polys[1], domain.g_coset ,));
println!("Evaluation of advice[0].advice_polys[1] at g_coset_inv: {:?}",
    eval_polynomial(&advice[0].advice_polys[1], domain.g_coset_inv ,));
```

尝试编译这个，我们会收到一条关于 `g_coset` 和 `g_coset_inv` 是私有字段的反映消息。幸运的是，使用的 halo2 本身是本地的，因此我们将这些字段改为公共的。我们得到了以下输出：

```
advice_polys[1][0] = 0x0000000000000000000000000000000000000000000000000000000000000000
...
After advice was replaced by doing lagrange_to_coeff.
Evaluation of advice[0].advice_polys[1] at 1: 0x0000000000000000000000000000000000000000000000000000000000000000
Evaluation of advice[0].advice_polys[1] at g_coset: 0x06f0b7392dcdccedf941aa0bf089045e11e169c20c52fcb2bbaaf4191577ac48
Evaluation of advice[0].advice_polys[1] at g_coset_inv: 0x0fb6415c26119da23b2e5477ea4b179edcf8b149f6b9d1fa28397871b759b4e8
```

从中可以明显看出，第一个评估点是 `1`。对第二个点的检查也如下：

```
Evaluation of advice[0].advice_polys[1] at ω: 0x0000000000000000000000000000000000000000000000000000000000000000
Evaluation of advice[0].advice_polys[1] at ω^-1: 0x0000000000000000000000000000000000000000000000000000000000000001
Evaluation of advice[0].advice_polys[1] at ω_ext: 0x05af6f83949440a64e85850e1123de4c443ca875bac8bfefcfec1440bec9c633
Evaluation of advice[0].advice_polys[1] at ω_ext^-1: 0x2580e0afc76e0c038ff21baefaaaf13516b26ed9552142193da3a06b5d3d8c00
```

从中，我们看出 `omega` 被使用了。对 `omega^-1` 的评估结果为 `1`，这也是我们已知的最后一项的值。所以这表明列的长度确实是 `2^k` （推定为 `omega` 的乘法阶），所以 `omega^{2^k - 1} = omega^{-1}`。

最后，想想秘钥，始终出现在列的索引 `2`、`3` 和 `4` 处。对 `omega^2` 的评估确实得出了秘钥：

```
Evaluation of advice[0].advice_polys[1] at ω^2: 0x000000000000000000000000000000000000000000000000000000000000002a
```

#### 我们如何获取评估点？

现在我们可以忘记原始列。我们知道该多项式的三个评估 — 具体来说是需要向成绩单添加相同的多项式（假设同一秘密）并添加到成绩单——这些评估已经添加到成绩单中，我们需要提取的就是对 `omega^2` 的多项式评估。看来我们应该能够收集到 `64 * 3 = 192` 个这样的评估中的多项式（每 64 个证明三个评估），插值这些评估以恢复多项式，然后在 `omega^2` 处评估以获取秘密。为此，我们需要确认三件事情：

1. 确保通过 `transcript.write_scalar` 添加到成绩单的值确实可以从我们已经给出的证明文件中提取。
2. 三个评估点在何处进行 — 我们也必须能够根据这些证明计算。
3. 该多项式的阶是否小于 192。

我们可以轻松地回答第三点：

```
println!("Degree of polynomial is {}", advice[0].advice_polys[1].len());
```

这将输出：

```
Degree of polynomial is 64
```

确实，`192 > 64`，所以没有问题。

关于第二点，评估像这样进行：

```
// 在 omega^i x 处评估多项式
let advice_evals: Vec<_> = meta
    .advice_queries
    .iter()
    .map(|&(column, at)| {
        eval_polynomial(
            &advice.advice_polys[column.index()],
            domain.rotate_omega(*x, at),
        )
    })
```

注释表明评估点的形式是 `x \cdot omega^i`。我们可以检查一下 `rotate_omega` 函数来确认这一点：

```
/// 将某个值乘以运算中的某个 omega 的幂，基本上是在
/// 领域间进行旋转。
pub fn rotate_omega(&self, value: F, rotation: Rotation) -> F {
    let mut point = value;
    if rotation.0 >= 0 {
        point *= &self.get_omega().pow_vartime([rotation.0 as u64]);
    } else {
        point *= &self
            .get_omega_inv()
            .pow_vartime([(rotation.0 as i64).unsigned_abs()]);
    }
    point
}
```

但这并不一定是我们需要做的。我们应该这样做，根据我们从第一轮获得的旋转来检查每一对点在第二次循环中是否判断是否正确。

```
在 x*omega^0 的评估结果为 0x02d7c8ef98e58ad739ed798b2b33c03577082d1ada060a332b1c4c48f8f96315
在 x*omega^1 的评估结果为 0x21b649e53a77ca0ff9d6bdf4240dea039e99107b5fdef0b2993bda225c646f56
在 x*omega^2 的评估结果为 0x120391e84c7cee33e6528e479b6af56195af206907bf8177f9a0283f92d01d93
在 x*omega^-1 的评估结果为 0x17f7f5957d854c696698625c9d97072eea21736747c9d05f11cc7f3b42d73ed5
使用旋转 Rotation(0) 的评估结果为 0x05477ffb9c023e6b01ce94a95bf2e65983f5a88c262f3427f6069b47f4336984，结果为 0x02d7c8ef98e58ad739ed798b2b33c03577082d1ada060a332b1c4c48f8f96315
使用旋转 Rotation(1) 的评估结果为 0x0d71106ed9ff2e5eaec860f164bee38f73f0c326694e166e38ca1eab0cc3fb48，结果为 0x21b649e53a77ca0ff9d6bdf4240dea039e99107b5fdef0b2993bda225c646f56
使用旋转 Rotation(-1) 的评估结果为 0x0de7b88317bffbd94211877eca0db5509299e6eb5098c9baffb394c801ceeac5，结果为 0x17f7f5957d854c696698625c9d97072eea21736747c9d05f11cc7f3b42d73ed5

```

现在我们知道多项式评估的点：$x$、$x \cdot \texttt{omega}$ 和 $x \cdot \texttt{omega}^{-1}$。我们期望 `omega` 是设置的一部分，因此我们应该可以在解决方案中使用它，但 `x` 呢？

搜索 `x`，我们在多项式评估片段上方几行找到了以下代码：

```
let x: ChallengeX<_> = transcript.squeeze_challenge_scalar();
```

因此，我们应该能够从Transcript中获得 `x`。

#### 如何读取Transcript？

在实际比赛中，由于（事后看来）低效的尝试，这花费了相当长的时间。首先一个想法是自己读取Transcript，快进所有不感兴趣的数据，以便获取 `x` 和三个相关的评估。

这个计划有一个小问题，就是需要花费一点时间来写下Transcript的类型。在我们提供的代码中，Transcript是在 `verify_proof` 函数中实例化的：

```
let mut transcript = T::init(proof);

```

此函数由 `from_serialized` 调用，其中 `T` 仅被指定为 `Blake2bRead<_, _, Challenge255<_>>`。我们可以运行验证器并打印 `T` 的类型（使用 `std::any::type_name`），然后修复类型名称中出现的缺失导入和私有模块的问题。这解决了一个小问题，但已经花费了一些时间。

更大的潜在问题是我们需要知道如何正确快速移动通过Transcript。一个想法是读取标量并打印它们，直到在我们自己生成的证明上收到错误，并且知道 `x` 的值，然后 grep 已知的 `x` 值以获得正确的索引。但是，在证明过程中，点和标量都在Transcript中写入，我们可能需要按照正确的顺序读取这些不同类型。这无疑是一个可解决的问题，并且不一定需要静态从代码中找出。例如，我们可以在证明生成时将输出打印到Transcript中，告诉我们每个操作，这样就可以将此输出转换为在读取时快速移动到正确位置的命令序列。然而，这未必是最快的方法。

相反，我们可以直接重用已经存在的验证代码并对此稍作修改。验证最终在 halo2/halo2_proofs/src/plonk/verifier.rs 的 `verify_proof` 函数中结束，其中实际上读取了Transcript。我们复制并粘贴该函数（在同一文件中），赋予一个新的名称，如 `return_data_for_attack`。我们需要从Transcript中获得 `x` 的值和三个评估。因此，我们首先将返回值从 `Result<Strategy::Output, Error>` 更改为 `Result<[Scheme::Scalar; 4], Error>`。在代码中搜索 `let x`，我们找到了以下代码片段：

```
// 采样 x 挑战，用于确保电路
// 以高概率得到满足。
let x: ChallengeX<_> = transcript.squeeze_challenge_scalar();

```

在稍后的地方，我们找到以下内容：

```
let advice_evals = (0..num_proofs)
    .map(|_| -> Result<Vec<_>, _> { read_n_scalars(transcript, vk.cs.advice_queries.len()) })
    .collect::<Result<Vec<_>, _>>()?;

```

我们需要找出应该使用哪些索引以从 `advice_evals` 中获取正确的三个评估。为此，我们跟踪证明器中的索引并打印输出：

```
println!("Evaluation at x*omega^0 is {:?}",
    eval_polynomial(&advice[0].advice_polys[1], *x,));
println!("Evaluation at x*omega^1 is {:?}",
    eval_polynomial(&advice[0].advice_polys[1], *x * domain.omega,));
println!("Evaluation at x*omega^-1 is {:?}",
    eval_polynomial(&advice[0].advice_polys[1], *x * domain.omega_inv,));

// 为每个电路实例计算和哈希建议评估
for advice in advice.iter() {
    // 在 omega^i x 的位置评估多项式
    let mut zellic_advice_eval_index = 0;
    let advice_evals: Vec<_> = meta
        .advice_queries
        .iter()
        .map(|&(column, at)| {
            let zellic_eval_point = domain.rotate_omega(*x, at);
            let zellic_result = eval_polynomial(
                &advice.advice_polys[column.index()],
                zellic_eval_point,
            );
            if column.index() == 1 {
                println!("Evaluation index {} with rotation {:?} at {:?} with result {:?}",
                    zellic_advice_eval_index, at, zellic_eval_point, zellic_result);
            }
            zellic_advice_eval_index += 1;
            zellic_result
        })
        .collect();

// 对每个建议列评估进行哈希
    for eval in advice_evals.iter() {
        transcript.write_scalar(*eval)?;
    }

}

```

这产生了以下结果：

```
在 x*omega^0 处的评估为 0x13004cc8bcc62cb548db3b5c06bf79dbe0856cd7155137dd5a929f89d4d281cc
在 x*omega^1 处的评估为 0x06f04fdb8c7b00c9d59ebdb23cbab494aa6e109df4cd2f37c4ebf5b85b5cc6fb
在 x*omega^-1 处的评估为 0x145fb2b0580e9fe42f177441308e53de33a0c36f253396bca8cbe65a6b8d487b
评估索引 1，使用旋转 Rotation(0)，在 0x1fbac78b430ad5b176b57cf21e68d68d09a44c5b45fb7490561a5a6773856d1a 上，结果 0x13004cc8bcc62cb548db3b5c06bf79dbe0856cd7155137dd5a929f89d4d281cc
评估索引 4，使用旋转 Rotation(1)，在 0x1eac263188b07530b1dd195ef81e2791b2388c6472ce990376f1317f0a5679d0 上，结果 0x06f04fdb8c7b00c9d59ebdb23cbab494aa6e109df4cd2f37c4ebf5b85b5cc6fb
评估索引 9，使用旋转 Rotation(-1)，在 0x1def28d72cf461a07043902e0508a57c3f44b5a963479049f0884950f9123810 上，结果 0x145fb2b0580e9fe42f177441308e53de33a0c36f253396bca8cbe65a6b8d487b

```

因此，我们需要的索引是 `1`、`4` 和 `9`。

回到 halo2/halo2_proofs/src/plonk/verifier.rs 文件中的 `return_data_for_attack`，我们现在可以在分配 `advice_evals` 的代码后面添加以下行：

```
let advice_evals = (0..num_proofs)
    .map(|_| -> Result<Vec<_>, _> { read_n_scalars(transcript, vk.cs.advice_queries.len()) })
    .collect::<Result<Vec<_>, _>>()?;

return Ok([*x, advice_evals[0][1], advice_evals[0][4], advice_evals[0][9]]);

```

由于编译器对该 `return` 之后的返回不正确的类型产生了警告，我们删除了插入代码下面的其余部分。

halo2/halo2_proofs/src/plonk/verifier.rs 文件中的 `verify_proof` 函数由 src/main.rs 的此函数调用（在这里称为 `verify_plonk_proof`）：

```
pub fn verify_proof<
// ...
>(
    params_verifier: &'params Scheme::ParamsVerifier,
    vk: &VerifyingKey<Scheme::Curve>,
    proof: &'a [u8],
    nullifier: Fr,
    commitment: Fr,
) where
    Scheme::Scalar: Ord + WithSmallOrderMulGroup<3> + FromUniformBytes<64>,
{
    // ...
    let strategy = verify_plonk_proof(
        params_verifier,
        vk,
        strategy,
        &[&[&pubinputs[..]]],
        &mut transcript,
    )
    .unwrap();

assert!(strategy.finalize());
}

```

我们可以复制并粘贴此代码，给它一个新名称（也许是 `return_data_for_attack_wrapper`），让返回类型为 `[Scheme::Scalar; 4]`，并将

```
let strategy = verify_plonk_proof(
    params_verifier,
    vk,
    strategy,
    &[&[&pubinputs[..]]],
    &mut transcript,
)
.unwrap();

assert!(strategy.finalize());

```

替换为

```
return_data_for_attack(
    params_verifier,
    vk,
    strategy,
    &[&[&pubinputs[..]]],
    &mut transcript,
)
.unwrap()

```

现在，这个函数仍然需要作为参数的一些参数，所以我们最终复制这个反序列化证明并调用验证器的函数：

```
fn from_serialized(i: usize) -> (Vec<u8>, Fr, Fr) {
    use halo2_proofs::poly::kzg::commitment::{KZGCommitmentScheme, ParamsKZG};
    use halo2_proofs::poly::kzg::multiopen::VerifierSHPLONK;
    use halo2_proofs::poly::kzg::strategy::AccumulatorStrategy;
    use halo2curves::bn256::Bn256;

let setup_rng = ChaCha20Rng::from_seed([1u8; 32]);
    let params = ParamsKZG::<Bn256>::setup(K, setup_rng);

let pk = keygen::<KZGCommitmentScheme<_>>(&params);

let (proofs, nullifiers, commitments) = deserialize();

let proof = proofs[i].clone();
    let nullifier = nullifiers[i];
    let commitment = commitments[i];

let verifier_params = params.verifier_params();
    verify_proof::<
        _,
        VerifierSHPLONK<_>,
        _,
        Blake2bRead<_, _, Challenge255<_>>,
        AccumulatorStrategy<_>,
    >(
        verifier_params,
        pk.get_vk(),
        &proof[..],
        nullifier,
        commitment,
    );

(proof, nullifier, commitment)
}

```

创建新的 `get_attack_data_from_serialized` 函数，该函数返回 `[Fr; 4]`；在替换证明的验证和返回行时，替换为以下内容。

```
return_data_for_attack_wrapper::<
    _,
    VerifierSHPLONK<_>,
    _,
    Blake2bRead<_, _, Challenge255<_>>,
    AccumulatorStrategy<_>,
>(
    verifier_params,
    pk.get_vk(),
    &proof[..],
    nullifier,
    commitment,
)

```

#### 我们如何获取 Omega？

最后，我们还需要 `omega` 的值。在证明器中，我们能够访问该值作为 `domain.omega`，而搜索 `let domain` 时，我们发现 `let domain = &pk.vk.domain;`。这里 `pk` 是传递给 `create_proof` 函数的类型为 `&ProvingKey<Scheme::Curve>` 的参数。在 main.rs 中，我们可以找到一个生成的证明密钥，例如在我们刚刚考虑的 `from_serialized` 中。我们可以使用这段代码创建一个获取域的函数：

```
fn get_domain() -> EvaluationDomain<Bn256Fr> {
    use halo2_proofs::poly::kzg::commitment::{KZGCommitmentScheme, ParamsKZG};
    use halo2_proofs::poly::kzg::multiopen::VerifierSHPLONK;
    use halo2_proofs::poly::kzg::strategy::AccumulatorStrategy;
    use halo2curves::bn256::Bn256;

let setup_rng = ChaCha20Rng::from_seed([1u8; 32]);
    let params = ParamsKZG::<Bn256>::setup(K, setup_rng);

let pk = keygen::<KZGCommitmentScheme<_>>(&params);

return pk.vk.domain
}

```

尝试编译时，首先会出现一些关于私有字段的错误，但可以通过编辑相关的结构体来使问题字段可公开以修复这些问题。返回类型是通过尝试与其他类型编译并复制粘贴编译器声称正在提供的类型来获得的。

#### 解决方案

现在我们可以在 `main` 函数中完成解决方案。没有必要实现多项式插值，因为 halo2 已经提供了相关的函数：

```
let omega = get_domain().omega;
let omega_inv = get_domain().omega_inv;
let mut points = vec![];
let mut values = vec![];
for i in 0..64 {
    println!("提取证明中的数据 {}", i);
    let data = get_attack_data_from_serialized(i);
    let x = data[0];
    let atx = data[1];
    let atxomega = data[2];
    let atxomageinv = data[3];
    points.push(x);
    values.push(atx);
    points.push(x*omega);
    values.push(atxomega);
    points.push(x*omega_inv);
    values.push(atxomageinv);
}

println!("收集的值...");
let coeffs = lagrange_interpolate(&points, &values);
println!("获得多项式系数");
let secret = eval_polynomial(&coeffs, omega*omega*omega);

println!("恢复的秘密: {:?}", secret);

```

通过这种方式，挑战得以解决，恢复的秘密为 `0x066ab256379d1a0d7bd1dd54cf3f4171edbf5ca3976e8956fe0ddd10af67418d`！

### 谜题 2: Don't Look Up

这个谜题的描述告诉我们，它包含了 Rust 中的实现 [ProtoStar↗](https://eprint.iacr.org/2023/620)，一个变体的查找协议 [LogUp↗](https://eprint.iacr.org/2022/1530)，在有限域 $\mathbb{F}_{p^6}$ 上实例化，其中 $p$ 是一个 16 位素数。我们的任务是使协议接受一个在范围  $[0, 2^6 - 1]$ 内的 “证明” $2^{15}$。

#### 理解任务

谜题附带三个源文件：lib.rs，似乎包含了必要基础操作的实现，如有限域的算术运算；protocol.rs，包含查找协议的实现；以及主源码文件 main.rs。

main.rs 文件指定了挑战：

```
pub fn main() {
    welcome();
    puzzle(PUZZLE_DESCRIPTION);

let p = 70937;
    let irr = vec![3, 39025, 15086, 45405, 34941, 70897, 1]; // x^6 + 70897x^5 + 34941x^4 + 45405x^3 + 15086x^2 + 39025x + 3

let invalid_witness = FieldElement::new(vec![1<<15], p, irr.clone());

/* BEGIN HACK */
    let witness = vec![];
    let m = vec![FieldElement::new(vec![0], p, irr.clone()); 1<<6];
    /* END HACK */

let mut table = vec![];
    for i in 0..1 << 6 {
        table.push(FieldElement::new(vec![i], p, irr.clone()));
    }

let l = witness.len(); // witness length
    let t = table.len(); // table size
    assert!(witness.contains(&invalid_witness));

let protocol = Protocol::new(l, t, p, irr.clone());

let statement = Statement::new(&table);

let w = Witness::new(&witness);

let msg1 = protocol.prove_round1(&w, &m);
    let r = protocol.verify_round1(&msg1);
    let msg2 = protocol.prove_round2(&r, &msg1, &statement);
    assert!(protocol.verify_round2(&msg1, &msg2, &statement));
}

```

在 `HACK` 部分之后的代码创建了 `table`，一个包含范围 $[0, 2^6 - 1]$ 所有值的向量。然后它执行查找协议，使用 `table` 作为声明， `witness`，一个字段元素向量，作为见证。我们可以更改 `witness`。从挑战的上下文来看，明确的解释是 `witness` 向量的条目将在 `table` 向量中被查找。还有一个长度为 262^626 的字段元素向量 `m`，我们也可以更改。最简单的解释是 `m[i]` 是我们希望证明 `table[i]` 在 `witness` 中出现的次数。

#### 协议 without Looking 的解决方案

我们需要使两个断言通过：1）`witness` 必须包含 `invalid_witness`，2）协议必须成功。关于第一个条件几乎没有灵活性，因此至少需要一个 `witness` 组件为 `invalid_witness = 2<<15`，而这不幸的是在 `table` 中不存在。因此，让我们专注于第二个条件。

该协议在 protocol.rs 中实现，但该文件长达 253 行，如果希望快速解决挑战，我们没有时间通读它。我们可以尝试猜测实现该协议的关键特性。为此，我们可以问自己，协议如何捕捉 `witness` 组件的顺序不应重要的事实。如果协议最终在有限域中执行检查作为相等检查，它如何从许多元素中计算出有限域的某个元素，而不依赖于顺序？

很明显，两种容易想到的方式是加法和乘法。假设我们可以猜测一种可能性是协议执行检查 $ \sum f(w_i) = ?$ 或 $ \prod f(w_i) = ?$，其中 $w_1, \dots, w_l$ 是 `witness` 的组件， $f$ 是应用于见证的某种映射。暂时假设这确实是协议所做的，回顾我们的问题。

我们必须使至少一个 $w_i$ 等于 $2^{15}$，而这在 `table` 中并不存在。这很可能意味着我们无法将 $f(2^{15})$ 与检查方程右侧的项相抵消。因此，我们必须借助其他项取消这一项。由于我们不知道 $f$ 是什么，解决这一问题的一种方法是重复 $f(2^{15})$ 至少足够多的次数；有限域研究的特性意味着 $p \cdot f(2^{15}) = 0$，而有限域的乘法群的阶是 $p^6 - 1$，因此 $f(2^{15})^{p^6 - 1} = 1$。如果检查是乘法性的，这将无效，因为 $p^6 - 1$ 将太大。然而，$p$ 足够小，以使长度为 $p$ 的见证可行。因此，我们可以尝试将 `witness` 设置为正好 $p$ 重复 $2^{15}$，希望能够抵消并且不会对检查左侧贡献，并将 `m` 设置为全零：

```
    /* BEGIN HACK */
    let witness = vec![invalid_witness.clone(); p as usize];
    let m = vec![FieldElement::new(vec![0], p, irr.clone()); 1<<6];
    /* END HACK */

```

这确实解决了挑战！

#### 协议 with Looking的解决方案

上述解决策略涉及一些直觉，在我们的情况下，已经能够充分了解 LogUp，知道它确实执行了讨论中形式的检查。利用协议实施中的一些更多信息，最有希望的起点可能是验证第二轮，因为最终声称返回 true 并且可能执行重要检查：

```
pub fn verify_round2(&self, msg1: &ProverMessage1, msg2: &ProverMessage2, statement: &Statement) -> bool {
    // 从 msg1 重新计算挑战
    let r = self.hash_to_field(msg1);

// 检查 sum(h_i) = sum(g_i)
    let sum_h = msg2.h.iter()
        .fold(FieldElement::new(vec![0], self.field_char, self.irr.clone()),
                |acc, x| acc + x.clone());

let sum_g = msg2.g.iter()
        .fold(FieldElement::new(vec![0], self.field_char, self.irr.clone()),
                |acc, x| acc + x.clone());

if sum_h != sum_g {
        return false;
    }

// 检查 h_i·(w_i + r) = 1 对所有 i
    for i in 0..self.l {
        let one = FieldElement::new(vec![1], self.field_char, self.irr.clone());
        let w_plus_r = msg1.w[i].clone() + r.clone();
        if (msg2.h[i].clone() * w_plus_r) != one {
            return false;
        }
    }

// 检查 g_i·(t_i + r) = m_i 对所有 i
    for i in 0..self.t {
        let t_plus_r = statement.t[i].clone() + r.clone();
        if (msg2.g[i].clone() * t_plus_r) != msg1.m[i] {
            return false;
        }
    }

true
}

```

从中我们可以看出，实现的协议证明似乎特别由元素 $h_i$ 和 $g_i$ 组成。第一个检查是 $\sum_i h_i = \sum_i g_i$。第二和第三个检查看起来是验证每个 $h_i$ 和 $g_i$ 是否正确计算。如果我们记得以下两行来自主函数，

```
let l = witness.len(); // witness length
let t = table.len(); // table size

```

然后我们可以从 `verify_round2` 中的两个循环中得知每个组件的 `witness` 有一个 $h_i$，并且每个组件的 `table` 有一个 $g_i$。

根据这些观察，我们已经可以（即使不需要全面解析循环，假设注释不存在）推测出 $h_i$ 将采用形式 $h_i = f(w_i)$，以便第一个检查是 $\sum f(w_i) = ?$，如之前所猜测的，第二个会验证左侧每一项的正确计算，第三个会验证右侧的正确计算。从那里我们可以如之前一般进行。

### 谜题 3:  Shadow

这一谜题是用 Noir 编写的。自述文件指出，有一个白名单，由 `pk_pepper` 形式的哈希值组成，其中 `pk` 是公钥，`pepper` 是相关的秘密值。我们有一对合法的公钥–pepper，以及另一个公钥，我们的目标是通过使用这个目标公钥来通过电路的检查。

#### 理解任务

Noir 源代码并不冗长：

```
// 该文件不可修改

use noir_string_search::{StringBody, StringBody128, SubString, SubString32};

// alice_pk = [155, 143, 27, 66, 87, 125, 33, 110, 57, 153, 93, 228, 167, 76, 120, 220, 178, 200, 187, 35, 211, 175, 104, 63, 140, 208, 36, 184, 88, 1, 203, 62]
// alice_pepper = [213, 231, 76, 105, 105, 96, 199, 183, 106, 26, 29, 7, 28, 234, 145, 69, 48, 9, 254, 205, 79, 21, 90, 13, 39, 172, 114, 59, 131, 15, 78, 118]

fn main(identifier: BoundedVec<u8, 128>, pub_key: pub [u8; 32], whitelist: pub [[u8; 32]; 10]) {
    // identifier 哈希到的摘要在公共白名单中
    let digest = std::hash::sha256_var(identifier.storage(), identifier.len() as u64);
    let mut present = false;
    for i in 0..whitelist.len() {
        if whitelist[i] == digest {
            present = true;
        }
    }
    assert(present);

// 指定的公钥在 identifier 中
    let id_haystack: StringBody128 = StringBody::new(identifier.storage(), 128);
    let pk_needle: SubString32 = SubString::new(pub_key, 32);
    let (result, _): (bool, u32) = id_haystack.substring_match(pk_needle);
    assert(result);
}

```

注释揭示了我们所提到的有效的公钥–pepper 对。电路获得了一个由最多 128 个 `u8` 组件组成的私有见证 `identifier`，以及公共输入 `pub_key` 和 `whitelist`。这些数据来自 Prover.toml 文件，其中 `pub_key` 和 `whitelist` 是固定的，而我们允许更改私有见证 `identifier`：

```
## BEGIN HACK

[identifier]
[len = "128"]
[storage = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]

## END HACK

```

#### 解决方案

遍历电路，它首先计算前 `identifier.len()` 组件的 SHA-256 哈希，然后断言白名单中的某个条目等于生成的哈希。之后，它检测 `pub_key` 是否是前 128 个 `identifier.storage()` 的子字符串。

我们知道唯一的白名单条目，其预影是 `alice_pk` 与 `alice_pepper` 的连接，中间加一个下划线。请注意，这个预影的长度为 65。只要 SHA-256 没有被破坏到可以查找预影或者碰撞，我们必须使用 `identifier.len() = 65`，并用这个已知预影填充 `identifier.storage()` 的前 65 个组件。这将使第一个断言通过。对于第二个断言，我们可以注意到在 `identifier.storage()` 的前 128 - 65 = 63 个组件中放置长度为 32 的子字符串 `pub_key` 是足够的。

使用交互式 Python 解释器，我们可以非常快速地计算出可用于 `identifier.storage()` 的列表，以解决此挑战：

```
>>> alice_pk = [155, 143, 27, 66, 87, 125, 33, 110, 57, 153, 93, 228, 167, 76, 120, 220, 178, 200, 187, 35, 211, 175, 104, 63, 140, 208, 36, 184, 88, 1, 203, 62]
>>> alice_pepper = [213, 231, 76, 105, 105, 96, 199, 183, 106, 26, 29, 7, 28, 234, 145, 69, 48, 9, 254, 205, 79, 21, 90, 13, 39, 172, 114, 59, 131, 15, 78, 118]
>>> pub_key = [157, 133, 167, 136, 43, 161, 75, 166, 33, 14, 35, 106, 238, 18, 60, 56, 93, 209, 205, 52, 247, 110, 174, 192, 20, 58, 70, 42, 215, 98, 195, 150]
>>> alice_pk + [ord('_')] + alice_pepper + pub_key + [0]*(128-32-1-32-32)
[155, 143, 27, 66, 87, 125, 33, 110, 57, 153, 93, 228, 167, 76, 120, 220, 178, 200, 187, 35, 211, 175, 104, 63, 140, 208, 36, 184, 88, 1, 203, 62, 95, 213, 231, 76, 105, 105, 96, 199, 183, 106, 26, 29, 7, 28, 234, 145, 69, 48, 9, 254, 205, 79, 21, 90, 13, 39, 172, 114, 59, 131, 15, 78, 118, 157, 133, 167, 136, 43, 161, 75, 166, 33, 14, 35, 106, 238, 18, 60, 56, 93, 209, 205, 52, 247, 110, 174, 192, 20, 58, 70, 42, 215, 98, 195, 150, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

```

### 结论

我们要感谢 ZK Hack 组织这次比赛，也感谢 Bain Capital Crypto 创建这三道有趣的谜题。

### 关于我们

Zellic 专注于保护新兴技术。我们的安全研究人员已在最有价值的目标中发现漏洞，从财富 500 强到 DeFi 巨头。

开发者、创始人和投资者信任我们的安全评估，以快速、自信地发布，无关键漏洞。凭借我们在现实世界攻击性安全研究中的背景，我们发现他人所遗漏的。

[请联系我们↗](https://zellic.io/contact) 进行一次更好的审计。真正的审计，而非走过场。

>- 原文链接： [zellic.io/blog/zellic-wi...](https://www.zellic.io/blog/zellic-wins-two-puzzles-in-zkhack-v)
>- 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～

泽利克加密团队的成员（Malte Leip 和 Avi Weinstock）参加了最近的 ZK Hack 竞赛，ZK Hack V↗，总共有三个谜题。我们很高兴能赢得第二和第三个谜题，而在第一个谜题中仅以第四名错过了前三名的排名。

ZK Hack Puzzle V-2 结果

ZK Hack Puzzle V-3 结果

与去年的 ZK Hack IV↗ 竞赛一样，为了解决 ZK Hack V 的谜题，需要使用小型加密应用。所有谜题结合了通常在围绕 ZK 项目中使用的加密原语，但在每个谜题中也引入了一种漏洞。任务是理解提供的代码，找到漏洞，并实施利用发现的漏洞的解决方案。与 ZK Hack IV 相比，本届比赛在使用的语言和框架上提供了更大的多样性，谜题围绕 Rust 和 halo2↗，纯 Rust，以及 Noir↗。

在这篇文章中，我们总结了谜题及其解决方案。关于解决方案，我们专注于描述如何快速解决这些挑战，而无需熟悉全部背景。因此，它们是从熟悉一般加密原理但对挑战所构建的精确协议不熟悉的人的角度撰写的。每个谜题都有多个其他说明文档在 ZK Hack V 网站↗ 中，某些情况下包含有关各种协议的更多信息。

谜题 1: Zeitgeist

理解任务

谜题的描述如下：

几年前，Bob 注册了 SuperCoolAirdrop™。这个过程很简单：提供你的私钥的哈希值进行注册，当你的空投准备好了之后，你会收到通知。今天，Bob 终于收到了来自 SuperCoolAirdrop™ 的通知。是时候领取他的空投了！

过程很简单，他只需要提供一个证明，证明他知道与多年前所做的承诺相关的私钥。为了防止重放攻击，SuperCoolAirdrop™ 实施了一个无效化系统：除了证明他知道私钥，用户还必须创建一个秘密随机数并生成一个公共无效因子。一旦 SuperCoolAirdrop™ 服务器验证了证明并记录了无效因子，该证明将无法重用。

所以 Bob 随机选择了一个随机数，他最喜欢的证明系统并提交了证明。证明被拒绝了……真奇怪。他又采样了一个新的随机数再试一次。一次又一次，证明依然被拒绝。

突然他恍然大悟。SuperCoolAirdrop™ 是合法的吗？这是试图窃取他的私钥吗？

这个挑战随附 64 个承诺、证明和无效因子文件。所有的承诺都是相同的。

main.rs 中的 main 函数包含我们将要添加攻击的地方，代码如下：

pub fn main() {
    welcome();
    puzzle(PUZZLE_DESCRIPTION);

    /* 此处为序列化证明、无效因子和承诺的创建方式。 */
    // serialize();

    /* 在这里实现你的攻击，以找到加密消息的索引 */

    let secret = Fr::from(0u64);
    let secret_commitment = poseidon_base::primitives::Hash::&lt;
        _,
        P128Pow5T3Compact&lt;Fr>,
        ConstantLength&lt;2>,
        WIDTH,
        RATE,
    >::init()
    .hash([secret, Fr::from(0u64)]);
    for i in 0..64 {
        let (_, _, commitment) = from_serialized(i);
        assert_eq!(secret_commitment, commitment);
    }
    /* 攻击结束 */
}

所以承诺都是私钥的 Poseidon 哈希值，我们必须找到这个秘钥。我们可以假设这 64 个证明与无效因子都是使用相同的秘钥生成的。

电路的功能是什么？

让我们检查一下最后创建这些证明的 create_proof 函数：

pub fn create_proof&lt;
    'params,
    Scheme: CommitmentScheme&lt;Scalar = halo2curves::bn256::Fr>,
    P: Prover&lt;'params, Scheme>,
    E: EncodedChallenge&lt;Scheme::Curve>,
    R: RngCore,
    T: TranscriptWriterBuffer&lt;Vec&lt;u8>, Scheme::Curve, E>,
>(
    rng: R,
    params: &'params Scheme::ParamsProver,
    pk: &ProvingKey&lt;Scheme::Curve>,
) -> (Vec&lt;u8>, Fr, Fr)
where
    Scheme::Scalar: Ord + WithSmallOrderMulGroup&lt;3> + FromUniformBytes&lt;64>,
{
    let n_rng = OsRng;
    let witness = Fr::from_str_vartime(
        "0", /* 这只是创建证明的一种示例，在这里运气不好找到了它！ */
    )
    .unwrap();
    let nonce = Fr::random(n_rng);

    let msg = [witness, nonce];
    let nullifier = poseidon_base::primitives::Hash::&lt;
        _,
        P128Pow5T3Compact&lt;Fr>,
        ConstantLength&lt;2>,
        WIDTH,
        RATE,
    >::init()
    .hash(msg);

    let msg = [witness, Fr::from(0u64)];
    let commitment = poseidon_base::primitives::Hash::&lt;
        _,
        P128Pow5T3Compact&lt;Fr>,
        ConstantLength&lt;2>,
        WIDTH,
        RATE,
    >::init()
    .hash(msg);

    let circuit = MyCircuit {
        witness: Value::known(witness),
        nonce: Value::known(nonce),
    };

    let public_inputs = vec![nullifier, commitment];
    let mut transcript = T::init(vec![]);

    create_plonk_proof::&lt;Scheme, P, _, _, _, _>(
        params,
        pk,
        &[circuit],
        &[&[&public_inputs.clone()]],
        rng,
        &mut transcript,
    )
    .expect("证明生成不应失败");

    (transcript.finalize(), nullifier, commitment)
}

缺乏盲因子

在这个谜题的展示中提到，这个谜题涉及何时使用未针对零知识进行配置的证明方案，以及依赖于证明的小的大小作为攻击者提取秘密的障碍。

因此，值得看看 create_proof 函数中调用的 create_plonk_proof 函数。稍微令人困惑的是，这个函数也叫 create_proof，由于名称冲突，因此只以 create_plonk_proof 导入。它位于库的 halo2/halo2_proofs/src/plonk/prover.rs 中。挑战库中包含 halo2 的副本而不是仅作为依赖项，这已经可以看作是修改了某些内容的迹象。当寻找引用添加零知识或盲因子的地方时，以下段落似乎很有趣：

// 将盲因子添加到建议列
for advice_values in &mut advice_values {
    //for cell in &mut advice_values[unusable_rows_start..] {
    //*cell = C::Scalar::random(&mut rng);
    //*cell = C::Scalar::one();
    //}
    let idx = advice_values.len() - 1;
    advice_values[idx] = Scheme::Scalar::ONE;
}

评论表明，将盲因子添加到建议列的底部，但最后一行仅添加了一个值 1，而用来添加随机盲值的代码被注释掉了。与未修改版本的 halo2 对照检查，我们发现这个代码段应该如下所示：

// 将盲因子添加到建议列
for advice in &mut advice {
    for cell in &mut advice[unusable_rows_start..] {
        *cell = C::Scalar::random(&mut rng);
    }
}

所以看起来将填充了随机值的行添加到表底的过程被禁用了。

找到有趣的列

从这里继续，测试在证明过程中发生了什么并输出一些相关数据是非常有用的。为了能够在输出中识别秘钥，建议将 create_proof 中的秘钥值从 0 更改为更易于识别的值，例如 0x2a = 42。create_proof 需要一些参数，但幸运的是，main.rs 中已经有一个不带参数的 shplonk 函数，做了所有调用 create_proof 所需的事情，返回证明、无效因子和承诺。因此我们可以在 main 函数中添加以下内容进行测试：

let (proof, nullifier, commitment) = shplonk();
println!("nullifier = {:?}", nullifier);
println!("commitment = {:?}", commitment);

然后我们想要检查在证明生成过程中表格的列的值，以帮助弄清楚如何利用缺乏盲因子。在 halo2 的 create_proof 函数中，advice_values 向量应该填充盲因子的内容，但没有，将保存到一些 advice 变量中，如下所示，在引述的代码片段前面有几行：

for ((column_index, advice_values), blind) in
    column_indices.iter().zip(advice_values).zip(blinds)
{
    advice.advice_polys[*column_index] = advice_values;
    advice.advice_blinds[*column_index] = blind;
}

有了这些信息，我们可以构建以下代码，将其放置在处理所有建议列的大循环之后，打印出每一列的内容：

for zellic_i in 0..advice[0].advice_polys.len() {
    println!("");
    for zellic_j in 0..advice[0].advice_polys[zellic_i].len() {
        println!("advice_polys[{}][{}] = {:?}", zellic_i, zellic_j, advice[0].advice_polys[zellic_i][zellic_j])
    }
}

运行一次，我们可以看到，例如第一列包含秘钥，然后是 nonce，最后只有零（除了最后的条目是 1，如前所述）：

advice_polys[0][0] = 0x000000000000000000000000000000000000000000000000000000000000002a
advice_polys[0][1] = 0x28d6b056ad8c883722d5d617d4b2f9062a183a6f67389c4d5c30a08be28126bf
advice_polys[0][2] = 0x0000000000000000000000000000000000000000000000000000000000000000
advice_polys[0][3] = 0x0000000000000000000000000000000000000000000000000000000000000000
advice_polys[0][4] = 0x0000000000000000000000000000000000000000000000000000000000000000
...

由于 nonce 每次运行证明时都是不同的随机值，所以检查哪些值发生改变哪些不发生改变是非常有趣的。保存两个运行的输出并差异比较，我们可以看到第 0 列在两个运行中保持不变，除了索引 1 部分是符合预期。此外，第 1 列到第 4 列在两个运行之间没有任何差异，因此它们显然不依赖于 nonce。从第 5 列开始，两次运行之间存在许多差异。对我们来说最有用的是包含秘钥的列。通过筛选包含秘钥的列，我们找到以下内容：

% cargo run --release  | grep "0x000000000000000000000000000000000000000000000000000000000000002a"
...
advice_polys[0][0] = 0x000000000000000000000000000000000000000000000000000000000000002a
advice_polys[1][2] = 0x000000000000000000000000000000000000000000000000000000000000002a
advice_polys[1][3] = 0x000000000000000000000000000000000000000000000000000000000000002a
advice_polys[1][4] = 0x000000000000000000000000000000000000000000000000000000000000002a
advice_polys[5][2] = 0x000000000000000000000000000000000000000000000000000000000000002a
advice_polys[5][3] = 0x000000000000000000000000000000000000000000000000000000000000002a
advice_polys[5][4] = 0x000000000000000000000000000000000000000000000000000000000000002a

列号 1 因此似乎最具希望：在每次运行中相同，并且在三处地方包含秘钥。

我们掌握了什么信息？

可以推测的是，盲因子的缺失意味着这条证明泄露了有关分配的信息（包括我们需要的秘钥）到证明中。为了更快地找到代码中发生此事的地方，我们来看看这一证明包含的数据。shplonk 函数将证明作为第一个参数并以同样的方式从主函数中获取它：

let (proof, nullifier, commitment) =
create_proof::&lt;_, ProverSHPLONK&lt;_>, _, _, Blake2bWrite&lt;_, _, Challenge255&lt;_>>>(
    rng, &params, &pk,
);

检查该函数，我们可以看到证明由成绩单组成：

let mut transcript = T::init(vec![]);

create_plonk_proof::&lt;Scheme, P, _, _, _, _>(
    params,
    pk,
    &[circuit],
    &[&[&public_inputs.clone()]],
    rng,
    &mut transcript,
)
.expect("证明生成不应失败");

(transcript.finalize(), nullifier, commitment)

回到 halo2/halo2_proofs/src/plonk/prover.rs 中的 create_proof 函数，在相同的 transcript 参数中，我们可以搜索这个词，略读代码，检查数据写入成绩单的地方。

多项式评估

在此，我们找到以下代码段，在其中 advice.advice_polys 被使用（里面包含我们想要的数据），向 transcript 写入数据（收集我们实际上拥有的数据）：

// 计算并哈希每个电路实例的建议评估
for advice in advice.iter() {
    // 在 omega^i x 处评估多项式
    let advice_evals: Vec&lt;_> = meta
        .advice_queries
        .iter()
        .map(|&(column, at)| {
            eval_polynomial(
                &advice.advice_polys[column.index()],
                domain.rotate_omega(*x, at),
            )
        })
        .collect();

    // 哈希每个建议列的评估
    for eval in advice_evals.iter() {
        transcript.write_scalar(*eval)?;
    }
}

这个代码片段似乎将 advice.advice_polys[column.index()] 视为一个多项式，在某点处进行评估，将结果写入成绩单。

为了弄明白发生了什么，让我们将之前的打印语句更改为仅打印感兴趣的列，并将其打印只在此评估代码段之前以及进行评估的点和结果：

println!("Just before evaluation:");
for zellic_j in 0..advice[0].advice_polys[1].len() {
    println!("advice_polys[{}][{}] = {:?}", 1, zellic_j, advice[0].advice_polys[1][zellic_j])
}
// 计算并哈希每个电路实例的建议评估
for advice in advice.iter() {
    // 在 omega^i x 处评估多项式
    let advice_evals: Vec&lt;_> = meta
        .advice_queries
        .iter()
        .map(|&(column, at)| {
            let zellic_eval_point = domain.rotate_omega(*x, at);
            let zellic_result = eval_polynomial(
                &advice.advice_polys[column.index()],
                zellic_eval_point,
            );
            if column.index() == 1 {
                println!("Evaluation at: {:?} with result {:?}", zellic_eval_point, zellic_result);
            }
            zellic_result
        })
        .collect();

    // 哈希每个建议列的评估
    for eval in advice_evals.iter() {
        transcript.write_scalar(*eval)?;
    }
}

我们将获得如下输出（缩短）：

advice_polys[1][0] = 0x0000000000000000000000000000000000000000000000000000000000000000
advice_polys[1][1] = 0x0000000000000000000000000000000000000000000000000000000000000000
advice_polys[1][2] = 0x000000000000000000000000000000000000000000000000000000000000002a
advice_polys[1][3] = 0x000000000000000000000000000000000000000000000000000000000000002a
advice_polys[1][4] = 0x000000000000000000000000000000000000000000000000000000000000002a
advice_polys[1][5] = 0x08a62974fc6977295bf2283add4b3efb12fa85ff0cb70e26bc638bdac6d9bb3f
advice_polys[1][6] = 0x0cebe9b6b698c395b4a481c0f8766654a3885aaeee0fc03ff4271977f5caf56f
advice_polys[1][7] = 0x060da602f6da0624cd4ae8820e65eaf26d457e5609a7bb0d01a0608be81d1172
...
Just before evaluation:
advice_polys[1][0] = 0x0047b0bc6bbc49ddcc506fcc5bbb81e206c84506ccca9dc08392d26a11205c14
advice_polys[1][1] = 0x06be2f5f221c5e1f0e2a8aa8f3a7291881e5b312180d758baf42e22fb5564178
advice_polys[1][2] = 0x14e2da0bdbb6f13ea757bbc47e30931a3d437b0d668abb1d191a93664bc87f42
advice_polys[1][3] = 0x2bc488b432b21f6dd20172156de40fabb66187197f05ef774f2b54332d718d9d
advice_polys[1][4] = 0x14f880531ff79a8135dfa79591a5ccedf2228f77e0cb0eeb0be3ab518ce7c258
advice_polys[1][5] = 0x276d2d2370684496b1e47d75b683bcb4d59379a0cdeba9ec60660d3650160b8f
advice_polys[1][6] = 0x13e283c1275092e6ae3495fa7f8ab315db082c16ce763ae72807496a935bb7e4
advice_polys[1][7] = 0x2c06bd7148e6fb37f6f344cd03a615925c9d588b089c96c7cfb902417b3a4b22
...
Evaluation at: 0x2e41c57b0b55f6c28fe3400a1ef0dec2aa51f185e1156f285e78dda24c102bf5 with result 0x17fc29532cb3c0aa587c283328270d76b99f50c0f038e9e66431438bdacc8ad3
Evaluation at: 0x1b36a3314892fc220c1c3558d692f0d17cdea0359317ea9ba05f7af557592553 with result 0x08a3c5b002343a928d7a81021399b78723bd72fd3beba19d9e7bdafca4fc753d
Evaluation at: 0x0f7821cf94df9c91b51d3ce6cb7cb34c590c7997a59537cb59bb677400e86f81 with result 0x30545dd7c357e8584beb0913f43cdb5596a8e60184dd10ba69bb2fb70b70acf6

我们可以立即做出两个观察。第一个是 advice[0].advice_polys[1] 在我们打印它的前后发生了变化，我们需要理解是什么让他发生了变化。第二个是，实际上不止一个而是三个对列 1 的评估。如果我们再运行程序，我们注意到 advice[0].advice_polys[1] 的值在第一次打印和第二次评估之间是相同的，这表明它们保持不变，但是所评估的点不同。

`advice_polys` 是如何被修改的？

检查 advice[0].advice_polys[1] 在两个打印位置之间可能被修改的地方，我们发现如下代码段：

    // 计算建议多项式
    let advice: Vec&lt;AdviceSingle&lt;Scheme::Curve, Coeff>> = advice
        .into_iter()
        .map(
            |AdviceSingle {
                 advice_polys,
                 advice_blinds,
             }| {
                AdviceSingle {
                    advice_polys: advice_polys
                        .into_iter()
                        .map(|poly| domain.lagrange_to_coeff(poly))
                        .collect::&lt;Vec&lt;_>>(),
                    advice_blinds,
                }
            },
        )
        .collect();

这表明原始数据被视为某个域上的多项式评估（因此多项式是以拉格朗日形式给出的），然后被替换成该多项式的系数（通过执行拉格朗日插值↗）。

domain 变量的类型是

/// 该结构包含执行相关操作所需的预计算常数及其他详细信息
/// 在大小为 \(2^k\) 的评估域上和大小为 \(2^{k} * j\) 的扩展域上的操作, \(j \neq 0\)。
##[derive(Clone, Debug)]
pub struct EvaluationDomain&lt;F: Field> {
    n: u64,
    k: u32,
    extended_k: u32,
    omega: F,
    omega_inv: F,
    extended_omega: F,
    extended_omega_inv: F,
    g_coset: F,
    g_coset_inv: F,
    quotient_poly_degree: u64,
    ifft_divisor: F,
    extended_ifft_divisor: F,
    t_evaluations: Vec&lt;F>,
    barycentric_weight: F,
}

并在 create_proof 函数开始的地方生成如下：let domain = &pk.vk.domain;。lagrange_to_coeff 函数的实现使用某种逆傅里叶变换函数，所以通过阅读代码来确认它具体做了什么（例如它正在插值的精确点）可能需要花费很长时间。

相反，我们可以尝试猜测并检查猜测是否正确。通过结构体及其注释，我们可以猜测 omega 很可能是乘法阶为 2^k 的一个域元素，并且 extended_omega 是一个阶为 2^k \cdot j 的元素（其中 (j)取非零），拉格朗日插值所使用的域可能是 1, omega, omega^2, ... 或 1, extended_omega, extended_omega^2, ... — 或 g_coset, g_coset*omega, g_coset*omega^2, ... 或类似的（也许 omega、extended_omega 或 g_coset 的逆也可能使用）。我们可以通过打印 advice[0].advice_polys[1] 在被更改后的评估来检查这些：

首先检查序列中的常数因子。它是 1，g_coset，g_coset_inv，还是 none？

println!("After advice was replaced by doing lagrange_to_coeff.");
println!("Evaluation of advice[0].advice_polys[1] at 1: {:?}",
    eval_polynomial(&advice[0].advice_polys[1], 1.try_into().unwrap() ,));
println!("Evaluation of advice[0].advice_polys[1] at g_coset: {:?}",
    eval_polynomial(&advice[0].advice_polys[1], domain.g_coset ,));
println!("Evaluation of advice[0].advice_polys[1] at g_coset_inv: {:?}",
    eval_polynomial(&advice[0].advice_polys[1], domain.g_coset_inv ,));

尝试编译这个，我们会收到一条关于 g_coset 和 g_coset_inv 是私有字段的反映消息。幸运的是，使用的 halo2 本身是本地的，因此我们将这些字段改为公共的。我们得到了以下输出：

advice_polys[1][0] = 0x0000000000000000000000000000000000000000000000000000000000000000
...
After advice was replaced by doing lagrange_to_coeff.
Evaluation of advice[0].advice_polys[1] at 1: 0x0000000000000000000000000000000000000000000000000000000000000000
Evaluation of advice[0].advice_polys[1] at g_coset: 0x06f0b7392dcdccedf941aa0bf089045e11e169c20c52fcb2bbaaf4191577ac48
Evaluation of advice[0].advice_polys[1] at g_coset_inv: 0x0fb6415c26119da23b2e5477ea4b179edcf8b149f6b9d1fa28397871b759b4e8

从中可以明显看出，第一个评估点是 1。对第二个点的检查也如下：

Evaluation of advice[0].advice_polys[1] at ω: 0x0000000000000000000000000000000000000000000000000000000000000000
Evaluation of advice[0].advice_polys[1] at ω^-1: 0x0000000000000000000000000000000000000000000000000000000000000001
Evaluation of advice[0].advice_polys[1] at ω_ext: 0x05af6f83949440a64e85850e1123de4c443ca875bac8bfefcfec1440bec9c633
Evaluation of advice[0].advice_polys[1] at ω_ext^-1: 0x2580e0afc76e0c038ff21baefaaaf13516b26ed9552142193da3a06b5d3d8c00

从中，我们看出 omega 被使用了。对 omega^-1 的评估结果为 1，这也是我们已知的最后一项的值。所以这表明列的长度确实是 2^k （推定为 omega 的乘法阶），所以 omega^{2^k - 1} = omega^{-1}。

最后，想想秘钥，始终出现在列的索引 2、3 和 4 处。对 omega^2 的评估确实得出了秘钥：

Evaluation of advice[0].advice_polys[1] at ω^2: 0x000000000000000000000000000000000000000000000000000000000000002a

我们如何获取评估点？

现在我们可以忘记原始列。我们知道该多项式的三个评估 — 具体来说是需要向成绩单添加相同的多项式（假设同一秘密）并添加到成绩单——这些评估已经添加到成绩单中，我们需要提取的就是对 omega^2 的多项式评估。看来我们应该能够收集到 64 * 3 = 192 个这样的评估中的多项式（每 64 个证明三个评估），插值这些评估以恢复多项式，然后在 omega^2 处评估以获取秘密。为此，我们需要确认三件事情：

确保通过 transcript.write_scalar 添加到成绩单的值确实可以从我们已经给出的证明文件中提取。
三个评估点在何处进行 — 我们也必须能够根据这些证明计算。
该多项式的阶是否小于 192。

我们可以轻松地回答第三点：

println!("Degree of polynomial is {}", advice[0].advice_polys[1].len());

这将输出：

Degree of polynomial is 64

确实，192 > 64，所以没有问题。

关于第二点，评估像这样进行：

// 在 omega^i x 处评估多项式
let advice_evals: Vec&lt;_> = meta
    .advice_queries
    .iter()
    .map(|&(column, at)| {
        eval_polynomial(
            &advice.advice_polys[column.index()],
            domain.rotate_omega(*x, at),
        )
    })

注释表明评估点的形式是 x \cdot omega^i。我们可以检查一下 rotate_omega 函数来确认这一点：

/// 将某个值乘以运算中的某个 omega 的幂，基本上是在
/// 领域间进行旋转。
pub fn rotate_omega(&self, value: F, rotation: Rotation) -> F {
    let mut point = value;
    if rotation.0 >= 0 {
        point *= &self.get_omega().pow_vartime([rotation.0 as u64]);
    } else {
        point *= &self
            .get_omega_inv()
            .pow_vartime([(rotation.0 as i64).unsigned_abs()]);
    }
    point
}

但这并不一定是我们需要做的。我们应该这样做，根据我们从第一轮获得的旋转来检查每一对点在第二次循环中是否判断是否正确。

在 x*omega^0 的评估结果为 0x02d7c8ef98e58ad739ed798b2b33c03577082d1ada060a332b1c4c48f8f96315
在 x*omega^1 的评估结果为 0x21b649e53a77ca0ff9d6bdf4240dea039e99107b5fdef0b2993bda225c646f56
在 x*omega^2 的评估结果为 0x120391e84c7cee33e6528e479b6af56195af206907bf8177f9a0283f92d01d93
在 x*omega^-1 的评估结果为 0x17f7f5957d854c696698625c9d97072eea21736747c9d05f11cc7f3b42d73ed5
使用旋转 Rotation(0) 的评估结果为 0x05477ffb9c023e6b01ce94a95bf2e65983f5a88c262f3427f6069b47f4336984，结果为 0x02d7c8ef98e58ad739ed798b2b33c03577082d1ada060a332b1c4c48f8f96315
使用旋转 Rotation(1) 的评估结果为 0x0d71106ed9ff2e5eaec860f164bee38f73f0c326694e166e38ca1eab0cc3fb48，结果为 0x21b649e53a77ca0ff9d6bdf4240dea039e99107b5fdef0b2993bda225c646f56
使用旋转 Rotation(-1) 的评估结果为 0x0de7b88317bffbd94211877eca0db5509299e6eb5098c9baffb394c801ceeac5，结果为 0x17f7f5957d854c696698625c9d97072eea21736747c9d05f11cc7f3b42d73ed5

现在我们知道多项式评估的点：$x$、$x \cdot \texttt{omega}$ 和 $x \cdot \texttt{omega}^{-1}$。我们期望 omega 是设置的一部分，因此我们应该可以在解决方案中使用它，但 x 呢？

搜索 x，我们在多项式评估片段上方几行找到了以下代码：

let x: ChallengeX&lt;_> = transcript.squeeze_challenge_scalar();

因此，我们应该能够从Transcript中获得 x。

如何读取Transcript？

在实际比赛中，由于（事后看来）低效的尝试，这花费了相当长的时间。首先一个想法是自己读取Transcript，快进所有不感兴趣的数据，以便获取 x 和三个相关的评估。

这个计划有一个小问题，就是需要花费一点时间来写下Transcript的类型。在我们提供的代码中，Transcript是在 verify_proof 函数中实例化的：

let mut transcript = T::init(proof);

此函数由 from_serialized 调用，其中 T 仅被指定为 Blake2bRead<_, _, Challenge255<_>>。我们可以运行验证器并打印 T 的类型（使用 std::any::type_name），然后修复类型名称中出现的缺失导入和私有模块的问题。这解决了一个小问题，但已经花费了一些时间。

更大的潜在问题是我们需要知道如何正确快速移动通过Transcript。一个想法是读取标量并打印它们，直到在我们自己生成的证明上收到错误，并且知道 x 的值，然后 grep 已知的 x 值以获得正确的索引。但是，在证明过程中，点和标量都在Transcript中写入，我们可能需要按照正确的顺序读取这些不同类型。这无疑是一个可解决的问题，并且不一定需要静态从代码中找出。例如，我们可以在证明生成时将输出打印到Transcript中，告诉我们每个操作，这样就可以将此输出转换为在读取时快速移动到正确位置的命令序列。然而，这未必是最快的方法。

相反，我们可以直接重用已经存在的验证代码并对此稍作修改。验证最终在 halo2/halo2_proofs/src/plonk/verifier.rs 的 verify_proof 函数中结束，其中实际上读取了Transcript。我们复制并粘贴该函数（在同一文件中），赋予一个新的名称，如 return_data_for_attack。我们需要从Transcript中获得 x 的值和三个评估。因此，我们首先将返回值从 Result<Strategy::Output, Error> 更改为 Result<[Scheme::Scalar; 4], Error>。在代码中搜索 let x，我们找到了以下代码片段：

// 采样 x 挑战，用于确保电路
// 以高概率得到满足。
let x: ChallengeX&lt;_> = transcript.squeeze_challenge_scalar();

在稍后的地方，我们找到以下内容：

let advice_evals = (0..num_proofs)
    .map(|_| -> Result&lt;Vec&lt;_>, _> { read_n_scalars(transcript, vk.cs.advice_queries.len()) })
    .collect::&lt;Result&lt;Vec&lt;_>, _>>()?;

我们需要找出应该使用哪些索引以从 advice_evals 中获取正确的三个评估。为此，我们跟踪证明器中的索引并打印输出：

println!("Evaluation at x*omega^0 is {:?}",
    eval_polynomial(&advice[0].advice_polys[1], *x,));
println!("Evaluation at x*omega^1 is {:?}",
    eval_polynomial(&advice[0].advice_polys[1], *x * domain.omega,));
println!("Evaluation at x*omega^-1 is {:?}",
    eval_polynomial(&advice[0].advice_polys[1], *x * domain.omega_inv,));

// 为每个电路实例计算和哈希建议评估
for advice in advice.iter() {
    // 在 omega^i x 的位置评估多项式
    let mut zellic_advice_eval_index = 0;
    let advice_evals: Vec&lt;_> = meta
        .advice_queries
        .iter()
        .map(|&(column, at)| {
            let zellic_eval_point = domain.rotate_omega(*x, at);
            let zellic_result = eval_polynomial(
                &advice.advice_polys[column.index()],
                zellic_eval_point,
            );
            if column.index() == 1 {
                println!("Evaluation index {} with rotation {:?} at {:?} with result {:?}",
                    zellic_advice_eval_index, at, zellic_eval_point, zellic_result);
            }
            zellic_advice_eval_index += 1;
            zellic_result
        })
        .collect();

    // 对每个建议列评估进行哈希
    for eval in advice_evals.iter() {
        transcript.write_scalar(*eval)?;
    }

}

这产生了以下结果：

在 x*omega^0 处的评估为 0x13004cc8bcc62cb548db3b5c06bf79dbe0856cd7155137dd5a929f89d4d281cc
在 x*omega^1 处的评估为 0x06f04fdb8c7b00c9d59ebdb23cbab494aa6e109df4cd2f37c4ebf5b85b5cc6fb
在 x*omega^-1 处的评估为 0x145fb2b0580e9fe42f177441308e53de33a0c36f253396bca8cbe65a6b8d487b
评估索引 1，使用旋转 Rotation(0)，在 0x1fbac78b430ad5b176b57cf21e68d68d09a44c5b45fb7490561a5a6773856d1a 上，结果 0x13004cc8bcc62cb548db3b5c06bf79dbe0856cd7155137dd5a929f89d4d281cc
评估索引 4，使用旋转 Rotation(1)，在 0x1eac263188b07530b1dd195ef81e2791b2388c6472ce990376f1317f0a5679d0 上，结果 0x06f04fdb8c7b00c9d59ebdb23cbab494aa6e109df4cd2f37c4ebf5b85b5cc6fb
评估索引 9，使用旋转 Rotation(-1)，在 0x1def28d72cf461a07043902e0508a57c3f44b5a963479049f0884950f9123810 上，结果 0x145fb2b0580e9fe42f177441308e53de33a0c36f253396bca8cbe65a6b8d487b

因此，我们需要的索引是 1、4 和 9。

回到 halo2/halo2_proofs/src/plonk/verifier.rs 文件中的 return_data_for_attack，我们现在可以在分配 advice_evals 的代码后面添加以下行：

let advice_evals = (0..num_proofs)
    .map(|_| -> Result&lt;Vec&lt;_>, _> { read_n_scalars(transcript, vk.cs.advice_queries.len()) })
    .collect::&lt;Result&lt;Vec&lt;_>, _>>()?;

return Ok([*x, advice_evals[0][1], advice_evals[0][4], advice_evals[0][9]]);

由于编译器对该 return 之后的返回不正确的类型产生了警告，我们删除了插入代码下面的其余部分。

halo2/halo2_proofs/src/plonk/verifier.rs 文件中的 verify_proof 函数由 src/main.rs 的此函数调用（在这里称为 verify_plonk_proof）：

pub fn verify_proof&lt;
// ...
>(
    params_verifier: &'params Scheme::ParamsVerifier,
    vk: &VerifyingKey&lt;Scheme::Curve>,
    proof: &'a [u8],
    nullifier: Fr,
    commitment: Fr,
) where
    Scheme::Scalar: Ord + WithSmallOrderMulGroup&lt;3> + FromUniformBytes&lt;64>,
{
    // ...
    let strategy = verify_plonk_proof(
        params_verifier,
        vk,
        strategy,
        &[&[&pubinputs[..]]],
        &mut transcript,
    )
    .unwrap();

    assert!(strategy.finalize());
}

我们可以复制并粘贴此代码，给它一个新名称（也许是 return_data_for_attack_wrapper），让返回类型为 [Scheme::Scalar; 4]，并将

let strategy = verify_plonk_proof(
    params_verifier,
    vk,
    strategy,
    &[&[&pubinputs[..]]],
    &mut transcript,
)
.unwrap();

assert!(strategy.finalize());

替换为

return_data_for_attack(
    params_verifier,
    vk,
    strategy,
    &[&[&pubinputs[..]]],
    &mut transcript,
)
.unwrap()

现在，这个函数仍然需要作为参数的一些参数，所以我们最终复制这个反序列化证明并调用验证器的函数：

fn from_serialized(i: usize) -> (Vec&lt;u8>, Fr, Fr) {
    use halo2_proofs::poly::kzg::commitment::{KZGCommitmentScheme, ParamsKZG};
    use halo2_proofs::poly::kzg::multiopen::VerifierSHPLONK;
    use halo2_proofs::poly::kzg::strategy::AccumulatorStrategy;
    use halo2curves::bn256::Bn256;

    let setup_rng = ChaCha20Rng::from_seed([1u8; 32]);
    let params = ParamsKZG::&lt;Bn256>::setup(K, setup_rng);

    let pk = keygen::&lt;KZGCommitmentScheme&lt;_>>(&params);

    let (proofs, nullifiers, commitments) = deserialize();

    let proof = proofs[i].clone();
    let nullifier = nullifiers[i];
    let commitment = commitments[i];

    let verifier_params = params.verifier_params();
    verify_proof::&lt;
        _,
        VerifierSHPLONK&lt;_>,
        _,
        Blake2bRead&lt;_, _, Challenge255&lt;_>>,
        AccumulatorStrategy&lt;_>,
    >(
        verifier_params,
        pk.get_vk(),
        &proof[..],
        nullifier,
        commitment,
    );

    (proof, nullifier, commitment)
}

创建新的 get_attack_data_from_serialized 函数，该函数返回 [Fr; 4]；在替换证明的验证和返回行时，替换为以下内容。

return_data_for_attack_wrapper::&lt;
    _,
    VerifierSHPLONK&lt;_>,
    _,
    Blake2bRead&lt;_, _, Challenge255&lt;_>>,
    AccumulatorStrategy&lt;_>,
>(
    verifier_params,
    pk.get_vk(),
    &proof[..],
    nullifier,
    commitment,
)

我们如何获取 Omega？

最后，我们还需要 omega 的值。在证明器中，我们能够访问该值作为 domain.omega，而搜索 let domain 时，我们发现 let domain = &pk.vk.domain;。这里 pk 是传递给 create_proof 函数的类型为 &ProvingKey<Scheme::Curve> 的参数。在 main.rs 中，我们可以找到一个生成的证明密钥，例如在我们刚刚考虑的 from_serialized 中。我们可以使用这段代码创建一个获取域的函数：

fn get_domain() -> EvaluationDomain&lt;Bn256Fr> {
    use halo2_proofs::poly::kzg::commitment::{KZGCommitmentScheme, ParamsKZG};
    use halo2_proofs::poly::kzg::multiopen::VerifierSHPLONK;
    use halo2_proofs::poly::kzg::strategy::AccumulatorStrategy;
    use halo2curves::bn256::Bn256;

    let setup_rng = ChaCha20Rng::from_seed([1u8; 32]);
    let params = ParamsKZG::&lt;Bn256>::setup(K, setup_rng);

    let pk = keygen::&lt;KZGCommitmentScheme&lt;_>>(&params);

    return pk.vk.domain
}

解决方案

现在我们可以在 main 函数中完成解决方案。没有必要实现多项式插值，因为 halo2 已经提供了相关的函数：

let omega = get_domain().omega;
let omega_inv = get_domain().omega_inv;
let mut points = vec![];
let mut values = vec![];
for i in 0..64 {
    println!("提取证明中的数据 {}", i);
    let data = get_attack_data_from_serialized(i);
    let x = data[0];
    let atx = data[1];
    let atxomega = data[2];
    let atxomageinv = data[3];
    points.push(x);
    values.push(atx);
    points.push(x*omega);
    values.push(atxomega);
    points.push(x*omega_inv);
    values.push(atxomageinv);
}

println!("收集的值...");
let coeffs = lagrange_interpolate(&points, &values);
println!("获得多项式系数");
let secret = eval_polynomial(&coeffs, omega*omega*omega);

println!("恢复的秘密: {:?}", secret);

通过这种方式，挑战得以解决，恢复的秘密为 0x066ab256379d1a0d7bd1dd54cf3f4171edbf5ca3976e8956fe0ddd10af67418d！

谜题 2: Don't Look Up

这个谜题的描述告诉我们，它包含了 Rust 中的实现 ProtoStar↗，一个变体的查找协议 LogUp↗，在有限域 $\mathbb{F}_{p^6}$ 上实例化，其中 $p$ 是一个 16 位素数。我们的任务是使协议接受一个在范围 $[0, 2^6 - 1]$ 内的 “证明” $2^{15}$。

理解任务

谜题附带三个源文件：lib.rs，似乎包含了必要基础操作的实现，如有限域的算术运算；protocol.rs，包含查找协议的实现；以及主源码文件 main.rs。

main.rs 文件指定了挑战：

pub fn main() {
    welcome();
    puzzle(PUZZLE_DESCRIPTION);

    let p = 70937;
    let irr = vec![3, 39025, 15086, 45405, 34941, 70897, 1]; // x^6 + 70897x^5 + 34941x^4 + 45405x^3 + 15086x^2 + 39025x + 3

    let invalid_witness = FieldElement::new(vec![1&lt;&lt;15], p, irr.clone());

    /* BEGIN HACK */
    let witness = vec![];
    let m = vec![FieldElement::new(vec![0], p, irr.clone()); 1&lt;&lt;6];
    /* END HACK */

    let mut table = vec![];
    for i in 0..1 &lt;&lt; 6 {
        table.push(FieldElement::new(vec![i], p, irr.clone()));
    }

    let l = witness.len(); // witness length
    let t = table.len(); // table size
    assert!(witness.contains(&invalid_witness));

    let protocol = Protocol::new(l, t, p, irr.clone());

    let statement = Statement::new(&table);

    let w = Witness::new(&witness);

    let msg1 = protocol.prove_round1(&w, &m);
    let r = protocol.verify_round1(&msg1);
    let msg2 = protocol.prove_round2(&r, &msg1, &statement);
    assert!(protocol.verify_round2(&msg1, &msg2, &statement));
}

在 HACK 部分之后的代码创建了 table，一个包含范围 $[0, 2^6 - 1]$ 所有值的向量。然后它执行查找协议，使用 table 作为声明， witness，一个字段元素向量，作为见证。我们可以更改 witness。从挑战的上下文来看，明确的解释是 witness 向量的条目将在 table 向量中被查找。还有一个长度为 262^626 的字段元素向量 m，我们也可以更改。最简单的解释是 m[i] 是我们希望证明 table[i] 在 witness 中出现的次数。

协议 without Looking 的解决方案

我们需要使两个断言通过：1）witness 必须包含 invalid_witness，2）协议必须成功。关于第一个条件几乎没有灵活性，因此至少需要一个 witness 组件为 invalid_witness = 2<<15，而这不幸的是在 table 中不存在。因此，让我们专注于第二个条件。

该协议在 protocol.rs 中实现，但该文件长达 253 行，如果希望快速解决挑战，我们没有时间通读它。我们可以尝试猜测实现该协议的关键特性。为此，我们可以问自己，协议如何捕捉 witness 组件的顺序不应重要的事实。如果协议最终在有限域中执行检查作为相等检查，它如何从许多元素中计算出有限域的某个元素，而不依赖于顺序？

很明显，两种容易想到的方式是加法和乘法。假设我们可以猜测一种可能性是协议执行检查 $ \sum f(w_i) = ?$ 或 $ \prod f(w_i) = ?$，其中 $w_1, \dots, w_l$ 是 witness 的组件， $f$ 是应用于见证的某种映射。暂时假设这确实是协议所做的，回顾我们的问题。

我们必须使至少一个 $w_i$ 等于 $2^{15}$，而这在 table 中并不存在。这很可能意味着我们无法将 $f(2^{15})$ 与检查方程右侧的项相抵消。因此，我们必须借助其他项取消这一项。由于我们不知道 $f$ 是什么，解决这一问题的一种方法是重复 $f(2^{15})$ 至少足够多的次数；有限域研究的特性意味着 $p \cdot f(2^{15}) = 0$，而有限域的乘法群的阶是 $p^6 - 1$，因此 $f(2^{15})^{p^6 - 1} = 1$。如果检查是乘法性的，这将无效，因为 $p^6 - 1$ 将太大。然而，$p$ 足够小，以使长度为 $p$ 的见证可行。因此，我们可以尝试将 witness 设置为正好 $p$ 重复 $2^{15}$，希望能够抵消并且不会对检查左侧贡献，并将 m 设置为全零：

    /* BEGIN HACK */
    let witness = vec![invalid_witness.clone(); p as usize];
    let m = vec![FieldElement::new(vec![0], p, irr.clone()); 1&lt;&lt;6];
    /* END HACK */

这确实解决了挑战！

协议 with Looking的解决方案

pub fn verify_round2(&self, msg1: &ProverMessage1, msg2: &ProverMessage2, statement: &Statement) -> bool {
    // 从 msg1 重新计算挑战
    let r = self.hash_to_field(msg1);

    // 检查 sum(h_i) = sum(g_i)
    let sum_h = msg2.h.iter()
        .fold(FieldElement::new(vec![0], self.field_char, self.irr.clone()),
                |acc, x| acc + x.clone());

    let sum_g = msg2.g.iter()
        .fold(FieldElement::new(vec![0], self.field_char, self.irr.clone()),
                |acc, x| acc + x.clone());

    if sum_h != sum_g {
        return false;
    }

    // 检查 h_i·(w_i + r) = 1 对所有 i
    for i in 0..self.l {
        let one = FieldElement::new(vec![1], self.field_char, self.irr.clone());
        let w_plus_r = msg1.w[i].clone() + r.clone();
        if (msg2.h[i].clone() * w_plus_r) != one {
            return false;
        }
    }

    // 检查 g_i·(t_i + r) = m_i 对所有 i
    for i in 0..self.t {
        let t_plus_r = statement.t[i].clone() + r.clone();
        if (msg2.g[i].clone() * t_plus_r) != msg1.m[i] {
            return false;
        }
    }

    true
}

let l = witness.len(); // witness length
let t = table.len(); // table size

然后我们可以从 verify_round2 中的两个循环中得知每个组件的 witness 有一个 $h_i$，并且每个组件的 table 有一个 $g_i$。

谜题 3: Shadow

这一谜题是用 Noir 编写的。自述文件指出，有一个白名单，由 pk_pepper 形式的哈希值组成，其中 pk 是公钥，pepper 是相关的秘密值。我们有一对合法的公钥–pepper，以及另一个公钥，我们的目标是通过使用这个目标公钥来通过电路的检查。

理解任务

Noir 源代码并不冗长：

// 该文件不可修改

use noir_string_search::{StringBody, StringBody128, SubString, SubString32};

// alice_pk = [155, 143, 27, 66, 87, 125, 33, 110, 57, 153, 93, 228, 167, 76, 120, 220, 178, 200, 187, 35, 211, 175, 104, 63, 140, 208, 36, 184, 88, 1, 203, 62]
// alice_pepper = [213, 231, 76, 105, 105, 96, 199, 183, 106, 26, 29, 7, 28, 234, 145, 69, 48, 9, 254, 205, 79, 21, 90, 13, 39, 172, 114, 59, 131, 15, 78, 118]

fn main(identifier: BoundedVec&lt;u8, 128>, pub_key: pub [u8; 32], whitelist: pub [[u8; 32]; 10]) {
    // identifier 哈希到的摘要在公共白名单中
    let digest = std::hash::sha256_var(identifier.storage(), identifier.len() as u64);
    let mut present = false;
    for i in 0..whitelist.len() {
        if whitelist[i] == digest {
            present = true;
        }
    }
    assert(present);

    // 指定的公钥在 identifier 中
    let id_haystack: StringBody128 = StringBody::new(identifier.storage(), 128);
    let pk_needle: SubString32 = SubString::new(pub_key, 32);
    let (result, _): (bool, u32) = id_haystack.substring_match(pk_needle);
    assert(result);
}

注释揭示了我们所提到的有效的公钥–pepper 对。电路获得了一个由最多 128 个 u8 组件组成的私有见证 identifier，以及公共输入 pub_key 和 whitelist。这些数据来自 Prover.toml 文件，其中 pub_key 和 whitelist 是固定的，而我们允许更改私有见证 identifier：

## BEGIN HACK

[identifier]
[len = "128"]
[storage = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]

## END HACK

解决方案

遍历电路，它首先计算前 identifier.len() 组件的 SHA-256 哈希，然后断言白名单中的某个条目等于生成的哈希。之后，它检测 pub_key 是否是前 128 个 identifier.storage() 的子字符串。

我们知道唯一的白名单条目，其预影是 alice_pk 与 alice_pepper 的连接，中间加一个下划线。请注意，这个预影的长度为 65。只要 SHA-256 没有被破坏到可以查找预影或者碰撞，我们必须使用 identifier.len() = 65，并用这个已知预影填充 identifier.storage() 的前 65 个组件。这将使第一个断言通过。对于第二个断言，我们可以注意到在 identifier.storage() 的前 128 - 65 = 63 个组件中放置长度为 32 的子字符串 pub_key 是足够的。

使用交互式 Python 解释器，我们可以非常快速地计算出可用于 identifier.storage() 的列表，以解决此挑战：

>>> alice_pk = [155, 143, 27, 66, 87, 125, 33, 110, 57, 153, 93, 228, 167, 76, 120, 220, 178, 200, 187, 35, 211, 175, 104, 63, 140, 208, 36, 184, 88, 1, 203, 62]
>>> alice_pepper = [213, 231, 76, 105, 105, 96, 199, 183, 106, 26, 29, 7, 28, 234, 145, 69, 48, 9, 254, 205, 79, 21, 90, 13, 39, 172, 114, 59, 131, 15, 78, 118]
>>> pub_key = [157, 133, 167, 136, 43, 161, 75, 166, 33, 14, 35, 106, 238, 18, 60, 56, 93, 209, 205, 52, 247, 110, 174, 192, 20, 58, 70, 42, 215, 98, 195, 150]
>>> alice_pk + [ord('_')] + alice_pepper + pub_key + [0]*(128-32-1-32-32)
[155, 143, 27, 66, 87, 125, 33, 110, 57, 153, 93, 228, 167, 76, 120, 220, 178, 200, 187, 35, 211, 175, 104, 63, 140, 208, 36, 184, 88, 1, 203, 62, 95, 213, 231, 76, 105, 105, 96, 199, 183, 106, 26, 29, 7, 28, 234, 145, 69, 48, 9, 254, 205, 79, 21, 90, 13, 39, 172, 114, 59, 131, 15, 78, 118, 157, 133, 167, 136, 43, 161, 75, 166, 33, 14, 35, 106, 238, 18, 60, 56, 93, 209, 205, 52, 247, 110, 174, 192, 20, 58, 70, 42, 215, 98, 195, 150, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

结论

我们要感谢 ZK Hack 组织这次比赛，也感谢 Bain Capital Crypto 创建这三道有趣的谜题。

关于我们

Zellic 专注于保护新兴技术。我们的安全研究人员已在最有价值的目标中发现漏洞，从财富 500 强到 DeFi 巨头。

请联系我们↗ 进行一次更好的审计。真正的审计，而非走过场。

原文链接： zellic.io/blog/zellic-wi...

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

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

拆解ZK Hack V中的难题

谜题 1: Zeitgeist

理解任务

电路的功能是什么？

缺乏盲因子

找到有趣的列

我们掌握了什么信息？

多项式评估

`advice_polys` 是如何被修改的？

我们如何获取评估点？

如何读取Transcript？

我们如何获取 Omega？

解决方案

谜题 2: Don't Look Up

理解任务

协议 without Looking 的解决方案

协议 with Looking的解决方案

谜题 3: Shadow

理解任务

解决方案

结论

关于我们

0 条评论

文章目录

拆解ZK Hack V中的难题

谜题 1: Zeitgeist

理解任务

电路的功能是什么？

缺乏盲因子

找到有趣的列

我们掌握了什么信息？

多项式评估

advice_polys 是如何被修改的？

我们如何获取评估点？

如何读取Transcript？

我们如何获取 Omega？

解决方案

谜题 2: Don't Look Up

理解任务

协议 without Looking 的解决方案

协议 with Looking的解决方案

谜题 3: Shadow

理解任务

解决方案

结论

关于我们

0 条评论

文章目录

`advice_polys` 是如何被修改的？