2012-07-31

There and Back Again: A Tale of 31 Bitcoins or "How I nearly lost $300 in the Bitcoin cryptocurrency"

I wanted to pay my brother back for something, but I wanted to have a little fun while doing it. So I decided to send him the money in Bitcoins which I have a little stockpile that I incidentally created while playing around with it back when it was easy to do such things (before it became 'popular').

I didn't want him to have to deal with creating his own wallet and downloading the blockchain (2+ GB on my machine), so I decided to use the new YCombinator startup Coinbase to send him the Bitcoins to his email address (which would then walk him through the easy process of setting up an online wallet).

I also wanted to play around with a more advanced local bitcoin client than the traditional one called Armory. It had quite a few neat features that I wanted to play around with so I gave it a spin and converted my traditional 'Satoshi' wallet to an Armory wallet. I then transferred 19 BTC from my main wallet to my coinbase wallet in preparation for paying my brother back.

At this point, I saw the 19 BTC land in my coinbase wallet, but I had goofed up the Armory wallet by accidentally importing two of the same wallets, having it show twice the amount that I had to spend. So I decided to blow away ~/.armory with a quick rm -rf and restart the program to reimport my wallet from the pristine 'Satoshi' wallet backup.

At this point I noticed that my account balance was 50 BTC lower than it was originally and I got that sinking feeling in my stomach. My first thought was to theft, as the bitcoin community has been inundated with compromised wallets and online services, but I knew that was extremely unlikely so I kept digging.

At this point I the wonderful blockexplorer showed me this page which shows my 19 BTC going out from my wallet, and an additional 31 BTC going out as well! Here if you click on the outgoing address you are treated to this handy text that ultimately tipped me off: "Every time a transaction is sent, some bitcoins are usually sent back to yourself at a new address..." Then after some more digging I found this handy page which describes the concept of 'change' which is similar to the concept of trying to buy a pack of gum with a $20 bill. Sometimes, when trying to send an amount of bitcoins, you will actually need to send out more than you specified, and then receive the remainder into a newly created address in your wallet.

At this, the swift, crystalline hammer of realization struck: I had just deleted the freshly created 'keys' for my bitcoin 'change' when I deleted the .armory folder!

In effect, I had told the universe to 'keep the change'. As if I couldn't get those 'keys' back, then no one in the rest of the history of the universe would be able to use my 31 lost bitcoins.

The alarm bells began clanging as I realized I had limited time: those 'deleted' files are only really deleted when overwritten (not necessarily when first deleted) so every additional write to my filesystem was another shotgun blast at those poor defenseless keys sitting on the little NAND gates of my SSD. I realized I had three options 1) unmount my filesystem or remount it read-only 2) cleanly shutdown the machine or 3) 'pull the cord'. I knew 2 was a bad idea, as the amount of writes that Chrome alone would make shutting down would be disastrous, and I was unsure if 1 would cause extra writes with flushing the kernel caches to the system and persisting any remaining journal entries so I chose 3 after watching to make sure there was no transient disk writes. If anyone knows which is actually better, I would be curious to find out.

Now upon rebooting into a Live Ubuntu flash drive, I began researching my options. A program called ext3grep had the promising tag line:
On February 7th, 2008, I accidently deleted my whole home directory: over 3 GB of data, deleted with rm -rf. The only backup that I had was from June 2007. Not being able to undelete was unacceptable. So, I ignored what everyone tried to tell me and started to learn how an ext3 file system really works, and what exactly happens when files are deleted... 
Three weeks and nearly 5000 lines of code later, I had recovered every file on my disk.
Unfortunately, it kept bugging out on me due to the differences between ext4 and ext3, so I had to move on, but it helped me wrap my head around some of the ext filesystem.

Next I found extundelete, which also looked promising due to it's claim of being better than ext3grep and supporting ext4.

After finding the source doesn't compile on e2fslibs-dev > 1.49 (or something like that), I found a newer version available in the Debian sid repositories, but to make a long story short, it didn't find a single deleted file on my filesystem.

At this point it began to look hopeless, as I figured if I couldn't achieve my desired ends with these powerful tools, then what luck did I have left?

Luckily I kept going and found the wonderful PhotoRec which scans the filesystem block by block -ignoring the inodes that normally direct the ext filesystem - and searching for specific header bytes. Obviously the wallet format of Armory was not one of the 300+ supported filetypes, but with a bit of ghex (hex editor), some documentation, and a flexible program I was able to specify my own filetype.

At this point, upon scanning all 32GB of my SSD, it found 3 candidates. A promising number, because I expected 2 (from the reinitialized .armory directory), so perhaps one had survived? Unfortunately, it was not all fun and games, as 2 of those 3 were over 4GB in size, so they had either been overwritten somehow (the inodes, which describe the file and the the number of blocks that a file resides on, are often the first to go when a file is deleted, so perhaps the inode and some of the downstream blocks of the wallet files had been deleted and photorec naively and safely just kept copying).

Luckily, after failing to find the address string [1] in any of these three files, I realized that the Bitcoin protocol and Armory wallet actually use the Hash160 of the public key, and upon searching for that, I found that only one of the 3 fit the bill, and upon some inspection by ghex and a simple head -c 64387 file.dump > possible_wallet I had a winner! It was a pleasure to see those 30 BTC back in my wallet.

I didn't cover some of the fun things I tried here, like binary grepping, grepping an entire block device, the creation of testing block devices etc... but you get the idea.

So overall, I had a bit of fun learning some linux filesystem tricks and realizing the valuable service that online bitcoin wallets bring to the table.

Now the only question that remains is should I switch to online wallets for all my funds to avoid any future mishaps or continue down the path I'm on?

[1] - 1AEhBXbFbZ6aGNppGHntm4LQbumQXDi99s