Proof of Work, Explained (Part 2 – A Hash Bash for Techies)

Overview

In the last article, we looked at the overall idea of proof of work and its applications. That article covered the origins of this concept, how it works at a high level, and some of its applications. Now, let’s take a look at the technical inner workings of these algorithms.

In a nutshell, proof of work involves the use of hash functions. These one way functions form the basis for a difficult to solve, but easily verifiable computational puzzle as a way to prove that one did some amount of desired computing work.

Proof of Work, the Technical Perspective

Hash Functions

First, we need to understand a bit about hash functions and why they form the basis for proof of work. A hash function is a one-way function that takes some input of any size and outputs a consistently sized set of bits. The two most important characteristics of hash functions are that they:

  • Are one-way – you cannot take an output and find the input without brute force guessing
  • Have unique outputs for every possible input (if the hash function is a good one!)

These two properties are critical for proof of work. First, the one-way nature of these makes it so that brute-force is required to find some desired output. Second, the desired one-to-one input/output property makes it so we can easily verify the solution once we have one.

An Overview of the Algorithm

Hashing and Binary and Difficulty Targets, Oh My!

Proof of work builds on top of the properties of hash functions by realizing that as a stream of bits, hash outputs actually represent binary numbers. For example, an 8 bit hash 00001000 represents the decimal number “8”. Now remember that hash outputs can only be matched to a particular input by using brute force to guess.

Using these properties, proof of work takes a pretty ingenious approach to making a user do some amount of predetermined work – it makes them look for a hash that, interpreted as a number, is less than some target value!

This is where the idea of difficulty comes in. Let’s say you want the user to find some input where the hash value, when representing an 8 bit number, has two zeros in the front (00101010, for example). Now imagine you want the user to find an input that gives a hash with four zeros in front (00001011). Which one takes more guesses to compute? It turns out that the smaller the “difficulty target” value, the more guesses (and more computing time) it takes to find an input that gives the desired hash output. This is the fundamental basis for proof of work. It can be statistically predicted that a certain difficulty target will take roughly some amount of guesses (and therefore computing time) to find. So the smaller the difficulty target, the harder the puzzle.

The nonce value

Now since hash outputs map one-to-one with some input, how can we prevent the worker from just using a dictionary to find an input that meets the difficulty? Here is what makes proof of work truly proof – we always create a hash input unique to the problem we’re trying to solve, using an applicable message and a random guess we call a nonce.

See, for our proof of work to truly require the desired amount of work, we always start with a unique message for the problem. In the case of Bitcoin, our message is what is called the “block header” – a chunk of data containing information about the transactions included in the current block. In an anti-spam application, this message would be something like a forum post or the contents of an email message. Since this message is unique, a dictionary cannot be used to guess a hash that meets the difficulty target.

The worker then has to take the message plus a random number guess called the nonce, and run that combined string through the hashing function. If the hash output isn’t less than the target number, then the worker increments that random number guess concatenated to the message and tries again – and again and again until the right output is found.

Verifying the nonce

Once a nonce is found, another node or server can very easily verify that the solution (the nonce) is correct. All the verifying party has to do is take the original message plus the nonce value found by the worker and run that through the hash function. Since a hash input will always give the same output, it only takes one step to verify that the worker’s nonce is in fact a correct solution to the proof of work problem.

A Practical Example

Let’s take a look at an example anti-spam proof of work problem. Let’s say a user wants to contact a site owner with the message “Hello”, and the site owner wants the user to do some proof of work before sending that email. The site owner specifies a difficulty target of 2^240. This difficulty target can be any 8 bit number in this case, but a power of two is easy to work when building an application. This system uses the compute-intensive SHA-256 hashing algorithm for its proof of work. Here’s what the steps would look like:

Worker (Client)

  1. Uses “Hello” as the message
  2. Starts guessing a nonce with 0 – the hash input is the string “Hello0”
  3. The SHA-256 output of “Hello0” (in hexadecimal format) is 80878c5b013ba72c0d2b7e8f65868649cbdb1e7e7a8c8a07537d6b3619e4e32f
  4. Clearly, this output is greater than the difficulty target of 2^240, which would have three prepending 0’s in hexadecimal: 0001000000000000000000000000000000000000000000000000000000000000
  5. Increment nonce to 1, and try again. This continues until an appropriate nonce is found
  6. The client finally finds a nonce that works with the value 9172. The SHA-256 hash of “Hello9172” is 00001f2e9f8f74117b4178eb04b368c807f906ae2a07bece562266cbc9adff3c, which is less than the difficulty target of 0001000000000000000000000000000000000000000000000000000000000000 (2^240)
  7. Since the client has a nonce guess that meets the difficulty target for this unique message, it now has proof that it did all that computing work!

