I first learned about cryptocurrencies back when it was still useful to mine Bitcoin on a GPU. While I didn’t capitalize on that opportunity (hindsight is 20/20), a few years later I picked the interest up again. Ethereum made me a bit of profit, but I was never drawn heavily by the economics and trading of cryptocurrencies. The technology is the cool part.
I decided to make my own cryptocurrency, simply to learn how they work on a more intimate level. Among the hundreds of ICOs, it would be wasted effort to try and promote it as a legitimate coin, but the knowledge you can get from building a project from the ground up is quite valuable. And again, the tech is really neat!
Note: The commits linked below are not representative of the final code! Take a look at master branch instead.
Implementing the basics
I started off with one of the key aspects to most cryptocurrencies: proof-of-work!
It’s a pretty simple algorithm. You have your base data, and you have a number (the nonce). Concatenate them, and hit the result with SHA-256. If the hash output isn’t under the target hash, increase the nonce and try again! In the below example, we’re looking for a hash that starts with a minimum of four zeroes.
This is mining. Instead of the string , the computer performs the algorithm on a block (or more accurately, a block header) of cryptocurrency transactions. The quicker a computer can calculate SHA-256 hashes, the more likely it is to find a hash under the target, and consequentially, produce a valid or solved block. Once found, the winning nonce can be passed with the block to other nodes. They can then very easily validate the incoming block, as a node only needs to hash a block header with its nonce once to verify that the corresponding block has been solved.
To make this computation worthwhile for the computer, miners include a reward transaction to themselves in each block that they mine. Essentially, this special transaction makes the coins that compose a cryptocurrency. This means that the number of coins in a cryptocurrency circulation depends completely on the number of blocks mined. At least, for a while.
In most (or probably all) cryptocurrencies, to enforce a cap on the number of coins that can exist, the amount of the reward transaction in blocks halves every time a certain number of blocks have been mined. In Bitcoin, for example, this is every 210,000 blocks. Eventually, it can be halved no more, and miners will no longer get rewarded just for discovering a block, and rather, will only get fees from included transactions. Anyway, we’re getting off track!
Proof-of-work is important. To show why, say, hypothetically, blocks don’t exist. The state of the network (who has what, who did what) is then based solely on the consensus of the majority of nodes.
In this case, an attacker can take over the network by holding that majority. They then have the final say on what is and isn’t valid. Even if we increase the percentage needed for consensus, this is a major security flaw. It’s cheap to run nodes that only require memory and connectivity, with say, a VPS provider like AWS.
To combat this, the state of the network is instead based on the product of hashing: the mined block. To attack this model, one must instead take over the majority of the hashing power. This is significantly more difficult and expensive, as scaling hashing power means scaling processing power, not just memory.
Next, I implemented Merkle trees! These are really cool. Simply put, a Merkle tree is a tree of SHA-256 hashes, where the top row
L0 contains the hashes of all the transactions in the block. The hashes are paired up in twos, concatenated, and then hashed to make a child hash in the next row. Each row needs to have an even number of elements to allow this pairing, so if it’s odd, we can duplicate the last hash in a row.
For ease of viewing, I am only showing the first two bytes of each hash.
This process continues until there is a single hash in the final row. We can call this hash the Merkle root. Because of the cascading nature of the tree, the Merkle root is guaranteed to change if any transaction in the block changes, and thus can be used as a single representative hash of all the transactions. So, we can include this, rather than all the transaction data, in the block header when mining, reducing the amount of data we need to hash. This speeds up the process of calculating hashes. Pretty cool huh?
A namesake of cryptocurrencies, the mighty blockchain. This brings together the last two topics into a nicely formed package.
A blockchain is exactly what it sounds like, a chain of mined blocks. More importantly, the blocks in the chain are linked in such a way that it’s impossible to change any data in the chain without everything further along completely changing too.
On the left, we have a valid blockchain. Each block header has been mined to find a hash under the target. That hash is then included in the header of the next block, linking them together.
On the right, we make a small change to the same blockchain: tweaking the Merkle root of
2397. Uh-oh! First, the block data and the nonce no longer produce a hash under the target. This new invalid hash is then fed into the next blocks header, which causes the same effect to it’s hash as well. This effect cascades down the chain, causing all blocks below the modified one to become invalid.
NOTE: Blocks vs block headers
Previously in this blog entry, I’ve explicitly defined blocks and block headers as two different things.
During mining, the unmined block is first converted into a hashable block header. This is done to remove any data that is not required to be hardened by mining, such as the height of the block, and the raw transaction data. Then, the block header is mined with its nonce to produce the hash for the block.
That’s about it, really!
While the first prototype of DrakeCoin implemented the cool data structures and algorithms that are fundamental to a cryptocurrency, it still needed a lot of pizazz to be fully-functional. In particular:
- Asymmetric key generation and addresses.
- Communication, synchronization, and consensus.
- Transactions: signing, verification, and UTXOs.
- Finally, practical data structures for all of the above.
In the next part, I’ll describe what it took to put all these concepts together into a functional coin.
Happy New Year folks!