Sep 28

Understanding How Bitcoin Works

Long time, no update. ūüôā It’s difficult to produce quality content, which is why I was very impressed with the person who made this particular video:

 

 

Understanding how Bitcoin works can be difficult, but this particular video is exceptional in breaking the concepts down and connecting them together. I consider it another “must-see” YouTube video, if you have any interest at all in cryptocurrency.

May 12

C++, WebSockets, and Mt.Gox

I’ve been reading quite a bit about websockets lately. To test my understanding of the concepts involved, I was trying to connect an application to Mt.Gox in order to collect bitcoin-related pricing information. I was having some difficulty getting all of the parameters aligned properly with all of the various websocket libraries, so I went through the process of reading other people’s code on github, sifting through stackoverflow-style-forums, and experimenting until things worked correctly. I thought I’d document some of the minor hurdles here, just to save some people out there in the wild some effort.

I tried a few approaches:

  • Python using autobahn
  • C++ using libwebsockets (a C library)

The Python implementation worked perfectly. ¬†The only quirk was that I had to trick the application into inserting an “Origin:” field in the websocket handshake in order to get the application to connect. ¬†(This had something to do with something called the Web Origin Concept. ¬†It’s a safety mechanism for web browsers.) ¬†After tweaking the code to force an ‘Origin’ using the autobahn library, the handshake with the server ended up looking something like this:

GET /mtgox HTTP/1.1
User-Agent: disease
Origin: websocket.mtgox.com:80
Host: websocket.mtgox.com:80
Upgrade: WebSocket
Connection: Upgrade
Pragma: no-cache
Cache-Control: no-cache
Sec-WebSocket-Key: JI2o83NARHJDps1XCN7eCQ==
Sec-WebSocket-Version: 13

After a handshake of this style, data starts streaming over the connection with no issue. With a working Python version, I had enough knowledge to craft an appropriate handshake in the C++ version of my bitcoin application.

With libwebsockets, it took some tinkering with the source code to get things to work right with Mt.Gox. The extensions field in the ‘lws_context_creation_info’ should not be filled in, and in the connection phase in libwebsocket_client_connect(), the specified protocol should be NULL. The origin and host strings fed into the libwebsocket_client_connect() function should mirror what you see above in the successful python handshake.

I didn’t bother to post code here, but the general idea to get things to start streaming correctly is to have a handshake that looks something like what I’ve copied above for the python implementation I used.

I hope this helps the random Googler out there searching for information.

Apr 30

Matonis: “Fincen’s New Regulations Are Choking Bitcoin Entrepreneurs”

I found this informative¬†article written by Jon Matonis detailing the current hurdles in the way of mass adoption of crypto-currencies within the US. ¬†Technology enthusiasts (like me) tend to dive headfirst into the “how things work” angle of emerging trends like bitcoin, but much of what determines the fate of new technology lands in other domains such as government and public policy.

Matonis talks about past efforts (PayPal, E-Gold) and moves into descriptions of how current bitcoin businesses are navigating the landscape. ¬†I thought the content presented was an excellent summary and worth the read. ¬†Here’s a snippet from the article:

In a recent speech, Fincen Director Jennifer Shasky Calvery said the new guidance aims “to protect [digitial currency] systems from abuse and to aid law enforcement in ensuring that they are getting the leads and information they need to prosecute the criminal actors.” She reiterated that the guidance does not apply to everyday users who pay or accept bitcoin for goods and services.

But by saddling startups with compliance requirements, and making them unattractive clients for regulated banks that despair of serving MSBs, Fincen is choking these businesses that facilitate conversion of bitcoins into dollars. Fewer exchanges and more red tape will make it harder for merchants or consumers (who, after all, must still pay the bills with dollars) to take advantage of the Bitcoin payment system’s speed, privacy and competitive costs.

 

Apr 24

Pitfalls of Bitcoin Ownership: Disk Failure

