简洁证明是如何泄露信息的: 选择实例攻击(Chosen-Instance Attack)

本文翻译自: https://baincapitalcrypto.com/chosen-instance-attack/#conclusion

• Threat model
• Leaky primitives
• Non-interactive proofs
• Chosen-instance attacks in the wild
• Conclusion

如果一个证明仅仅是SNARK, 但不是zkSNARK会有什么问题? 人们通常会产生误解: 单个SNARK太少了, 并不会泄露关于witness的信息. 这显然是错误的. 事实上, 单个SNARK会泄露关于 witness 的信息, 但是不会泄露 full witness(我们将在这篇博客中讨论). 值得注意的是, 今年的 ZK Hack V puzzle 就是基于这个主题.

在这片文章中, 我们将展示一种名为 "chosen-instance attack" 的攻击, 类似于加密中的 chosen-plaintext attack. 敌手要求证明者生成对于 \((x_0, w), (x_1, w), (x_n, w)\) 的证明. 拿到这些证明敌手可以通过插值法还原出原来的 witness polynomial.

本文假设读者明白以下术语的含义: "NP", "instance", "witness", "SNARK", "IOP/polyIOP".

Threat model

我们考虑非交互的 proof(或argument), 模型如下. 敌手 \(\mathcal A\) 知道电路的公共输入, 与一个诚实的证明者 \(\mathcal P\) (knows witness)进行交互. 敌手是自适应的(adaptive), 可以自己选择 statement 来让证明者证明. 最终, 敌手必须输出证明者的 witness. 整个模型可以用下面的图来描述.

这种设置在实际中是常见的. 例如, 在有 client-server 的应用中, client往往相当于诚实的证明者, 具有一些 witness, 而 server 通常是敌手. 这也是我们为 ZK hack puzzle 选择的环境. 另外, 我们可以想象一个不受信任的服务器, 他需要生成证明去证明自己是诚实的. 一个恶意的服务器可能会尝试通过选择特定的 statement 让服务器证明, 来抽取出服务器的秘密.

Leaky primitives

IOPs 大部分SNARK都是基于IOP或者他的变形polyIOP. IOP的结构通常是这样的.

第 \(1\) 轮. 证明者发送一个 oracle(可以理解为由 witness 编码而来的一个多项式).

第 \(i\) 轮. 证明者发送一个 "helper" oracle. 让验证者把 "检查witness" 这个任务 归约到一个更简单的问题上.

最后一轮. 验证者在一个或多个点上询问 witness 和 helper oracles.

这个构造至少泄露 witness polynomial 的一个值. 如果 witness 被编码成一个 \(d\) 次的多项式, 那么敌手可以收集 \(d+1\) 个证明, 然后使用这些值通过插值来恢复整个 witness polynomial! 这些协议要求Prover打开 \(k\) 个witness value, 从而需要收集的证明数量从 \(d+1\) 减少到了 \((d+1)/k\).

我们一般使用两种方法把IOP编译成SNARK. 分别是通过多项式承诺和Merkle tree.

Compilation using polynomial commitments 使用多项式承诺方案对 Prover 的消息进行承诺, 然后通过FS转换变为非交互. 大多数 elliptic curve SNARK 是通过这种方法产生的. 这种方式通常不会泄露许多witness的值.

Compilation using IOPPs and Merkle tree 第二种方法是调用一个另外的协议, 生成 Prover 的消息离某个多项式很近. 这就是 IOP of proximity(IOPP), 比如FRI[BBHR18], STIR[ACFY24]. IOP+IOPP能够通过BCS transform[BCS16] 编译成 SNARK. 对Prover的每个消息进行 Merkle Tree 承诺, 再通过 FS 转换变为非交互的. 大多数hash-based SNARK就是这样产生的. IOPP compilation 会泄露 witness polynomial 额外的求值(因为每次会要求验证者重复打开多项式的点, 根据参数和安全性, 通常每个证明会打开20~50个点).

Non-interactive proofs

正如我们上面所说: 交互式的SNARK会泄露 witness polynomial 的求值. 在交互的情况下抽取出证明者的 witness 是相对简单的. 我们只需要作为验证者诚实地运行协议, 保证每次询问的点是不同的, 次数足够多之后我们可以通过插值法获得 witness polynomial.

