Announcements

Zcoin’s Zerocoin bug explained in detail

By February 21, 2017 No Comments

Understanding how Zerocoin works

To understand the bug, we first need to explain how the Zerocoin protocol works on a high level and what minting and spending does. Minting a Zerocoin involves burning up a coin and making it unspendable and Spending a Zerocoin means redeeming a new coin with no previous transaction history. It is this burning up and generation of new coins that gives Zcoin its anonymity characteristics as any link between the burnt coin and the newly generated coin is broken.

To prove that you’re entitled to redeem new anonymous coins with no transaction history (a Zerocoin spend transaction), you need to show proof that you did indeed burn an equivalent number of coins (a Zerocoin mint transaction). This proof is a zero-knowledge proof since it allows the person redeeming the coin to prove that they minted a coin without having to show which one it was which is the crux of how Zerocoin anonymity works. The proof only shows that the person burnt a coin but not whether they have redeemed it or not. To check if redemption has been madea unique random serial number is generated during the mint phase of the coin and posted together with the proof during the spend transaction phase. Miners then double-check to verify that this serial number has not been used before, which prevents someone from re-using a proof to redeem multiple coins. It was at the serial number validation part where the bug occurred.

How we discovered the bug

Slightly before midnight on February 16th GMT+0, during a check to analyze how widely used Zerocoin transactions were in Zcoin, we discovered that the total Zerocoin spend amounts did not tally with the number of mint transactions and the spend transactions far exceeded the number of mint transactions.

Upon further investigation, the dev team discovered that at block 11002, the serial number for the spend transaction had been reused which meant that someone was exploiting a single proof to generate multiple spends. If the code was working correctly, the duplicate serial numbers should have been rejected.

What we did following discovery of the bug

In the following few hours, our developers had identified that the issue was caused by a “==” sign being used instead of a “=” sign as linked here.

In programming logic, “=” assigns a value to a variable while “==” is used to compare whether two values are equal.

“==” is a comparison operator which means that if both values are equal, it will return a “true” function.

To illustrate:

a == b tells you whether a and b are equal or not
a = b makes a and b equal, by changing a to the value of b, regardless of what a was.

The use of the “==” sign instead of “=” broke the serial code validation which allowed the attack to happen.

We will show the code logic at the bottom of this post for those of you who can read code as there has been much speculation and incorrect information of the true cause and nature of the bug and we hope people can draw their own conclusions from there.

After identifying the bug, on the February 17th we contacted the major exchanges to suspend trading while we investigated further. We also noticed that the attacker was creating spend transactions and immediately sending them to an altcoin exchange address. Working with the altcoin exchange, we realised there was no option to freeze the attacker’s accounts as all the Zcoins had already been sold and the funds withdrawn. This had occurred  over a period of time in batches and across more than 60 different accounts, making it harder to detect. We also could not blacklist or burn those coins as they have been bought by the market and neither could we roll back as too much time had passed since the exploit was first used. A few hours later from the exchange lockdowns, we published our blog post  informing the public of the bug.

We knew the attacker was already alerted once the exchanges were shut and so we were in a race against time to roll out our fix and get the network to update as the fix required a hard fork. Until the network was updated, the attacker could continue to exploit the bug.

To limit the damage and to give us time to thoroughly test our fix, on the same day, we contacted all the major mining pools to temporarily suspend the processing of Zerocoin transactions. Some pools were a bit slower to update than others, which allowed the attacker to get in several further Zerocoin spend transactions before it could be halted completely.

On late 18th February, we rolled out our fix on Github as release v0.8.7.7 and informed all exchanges and pools to update and gave them the go ahead to reopen full trading, deposits and withdrawals. At block 22,001, the new code will automatically take effect, preventing this exploit from happening again and re-enabling Zerocoin spend transactions.

On the 20th February, the fork completed with the new code and bug fix in place. Zerocoin spend transactions have been re-enabled. A total of 388450 XZC were created from this bug.

Moving Forward