I was in the middle of browsing the web when suddenly my system stopped responding to me. ¬†The mouse was still moving, but none of the windows were registering actions. ¬†My system froze and locked up on me. ¬† After cycling the power,¬†I noticed the kernel message log spewing out all kinds of errors related to the disk drive that housed my “/home” partition. ¬†My disk was failing. ¬†Normally, I’d just throw a new disk in, recover from backups, clone the appropriate git repos, and proceed. ¬†However, this time was slightly different because ¬†my¬†bitcoin wallet was on the failing drive and wasn’t backed up yet.

Thankfully, the value of my bitcoins doesn’t amount to much more than a few dollars. ¬†Nevertheless, had I been reliant on bitcoins for substantial financial purchases, this could have been a disaster scenario. ¬†There is much talk on internet forums about people losing thousands of dollars worth of bitcoins due to hardware failure. ¬†Even though there was more than adequate warning to pursue backups, ¬†I didn’t consider that I’d be confronted with such a scenario so early on in my experience with crypto-currency. ¬†(I sort of figured the dollar value of my holdings wasn’t substantial enough to care, and I had only had the coins for a week or two before the disk failed.) ¬†However, after the disk failed, I was determined to get my coins back and I managed to succeed.

This post details roughly what I did to recover my wallet file on a linux-kernel based operating system with an ext4 filesystem. ¬†Unfortunately I don’t have screenshots and the process I describe below may be somewhat imprecise. ¬†However, my post might serve as a rough outline of how to retrieve your wallet in the event you start seeing evidence of disk failure. ¬†Please note that I can’t make safety/success guarantees about these steps and they may not work for you (in fact, they may even cause damage.) ¬†If you have substantial bitcoin value at risk, you may want to consider reading a few different sites before trying these steps or, better yet, find a data recovery specialist or expert.

In my situation, I use an ext4 file system.  Because my system was for general purpose use, I did not have the /home partition encrypted.  When the disk stopped operating, I took the following procedures to recover my bitcoins:

  1. I downloaded an Ubuntu 12.04 LiveCD
  2. After booting from the CD, I clicked “Try Ubuntu”
  3. I loaded FireFox and downloaded TestDisk  and unpacked the files.
  4. After launching XTerm, I ran TestDisk (as root/sudo’d). ¬†I then navigated to the partition I knew was my ext4 partition on the disk device I knew was failing (in my case, a partition on /dev/sdb). ¬†I then used the file system utilities ¬†menu (“Filesystem Utils”) and tagged the partition (via the [T]ype operation in TestDisk) as an LVM->Ext4 partition. ¬†Before using the [T]ype operation, TestDisk showed the ext4 partition as just “MS Data”. ¬†Specifying the type made TestDisk “see” the partition correctly.
  5. I tried to list the files in TestDisk (I think it was the “L” command); this failed. ¬†Don’t panic (yet.)
  6. Since listing the files failed, I used the TestDisk superblock option to get the appropriate disk information from the backup superblocks on the filesystem. ¬†TestDisk gives some fsck.ext4 command to attempt to repair the filesystem, but I ignored it and just went back to the menu and retried the “list” operation
  7. Once the files started listing, I navigated to the /home/<username>/.bitcoin directory, and then I copied the wallet.dat to a USB memory stick that I had inserted.

Once the wallet.dat was recovered and the disk drive was replaced, I recovered /home from my usual backups and I placed the file into a new .bitcoin directory on my system. ¬†‘bitcoin-qt’ (my wallet app) accepted the file and successfully recovered all of my bitcoins. ¬†It began synchronizing with the p2p network.

To prevent future scenarios like this, I configured RAID and put a script in place to routinely backup the wallet file. ¬†For the record, TestDisk is amazing software. ¬†I just hope I never have to use it again. ¬†ūüôā

Good luck to those who are ever in this situation.  I hope the steps above help you, or at least point you in the direction of the right tools to recover your coins.

 

Apr 16

Merkle Trees

The paper detailing the mechanics of Bitcoin is a fascinating read. However, the technology involved requires several re-readings of the paper to make sense of what is going on. ¬†I’ve been attacking the concepts piece by piece as time permits. In particular, the Bitcoin paper’s comments regarding the use of the Merkle Tree caught my eye. I had never encountered the concept of a Merkle Tree before in any applications I’d worked with, so I figured some investigation would be worthwhile.

