CryptoNote and the CryptoNote community invest a lot of time and energy to create reliable, innovative, and user-friendly, state-of-the-art code. Unfortunately, attempts to discredit or attack innovative technologies are inevitable. Summary
One of the CryptoNote-based coins, Monero, has been affected by malicious activity on September 4th 2014 in which the Merkle root calculation vulnerability was successfully exploited. Even though the corrupt block that has led to the network split was found on height 202612
, it required certain targeted measures prior to and after its creation for the exploit to be successful. Details of the damage caused to the Monero network by the attacker’s actions and the Merkle root calculation overview are provided below.
CryptoNote code had a flaw in the Merkle root
calculation, which was used to compute the block hash from the hashes of the transactions contained within it. In certain situations the transactions inside the block may be substituted without the block hash being affected. In this particular case if there are exactly 513 transactions in the block (excluding the coinbase transaction), the 512th and 513th transactions can be replaced with no consequences to block hash.
The attacker has created two blocks with exactly the same 513 transactions except for the last 2, which were different for the blocks. Due to the flaw in the Merkle root calculation, these two blocks had the same hashes. Each of the two blocks have been relayed across various Monero network nodes, dividing them into two sub-networks. Pre-requisite
The attacker had to create the block containing 513 transactions. Normally, the Monero network block size does not exceed 25,400 bytes, since the daemons are creating blocks within 1.3 medians of the last 100 blocks. The block size median was originally roughly equal to 20,000 bytes. This corresponds to a normal block containing less than 10 typical transactions. Even though CryptoNote has adaptive limits imposed on the block median size allowing it to be shifted, the attacker could not easily move the median to include 513 ordinary transactions as it would require the median size to be substantially larger than 20,000 bytes.
Therefore, certain actions had to be performed for the Monero network to accept and relay the 513-transaction blocks. The pre-requisites are:
1. First 511 transactions should be of the smallest possible size. The attacker has created special transactions for this particular purpose that had only 1 input, no outputs, and an empty extra field. Each of these transactions is roughly 105-106 bytes, which is likely the smallest possible transaction size.
2. The 512th and 513th transactions of both corrupt blocks should be normal for either of them to be included into one the sub-network’s blockchains, or these transactions are spent on different sub-networks.
3. The median block size should be increased for the corrupt block to be accepted by the network. The 202612 block size is 55503 bytes, which means that the median has been lifted from 20,000 bytes to at least 55,503 / 2 = 27,752 bytes.DetailsPart 1. Attack preparation
The malicious activity had likely started on 2014-08-31. The attacker had created 2574 outputs equal to 0.000000000001 XMR (1 atomic unit). This had been done to generate enough inputs for the 511 small transactions of the corrupt block. Note that 2574 outputs is enough for 5 of such blocks, which implies that the attack might have been plotted to be broader than its actual reach.
Here is the last transaction with such small output: http://chainradar.com/xmr/transaction/34c75f71fd8999fac02cd13a29439cf1e58dbf8ab1b7e4f272fbff3aac5696b0Part 2. Median shifted with the transaction flood
2014-09-03, 08:47:20 UTC (block 201481
At height 201481 the blocks containing 1 and more transactions started to emerge on the network. The attacker had likely started the transaction flood in order to gradually shift the median size from 20,000 bytes to 27,752 bytes.Part 3. Finding the corrupt block
2014-09-03, 17:16:19 UTC (block 202023
The median has exceeded 27,752 bytes starting with the block height 202023 and continued to increase further. Apparently, this was the time when the corrupt block with 513 transactions started to be mined.
2014-09-04, 04:22:50 UTC (block 202612
The mining had taken approximately 11 hours until the corrupt block was found on height 202612. After the block had been mined, the transaction flood stopped around the block 202646
(when the block median size started to decrease). Thus, the transaction flood took place between 2014-09-03, 08:47:20 UTC and 2014-09-04, 04:52:05 UTC, lasting roughly 20 hours.
According to our analysis, during this period 4037 transactions with an overall fee of 344.174025917752 XMR have been created. The total size of these transactions was 35,756,751 bytes (31.1 MB). However, the transaction flood had been well orchestrated to look indistinguishable from the normal network transactions. Thus, this is the upper estimate of the malicious activity and the costs of the transaction flood.Part 4. Relaying the blocks
The corrupt 202612 block had been relayed to one part of the network (sub-network A). Its exact copy with the 512th and 513th transactions replaced had been relayed to the second part of the network (sub-network B). Due to the Merkle root calculation flaw, both of these blocks had exactly the same hash.
This does not imply a split, at least until the 512th and 513th transactions of one of the sub-networks are accepted by the other sub-network as valid transactions.
The block 202612 on sub-network A had the following 2 last transactions:d2d714c86291781bb86df24404754df7d9811025f659c34d3c67af3634b79da6d59297784bfea414885d710918c1b91bce0568550cd1538311dd3f2c71edf570
The block 202612 on sub-network B had the following 2 last transactions:2a58f802202db09cbd1377630ae73becff1eaff52e8969980672496dc39a5f6f57ce3aab446d75726221c908a4bf6ac2f67485cab80a2e2bedfe5519cabd8848
(Note that certain URLs above might become unavailable when all block explorers migrate to the correct chain)Part 5. Split starts
2014-09-04, 04:25:05 UTC (block 202614
The attacker had likely sent the transactions of the block 202612-B to mining pools on the sub-network A. These transactions had been included in the blockchain on height 202614 by one of the pools
The sub-network A daemons accepted that block since they didn't have the 2a58f802202db09cbd1377630ae73becff1eaff52e8969980672496dc39a5f6f and 57ce3aab446d75726221c908a4bf6ac2f67485cab80a2e2bedfe5519cabd8848 transactions on the blockchain.
The sub-network B deamons rejected the block since those transactions had already been included in block 202612-B. Accepting these transactions a second time would imply double-spending.
Therefore, the network had been split on height 202614 when the two sub-networks turned into two different chains. Fortunately, the large majority of the Monero network had remained on the chain A, which helped to avoid larger negative consequences for the currency.Part 6. Second attempt to perform the split
As discussed above, there are 2 possibilities for the split to emerge. Apart from the case explained in part 5, the split could have been started if the outputs of the 512th and 513th transactions were spent on each of the sub-networks.
We have checked whether such actions took place by analyzing the blockchains of the 2 sub-networks. Indeed, we’ve identified that the attacker tried to spend the outputs of the corrupt transactions.
Here are these transactions:
Tx 8167e70172da333859220771838c0c338de15c8a4ca9fbd6ba779e579b19eb22 spends all the outputs of tx d2d714c86291781bb86df24404754df7d9811025f659c34d3c67af3634b79da6 of the block 202612-A.
Tx 2cad16a7734c0084e5590fb264be1879c82d590d139d789876444920a0079dd6 spends all the outputs of tx d59297784bfea414885d710918c1b91bce0568550cd1538311dd3f2c71edf570 of the block 202612-A.
Tx f7a2c4d0c4ccbfae37d550253c5f032156d9e8d0897d76137e26ea5fa8a92f44 spends all the outputs of tx 2a58f802202db09cbd1377630ae73becff1eaff52e8969980672496dc39a5f6f of the block 202612-B.
Tx e3b94625d8eb5513dbc98b599a86a3b8622a23dce0124334f5b9982b656c59c5 spends all the outputs of tx 57ce3aab446d75726221c908a4bf6ac2f67485cab80a2e2bedfe5519cabd8848 of the block 202612-B.
We are unsure why the attacker had pursued both ways to split the network. It might have been done to ensure that the split actually started. Nevertheless, even if the split would not have started at block 202614 the way it has, it could have still be caused by spending the transaction outputs at a later time.Timeline
The timing is derived from the timestamps of the corresponding blocks.
2014-08-31 — the transactions with 1 atomic unit outputs are created for the corresponding 511 small transactions of the corrupt block
2014-09-03, 08:47:20 UTC — transaction flooding begins in an attempt to increase the median block size
2014-09-03, 17:16:19 UTC — the median is exceeded and reaches the size required for the split
2014-09-04, 04:22:50 UTC — the corrupt block is found, duplicated, and relayed across the network dividing Monero network into two sub-networks
2014-09-04, 04:25:05 UTC — the transactions of the 202612-B block has been included into the sub-network’s A blockchain and the split startsThe fix
In order to patch the vulnerability and fix the split, the following steps are required:
1. Apply the official CryptoC-3 patch
for the Merkle root calculation algorithm vulnerability.
2. Hardcode the block height and the block hash for the software to know which sub-network is the “right” one.
3. Hardcode the transaction hashes of the “right” block.
4. Adjust the daemon so it checks at startup whether it is on the correct chain. If it’s not, the daemon should prune the incorrect part of the blockchain.
This would protect the network from the future exploits and explicitly state which of the two chains is correct.Conclusion
The vector of the network split had likely been the financial gains. The attacker had spent a significant amount of time and funds to research the vulnerability and organize the series of activities that had led to the network split. Theoretically, the attacker could have divided the exchanges across sub-networks to trade the coins for Bitcoins on both sub-networks by applying a double-spending attacks. Fortunately, the community had responded quickly by freezing the trades on all the major exchanges, which helped avoid financial losses.
In this document we have investigated the root causes and identified an imperfection in the CryptoNote code base that has led to the Monero network split. As soon as an official patch
was made available CryptoNote communicated it to all the CryptoNote-based coins. All CryptoNote-based coins are urged to apply this pre-emptive patch to protect them against this condition. CryptoNote’s team and community are committed to the technology and are continuing to contribute to the development of CryptoNote based coins.