别名攻击

摘要

有些ZKP隐私应用需要通过nullifier阻止双花，该nullifier以ZK的形式绑定在proof中，可以被验证者证明，并在相关动作结束后标记为“已使用”，来避免双花。

不过，如果应用实现有问题，这一点可以通过循环群的特性来绕开。

以下是几个例子：

https://github.com/semaphore-protocol/semaphore/issues/16

https://github.com/eea-oasis/baseline/issues/34

https://github.com/semaphore-protocol/semaphore/pull/96/

背景

为了减少某些ZKP方案的gas消耗，以太坊为alt_bn128 in EIP-196曲线定义了加法和乘法的两个预编译合约。

曲线alt_bn128的定义为：

$$(x,y)\in (\mathbb F_p)^2\space\space |\space \space \lbrace y^2 ≡ x^3 + 3(mod \, p)\rbrace \cup \lbrace (0,0) \rbrace$$

$$\\p= 21888242871839275222246405745257275088696311157297823662689037894645226208583$$

在有限域F_p中，基于生成元P1(1,2)的循环子群的阶为q。

$$q = 21888242871839275222246405745257275088548364400416034343698204186575808495617$$

在循环子群中，有

$$x \in \mathbb F_q\, ,n \in \N \, | \, x+nq≡x(mod\,p)$$

也即，q在有限域计算中可以被视为0，对任意相同点加上任意数量的q都会得到它自己。

由于我们在相关计算中一般使用uint256，其最大值为M，那么对于给定的参数A，有N个相同结果的别名：

$$N =⌊(M-A)/q⌋$$

也就是说，如果A是nullifier，你可以构建至多N个别名，它们是不同的自然数，但在循环群的运算中会得到相同的结果。因此，防止双花的证明就无效了，甚至可以三花四花五花。

此类型的攻击最初发现于隐私层应用Semaphore中，而其源头可以追溯至2017年Christian Reitwiessner写的一段不安全的样例实现。不幸的是，很多zkSNARKS的库如snarkjs和ethsnarks也都遵照了该样例。

解决方案

解决方案很简单，只需要限制输入值需要小于q (snark_scalar_field)。

    VerifyingKey memory vk = verifyingKey();
    require(input.length + 1 == vk.IC.length, "verifier-bad-input");
    Pairing.G1Point memory vk_x = Pairing.G1Point(0, 0);
    for (uint256 i = 0; i < input.length; i++) {
       // Check for field arithmetic less than q
      require(input[i] < snark_scalar_field, "verifier-gte-snark-scalar-field");
      vk_x = Pairing.addition(vk_x, Pairing.scalar_mul(vk.IC[i + 1], input[i]));
    }

参考

https://paper.seebug.org/995/

https://ethereum.github.io/yellowpaper/paper.pdf

https://ecips.ethereumclassic.org/ECIPs/ecip-1025