Is the Zcoin bug in CheckTransaction() validation code?

Update 4: How the attacker is using the bug in validation code to create coins

Update 6: Attacker created 388,000 Zcoin

It seems that Zcoin (XZC) has a bug  which has allowed an attacker to magically summon 370,000 coins out of thin air.  Reading the discussion over at HackerNews, I saw that there was a commit to fix the problem and it was a one character patch titled “Urgent fix for pool owners to prevent malicious zerospend txs”.

Could it be so simple?  Intrigued, I spent an hour or two digging into the source code. I’m not familair with Zcoin but I know my way around the Bitcoin source code (which Zcoin is a fork of) and I have a high-level understanding of the Zerocoin protocol (which Zcoin claims to implement).

Here are some notes I made:

First, for those unfamiliar with the Zerocoin protocol,

  • A Zcoin Mint transaction transfers funds from the public pool to the private pool.
  • A Zcoin Spend transaction transfers funds from the private pool to the public pool.

Next, what does the single character patch do?  The change from

unsigned int MAX_SPEND_ZC_TX_PER_BLOCK = 1;

to

unsigned int MAX_SPEND_ZC_TX_PER_BLOCK = 0;

means that Zcoin Spend transactions are no longer mined in a block.

The section of code which used to include the transaction in a block is here.  Why the previous limit on Zcoin Spend transactions was 1 is an open question.

Since these Zcoin Spend transactions can no longer be mined, this means that legitimate holders of private Zcoin can no longer transfer their private funds to the public pool until the restriction is lifted.

Of course, the real intent is to stop the attacker digitally printing Zcoin, and this patch does solve that problem since the fraudulent transactions will no longer be mined.

Important: the points above are only true if we assume that all miners and nodes use the Zcoin reference client.  There doesn’t actually seem to be a consensus rule which actually forbids the inclusion of 1 or 100 ZCoin Spend transactions in a block. You can check yourself by looking at CBlock::CheckBlock.  Maybe I missed something.

With a block explorer, if you examine the history of blocks you will see many blocks with 100 or 150 XZC value, where there are two transactions.

Drilling down into the raw transaction data you can see the attacker’s transaction is listed after the coinbase transaction.

Zcoin Spend transactions are identified via the OP_ZEROCOINSPEND opcode.  On the output side you can see the address at which the attacker is sending funds to.

So how does someone create a Zcoin Spend transaction?

Well, the only way an honest end-user can create a Zcoin Spend transaction is to use the rpc call, spendzerocoin.  This in turn invokes CWallet::CreateZerocoinSpendTransaction() which in the process of creating the transaction, will check for double-spending and perform sanity checks.

A node which receives a Zcoin Spend transaction from a peer, or receives a mined block containing such a transaction, will of course validate the Zcoin Spend transaction in CTransaction::CheckTransaction().  Invalid transactions should be rejected, somewhere in this block of code.

Which begs the question, if the attacker is crafting bogus OP_ZEROCOINSPEND transactions which spend non-existent private funds, shouldn’t the fraudulent transaction be detected in CheckTransaction()?

Zcoin’s blog post hints at this:

The bug  from the typo error allowed the attacker to reuse his existing valid proofs to generate additional Zerocoin spend transactions.

As discussed earlier, the single character patch posted to GitHub could potentially stop the attacker from making any further financial gain, but it would require all miners to upgrade and a consensus rule added to prevent valid blocks from including Zcoin Spend transactions.  As it stands, the patch on its own does not prevent the attacker from writing their own miner which does include Zcoin Spend transactions.

However, since the intent of the patch is to effectively prevent OP_ZEROCOINSPEND transactions from being mined, it seems to me that the real bug lies somewhere in CheckTransaction()’s validation code.

To demonstrate that the bug has been fixed, all the fraudulent Zcoin Spend transactions found on the blockchain should be run through a patched CheckTransaction and detected as invalid.

Whether or not those transactions stay valid in a future hard fork is a non-technical decision for Zcoin policy-makers.

Despite the severity of the hack, we will not be forfeiting or blacklisting any coins.

It’s understandable why this decision was made. First, it protects honest folk who purchased Zcoin on exchanges. Second, the numbers look better over time.  Today, the legitimate monetary base of Zcoin is approaching 1.1 million but the attacker has expanded that to 1.47 million.  So 25% of Zcoin has been minted by the attacker.  In the long run, assuming the problem is resolved, this percentage will trend towards 1.7% since Zcoin inherits Bitcoin’s money supply limit of 21 million coins.

