What Problem is Solved by Bitcoin Miners?

Some of the most common questions about Bitcoin mining are; What are they doing?  What problem are they trying to solve?  Can it be solved with pen and paper?  Are they wasting resources?  Are they using the computer power to hack something?

The problem being solved involves cryptography.  To put it simply, a cryptographic cipher turns one string into another string.  A simple cipher would be multiplying by 6.

1 >> 6

2>>12

3 >> 18

…

The are are problems with using “multiplying 6” as scheme.  The biggest problem is that it is pretty easy to figure out the original number by just diving by 6!  Also, the number will get larger and larger.

To get around this all kinds of complicated mathematical operations are done on very long strings of numbers.  It would take a very long explanation of the algorithm used.  Below is diagram of one step of one hash.  Those things on the right are special mathematical functions that are tedious to calculate and require a computer.

 

Modern Bitcoin miners can do this problem approximately 1 billion times a second so it might not be worth while to use pen and paper.

You can try it yourself on this website. Put in a value in the top and you will see a string come up in the bottom.  Then you have to keep changing the input by adding stuff until the answer starts with a zero.

Bitcoin is more complicated because certain information has to be included, including the hash from the last block.  That way the current block depends on all the blocks before it so it is “chained” together which is why it is called the “Blockchain.”.  The “difficulty” of the problem is changed by simply increasing the number of zeros in the start of answer (0h4fgs64j…, 00h3uyf8h…, 000yheofle… ) so it is harder to find the answer.  As more people mine, the problem becomes more difficult and the problem adjusts so it is solved every 10 minutes on average.

The Proof of Work (PoW) ideas goes back to a concept called HashCash which was meant as a deterrent to spam.   The sender must provide a solution to a cryptographic problem before the message will be accepted.

For instance, take a cryptographic hash using the SHA256 hashing algorithm of the term “message” (without quotes) and you get:

ab530a13e45914982b79f9b7e3fba994cfd1f3fb22f71cea1afbf02b460c6d1d

Now if the rules say you must have a hash that starts with a zero you can start adding stuff until you get a hash that works:

1message daad0bc80059253928621a10365de153e335a18f03b9dc7e7e25897fb791f023

2message 6532f42bd1d6ccd00f47c133c3ca1a0fc852598e67c62eb31adab8ceb3aaa680

…

51message 0985e57510d017b177867168642543ab4f143333ad63782680e812251ab3141e

After going through the numbers sequentially 51 was the first one that worked.  As long as ”51″ is sent along with the message the receiver can quickly verify it meets the requirements by performing the hash and accept the message.  The added portion, in this case”51,” is called a “nonce.”

Bitcoin mining works by compiling the transactions, the value that depends on all previous blocks, and then finding a “nonce” that meets the criteria.

The purpose of solving this problem is merely to show that work was done to get the answer.  It comes from a problem called the “Byzantine General’s problem.”  You have general who is giving orders to “attack” or “retreat” and he sends those orders to his underlings.  These underlings then relay the orders to troops.  The problem is that a small number of underlings are traitors and will relay false orders.  In order to prevent the traitors from causing catastrophic results an order is not accepted unless it is received from multiple sources.  To recreate the false message a traitor would have to do a tremendous amount of work.  The purpose of all the extra work is to prevent the traitors from sending false messages but serves no other purpose.

When the mining a block the Bitcoin mining algorithm works like this:

1. A block starts out with a header and a single transaction to pay the miner reward.  This transaction has a special name (called the “coinbase”).
2. Transactions are added to the block.
3. A block “header” of fixed length is formed by doing cryptographic hashes of the transactions (called the Merkle root).
4. Mining uses SHA256 cryptography which breaks the data up into 64 byte chunks and operates on each chunk so there are 2 chunks and 2 steps to the SHA256 algorithm in this case.
5. The first sha256 step is performed on the first chunk of the header and that does not change.  This is called the “midstate” because it is partway through the SHA256 process which is 2 steps in this case.  The “midstate” is sent to the ASIC processor,
6. The second step of SHA256 is done on the second chunk of the header.  This includes the nonce field.  This is done on the Application Specific Integrated Circuit (ASIC) chip.
7. The entire solution is run through a second round of SHA256 and the solution compared to the difficulty (that is part of the block header).  The nonce is returned if it meets the difficulty.  This is done on the ASIC chip.
8. The nonce is incremented and the last 2 steps (6 and 7) are done again 2**32 times to exhaust all possible nonce values.  This is done on the ASIC chip.
9. If no solution is found another nonce contained within the coinbase transaction is incremented.  This changes the hash of the coinbase transaction and the merkle root
10. The process goes back to step 5 and continues until a solution is found.

Because the chips do 2 rounds of SHA256 they cannot be used for other SHA256 tasks that generally only use 1 pass.  This means Bitcoin miner ASIC chips cannot be used for anything other than Bitcoin mining.