Category: Not So Easy Pieces

What this is

An in depth perspective on how blockchain and cryptocurrencies work, along with a running commentary on social value, libertarianism, and whatever the heck fits my fancy. I’m attempting to write this at a high school comprehension level so that those who haven’t sat through 4 years of computer engineering classes can make sense of all of this.

What this isn’t

A primer on Bitcoin, an economic treatise, or a how-to. (Although, elements of all of those things will appear)

For those who don’t feel like scrolling through pages and pages of my ramblings, here’s the TL;DR. Blockchain is a bunch of messages with security built into them. The security isn’t perfect, but each message is increasingly secure as time passes. The list of messages is saved on every computer that participates in the blockchain, and the lists are constantly being compared for agreement. Blockchain relies on a bit of a gambit. They essentially say “you may be able to break the security on one node, or even a few, but after a few the increased security that comes with time passing will catch up with you, and you’ll be stuck well before you come close to succeeding in fraud.”

 

A Survey of Computer Science

Numbers in an Array

Computers are complex and simple at the same time. It takes millions of lines of code and tens of thousands of man-hours to put together the latest Windows or OSX version, and yet everything a computer does is simply a whole bunch of numbers saved in an array called memory.

Let’s look at an example computer memory:

Let’s ignore all of the writing for a moment and discuss what we’re looking at. Memory is “byte-addressable,” which means that you can access information 8 bits (there are 8 bits in a byte; a bit is a single value of “1” or “0”) at a time. If I want to access the byte at address 0, I write some code that properly references address 0, and I have access to the value in that address of memory. If all data was 8 bits long (e.g. a number between 0 and 255), then we’d have a pretty easy go of accessing data. Just remember the order you put it in, and you just call the number that you put it in (minus 1 because the addresses start at 0).

However, as shown in the above image, data can be much larger than 8 bits. The yellow 2-byte data is a short integer (e.g. a value between 0 and 65,535). The purple 4-byte data is an integer (e.g. a value between 0 and ~4.3 billion). There are other types of data that are even longer, like decimal numbers (called floating point numbers). Here’s more info on memory and how it works. Now it gets a bit more complicated to remember where things are in memory.

Arrays: A Simple Way to Store Large Amounts of Data

When dealing with simple data, like an integer, storing it in memory is relatively simple. As long as you know what address it starts at and how long that type of data is, you can access and retrieve the data. However, what are we to do when there is a bunch of related data?

For example, what if we want to store the daily profits for the week from our monocle and top hat shop? Now we don’t have just one piece of data to deal with, but seven. We could just toss each day’s profit into memory as we encounter it, but the accounting program we’re running may store additional info in memory: temporary values, user credentials, and other information needed by the program will also reside in memory.

We can remember each address for each individual day’s profit data, but these values are related, and it’s hard to manage access information on seven values, let alone 70 or 700 or 700,000. Treating each value individually doesn’t scale.

As shown above, Sunday’s Profit is separated from Monday’s Profit (both in red) by intervening unrelated data (in green). In order to access the week’s profit, you need to know the address of each and every day’s profit, and you have to individually retrieve each data point.

In comes a better way to handle such data: Arrays! Much like memory is an array with addresses referencing each byte, array data structures store related information sequentially so that each piece of information can be referenced with an array address.

The difference is clear. The array groups the related data together, and you can simply reference the array to get to any of the data. Array address 0 is Sunday’s profit, which is located in memory addresses 0-3. Array address 1 is Monday’s Profit and is located in memory addresses 4-7. Rather than needing to remember all of the memory addresses for each day’s profit, you can simply remember the starting memory address of the array, and use the array address to calculate where each piece of information in the array is located. For example, array address 1 translates to the array starting memory address (0) plus one array element (which is 4 bytes long), resulting in a memory address of 4. If you look at the above image, array address 1 starts at memory address of 4. NOTE: I haven’t included all 7 days of profit in the above image so that it won’t get too complicated and confusing. Here is some additional information on arrays.

However, you can also see a limitation in the above image. It works great if you know exactly how much data you need to store, but look at where the Temporary Data and User Credentials are stored. If you need to include one more piece of information in the array, you’re hosed. Either you have to start moving a bunch of stuff around in memory to make room (which is not ideal), or you have to continue the array somewhere else in memory and keep track of 2 array portions (which is also not ideal).

Linked Lists: Good for dynamic data

You may be wondering what the point of all of this is. We’re talking about blockchain, not about memory management, right? I promise, this is where we connect to blockchain.