If I’ve got this completely wrong and none of the above is true, intrepid bug-hunters might want to jump down the RSA rabbit hole

Update: There are two Zcoins.  Both Zcoin.io and Zcoin.tech have similar looking websites and share co-founders.  Looking at the code it appears the problem exists in both projects as they share the same validation code.

Update 2: Zcoin have now tweeted that a fix is available.  Pull requests #72 and #73 confirm a bug in CheckTransaction() where an incorrect constant was being used.  Also, the default miner will no longer include Zcoin Spend transactions. As discussed, this puts ordinary users at a disadvantage, since there is no consensus rule which forbids custom mining software from doing so.  It’s also not clear what happens if a user reindexes as existing bogus transactions will no longer validate.

Update 3: So this is probably how the attacker is minting coins (also see thread from one of the authors of the Zerocoin protocol).

A Zcoin Spend transaction claims that a value of 100 should move from the private pool to the attacker’s address at the public pool.  This may be the attacker’s transaction in a recent block.

Such a transaction is verified in the block of code beginning main.cpp, line 1484

else if (txout.nValue == libzerocoin::ZQ_WILLIAMSON * COIN) {

This ZQ_WILLIAMSON constant is defined in libzerocoin and has a value of 100.

enum CoinDenomination {
 ZQ_LOVELACE = 1,
 ZQ_GOLDWASSER = 10,
 ZQ_RACKOFF = 25,
 ZQ_PEDERSEN = 50,
 ZQ_WILLIAMSON = 100 // Malcolm J. Williamson,
 // the scientist who actually invented
 // Public key cryptography
 };

Back to main.cpp.  During verification, the code should check that a private coin of ZQ_WILLIAMSON (100) denomination is being spent.  It doesn’t.  Instead it checks that a ZQ_PEDERSEN (50) is being spent.  Could this be a copy and paste bug?

See here, main.cpp, line 1551-1553:

if (pubCoinItem.denomination == libzerocoin::ZQ_PEDERSEN && pubCoinItem.id == pubcoinId && pubCoinItem.nHeight != -1) {
 ...
 libzerocoin::PublicCoin pubCoinTemp(ZCParams, pubCoinItem.value, libzerocoin::ZQ_PEDERSEN);

So the attacker creates a Zcoin Spend transaction which consumes a valid private coin worth 50.  On the output side, instead of specifying a value of 50, they set a value of 100 which passes the broken validation code.  The transaction is now deemed valid, accepted into the memory pool and later mined into a block?

Update 4: Double-spending

Having run a patched version of Zcoin to examine the blockchain in more detail, it appears there is a bug that could have enabled an attacker to double-spend private coins.

This may be what Zcoin alluded to in their blog post; which observers confused with the single character fix intended for mining pools, as discussed above.

A typographical error on a single additional character in code allowed an attacker to create Zerocoin spend transactions without a corresponding mint.

Private coins have unique serial numbers.  A Zcoin Spend transaction will transfer coins from the private pool to the public pool.   The wallet keeps track of the serial number of spent coins.

If you create a new Zcoin Spend transaction and try to double-spend a private coin, the wallet will check to see if the serial number has already been used, and if so, reject the transaction as invalid.

However, a typo, repeated across multiple blocks of code, allows the same serial number to be re-used for each private coin denomination.

When recording a serial number as spent, an instance of class CZerocoinSpendEntry is created and stored.  See wallet.h:

class CZerocoinSpendEntry
{
public:
 Bignum coinSerial;
 uint256 hashTx;
 Bignum pubCoin;
 int denomination;
 int id;

Unfortunately when populating the denomination member variable, an equality operator was used instead of assignment, resulting in the denomination always being zero, as set in the class constructor.

zccoinSpend.denomination == libzerocoin::ZQ_LOVELACE;

This error is repeated for each coin denomination.

zccoinSpend.denomination == libzerocoin::ZQ_GOLDWASSER;
...
zccoinSpend.denomination == libzerocoin::ZQ_RACKOFF;
...
zccoinSpend.denomination == libzerocoin::ZQ_PEDERSEN;
...
zccoinSpend.denomination == libzerocoin::ZQ_WILLIAMSON;

When checking to see if a serial number has already been used, details of the private coin are checked against every CZerocoinSpendEntry object stored in the wallet.  This includes the denomination field.  See main.cpp:

 if (item.coinSerial == serialNumber
 && item.denomination == libzerocoin::ZQ_LOVELACE
 && item.id == pubcoinId
 && item.hashTx != hashTx) {
 return state.DoS(100, error("CTransaction::CheckTransaction() : The CoinSpend serial has been used"));
 }

Since the CZerocoinSpendEntry item has a denomination of zero, the condition above will be false.  As a result, the private coin passes this double-spending check.

It also passes the next check…

if (item.coinSerial == serialNumber
&& item.hashTx == hashTx
&& item.denomination == libzerocoin::ZQ_LOVELACE
&& item.id == pubcoinId
&& item.pubCoin != 0) {

…and the final check:

else if (item.coinSerial == serialNumber
&& item.hashTx == hashTx
&& item.denomination == libzerocoin::ZQ_LOVELACE
&& item.id == pubcoinId
&& item.pubCoin == 0) {

Since all checks have passed, the wallet mistakenly believes the transaction is valid.  The wallet will create an instance of CZerocoinSpendEntry for the transaction, which due to the bug, will have its denomination field set to zero.

If you set a breakpoint or add some debug statements here and then sync up with the blockchain, you’ll see that the wallet will sometimes add the same serial number multiple times, even though that shouldn’t be possible.

if (!isAlreadyStored) {
   ...
   walletdb.WriteCoinSpendSerialEntry(zccoinSpend);

The Zcoin developers proposed fix will hard fork the network at block 22,000.  From that point onwards, CZerocoinSpendEntry instances will be populated correctly:

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

A postmortem of the problem from the Zcoin developers would be most welcome.  I’m sure many would like to better understand the issue, such as how and when the bugs entered the code base; the project on Github does not have a full history.

I hope the community do not confuse or conflate implementation bugs found in the Zcoin client with the underlying protocol it is trying to implement.

Update 5: Zcoin have now confirmed in a blog post that serial number tracking was broken.  The attacker was able to double-spend private coins by using the same proof over and over again.

Update 6: (6 March 2017) Examining the serial numbers spent in the blockchain, it looks like the Zcoin attacker created over 388,000 Zcoins – the same private coin worth 100 XZC was spent 3884 times.

The coin had serial number 3266697156756944707956118971468504870401894708478006058931961100760185691753 and you can see which transactions it was spent in here: https://gist.github.com/bitcartel/bbb3bb6b04aea1e17e9ff90b0b88e483

At the time, this would have represented 30-40% of the monetary base, an amount slightly greater than mentioned in Zcoin’s blog post.  The difference of ~18,000 coins is likely due to the ongoing attack between the time of publication and resolving the issue.

We estimate the attacker has created about 370,000 Zcoins

So when did the attack begin?  In a second blog post, Zcoin writes:

Upon further investigation, the dev team discovered that at block 11002, the serial number for the spend transaction had been reused

It does appear to be the case that the attacker was experimenting with the bug from block 11002 (December 9th, 2016).

  • Block 11002, 50 XZC private coin is spent, with serial number 15348264208363743419987472354309310345136001435528362425226759289333380951502
  • Block 11013, the same 50 XZC private coin is spent again
  • Block 11029, first appearance of 100 XZC coin which gets spent 3884 times

It’s interesting to note that the attacker could only include a single fraudulent transaction per block, because the code artificially restricted private spends to one a block.  This slowed down the rate of attack to 100 XZC per block but may also have enabled the attack to go unnoticed by casual observers of the blockchain.

From the start of the attack to when it was stopped, at block 22000, the price of XZC rose from USD 0.50 to USD 2.00.  If the attacker managed to liquidate their Zcoins at an average price of $1.25, they could have netted themselves USD 500,000.

Update 7: (8 March 2017) The previously stated figure of 548,000 Zcoin where a private coin was spent 5487 times for an estimated gain of USD 750,000 was incorrect due to a processing error involving sort and uniq.  Update 6 has been amended to reflect this.

 

Advertisements

One comment

  1. “I hope the community do not confuse or conflate implementation bugs found in the Zcoin client with the underlying protocol it is trying to implement.”

    Zcoin (unlike Zcash) does not have a well-defined protocol specification. It is different from Zerocoin as defined in the paper (http://zerocoin.org/media/pdf/ZerocoinOakland.pdf), but the intended differences are not documented. So, I don’t know how you would make a well-defined distinction between implementation bugs and protocol bugs for Zcoin.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s