解析ZK Hack IV中的难题

Zellic 的加密团队（Malte Leip、Mohit Sharma 和 Avi Weinstock）以及 Sampriti Panda 参与了最近的 ZK Hack 竞赛 ZK Hack IV↗，该竞赛共包含三个难题，得分由解决问题的速度决定。我们很高兴地赢得了第一个难题，并在第三个难题中获得第二名，最终总排名为第二。

此次 ZK Hack 的难题由小型加密应用程序组成，这些应用程序使用 arkworks 库↗ 编写。它们结合了通常用于 ZK 项目的加密原语，但在每个难题中都引入了一种漏洞。任务是理解提供的代码，理论上找到漏洞，然后实现一个利用所发现漏洞的解决方案。

难题 1: Gamma Ray

在第一个难题中，给出了一部分小型 Zcash 克隆，任务是对一个票据进行双重支付。Zcash 通过使用 nullifiers（无效标识）来防止双重支付；要花费一个票据，你必须揭示与该票据相关联的无效标识，而这一无效标识会被标记为已使用。已经使用的无效标识无法再使用，因此只要每个票据只能计算出一个有效的无效标识，就可以防止双重支付。

然而，在这个难题中，关系大致为：nullifier=hash(secret) 和 note=(secret⋅basepoint).x，其中 basepoint 是椭圆曲线上的一个点，而 .x 指的是仿射坐标中的 x 坐标。如果 (x,y) 是该椭圆曲线上的一个仿射坐标点，则有 −(x,y)=(x,−y)，因此它们具有相同的 x 坐标。因此，如果我们将 secret 替换为 −secret（以 basepoint 的阶取模），那么 note 不会改变，但 hash 将发生变化，因此我们获得了与该票据关联的第二个无效标识。可以在 ZK Hack 针对此难题的页面↗ 找到更详细的说明。

这是我们的解决方案代码：

let secret_hack = MNT4BigFr::from(MNT6BigFr::MODULUS) - MNT4BigFr::from(leaked_secret);
let nullifier_hack = <LeafH as CRHScheme>::evaluate(&leaf_crh_params, vec![secret_hack]).unwrap();

难题 2: Supervillain

第二个难题涉及聚合 BLS 签名与简单的知识证明方案的结合。这两者都使用了配对 e:G1×G2→G3。我们最近发布了一篇 关于配对的入门文章↗，如果你想要入门，请查看一下。

在固定的哈希消息 m∈G2 的签名序列中，签名序号 iii 的签名使用的公钥为 pki，形式为 pki=ski⋅g，其中 g 是 G1 的一个固定元素。签名是一个普通的 BLS 签名，因此 sigi=ski⋅m。这些签名可以被聚合为 sig=∑isigi，pk=∑ipki，并通过检查 e(pk,m)=e(g,sig) 来验证。这一等式的成立源于 e(pki,m)=e(g,sigi)，而这些等式成立则是 e 的双线性性质的结果。

为了证明签名者真正知道 sk，签名者可以提供另一个椭圆曲线元素 pfi，验证检查是 e(pki,i⋅h)=e(g,pfi)，其中 h∈G2 是一个固定元素。

在该难题中，我们提供了一组公钥和证明 pk1,…,pkn 和 pf1,…,pfn，对这些证明的知识验证成功（我们未获得 sk）。我们的任务是为 skn+1 和 pfn+1 提供一个合法组合，使得这个证明的知识验证成功，同时提供一个将为特定哈希消息 m 验证的 BLS 签名 sig。这意味着我们的约束为。

e(pkn+1,(n+1)⋅h)=e(g,pfn+1)

和

e(∑i=1n+1pki,m)=e(g,sig)

我们有 e(pki,i⋅h)=e(g,pfi) 对于 i≤n。可用的等式可以用于第一个约束，但不能用于第二个，因此为了使第二个约束成立，我们选择 pkn+1=−∑i=1n pki 和 sig=0，从而使两边均为 0。第一个约束的左侧可以重新写为：

e(pkn+1,(n+1)⋅h)=e(−∑i=1npki,(n+1)⋅h)=−∑i=1ne(pki,(n+1)⋅h)

这样我们必须选择 pfn+1 的方式使得以下等式成立：

e(g,−∑i=1nn+1ipfi)=e(g,pfn+1)

该难题因此得以解决，通过使用 pfn+1=−∑i=1nn+1ipfi。

可以在其 ZK Hack 页面↗ 找到对此难题的更详细的说明。

这是我们的解决方案代码：

let aggregate_rest = public_keys
    .iter()
    .fold(G1Projective::zero(), |acc, (pk, _)| acc + pk)
    .into_affine();
let new_key = aggregate_rest.neg();

let proofs_raw = public_keys
    .iter()
    .enumerate()
    .map(|(i, (_pk, proof))| *proof * Fr::from(i as u64 + 1).inverse().unwrap());
let proofs_add = proofs_raw.fold(G2Projective::zero(), |acc, el| acc + el).neg();
let new_proof = (proofs_add * Fr::from(new_key_index as u64 + 1)).into();

let aggregate_signature = G2Affine::zero();

难题 3: Chaos Theory

在这个难题中，我们再次遇到了 BLS 签名，这次与 ElGamal 加密相结合。我们获得了一条加密的、经过认证的消息，并需要在少量可能性中找出哪条消息。

与难题 2 类似，发送者具有私钥 sksend 和公钥 pksend=sksend⋅g，接收者也是如此。消息 m 的 ElGamal 密文为 c=(pksend,d)，其中 d=sksend⋅pkrecv+m。接收者可以通过从 d 中减去 sksend⋅pkrecv 来解密。我们还提供的签名是 ElGamal 密文哈希的 BLS 签名——即满足 e(g,s)=e(pksend,hash(c)) 的 s。

我们有少量可能的消息 m′ 进行检查。为了消除对消息的依赖，如果我们猜测正确，我们首先考虑 d−m′，在这种情况下将是 sksend⋅pkrecv，而如果 m′≠m，则它是不同的。因此，如果 m′=m，我们将有：

e(d−m′,hash(c))=e(skrecv⋅pksend,hash(c))=skrecv⋅e(pksend,hash(c))=skrecv⋅e(g,s)=e(skrecv⋅g,s)=e(pkrecv,s)。

虽然上面的中间步骤涉及我们不知道的项，但我们可以检查 e(d−m′,hash(c))=e(pkrecv,s)。如果这个等式成立，那么 m′=m。

与其他难题一样，可以在其 ZK Hack 页面↗ 找到更详细的说明。

这是我们的解决方案代码：

for (i, msg) in messages.iter().enumerate() {
    let shared = blob.c.1 - msg.0;

    let lhs = { Bls12_381::pairing(shared, blob.c.hash_to_curve()) };
    let rhs = { Bls12_381::pairing(blob.rec_pk, blob.s) };

    if lhs == rhs {
        println!("Msg {i} is correct");
    }
}

结论

我们要感谢 ZK Hack 组织此次竞赛，并感谢 Geometry Research 制作这三道有趣的难题。

关于我们

Zellic 的专注于零知识的团队结合了先进的加密技术、漏洞研究和竞争性黑客方面的优秀技能。我们审查 Circom、Halo2 及其他 zkEVM、zkVM、隐私和身份协议以及互操作性基础设施的电路。

值得注意的客户包括 Rollup（Scroll）、协处理器（Axiom）、隐私原语（Nocturne）以及 zk-桥（Polyhedra）。

联系我们↗ 获取 ZK 审计。

脚注

1. 我在这里以加法形式写 G3，以简化表述。↩

• 原文链接： zellic.io/blog/zellic-wi...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～