Verifying Party (Server)

  1. Take the message for this problem, “Hello”, plus the client’s found nonce, “9172” and pass “Hello9172” through the SHA-256 hash function
  2. Since hash functions produce the same output for any input, we get the same output the client found: 00001f2e9f8f74117b4178eb04b368c807f906ae2a07bece562266cbc9adff3c.
  3. Since the above output is indeed less than the difficulty target 2^240, the server has now verified that the client did the desired amount of computing work to find the nonce. The message can now be sent.

Proof of Work – Hashing for a Cause

These algorithms put the properties of hashing algorithms to new and innovative uses, particularly in the incredible space of cryptocurrencies. Proof of work takes the one-to-one input/output and irreversible properties of hash functions and uses them to create difficult to solve, easy to verify computing problems. This simple but interesting bit of math and computer science powers new approaches to interesting challenges. Proof of work can be used to help prevent spam in a new and unique way – by making large-volume spam uneconomical for its propagators. Arguably at its most revolutionary, proof of work powers the transaction verification and currency issuance components of cryptocurrencies like Bitcoin and Litecoin, allowing for an entirely new form of money free from centralized institutions.

Proof of Work, Explained (Part 1 – POW for Non-Techies)

Overview

Personally, I’m fascinated by both the technical and financial implications of cryptocurrencies like Bitcoin, Bitcoin Cash, and Litecoin (to name a few). The way these currencies work is a complex topic, with lots of moving parts to discuss. One of the core components of cryptocurrencies like Bitcoin is the mechanism by which an entirely decentralized system of money can securely verify transactions as well as issue new currency, all while preventing fraud and issuing at a predictable rate.

Most of these currencies solve this problem using a concept called “proof of work” by which nodes solve a computationally difficult but easily verifiable mathematical problem. This concept goes beyond cryptocurrencies as well, and actually originated as an anti-spam measure.

Proof of Work – The 10,000 foot view

What is Proof of Work?

Proof of work, fundamentally, is the solving of a computationally intensive mathematical problem. This problem has two very important properties – the solution to the problem is both:

  • Difficult (computationally intensive) to find
  • Easy to verify once found

The idea is this: for an application like cryptocurrency or anti-spam, a “node” or computer is challenged to find a solution to this puzzle. The solution can only be found by brute-force guessing. However, once the solution is found, all the other nodes on a network or a server can verify the solution in one step. Since the answer can only be found by brute-force computation but can easily be verified as correct, the solution to the problem serves as proof that a certain amount of computing work was done – hence the term “proof of work”.

Why is it Useful?

First, let’s look at the original application of proof of work: anti-spam. The original idea was implemented in a system called HashCash, invented by Adam Back. Back’s system works like so: Before performing an action like posting to a forum or sending an email, the user of a site is made to do a small proof of work problem. This problem only takes half a second or so of computing to solve, and of course is almost instantaneous for the system to verify. For a legitimate user of a forum or email system, the half second of computing is no obstacle to completing his or her task. However, for a spammer trying to send hundreds of thousands of spam messages, the task suddenly becomes very uneconomical since it would tie up their computer for minutes or even hours at a time!

Now how does this system apply to cryptocurrencies like Bitcoin? In this system, transaction verification and currency issuance is totally decentralized – no third party is trusted to create new value tokens or verify that transactions are legitimate. This of course presents a massive fraud-prevention challenge – how can the network ensure that malicious parties don’t create “counterfeit” currency or send through transactions that aren’t valid?

Proof of work helps to solve this problem. On the Bitcoin network, new transactions are broadcast to computers running what is called “mining” software and accumulated into “blocks” of transactions that will be validated at one time. Every time a new block is waiting to be verified, all the nodes on the network running this software essentially “race” to solve a proof of work problem first. The Bitcoin network adjusts the difficulty of this problem so that about once every ten minutes, one miner wins the race and finds a solution to this problem. Once one node finds the answer, it tells all the other nodes on the network that it’s found an answer, and the other nodes can instantly verify that the answer is correct.

The node that finds proof of work for this block is rewarded with brand new Bitcoin (issued at a predictable rate) as well as all the transaction fees in that block. This computationally expensive proof of work problem creates an excellent system of economic incentives- the reward of new Bitcoin drives miners to to verify transactions are correct, and also make fraud more expensive than legitimate mining. If a miner were to try and cheat, all the other nodes running the legitimate software would instantly reject the new block since it doesn’t meet the rules of the network, and all of the time and computing power of the malicious node would thus be wasted.

Proof of Work – Powering Cryptocurrency and Thwarting Spammers

