😨a16z ZkDrops: Missing Nullifier Range Check

Book an audit with Zokyo

Summary

Related Vulnerabilities: 1. Under-constrained Circuits, 2. Nondeterministic Circuits, 3. Arithmetic Over/Under Flows

Identified By: Kobi Gurkan

ZkDrops is very similar to the 0xPARC StealthDrop (related bug just above). ZkDrops requires that users post a nullifier on-chain when they claim an airdrop. If they try to claim the airdrop twice, the second claim will fail because the nullifier has already been seen by the smart contract. However, since the EVM allows numbers (256 bits) larger than the snark scalar field order, arithmetic overflows allowed users to submit different nullifiers for the same airdrop claim. This made it possible for a user to claim a single airdrop multiple times.

Background

In order to claim an airdrop, users must post a nullifier on-chain. If the nullifier is already present on-chain, the airdrop will fail. The nullifier is supposed to be computed in a deterministic way such that given the same input parameters (the user’s claim in this case), the output nullifier will always be the same. The nullifier is stored on-chain as a 256 bit unsigned integer.

Since the SNARK scalar field is 254 bits, a nullifier that is > 254 bits will be reduced modulo the SNARK field during the proof generation process. For example, let p = SNARK scalar field order. Then any number x in the proof generation process will be reduced to x % p. So p + 1 will be reduced to 1.

The Vulnerability

The smart contract that checked whether a nullifier has been seen before or not, did not verify whether the nullifier was within the SNARK scalar field. So, if a user has a nullifier x >= p, then they could use both x and x % p as separate nullifiers. These both will be evaluated to x % p within the circuit, so both would generate a successful proof. When the user first claims an airdrop with the x nullifier, x hasn't been seen before so it is successful. Then when the user claims the same airdrop with x % p, that value hasn't been seen by the contract before either, so it is successful as well. The user has now claimed the airdrop twice.

The Fix

The fix to this issue is to add a range check in the smart contract. This range check should ensure that all nullifiers are within the SNARK scalar field so that no duplicate nullifiers satisfy the circuit. The following function to claim an airdrop:

/// @notice verifies the proof, collects the airdrop if valid, and prevents this proof from working again.
function collectAirdrop(bytes calldata proof, bytes32 nullifierHash) public {
	require(!nullifierSpent[nullifierHash], "Airdrop already redeemed");

	uint[] memory pubSignals = new uint[](3);
	pubSignals[0] = uint256(root);
	pubSignals[1] = uint256(nullifierHash);
	pubSignals[2] = uint256(uint160(msg.sender));
	require(verifier.verifyProof(proof, pubSignals), "Proof verification failed");
	nullifierSpent[nullifierHash] = true;
	airdropToken.transfer(msg.sender, amountPerRedemption);
}

Was fixed by adding this range check:

require(uint256(nullifierHash) < SNARK_FIELD ,"Nullifier is not within the field");

Conclusion

The vulnerability and its explanation revolve around the differences in bit-lengths between the Ethereum Virtual Machine (EVM) and zk-SNARK scalar fields. Let me break down the key points for you:

Background:

  1. zk-SNARKs: These are cryptographic proofs that can verify the accuracy of a computation without revealing the actual inputs to the computation.

  2. Nullifiers: Nullifiers are unique identifiers associated with claiming an airdrop. They ensure that each airdrop can only be claimed once.

  3. EVM and SNARK Scalar Field Bit Lengths: The Ethereum Virtual Machine (EVM) allows for integers of 256 bits. However, zk-SNARKs typically operate on a scalar field of size 254 bits.

  4. Modulo Operation: If a number exceeds the size of the field, it wraps around starting from zero again, much like an odometer in a car that rolls over after reaching its maximum displayable value.

The Vulnerability:

Because of the size difference mentioned above, if someone creates a nullifier that's larger than the zk-SNARK's field (e.g., a 256-bit number), when it's processed inside the zk-SNARK proof generation, it gets wrapped around (using modulo operation).

For illustration:

  • Let's say the maximum value for the zk-SNARK field is p.

  • If someone creates a nullifier x such that x = p + 5, within the zk-SNARK computation, this becomes just 5 because of the modulo operation (x % p = 5).

  • Now, the vulnerability arises because the smart contract on the Ethereum chain, which doesn't inherently understand zk-SNARK fields, sees two distinct nullifiers: p + 5 and 5. Thus, it would allow an airdrop claim for both, even though, within the zk-SNARK, they're effectively the same.

The Fix:

The solution is to add a check in the Ethereum smart contract to ensure that any nullifier submitted is within the acceptable range of the zk-SNARK field (i.e., 0 to p-1). If it's outside this range (e.g., if it's 256 bits and too large), the smart contract will reject it. By ensuring that the nullifiers are within the correct range, you prevent the possibility of two different nullifiers effectively becoming the same within the zk-SNARK computation.

Further explaination on why the proof still passes:

The proof still passes because, within the zk-SNARK circuit, everything is computed modulo the scalar field size p.

To further explain

Let's take a simple example:

Imagine a zk-SNARK scalar field that has a maximum size of 10 (in reality, it's a much larger prime number, but this is just for illustrative purposes). This means any computation within the zk-SNARK would wrap around this number.

If a user creates a nullifier value of 12, the zk-SNARK circuit would compute with this value as if it's 2 because 12 % 10 = 2. Thus, when the proof is generated, it's effectively using the value 2.

Now, when this proof is submitted to the Ethereum smart contract, the contract doesn't inherently "know" about this modulo operation inside the zk-SNARK. So if the user submits a nullifier of 12 for one claim and then uses the equivalent modulo value 2 for another, both are seen as different by the contract. But for the zk-SNARK circuit, both are essentially the same, so proofs for both will pass.

That's the crux of the vulnerability. The discrepancy arises because the Ethereum smart contract operates on 256-bit numbers without the constraints of the zk-SNARK scalar field. In contrast, inside the zk-SNARK circuit, numbers are automatically wrapped around the scalar field size. So, unless the Ethereum contract is explicitly coded to account for this, it'll treat values like 12 and 2 as distinct, even though the zk-SNARK circuit sees them as equivalent.

References

  1. Github PR

Previous0xPARC StealthDrop: Nondeterministic NullifierNextMACI 1.0: Under-constrained Circuit

Last updated