Speculation: How to lose significant funds through malleability

[grau]

While thinking through implications of malleability and the story of Empty Gox, I came up with a speculative idea how one could burn significant funds while facing a malleability attack.

This is pure speculation, a thought exercise to elaborate what to watch out for if developing a custom wallet.

Assume one have a set of coins, that is UTXOs and a set of keys that are able to spend them.

Now for some reason, that could be withdraw or even internal reshuffling one spends some of them in a transaction t1. Since the wallet is privacy aware, the change of t1 goes to a new key and is added to the key set. Since the change of t1 only depends on own transaction, one might fall for the assumption that this new UTXO is as good as any other in the pool and spend it in a subsequent step with t2 before it is confirmed. We know that this scheme could blow up if t1 is confirmed with a different hash as t2 will loose its input and become invalid.

This is an inconvenience but not really a big deal since t2 can be recreated referring to new t1 hash. WAIT there is one other thing you need that is the key to unlock t1. I believe that the key could fall victim to an aggressive optimization of the key set. Why keep a key around for coins spent?

Once one sees the trap it becomes obvious that even confirmed transactions that come in with a new hash after a reorganization of the chain might trigger the need for a key that was previously considered useless for good.

I read in some thread that satoshi said there is no reason to ever delete a key. He is right as usual. In a high demand environment such as an exchange that creates tons of keys a day (because it is also privacy aware) keeping all keys at hand that were ever used is a significant burden.

An efficient storage of that amount of keys can only be algorithmic, that is HD. Good that I build exchanges with that...

[BeataTX91]

I admire your way of thinking. After this I will also save my keys! I like your wordplay "Empty Gox" - very appropriate nick for this company

[bitserve]

Interesting theory... except that it doesnt match with the facts:

Considering you could reuse any deposit address at any point of time in the future, one can conclude that mtgox system was storing all public/private keys and its relationship forever.

[grau]

Interesting theory... except that it doesnt match with the facts:

Considering you could reuse any deposit address at any point of time in the future, one can conclude that mtgox system was storing all public/private keys and its relationship forever.

I did not claim this explains how Mt. Gox became Empty Gox, but is a present danger if one attempts to optimize key store.

BTW. having the deposit address forever does not prove that addresses that received change where kept after they were spent.

Pure speculation, but imagine that Gox worked like:

loop:
if hot wallet empty get a big coin from cold store
    use big coin to pay A while change goes to k1
    use k1 to pay B while change goes to k2
    ...
    ...
    use k26 to pay Z while change goes to k27
...

Since the big coin change controlled by k1 is spent one could think to forget it for good, BUT then comes in a malled transaction replacing the payment for A and the entire chain becomes invalid. Should k1 be no longer at hand, then big change of big coin is gone for ever...
repeat until cold storage is empty.

[bitserve]

If my understanding is correct, exchanges use their custom code to create the transactions. That would mean they are the ones that specify also the address that would receive the change. I think it is easier to reuse them from a pool (which you are already storing private keys) of "hot" change address than to create new ones each time and "erase" the private key after spending...

In this case I think the "wrong" way is more effort than the right one.

But yes, not only exchanges should not erase private keys of any address ever used... Exchanges should NEVER EVER erase ANY transactional data, logs, accounting, ANYTHING.

[grau]

If my understanding is correct, exchanges use their custom code to create the transactions. That would mean they are the ones that specify also the address that would receive the change. I think it is easier to reuse them from a pool (which you are already storing private keys) of "hot" change address than to create new ones each time and "erase" the private key after spending...

In this case I think the "wrong" way is more effort than the right one.

But yes, not only exchanges should not erase private keys of any address ever used... Exchanges should NEVER EVER erase ANY transactional data, logs, accounting, ANYTHING.

I do not claim, this is how Gox worked, and the problem is not limited to an exchange but anyone dealing with Bitcoin transactions at a high volume. If however Gox worked like this, then this allows for burning arbitrary amounts in a short period of time if attacked with malled transactions.

