量子可恢复的 Zcash

Dev @zkDragon

当量子计算机到来时，是什么保护你的 Zcash 资金安全？

量子计算机能够破解 Elliptic Curves，因此它们将破解 Orchard shielded pool。所以有一天，Orchard 必须被冻结。我们如何在量子对手存在的情况下，仍然保留 Orchard 状态并安全地迁移用户资金？这就是 Quantum Recoverability。它需要创建一个新的 Post-Quantum STARK，它能让你：

• 量子安全地证明你拥有一张 note

• 量子安全地证明那张 note 确实存在

我们将把这两个问题都归结为破解一个哈希函数，而量子计算机在这方面没有优势。

Quantum recoverability 是一种易于部署的保护措施，它确保所有资金安全，并且只需要进行小规模的钱包更新。在具有密码学相关性的量子计算机出现之前，将会开发一个新的量子安全的 shielded pool，供人们迁移使用。

本文是对 Daira-Emma 关于 Quantum Recoverable Orchard 工作的解释：https://zips.z.cash/draft-ecc-quantum-recoverability；所有错误均由我个人承担。

证明所有权

这是所有区块链中普遍存在的标准量子问题。今天，一张 note 由一个 elliptic curve public key 拥有。但是量子对手可以破解该公钥，恢复私钥并伪造签名。因此他们可以声称他们拥有的 note。

有一个标准的技巧来解决这个问题。在 Orchard 中，每个钱包都有一个 spending key sk，它被哈希以创建 elliptic curve private key（"ask" - authorization secret key）和 public key（"ak" - authorization key）。通常，我使用签名来证明我知道 secret key (ask)。为了实现量子恢复，我 zk 证明我知道一个 spending key sk，使得 "sk = H(ask)"。

Orchard 密钥派生

从 sk 到 ask 的派生已经使用了量子安全的哈希（SHA-2），并且自第一天起就已要求所有 Orchard 钱包使用。因此，证明所有权在没有更改的情况下已经是量子安全的。

证明存在有效的 note

令人惊讶的问题是，我们今天创建 note-commitments 的方式目前并非量子安全。假设有一张 Alice 拥有的 10 zec 的 note commitment。量子攻击者可能会声称这实际上是一张 Bob 拥有的 1000 zec 的 commitment。这听起来不对，因为 commitment 通常是哈希，而哈希是量子安全的，不是吗？这是因为哈希在 ZK 证明时间中占主导地位，并且普通的哈希证明起来非常昂贵。在编写 Orchard 时，Zcash 社区认为 Poseidon（一种 ZK friendly hash）的抗碰撞性不足。因此，对于电路中需要抗碰撞性的所有事物，都选择了一种基于 elliptic curve 的哈希。

对于 note N、"commitment randomness" rcm 以及固定曲线点 (G,R)，Orchard note commitment 是：

note_commit(N,rcm)=[bits(N)]∗G+[rcm]∗R\text{note\_commit}(N,rcm) = [bits(N)] G + [rcm] R

当 Alice 付款给 Bob 时，Alice 为 Bob 构建 note N，选择一个随机的 rcm，并创建 note commitment。类似地，Bob 要花费该 note，他必须从 Alice 那里收到 N 和 rcm。Alice 和 Bob 都必须 ZK 证明 note commitment 构建正确。在量子时代之前，这在 discrete logarithm 下是安全的。然而，一个量子对手，在给定 nc 和 note N 的情况下，总是可以解出 rcm。

我们如何解决这个问题？rcm 应该是伪随机的吗？一个想法是，让 rcm 仅作为哈希函数的输出。例如 "rcm = H(rseed)"？这将使我们能够继承哈希函数的安全性，不允许攻击者解出 rcm，同时保持 rcm 的不可预测性。量子恢复 ZKP 将证明你对 rseed 的了解。问题是：这本身不足以实现量子安全。量子攻击者可以挑选一个诚实的 rseed 和 rcm，以及一个目标 note commitment。然后他们利用其对 discrete logarithm 的破解来找到一个对该 commitment 有效的 Note。

新想法：如果我让 rcm 提交 note 中的每一个值呢？比如 "rcm = H(rseed, N)"。那么，如果量子对手要破解它，他们首先必须选择一个 note N。这限制了他们等式的两边，阻止他们利用量子优势。一旦量子攻击者破解了 discrete logarithms，他们就会找到 y,r，使得：

note_commitment=[y]GR=[r]G
\begin{align*} \mathsf{note\\_commitment} &= [y]G \\\ R &= [r]G \end{align*}

这意味着他们要解决的方程是：

y=bits⁡(N)+H(rseed,N)(modp)\begin{equation} y = \operatorname{bits}(N) + H(r_{\mathsf{seed}}, N) \pmod{p} \end{equation}

对于固定的 y 和 N，解决这个方程没有量子优势！它是在寻找哈希的原像，这是量子安全的，因此我们是量子安全的！

现在我们有了一种方法来证明 note commitment 未被量子伪造，这通过一个新的 ZKP 来实现。实现这一点不需要任何 Orchard ZKP 的更改。给定 rcm，nc 没有变化，并且 Orchard 电路不限制 rcm 的选择方式。今天，发送方通过选择一个随机的 rseed，将其放入发送给接收方的 note 中，并设置 "rcm = H(rseed)" 来传递 rcm。我们只需要将发送方/接收方约定更改为 "rcm = H(rseed, N)"。实际的 note 数据格式不需要更改，它已经包含 rseed。通过版本控制可以很容易做到这一点。

TL;DR: 今天，note commitment 使用 elliptic curves。因此，我们通过将 "rcm = H(rseed)" 更改为 "rcm = H(rseed, Note)" 来进一步限制诚实的 note 创建者对“commitment randomness” rcm 的选择。所有这些只需要一个新的钱包约定版本。这样 note commitment 就具有量子可恢复性，因为它们可以证明对哈希原像的了解。

量子恢复 ZKP

那么我们如何制作量子恢复 ZKP 呢？我们收集所有 Orchard note commitments，并使用量子安全的哈希（SHA2 或 Poseidon）为它们创建一个新的 Merkle tree。

然后你将进行一个量子安全的 ZKP (STARK)，它证明：

• 你知道新树中 note commitment nc 的 Merkle path

• 你知道此 note 提交给的 (N,rcm)

• Rcm = H(rseed,N)

• 你知道 sk，当你遵循 Zcash 密钥派生时，你会得到拥有 note N 的 (ak, nk, rivk)

• 原文链接： x.com/zkdragon/status/20...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～