Within Bitcoin, the Merkle Tree is a disk-space saving mechanism.   From the Bitcoin paper:

”¬†Once the latest transaction in a coin is buried under enough blocks, the spent transactions before¬†it can be discarded to save disk space. To facilitate this without breaking the block’s hash,¬†transactions are hashed in a Merkle Tree […], with only the root included in the block’s hash.¬†Old blocks can then be compacted by stubbing off branches of the tree. The interior hashes do¬†not need to be stored.

I did some digging into the Merkle Tree and read some of the implementation code to understand it. I found that the Wikipedia page does a pretty good job summarizing the data structure:

“In cryptography¬†and computer science¬†a¬†hash tree¬†or¬†Merkle tree¬†is a tree in which every non-leaf node is labelled with the hash of the labels of its children nodes. Hash trees are useful because they allow efficient and secure verification of the contents of larger data structures. Hash trees are a generalisation of hash lists¬†and hash chains. To demonstrate that a leaf node is part of a given hash tree requires an amount of data proportional to the log of the number of nodes of the tree. (This contrasts with hash lists, where the amount is proportional to the number of nodes.) The concept is named after Ralph Merkle.”

The bitcoin source code helps make some of the concepts clearer. ¬†Within the code, the CBlockHeader shows a member variable ‘uint256 hashMerkleRoot’ that refers to the concept mentioned in the paper:

class CBlockHeader
{
public:
    // header
    static const int CURRENT_VERSION=2;
    int nVersion;
    uint256 hashPrevBlock;
    uint256 hashMerkleRoot;
    unsigned int nTime;
    unsigned int nBits;
    unsigned int nNonce;
    ...

And, as far as the actual construction of the Merkle Tree:

uint256 BuildMerkleTree() const
{
    vMerkleTree.clear();
    BOOST_FOREACH(const CTransaction& tx, vtx)
        vMerkleTree.push_back(tx.GetHash());
    int j = 0;
    for (int nSize = vtx.size(); nSize > 1; 
         nSize = (nSize + 1) / 2)
    {
        for (int i = 0; i < nSize; i += 2)
        {
            int i2 = std::min(i+1, nSize-1);
            vMerkleTree.push_back(
                Hash( BEGIN(vMerkleTree[j+i]),
                      END(vMerkleTree[j+i]),
                      BEGIN(vMerkleTree[j+i2]), 
                      END(vMerkleTree[j+i2])));
        }
        j += nSize;
    }
    return (vMerkleTree.empty() ? 0 : vMerkleTree.back());
}

The first thing to note is that the Hash() function mentioned in this code is actually a SHA256 double hash. (You can look into the code for yourself to validate this.)

The code appears to iterate over a vector of transactions and pushes their hashes into a vector representing the nodes of the Merkle tree. It then loops in such a manner that it appears to hash adjacent transaction hashes together (if an adjacent node is available — if one isn’t, the node is concatenated with itself). So if there are 3 transactions (nSize=3), [1, 2, 3]. The first pass of the outer loop, nSize = 3, you get an inner loop where there’s a hash of the hash computed over the hashes of element 1 and element 2 (we’ll call it dhash[1,2]), then a hash of the hash of element 3 concatenated with itself (dhash[3,3]). The variable j increments forward, so that on the next loop iteration, the double hash of dhash[1,2] and dhash[3,3] (both from the previous iteration) is computed, etc., etc. and the process continues until the tree gets built within a vector. The last node (vMerkelTree.back()) ends up being the root hash.

When I queried some people on various forums as to the necessity of the double hash as opposed to a single hash, they claimed it was desirable as a means of increasing the cost of calculation within the bitcoin framework.

Interesting, right? I hope to look more into the transaction mechanisms as I dig further into the system. Nevertheless, the exercise of going through the code to construct the Merkle Tree was educational and enlightening.

 

Apr 15

jQuery, Websockets, and Bitcoin Time and Sales

If you haven’t seen Clark Moody’s Mt.Gox bitcoin market data website¬†yet, you should. ¬†It’s a really beautiful presentation of realtime Mt.Gox BitCoin orderbook depth, the trade tape, and charts at various time frames.

I was so impressed by Clark’s presentation of market information that I wanted to dig into how modern web sites present information from real-time data sources. ¬†I don’t typically work on web applications, so I had to figure out what was involved. ¬†There were three pieces of key knowledge: ¬†1) Basic javascript, 2) knowing how to use a websocket API, and 3) using CSS and jquery to figure out how to manipulate documents in a web browser. ¬†(I had very minimal knowledge of all three. ¬†Fortunately, Javascript is easy to get a handle on for someone with previous programming experience.)