This bug was a hard lesson and stresses the importance of routine code review even in beta software. Internal and external processes such as routine third party code audits by reputable parties and automated checking systems monitoring the blockchain are being put in place to detect any exploits early and to prevent bugs of this magnitude from happening again.

We would like to thank everyone for their patience and trust during this challenging time and it is heartening to have received support from our investors, the exchanges, mining pools and our community. We resolve to be worthy of your trust and support and are confident our future efforts will reflect this.

Should you have any further questions regarding this or just would like to be a part of the Zcoin discussion, do drop by our Slack!

The Code behind the Bug

After finding the serial number was reused, we ran a debug, and found that the denomination in walletdb always showed “0” although it had been processed. Our working theory was that it had to be a problem with the updating part in walletdb. So we looked further and saw that the last line number before update “CoinSpendSerialEntry” showed the following :

zccoinSpend.denomination == libzerocoin::ZQ_WILLIAMSON;

At this point, we narrowed down exactly what was the root cause that allowed this exploit to occur. Moreover, we looked at the conditions above and then confirmed our theory that because of the “==” line, the bug was created. As you can see

First condition:

if (item.coinSerial == serialNumber
&& item.denomination == libzerocoin::ZQ_WILLIAMSON << alway false due to item.denomination is always equal 0, and 0 not equal 100, then it skips to go inside loop to reject this invalid transaction
    && item.id == pubcoinId
&& item.hashTx != hashTx)

Second condition:

else if (item.coinSerial == serialNumber
&& item.hashTx == hashTx
&& item.denomination == libzerocoin::ZQ_WILLIAMSON << alway false due to item.denomination is always equal 0, and 0 not equal 100,  then it skips to go inside loop.
            && item.id == pubcoinId
&& item.pubCoin != 0)

Third condition:

else if (item.coinSerial == serialNumber
&& item.hashTx == hashTx
&& item.denomination == libzerocoin::ZQ_WILLIAMSON << alway false due to item.denomination is always equal 0, and 0 not equal 100,  then it skips to go inside loop.
&& item.id == pubcoinId
&& item.pubCoin == 0)

As a result, isAlreadyStored will always be set to false, and then forwarded to the “INSERTING COINSPEND TO DB” section, with the denomination equal 0 again like the following code below:

if(!isAlreadyStored){

// INSERTING COINSPEND TO DB

CZerocoinSpendEntry zccoinSpend;
zccoinSpend.coinSerial = serialNumber;
zccoinSpend.hashTx = hashTx;
zccoinSpend.pubCoin = 0;
zccoinSpend.id = pubcoinId;
zccoinSpend.denomination == libzerocoin::ZQ_WILLIAMSON; << It means nothing, so zccoinSpend.denomination will be set back to default value, which is 0
walletdb.WriteCoinSpendSerialEntry(zccoinSpend);

}

We know that it has to be “=” not “==”. After we changed the code and recompiled, it showed the correct result and the transaction got rejected right away.

We also wanted to make sure this bug did not occur  as a result of a merged request but our investigation uncovered that this bug had existed since we launched the project as seen under following link.

We found this bug, and we tried to fix without affecting old transaction because we were at block 21000+ at that time. So It was impossible to restore back to 11001.

We fixed the code by changing it to:

if(nHeight > 22000 && nHeight < INT_MAX){
zccoinSpend.denomination = libzerocoin::ZQ_WILLIAMSON;
}

We are able to pass old blocks with invalid spend txs inside. But the attacker also bombarded spend txs to the network. We decided to prevent future losses and asked pools to temporarily stop accepting spend tx by changing:

unsigned int MAX_SPEND_ZC_TX_PER_BLOCK = 1

to

unsigned int MAX_SPEND_ZC_TX_PER_BLOCK = 0;

This line was not to fix the bug but as a temporary measure to slow down the attacker until we deployed the new code to pool and exchanges.

In the new code, spending tx are be re-enabled automatically after block 22000 as seen below and we are currently live on the new code.

if(pindexBest->nHeight + 1 > 22000){
MAX_SPEND_ZC_TX_PER_BLOCK = 1;
}