cover_image

题解：ZK HACK IV- Puzzle F1 Gamma Ray

Kurt Pan XPTY
2024年01月25日 17:28

原文：https://zkhack.dev/zkhackIV/solutionF1.html

作者：Nicolas IOOSS

译者：Kurt Pan

1. 题目

Bob was deeply inspired by the Zcash design [1] for private transactions and had
some pretty cool ideas on how to adapt it for his requirements. He was also
inspired by the Mina design for the lightest blockchain and wanted to combine
the two. In order to achieve that, Bob used the MNT6753 cycle of curves to
enable efficient infinite recursion, and used elliptic curve public keys to
authorize spends. He released a first version of the system to the world and
Alice soon announced she was able to double spend by creating two different
nullifiers for the same key...

[1] https://zips.z.cash/protocol/protocol.pdf

我们来搞清楚实现中包含哪些内容以及可能存在哪些错误！

2. 从Rust代码到零知识证明

问题在这个GitHub库中，包括一个Rust 项目和一些其他文件。主要代码在 src/main.rs 中。函数 main 加载一些文件，计算一些东西，然后生成一个证明：

let c = SpendCircuit {
    leaf_params: leaf_crh_params.clone(),
    two_to_one_params: two_to_one_crh_params.clone(),
    root: root.clone(),
    proof: tree_proof.clone(),
    nullifier: nullifier.clone(),
    secret: leaked_secret.clone(),
};

let proof = Groth16::<MNT4_753>::prove(&pk, c.clone(), rng).unwrap();

assert!(Groth16::<MNT4_753>::verify(&vk, &vec![root, nullifier], &proof).unwrap());

这段代码涉及了一些对于零知识世界的新手来说不熟悉的词。首先，它创建一个 SpendCircuit 结构体。ZK Jargon Decoder将“电路”定义为：

在 ZK 文献中，这通常指算术电路：加法和乘法（有时是自定义运算）的有序集合，应用于一组输入以产生输出。

在同一个文件中，有：

impl ConstraintSynthesizer<ConstraintF> for SpendCircuit {
    fn generate_constraints(
        self,
        cs: ConstraintSystemRef<ConstraintF>,
    ) -> Result<(), SynthesisError> {

此函数在结构体 SpendCircuit 中存在的变量（ leaf_params 、 two_to_one_params 、 root ...）之间进行操作，并确保这些操作的结果匹配一些称为约束的性质。

这在项目中被用于生成 Groth16 证明系统中使用的许多约束。该系统可以构造对一些性质的证明，例如“证明者知道一些匹配所有约束的值”。这些值称为见证或私有输入。证明系统还可以在不知道见证是什么的情况下验证这些证明。

什么是Groth16？当在 https://zkpod.ai/ 上询问时，聊天机器人回复道：

Groth16 是一个用于验证多项式关系的证明系统。 它通常部署在PLONK或Groth16自己的结构等系统中。 这是一种经济高效的解决方案，但需要可信设置仪式。 Groth16 证明系统是通过 Groth 16 论文引入的。 Groth16 对配对友好曲线可以更高效地工作。 在 zkEVM 项目中，创建 STARK 证明，然后使用 PLONK 或 Groth16 进行验证，结合了这两个系统的优点。

来源： Episode 194, Episode 242, Episode 289

还有一些关于 Groth16 的博客文章，例如 https://blog.lambdaclass.com/groth16/ 。文中解释说，Groth16 这个名字实际上来自 Jens Groth 在 2016 年发表的论文《On the Size of Pairing-based Non-interactive Arguments》。

Groth16 依赖椭圆曲线来执行运算。此处，代码使用 Groth16::<MNT4_753> ，其使用了 src/main.rs 顶部的此行导入的类型：

use ark_mnt4_753::{Fr as MNT4BigFr, MNT4_753};

这使用了 Rust crate ark-mnt4-753 ，文档写道：

该库实现了 [BCTV14] 中出现的 MNT4_753 曲线。该名称表示它是一条嵌入度为 4 的 Miyaji-Nakabayashi-Takano 曲线，在 753 比特（素数）域上定义。该曲线的主要特点是其标量域和基域分别等于MNT6_753的基域和标量域。

简而言之，该程序使用 MNT4-753 上的 Groth16 证明系统来生成证明。

那么，实际上证明了什么呢？

3. 解码约束

在该项目中， src/main.rs 构建了一个电路并使用 Groth16 生成了一个证明。该电路使用第 63-71 行中名为 SpendCircuit 的结构体中定义的六个参数：

struct SpendCircuit {
    pub leaf_params: <LeafH as CRHScheme>::Parameters,
    pub two_to_one_params: <LeafH as CRHScheme>::Parameters,
    pub root: <CompressH as TwoToOneCRHScheme>::Output,
    pub proof: Path<MntMerkleTreeParams>,
    pub secret: ConstraintF,
    pub nullifier: ConstraintF,
}

目前还不清楚这些字段的含义。这些类型可以提供一些在文档的提示。

CRHScheme 在 ark_crypto_primitives 中定义并记录为“CRH 接口”。但是CRH是什么意思呢？Cryptology ePrint Archive) 上的一篇论文提供了该缩写的含义：

抗碰撞哈希函数 (CRH) 是一种基本且普遍存在的密码学原语。

所以它似乎类似密码学哈希函数（CHF）。

MntMerkleTreeParams 指的是默克尔树，在维基百科中定义为：

在密码学和计算机科学中，哈希树或 默克尔树是一棵树，其中每个“叶子”（节点）都标有数据块的密码学哈希，并且每个不是叶子的节点（称为分支、内部节点或 inode）用其子节点标签的密码学哈希进行标记。哈希树允许对大型数据结构的内容进行高效且安全的验证。

维基百科文章还提供了一个有用的图：

这使得 root 和 TwoToOneCRHScheme 的目的更加清晰了： root 是默克尔树的顶部哈希， TwoToOneCRHScheme 是抗碰撞哈希函数 (CRH) ，用于将两个哈希合并为一个。顺便说一下，这被称为树，因为它是一种特殊的图。

nullifier 是 Zcash 协议规范中使用的术语，在题目的参考中给出。在第 3.2.3 节中：

票据的nullifier[...]是票据独有的值，用于防止双花。

在项目中， src/main.rs 的第155行为：

let nullifier = <LeafH as CRHScheme>::evaluate(&leaf_crh_params, vec![leaked_secret]).unwrap();

此代码实际上计算名为 leaked_secret 的值的哈希值，该值在字段 secret 中使用。因此 nullifier 是 secret 的哈希值。秘密为何会泄露？这一点之后会变得更加清楚。

现在分析第 74 行中的函数 generate_constraints ，以更好地理解 secret 、 root 、 nullifier ... 在Groth16证明中是如何紧密结合的。由于代码比较冗长，这里就不复制了。相反，这里是代码的英文翻译：