It might be safer to re-use a pool, but that might also be suboptimal for privacy and eventually also for performance. Privacy should not be an issue for exchanges since the should rather be audit able, but privacy is an issue for a bitcoin business that does not want to leak aggregated revenue to competitors.

HD key generation addresses this problem nicely since it ensures keys are not lost even if never re-used and not backed up regularly.

[comboy]

You surely would be able to recover them from your previous backups, right? .. Right??

[grau]

You surely would be able to recover them from your previous backups, right? .. Right??

If someone falls for the wrong assumption that keys of spent coins are worthless, then would also think that it is sufficient to back up keys that control current holdings. Some funds could be recovered using backups, provided malleability did not strike in-between them.

[StarfishPrime]

Interestingly, ongoing blockchain analysis has revealed that (at least recent) gox btc payouts used exactly that sequence, single payouts with disposable intermediate change addresses:


hw -> t1 -> t2 -> t3 ... etc
           \       \       \
         out1   out2   out3 ...

Beginning with a larger amount from a hot wallet with individual payouts (cust withdrawals) of decreasing size with the remaining dust amt. returned to a gox wallet.

A few possible TM attack payments were identified, but very few, and without rejected mempool inventory (or gox) logs, not really provable.

Edit: On the other hand, if grau's theory holds true, there should be some blockchain evidence out there (i.e. dead-end branches from hot wallets holding varying change amounts).
It would fit well with the vague gox claims of "not really gone, just not accessible..", large number of failed, non-confirming tx's etc.
Double payments wouldn't necessarily be evident either.

Interesting possibility.

Here's one of the few identified possible TM duplicate tx's within one such recent payout chain (just prior to gox withdrawal shutdown):

http://www.reddit.com/r/Bitcoin/comments/1z14j0/needed_any_bitcoin_addresses_you_have_used_to/cfptosz

originating gox hot wallet (or dust collector) for above tx chain:

https://blockchain.info/address/16MBuCHx5Q1JGmN3TTbbssfVSPpUjAv8SF


  

[DannyHamilton]

Any reasonable programmer would put into a place a system of archiving private keys that were no longer necessary.  To simply delete them would be pure incompetence.

A private key is 32 bytes.  Even if the exchange needed 100,000 addresses per day, they would be looking at archiving a bit over 3 MB per day. That's just barely more than a GB per year.  You could fit 3 decades of private keys on a 32 GB USB flash drive.

[StarfishPrime]

Any reasonable programmer would put into a place a system of archiving private keys that were no longer necessary.  To simply delete them would be pure incompetence.

A private key is 32 bytes.  Even if the exchange needed 100,000 addresses per day, they would be looking at archiving a bit over 3 MB per day. That's just barely more than a GB per year.  You could fit 3 decades of private keys on a 32 GB USB flash drive.

The key word being "reasonable" of course.  

If this mechanism was somehow partially responsible for coin loss it leaves two possibilities:
1. Keys were deleted and the coins are now inaccessible (unless HD key generation was used, or the keys can otherwise be recovered from backup, etc.)
2. Keys were saved, and just need to be correlated with the orphaned coins (i.e. they were lost track of)

Both seem relatively unlikely - but remember - this was Mt.gox where it seems almost nothing was beyond the realm of possibility.

[solex]

Any reasonable programmer would put into a place a system of archiving private keys that were no longer necessary.  To simply delete them would be pure incompetence.

Perhaps not exactly deliberately deleted, but "updated" during a rewrite.

[StarfishPrime]

Mt.Gox's vague description of the so called bitcoin "bug" that they are blaming for losses, from their latest site update (3/3/14) :

“At the start of February 2014, illegal access through the abuse of a bug in the bitcoin system resulted in an increase in incomplete bitcoin transfer transactions and we discovered that there was a possibility that bitcoins had been illicitly moved through the abuse of this bug.”

Time will tell if there's any truth to it at all, but one things for sure: Without any blockchain evidence, which they would of course have, no one is going to accept these increasingly unbelievable tales at face value.