I first went to look at the Mt.Gox API web page, where I found some simple explanations on how to connect to their streaming market data. ¬†After using a dozen console.log() statements to see what I was looking at, I finally tweaked my Javascript code to manipulate table rows in a tbody styled by CSS. ¬†I ended up with this time and sales viewer. ¬†(Please note that¬†when loading the viewer, it will take a few seconds to establish a connection to the exchange. ¬†Once the connection occurs, you should be able to see current trades happening in realtime. ¬†Note that I’ve only tried the viewer in Chrome and Firefox. ¬†I have no idea what browsers it works and doesn’t work in, as the project was just an experiment.)

The mini-project was a great deal of fun — websockets are very interesting. ¬†I was impressed by how much could be accomplished with so little work.

Apr 10

The Most Exciting Event Since the Flash Crash

… Well, most exciting to me, anyway. ¬†Who ever thought crypto-currency market dynamics would dominate office conversation on an average April day?

I don’t really own much in the way of BitCoins and only saw them as a fascinating academic topic, but I couldn’t take my eyes off of the BitCoin charting sites since the market was crashing today.

 

Image of BitCoin Market Crash

Market Crash

The net is full of rumors as to the cause of the crash.  Some are talking gloom and doom for crypto-currencies, but my guess is that these events are just part of the growing pains of a new and developing market.

These are certainly exciting times.

 

Apr 10

Cryptocoin Mining Information

While looking at merged mining[1] efforts in crypto-currencies, I stumbled across an interesting site: http://dustcoin.com/mining

The site is interesting, not only because it talks about merged mining, but because it lays out some of the variations between all of the crypto-currencies in relation to Bitcoin.

[1] Regarding merged mining, I found a good explanation here, at http://dot-bit.org/Merged_Mining:

“Merged mining works like this, you have two totally separate block chains, they are not related in any way nor does either contain any data from the other. When you mine you generate hashes that may be the solution to the current block, this is very very improbable per hash, its like a lottery where everyone generates tickets until someone finds the winning one. Normally you make tickets and check them against the Bitcoin block chain to see if they are the solution. With merged mining you create a ticket and check it against both the Bitcoin block chain and the Namecoin block chain, Bitcoin and Namecoin know nothing about each other, they are two totally different lotteries with different winning numbers, you just sent a copy of your ticket to both. Since you are sending the same ticket to two lotteries you increase your chances of winning one or the other. No Bitcoin data goes into Namecoin no Namecoin data into Bitcoin they remain totally separate, you simply run both the Namecoin and Bitcoin clients on the same machine and submit hashes to both networks, if your hash is the solution to the Namecoin block you get Namecoins if you hash is the solution to the Bitcoin block you get Bitcoins, its exactly like if you where mining on just one network, except you submit the same work twice.” -Credit: ttk2

 

Apr 08

Jeffrey Paul: “Financing the Revolution”

A friend passed me an URL today with this talk by Jeffrey Paul about the need for Bitcoin.  His talk is very good and he touches on the need for bitcoins, how they work, the evolution of the bitcoin market, and the future of bitcoins.  The video was uploaded about a year ago, but much of the information is still useful, clearly presented, and is enjoyable to follow. The video is a must watch if you are trying to make sense of the excitement around Bitcoin currently:

Financing The Revolution Lecture @ Chaos Communication Camp from Nuri Hodges on Vimeo.