  • 将变量 root 定义为公开输入。
  • 将 leaf_crh_params_var 和 two_to_one_crh_params_var 定义为常量。
  • 将 secret 定义为见证（因此是私有输入）。
  • 提取 secret_bits 中 secret 的比特（按小端序）。
  • 确保 secrets 小于等于 MNT6-753 标量域的模( MNT6BigFr::MODULUS ) 。
  • 将 nullifier 定义为输出。
  • 使用参数 leaf_crh_params_var 将 nullifier_in_circuit 计算为 [secret] 的哈希值，并确保其等于 nullifier 。
  • 将 base 定义为 MNT6-753 的 G1 曲线的生成元（在 ark-mnt6-753的文档中定义）。
  • 以仿射表示形式将 pk 定义为 secret_bits 与 base 的标量积。此操作通常在椭圆曲线密码学中计算与私钥 ( secret ) 关联的公钥 ( pk )。
  • 将 leaf_g 定义为 [pk.x] ，这是一个单元素向量，其 x 坐标为公钥。
  • 将 cw 定义为与结构体 SpendCircuit 的字段 proof 关联的见证。它的类型是 PathVar ，表示默克尔树路径。
  • 验证 cw 是 leaf_g 是具有根 root 、参数 leaf_crh_params_var 和 two_to_one_crh_params_var 的默克尔树的有效证明。

由于有很多变量，让我们稍微简化一下。

3. 理解约束

前面部分解释了该项目是如何在曲线 MNT4-753 上生成 Groth16 证明的，但其中的约束乍一看似乎相当复杂。这种复杂性可以通过一些记号来克服。

首先，函数 main 包括（第 153 行：

    let two_to_one_crh_params = leaf_crh_params.clone();

所以实践中，使用唯一的一个哈希函数，即由 src/poseidon_parameters.rs 中的 poseidon_parameters 给出参数定义。我们将此函数称为。

其次，MNT4-753 和 MNT6-753 曲线会使用多个可能令人困惑的参数，因为一条曲线的基域是另一条曲线的标量域。我们使用标量素数，并将定义为 MNT4-753 标量域的阶（即“元素数量”），将 定义为 MNT6-753 的阶。 Rust 代码中，是 MNT4BigFr::MODULUS ， 为MNT6BigFr::MODULUS 。

第三，结构体 SpendCircuit 中的 proof 是通过在第 166 行生成 Merkle 树的成员资格证明来计算的。电路验证此证明，把 pk 和 root联系在一起。

最后，还有一个问题：像 secret 、 nullifier ... 这样的值在哪个有限域中？所有这些变量都使用类型 ConstraintF ，在第 22 行定义为 MNT4BigFr 。因此 secret 和 nullifier 是 MNT4-753 标量域中的数。此外，MNT6-753 的 G1 曲线上的点的坐标也定义在 MNT4-753 的标量域上（这就是为什么说两条曲线构成一个循环）。所以 pk.x 也是MNT4-753标量域中的数。

使用这些记号，约束变为：