Let’s see if we can combine the best of both worlds. Writing each day’s profit to memory separately allows you to add additional days without having to shuffle data around in the memory. On the other hand, preserving the relationship between all of the days’ profits without having to keep track of each day’s memory address allows you to scale up to large amounts of data without overcomplicating things.

One of the “best of both worlds” solutions is called a linked list. A linked list operates much like writing each day’s profit to memory separately, but preserves the relationship between the different days by including an additional bit of information pointing to the location of another day’s profit in memory.

As you can see, we have expanded Sunday’s profit and Monday’s profit from 4 bytes to 5 bytes. The additional byte (in yellow) points to the previous node. Since Sunday’s profit is the first node, its previous node is NULL (meaning it doesn’t have a previous node). Since Monday’s profit is the second node, it points back to Sunday’s profit. Previous Node 0 points to the starting memory address of Sunday’s profit.

Visualized another way, the linked list looks like this:

This is the basis of blockchain. A data structure with a payload and a reference to the previous block in the chain. Now let’s talk about security.

Hashes: Breakfast for the Masses

I dunno about y’all, but I’m sick of reading. Let’s take a quick break before getting into hashes by enjoying some pictures

Breakfast Hash and some red meat for the audience.

 

Hashes: Preserving Relationships and Security

Alright, back out of your bunks. Time for some more learnin’. Hashes are conceptually simple, but mathematically complicated. Since we’re not diving into the math, this section should be a breeze!

Let’s take a look at the array again:

If we call Array[0] we get Sunday’s Profit, and if we call Array[1] we get Monday’s profit. However, we don’t always have a situation where we know exactly what order the data will be put into the array. Imagine, for a moment, that instead of 3 days of profits, we have 3 years of profits, entered manually by an employee who isn’t guaranteed to get everything perfectly in order. How do we find Monday’s Profit in that deluge of data?

The traditional way is to search for the data in the array. Here is some more information on searching.

The fun way is to use hashing! How about we use some relevant characteristic of the data to access the data instead of the array index (“index” is another term for array address number). All you need is two math equations: one to determine the hash from the data, and another to determine a memory location from the hash.

As you can see, Sunday’s Profit data was hashed to “Sunday”, which is a characteristic of the data (specifically, the day of the week), and “Sunday” was computed to be connected to array address 0. Now, instead of accessing Sunday’s Profit data by loading Array[0], you can access Sunday’s Profit data by loading HashArray[“Sunday”].

If this is a bit confusing, another simple hashing algorithm that appears in everyday life may clarify things. Placing medical records in alphabetical order by the first letter of the last name is another hashing algorithm. If the last name is SMITH, the “algorithm” for obtaining the hash involves looking at the first letter of the last name, “S”. Then, the hash “S” points to a specific shelf in the fileroom (the “S” shelf, for lack of a better name). SMITH’s folder is placed on the “S” shelf. When I want to retrieve a folder starting with “S”, I pull a folder off the “S” shelf, and I have SMITH’s folder.

But there are many people with a last name starting with “S”. What happens when SMITH’s folder is stored on the “S” shelf and I want to store Slaver’s folder? This is called a “hash collision.” Depending on the specific situation, a hash collision is either an inevitability or a disaster. In cases where hash collisions are expected, we could simply change the data stored. Rather than just storing one piece of data for each hashed value, we can store the data for each hash in a linked list. Now, the “S” shelf looks like this (pointer is just a fancy term for the memory address):

This is great for categorization hashes like the alphabetical sorting of medical records, but isn’t the best for cryptographic hashes like are used in blockchains. Instead, cryptographic hashes rely on another protection from hash collisions, small data density.

Bitcoin and most other cryptocurrencies use what is called SHA-256 hashing. In SHA-256, a message of any* size is hashed using really fancy math into a 256 bit number, which means there are 2^256 possible hashes (1.1×10^77 for you scientific notation folks, or roughly 1/10 of the total number of atoms in the universe). Hash collisions are so rare under SHA-256 as to be practically nonexistent.

*Technically, there is a maximum length of message, but it’s enormous.

But I mentioned above that hashes are based on characteristics of the data. “S” is the first letter of SMITH, and it’s fairly easy to see the relation. What is the relation between some seemingly random 256 digit number and a Bitcoin block? Well, it has to do with math well beyond my ken, but you can go here for a bit of an explanation (as well as a look ahead). In essence, the math takes all of the data, divides it into chunks, and does a mathematical transformation on each chunk before assembling the results into the hash.

Okay, assuming you’re following along so far, you understand how categorization hashes work and that cryptographic hashes are different, but how do cryptographic hashes work?

