Aztec Multiple-Spend Error Bugfix Review

On September 12th, 2023, the security researcher LonelySloth responsibly disclosed a Critical severity vulnerability from the Aztec Network codebase via Immunefi.

The vulnerability was a multiple-spend error that would have allowed an attacker to drain the entire total value locked (TVL) of the project if left unchecked, targeting approximately $5,000,000 in funds at the time of the report.

Thanks to the responsible disclosure by the whitehat and the Aztec Labs team’s lightning-quick response, the issue was quickly mitigated and no funds were affected. LonelySloth was awarded a $450,000 bounty for their discovery.

Aztec is a privacy-first L2 on Ethereum. The stated goal of the project is to bring confidentiality and scalability to the Ethereum blockchain, which is public by default.

Aztec is a cross chain bridge designed to provide a privacy improvement for DeFi transactions. This bridge was the next step after zk.money, a service that allowed privacy enhancement to apply directly to Ethereum transactions. But after Aztec Connect was launched, users gained the ability to add privacy to dApps through either bridge contracts, which consisted of smart contracts and Aztec rollups, or through an SDK that let developers integrate their dApps with Aztec Connect.

To better understand the nature of the vulnerability and the fix, let’s dive a little into zero-knowledge

If you are already familiar with the concept of zero-knowledge or ZK proofs, please feel free to skip this section.

ZK proof or ZK protocol is a method where one party, usually referred to as a prover, can prove to another party, usually referred to as a verifier, that some statement is true, without sharing any data except the truthfulness of the statement. The biggest challenge here is not to share the data — it is very easy to prove your statement if you share all the details with a witness.

However, for the purpose of ZK proofs — all of the details must stay private.

Let’s look at the example of a ZK proof presented by Jean-Jacques Quisquater, the Belgian cryptographer known as “The Ali Baba Cave”.

Peggy (the prover) and Ajay (the verifier) meet each other in front of the ring-shaped cave. On the left side we have an entrance to the cave, and on the right side, where two paths collide, we have a magic door that can be opened if somebody says a code word.

Peggy wants to prove to Ajay that she knows the code word to open the magic door, but she does not want to share the secret code word with Ajay. So the pair come up with a plan:

Ajay turns his back so that he cannot see the entrance, while Peggy chooses path A or B and goes into the cave until she reaches the door.

After that, Ajay shouts into the cave, instructing Peggy on which path she should take to get out of the cave: A or B.

If needed, Peggy uses the code word to open the magic door and returns using another path, or just returns via the initial path she took when reaching the door.

But what if Peggy just got lucky and returned through the path she came without needing to use the code word?

Well, both Peggy and Ajay are good at math, so they repeat the same scheme 20 times to reduce the probability of Peggy’s luck to 9.56 * 10^−7. Meaning, it is extremely, extremely unlikely for Peggy to have come out the correct path every single time without using the door, which proves beyond statistical doubt that she knows the code word.

This is a ZK proof in action!

As we determined earlier, in order to prove and verify our claim, we can implement a special check that will not disclose any private information but will objectively prove the initial statement.

Such a check is also called an arithmetic circuit. If a set of constraints presented in such a circuit is verified, then the initial statement is proven.

Let’s see how such a check will look if we want to prove that x is a modular inverse of y in a finite field of 30. We will not be calculating the y itself, but we will come up with a formula (x * y) mod 30 = 1.

As you can see, we are not resolving the actual variables, but we are verifying the truth of the prover’s claim by presenting an arithmetic circuit to verify the initial data.

Now that we have an understanding of the principles of ZK proof verification, we can dive into how Aztec uses them for DeFi interactions and how the vulnerability works.

For the purpose of this explanation, let’s assume that each claim should have an amount of outputs that is proportional to the amount of inputs in deposit transactions.

Let’s present this with a formula where O is the total output, D is the total amount of deposits, d is the claimer’s input, and o is the claimer's output.

o = d O/D

In order to avoid rounding issues, we can multiply the formula by D. Then we will receive another, more precise formula, which should look like this:

oD +R = dO,

where R is the residual of the division in the previous formula.

Let’s investigate how this residual R is generated in Aztec’s codebase.

As you can see, a new calculation of ‘witness’ is added to the formula. However, the result of this calculation fails to take into account a range check, allowing a potential attacker to tamper with the input freely to modify the value of the R residual, which is used in the formula above.

Moreover, this calculation is done on the side of the prover, which means that an attacker can freely make this modification without tripping any alarms — it does not affect the system’s ability to verify the proof as valid. This was the first bug in this finding.

There was also a second bug discovered, that allowed an attacker to withdraw the total output O in each claim. Ultimately, this is what allowed the multiple-spend bug to occur. The values are broken down into smaller parts known as “‘limbs”. When these “limbs” are combined in a certain way, an overflow of the modulus can occur.

An “overflow of the modulus” refers to a situation where a mathematical operation results in a value that exceeds the predefined limit, or modulus. In modular arithmetic, numbers “wrap around” when they exceed a certain modulus.

For example, in modular arithmetic with a modulus of 10, if you add 7 and 5, the result is 12. But in modulo 10, the answer is not 12; it “wraps around” and becomes 2 because 12 exceeds the modulus (10).

Because of that, an attacker could instantiate negative residuals in order to claim the entire output O in each individual claim, resulting in them spending the same tokens multiple times.

If you are interested in a more detailed description of the bug, you can check out a blogpost from Aztec Team.

On September 27th, the Aztec Labs team fixed the vulnerability by deprecating the existent calculation of residual and fixing the “limbs” calculation denying their overflow. The fixes were deployed in this branch.

We would like to thank the whitehat LonelySloth for stepping up to responsibly disclose this important bug. Big props as well also to the Aztec Labs team, who quickly responded to the report and patched the issue.

If you’re a developer or a whitehat considering a lucrative bug-hunting career in web3 — this message is for you. With 10–100x the rewards commonly found in web2, your efforts will pay off exponentially by switching to web3.

Check out the Web3 Security Library, and start earning rewards on Immunefi — the leading bug bounty platform for web3 with the world’s biggest payouts.