The idea of proof of work has incredible value for multiple applications. This system allows computing to be used as a precious resource in a purely digital economy; a way to both secure monetary transactions and prevent the waste of resources like time and storage space. In an anti-spam setting, proof of work allows the operators of a curated space to reduce the impact of spam on their systems, reducing wasted time, clutter, and storage space. In a cryptocurrency application, proof of work allows the secure verification of transactions and the issuance of new currency without the need for a trusted third party, the often fatal flaw in fiat systems.

The applications of this technology are incredibly interesting. In the case of cryptocurrencies, I would say its application is part of a system that is revolutionary. Now, as a software engineer, I find the actual technical workings of proof of work to be even more interesting than the surface description. In the next article, I’ll walk through how these algorithms work from a more technical perspective.

Bitcoin as “Digital Gold” is Bad for Crypto Adoption

“Digital Gold” vs. “Digital Cash”

The core Bitcoin network has a scaling problem, and has had this problem for a while now. As more and more transactions try to fit in Bitcoin’s 1MB blocks (once every 10 minutes), network fees have skyrocketed to $5-10 dollars, and that’s even a little low if you want your transaction confirmed within an hour or so.

One response to this problem, especially from supporters of the Bitcoin Core roadmap, is to ignore the problem to some extent. As Bitcoin has seen more attention over the last few years, the price has risen dramatically. As a result, many are now claiming that Bitcoin is not meant to be a “means of exchange” or a form of “digital cash” for day to day transactions. Rather, their viewpoint is that Bitcoin should be seen as a “store of value” or “digital gold”.

To be clear about my biases in this space – I think cryptocurrencies are at their most interesting and valuable as a means of exchange; a way to do truly global, peer-to-peer, decentralized cash. I do not care at all for the risky speculative investing that goes on in the crypto space; I believe these currencies should be used or held in small amounts, allowing one to learn more about this fascinating technology and spread adoption.

With that said, I don’t have a problem with a digital currency being used as a long term store of value like a “digital gold”. There is plenty of room in the crypto space for currencies that solve different problems in different ways. I do, however, think there is a big problem with Bitcoin being the currency of choice for that use case.

The Bitcoin Brand, and the problem with Bitcoin as “Digital Gold”

Let’s be honest, fellow crypto nerds. How many people in your daily life have actually heard of Bitcoin? And how many of them actually understand it, at least at a high level? How many people actually own some and use it? If you’ve got the same variety of people in your life as I do, the percentage isn’t that high.

Now how many of that small subset of Bitcoin-aware people in your life know about Bitcoin Cash? Ethereum? Litecoin, Vertcoin, Monero, Dash? It’s an even smaller percentage, surely. Even if they’ve heard of them, do they understand how these alternatives to Bitcoin solve different problems? We’re down to a sliver of people that understand and adopt these different currencies beyond Bitcoin.

Herein lies the crux of the problem:

Bitcoin is the defacto cryptocurrency. It is the face of digital money, the storefront, the brand, however you want to refer to it.

Whether anyone likes it or not, Bitcoin is what most people hear about first when they hear about cryptocurrencies. And with a now large chunk of the Bitcoin community marketing this as “digital gold”, we have the potential to miss out on opportunities for widespread adoption in the coming years.

More and more businesses are going to become interested in adopting cryptocurrencies as a form of payment, they’re going to want to start with Bitcoin. It is the biggest after all, and the original value proposition we still see on bitcoin.org is “fast peer-to-peer transactions” and “low processing fees”. The reality is far from that, however. When the coffee shop owner realizes his or her customer will have to pay $10 to buy a $3 coffee, they’re not going to find Bitcoin usable for their business. How many of the already small percentages of crypto-curious entrepeneurs are going to take the time to understand Bitcoin Cash, Litecoin, or Dash? Many will probably say: screw this and return to business as usual with fiat.

Satoshi’s “Peer-to-peer electronic cash” – How Does Bitcoin Continue That Vision?

The problem is not a cryptocurrency as “digital gold”, the problem is Bitcoin as “digital gold”. The original promise of Bitcoin was indeed a global, peer-to-peer, low fee alternative to centralized payment processors like Visa, Mastercard, or PayPal. But as the Bitcoin community shifts away from that vision, they take the adoption of that vision with them.

With a functional implementation of the lighting network at least two years away, and the lack of press for already-scaled alternatives like Bitcoin Cash, Litecoin, etc., it concerns me that adoption of cryptocurrencies will stall. I don’t at all fear that they will go away or stop the ceaseless flow of innovation that we’ve seen since the advent of Satoshi’s brilliant whitepaper. But I do worry that Bitcoin’s current scaling problems and the community’s attitude toward it will lead to several years of stalled adoption in the mainstream. I do hope, however, the problem gets fixed soon and that I am wrong.