Cryptographic hashes work on the principle that it’s much easier to do the math to hash the data than to derive the data from the hash. Let’s look again at the medical records example for a picture of how this works. If you’re given the last name SMITH and told that the hashing function (fancy term for the math to calculate the hash) is the first letter of the last name. It’s trivial to calculate a hash of “S” from the data “SMITH.” However, let’s go the other direction… if all I give you is “S”, you have thousands of last names to choose from. The chance of you guessing “SMITH” is extremely low.

The same principle applies to SHA-256 hashes. It’s relatively easy for a computer to calculate the hash from the original data, but (practically) impossible to derive the original data from the hash.

We’ll discuss the specific way cryptographic hashes are used in blockchains later on.

Let’s take another break. Things are getting a bit intense. In the spirit of the glib baby pics from a while back, here’s me in a sombrero.

How about some relaxing pics from a backpacking trip I took a long time ago?

Public Key Cryptography

Alright, back to talking security! We’ve laid the groundwork for explaining the structure and security of the blocks in a blockchain, but let’s talk about individual currency transactions and how they’re secured. If I want to send 50 bitcoins to ZARDOZ, we create a transaction to transfer the bitcoins from my wallet to his. The details will be covered later, but it’s important to notice that without any security, STEVE SMITH could read the transaction, and use the information contained in the transaction to create a fake transaction to send the 50 bitcoins to him instead of ZARDOZ.

What sort of security is used on these transactions? Public key cryptography! Public key cryptography uses the same concept of “one way” algorithms, just like the cryptographic hashes. In fact, in some cases, the mathematics for generating cryptographic hashes is used in public key cryptography.

How does it work? Let’s assume I want to send a secret message to ZARDOZ. I’m sending it over the Internet, which isn’t a particularly trustworthy place. I can’t just send the text in the open. ZARDOZ decides to generate two “keys.” In this context, one of the keys is used in combination with fancy math to encrypt the message so that it can’t be read by STEVE SMITH. The other key is used in combination with more fancy math to decrypt the message. The cool thing about public key cryptography is that you can’t figure out the decrypting key by looking at the encrypting key or at an encrypted message. This is called asymmetric cryptography.

In contrast, symmetric cryptography can be “broken” by looking at the encryption key and the encrypted message. Of course, that means you shouldn’t broadcast your symmetric encryption key on an insecure channel. For example, if my encryption algorithm is addition of the encryption key to the data, and my encryption key is 4, then if my data is the number 10, the encrypted data is the number 14 (10+4 = 14). I send 14 across the unsecured network to ZARDOZ, who uses the symmetric decryption key (the number 4), and the decryption algorithm of subtraction of the decryption key from the data, and ZARDOZ gets the original data, the number 10 (14 – 4 = 10).

Seems secure enough, especially when we use something more complicated than “add 4” as an encryption. But why are we talking about asymmetric cryptography instead? Well, because we have a problem. The Internet isn’t particularly secure, and we’re not gonna VPN with the entire bitcoin network, most of whom we don’t trust, to send them our secret key. With asymmetric cryptography, the encryption key (called the public key) can be known by everybody. It doesn’t matter if half the world can encrypt messages intended for you. As long as they’re not able to decrypt those encrypted messages, the system is secure. That’s why the decryption key is called the private key. The private key must be kept secret by the receiver of the message.

 

As shown above, I have sent ZARDOZ the message “Molon Labe!” ZARDOZ has vomited forth (published) his public key, which allowed me to encrypt my message and send it across the Internet securely. As you can see, STEVE SMITH can try his hardest to intercept my message to ZARDOZ, but all he gets is a bunch of gibberish. Then, once ZARDOZ receives the encrypted message, he uses his private decryption key (secreted away in the Vortex where nobody can access it except ZARDOZ) to decrypt the message and read “Molon Labe!”

Now, this is great and all, but isn’t blockchain about publicly accessible data and verification instead? Well, yes. Let’s take this public key encryption and flip it around. Now, instead of keeping the data secret, we want to make sure the data is from the right person. I’m expecting a message from ZARDOZ, and want to make sure that it’s legitimately from ZARDOZ and not from STEVE SMITH.

As you can see, the message stays public the entire time, but there is extra data added based on ZARDOZ’s private key. This is called a signature. Upon receipt, anybody can verify the authorship of the message by using the public key.

What happens when STEVE SMITH tries to meddle again?

As you can see, STEVE SMITH, in his ham fisted way, has altered the message before I have received it. When I try to verify the message’s authorship, I find out that it’s not from ZARDOZ, and thus it’s a suspect message to be ignored.

This is the basis for verifying cryptocurrency transactions. We’ll put all of this book learning together into a workable model in the next article or two, but this article explains most of the theoretical underpinnings of blockchain and cryptocurrencies.