🤖Aztec 2.0: Missing Bit Length Check / Nondeterministic Nullifier
Summary
Related Vulnerabilities: 1. Under-constrained Circuits, 2. Nondeterministic Circuits, 4. Mismatching Bit Lengths
Identified By: Aztec Team
Funds in the Aztec protocol are held in what are called “note commitments”. Once a note commitment is spent, it should not be possible to spend it again. However, due to a missing bit length check, an attacker could spend a single note commitment multiple times.
Background
Whenever a new note commitment is created, it is stored in a merkle tree on-chain. In order to prevent double spending of a single note commitment, a nullifier is posted on-chain after the note is spent. If the nullifier was already present on-chain, then the note cannot be spent.
The Vulnerability
The nullifier generation process should be deterministic so that the same nullifier is generated for the same note commitment every time. However, due to a missing bit length check, the process was not deterministic. The nullifier was generated based on the note commitment index in the merkle tree. The code assumed the index to be a 32 bit number, but there was no constraint enforcing this check.
An attacker could use a number larger than 32 bits for the note index, as long as the first 32 bits matched the correct index. Since they can generate many unique numbers that have the same first 32 bits, a different nullifier will be created for each number. This allows them to spend the same note commitment multiple times.
The Fix
A bit length check was needed on the given note commitment index to enforce that it was at max 32 bits.
Conclusion
Note Commitment: Think of this as a digital asset or "coin" in the Aztec protocol. Once it's spent, it should be locked or "burnt" to ensure it cannot be used again.
Merkle Tree: This is a cryptographic data structure where every leaf node is some piece of data, and each non-leaf node is a hash of its child nodes. In this context, the note commitments are stored as leaves in this tree.
Nullifier: After spending a note commitment, a nullifier is generated and posted on-chain. This nullifier acts as a unique identifier for the spent commitment, ensuring that once a commitment has a corresponding nullifier on the blockchain, it cannot be spent again.
The Vulnerability
Non-deterministic Nullifier Generation: The generation of the nullifier should always result in the same output for the same input, i.e., it should be deterministic. But there was an issue because of a missing bit-length check.
Issue with Index: The nullifier was generated based on the note commitment's index in the Merkle tree. The system assumes this index to be a 32-bit number.
Exploitation: An attacker could use an index number larger than 32 bits but with the first 32 bits correctly matching a legitimate index. This would allow the attacker to generate multiple unique nullifiers for the same note commitment, effectively enabling them to "double spend" or even multi-spend the same commitment.
To visualize, consider: Correct 32-bit index: 10101010101010101010101010101010 Attack example (more than 32 bits but starting with the correct 32 bits): 1010101010101010101010101010101010101010
Impact of the Exploit: This would break the core trust and security of the protocol. Users and stakeholders would lose confidence if note commitments could be spent multiple times, leading to potential financial losses and undermining the protocol's integrity.
The Fix
To address this vulnerability, a simple bit length check was added to the note commitment index to ensure it is, at most, 32 bits. By enforcing this constraint, the vulnerability where indices of more than 32 bits were accepted (leading to different nullifiers for the same commitment) was closed.
Summary
In simple terms, a flaw in the Aztec protocol allowed a digital asset to be spent more than once. This happened because of a missing security check in the system. The developers identified the flaw and fixed it by adding the missing security check.
References
Last updated