在非交互的情况下抽取出 witness 没那么简单. 因为我们需要使用 Fiat-Shamir transform. 在给定证明者先前的消息后, Verifier的消息是确定的( instance 与 previous message 的 hash). 对于一个固定的 \((x, w)\), 诚实的证明者会返回固定的 proof, 这就让敌手不能获得 witness polynomial 的多个值, 从而不能获得整个 witness.

很容易想到一个解决方法: 如果我们能获得这样一组实例的证明就好了: \((x_1, w), (x_2, w), \cdots, (x_n, w)\). 即多个不同的实例, 但是他们的 witness 相同. 但这样的条件是否有点太强, 是否是不可能的呢? 在下一节中, 我们会说明实际上很普通的电路就会满足这个条件. 现在我们先假设这样的集合是存在的.

使用不同的实例的直接结果就是: Verifier的消息在每次证明中都不一样, 所以可以获得不同的evaluation. 然而还有一些问题. 在一些算数化中, Prover的第一条消息既依赖witness \(w\), 也依赖instance \(x\). 如果我们使用不同的 instance, Prover的第一条消息会每次都不同, 这似乎不利于我们的插值攻击.

幸运的是这个问题也可以解决. 我们可以让敌手把 witness 部分的多项式和 instance 部分的多项式分开. 我们用 \(\tilde{z}\) 表示combined instance-witness polynomial: 包含了instance polynomial \(\tilde{x}\) 和 witness polynomial \(\tilde{w}\). 前者敌手是可以自己算出来的. 因此敌手也可以通过某种关系计算出 witness polynomial: 给定一个evaluation \(\tilde{z}(p)\), 敌手可以求出 \(\tilde{x}(p)\), 并计算 \(\tilde{w}(p) = \tilde{z}(p) - \tilde{x}(p)\). 下图我们用R1CS来表示, 当然可以等价地被应用到 PLONKish 或者 AIR table.

因此我们上面说的攻击可以正常进行: 收集足够多的 proofs, 然后插值得到 witness.

Chosen-instance attacks in the wild

乍一看, 我们描述的攻击似乎需要一个非常人为的电路: 许多instance, 但他们可以用同样的 witness 满足. 另外, 敌手一开始拥有一个instance, 那么他怎么产生更多同样 witness 的不同instance呢?

其实很多电路都会有这个性质. 特别地, 当区块链中的 "nonces" 或者 "nullifiers" 被使用时. 当我们处理非交互证明时, 我们一定需要注意: 不要让 proofs 被重新使用. 例如, Alice产生一个证明: 她的账户里有超过32个ETH. 那么我们需要保证 Alice 不能在不更新证明的情况下, 花费一些ETH并仍然使用之前的证明(这样她能永远证明自己拥有超过32个ETH). 在实际中, 这通常需要向原来的证明中引入一个public number(nonce). 如果这个 proof 被验证过了, 那么公开的 nonce 会被加入到日志中, 并且这个 proof 会被标记为"已使用". 如果同样的 proof 又被拿出来用, 这时 Verifier 就能识别这个用过的 proof, 并且拒绝. 因此这个 proof 就不会被接受.

这个 "nullifying" 机制对于阻止重放攻击(重新使用原来的proof)是很好的尝试. 但这个机制就让 Prover 能够用相同的 witness 生成不同的 instances: 我们现在有公开的输入 \((x, \text{nonce})\), 以及证据 \(w\). 敌手可以自己留着固定的 \(x\), 然后使用不同的 \(nonce\). 这是证明者总是使用同一个witness \(w\).

Conclusion

通过上面的分析我们知道: 简洁的证明是不足以保护隐私的(尽管单独的一个简洁证明不会泄露整个witness). 大多数简洁证明都会泄露关于witness的部分信息. 因此,

在某些情况下, 尤其是使用 nonces 去阻止重放攻击, 我们可以利用上面的选择实例攻击来恢复出整个 witness. 这个攻击对任何满足特定条件的电路都有效(多个 instance, 同一个 witness), 对于IOPP编译而来的SNARK尤其有效(FRI, STIR), 因为这些SNARK每一个 proof 会泄露大量的 evaluation(而不是一个).

我们所说的 chosen-instance attack 只是这种泄露的其中一个idea. 当然还有很多其他攻击的方法. 我们可以用一句废话来总结这篇文章: 如果一个系统的证明不是零知识的, 那么这个系统不保证隐私.