  • 确保 secret
  • 计算 nullifier =  ( secret ) 并确保它等于作为公共输入给出的 nullifier （在零知识电路中，输出变量通常被视为公开输入）。
  • 计算 pk 作为与 secret 关联的 MNT6-753 G1 曲线上的公钥。它是椭圆曲线上的一个点，其仿射表示由两个坐标 (pk.x, pk.y) 组成。
  • 确保 [pk.x] 是使用哈希构建并使用根 root 定义的 Merkle 树的叶子（作为公开输入给出）。

这是使用 root 和 nullifier 调用 Groth16 验证时在第 187 行所验证的内容：

    assert!(Groth16::<MNT4_753>::verify(&vk, &vec![root, nullifier], &proof).unwrap());

简而言之，该项目似乎为以下语句生成了证明：

“证明者知道 secret ，其哈希值是给定的 nullifier ，其公钥是根为 root 的 Merkle 树的叶子”。

实际上，这和Semaphore的电路类似。 secret 用作群组成员的私钥，这可能就是它被命名为 leaked_secret 的原因：该项目能够生成证明，因为它知道一个私钥。

4. Attacking the circuit 攻击电路

前面几节说明了该项目实现的电路验证了关联 secret 、 nullifier 和 root 的一些约束。但安全吗？

题目中说并不安全：

Alice很快宣布她能够通过为同一密钥创建两个不同的nullifiers来进行双花......

由于nullifier是直接从密钥（使用哈希函数）计算出来的，因此在使用相同的 secret 的同时拥有两个不同的 nullifier 值似乎很困难。那公钥呢？

secret 是 MNT4-753 标量域中的元素，可将其视为整数，使得：  secret  。公钥 pk 是在 MNT6-753 的 G1 曲线上计算的，这意味着 secret 被视为模  。且  。因此 secret   也将是同一公钥的有效私钥，并且会给出一个不同的 nullifier 。然而，电路通过验证 secret  阻止了这种攻击。糟糕，没有起作用。

但事实上，默克尔树中使用的公钥并不是点 pk ，而只是它的 x 坐标。电路这样做的原因由土木的第一个提示给出：

提示 1. 请参阅 Zcash 规范中的引理 5.4.7，了解 Bob 关于为什么在存储公钥时仅使用 x 坐标的理由。

事实上，“5.4.9.4 Jubjub 的坐标提取器”部分的引理 5.4.7 （第 102 页）证明了，如果点在子群中，则点 不能在子群中。接着同页定理 5.4.8 使用这个引理证明了函数  是单射的，意味着对于任何 ，最多存在一个使得点 在子群中。因此，在使用Jubjub曲线时，使用点的第一个坐标就足以保证两个密钥之间不会发生碰撞。

然而，该项目在这里使用的是 MNT6-753 的 G1 曲线而不是 Jubjub。这条曲线非常不同：

  • MNT6-753的G1曲线方程为  （其中  和  为常数）。这通常称为曲线的 Weierstrass 形式。
  • The equation of Jubjub is . This is usually called a twisted Edwards curve.
  • Jubjub 的方程为 。这通常称为twisted Edwards 曲线。

对于 Weierstrass 形式的曲线, 当 是子群中的点时, 相反的 始终在子群中, 其坐标为 。这意味着 -secret 是点 的私钥, 其 坐标与pk.x相同。这看起来有希望了!

但 secret 表示为小于的非负整数。在 MNT6-753 的标量域中取相反值的一种可能方法是计算： secret_hack = - secret （这是有效的，因为 secret 也小于）。以下代码测试了该攻击，写在第191行：

// 计算-pk的私钥和相关的nullifier
let secret_hack = MNT4BigFr::from(MNT6BigFr::MODULUS) - leaked_secret;
let nullifier_hack =
    <LeafH as CRHScheme>::evaluate(&leaf_crh_params, vec![secret_hack]).unwrap();

// 确保新nullifier是不同的
assert_ne!(nullifier, nullifier_hack);

//使用这个新secret和nullifier生成一个证明，使用同一个公钥
let c2 = SpendCircuit {
    leaf_params: leaf_crh_params.clone(),
    two_to_one_params: two_to_one_crh_params.clone(),
    root: root.clone(),
    proof: tree_proof.clone(),
    nullifier: nullifier_hack.clone(),
    secret: secret_hack.clone(),
};
let proof = Groth16::<MNT4_753>::prove(&pk, c2.clone(), rng).unwrap();

// 验证证明是正确的
assert!(Groth16::<MNT4_753>::verify(&vk, &vec![root, nullifier_hack], &proof).unwrap());

这成功了：该攻击为同一个公钥生成了不同的nullifier！

5. 结论

该项目实现了一个类似Semaphore的电路，其中默克尔树的每个成员都拥有一个秘密，并且可以发布一些与它们相关的nullifier。它重用了 Zcash 协议规范中的思想，仅使用默克尔树中公钥的第一个坐标。但它使用了 Weierstrass 形式的曲线，和Zcash 不同。这导致了一个漏洞，成员可以从他们的秘密中制作第二个nullifier。