The bitcoin mining algorithm from a programmer's viewpoint

Question

This page: Blocks said mining is actually to solve a mathematical problem, but reading Block hashing algorithm doesn't give much help. I also tried reading bitcoind source code, but reading code takes much more time than reading documentation:)

And I have written a simple json-rpc client to call getwork() method to fetch the "data", but what should I do next to this "data"?

Anyone could explain the mining process in programmer's view?

Answer 1

The Mining Algorithm is as follows:

• Step 0 - Retrieve the hash of the previous block from the network.

• Step 1 - Gather a list of potential transactions known as a "block". This list of transactions comes from the peer-to-peer bitcoin network.

• Step 2 - Calculate a hash for a block of potential transactions along with a random number.
• Step 3 - If the hash is more than the currently set difficulty level, then you have mined that block. If not, start over from Step 1. Any additions to the list of transactions from step 1 along with change in the random number from Step 2 mean that there's a chance that the criterion will be met in the next go around.

From a programmer's view, the pseudo code might look something like this:

P := The hash of the previously mined block
B := A block of transactions
H := A hash function
D := Difficulty Level

0 Retreive P
1 Construct/Modify B
2 IF H(P, B, Some Random Number) > D END
3 GOTO 1

I should warn you that there are a few inaccuracies in that description, but for the most part, that should be good enough. And here are a few more useful clarifications:

What's a hash?

A hash is a function that converts data into a number within a certain range. The hash has the property that knowing it's output is essentially unpredictable (within the given range). The specific hash function used for bitcoin mining is SHA256 applied twice.

How does the difficulty level work?

This unpredictable nature of the hash function means that putting in random data (the transaction + the random number) will essentially produce a random number within a certain range. Further restricting the range of the desired output affects how likely one is to find it in a single round. This creates a way to probabilistically determine how often a solution will be found based on the number of times the algorithm can be run on the network. Specifically, when you hear the term "gigahashes" or "terahashes", this refers to the number of times Step 3 can be run. As the number of hashes per second across the entire network grows, the network automatically raises the difficulty such that a solution will be found within about 10 minutes.

What happens when a block is mined?

When a block is mined, the miner sends the block to all other miners on the network as evidence that it has found it. This block contains a list of transactions, the found hash, the specific random number, and a reference to the previous hash. As each miner receives the newly mined block, it removes all transactions that it is currently mining that exist within the block (because they've already been confirmed in the block chain) and broadcasts the block to other miners that do the same thing. The propagation happens pretty quickly.

Note: the original miner of the block gets a "miners' fee", which is a reward consisting of any unspent coins from transactions in addition to a "coinbase" reward. The coinbase reward started out at 50 bitcoins and halves after every 210,000 blocks (about once every 4 years). The coinbase reward will eventually get so small that it will be miniscule compared to miners's fees.

Answer 2

The purpose of solving a 'puzzle' is to (a) delay the mining of the block to avg 10 minutes and (b) to incur real-world costs for mining a block (spending cpu power, thus energy). The costs are there to prevent a Sybil attack (putting many miner machines at work to do a 51% attack).

The delay is put in to allow a good block to propagate around the globe to all other miners, without giving the miner who just minted the new block a headstart advantage. For that, the blocktime (10 minutes) needs to be order of magnitudes larger then the propagation delay (a few seconds).

So the kind of puzzle is in a sense irrelevant, it could as well be a giant Sudoku.

Answer 3

Any hash is a valid hash. The question is if you're hash meets our criteria. What you hash is actually a couple of things (we'll come back to this) that lined up together make a string that is a string of a specific length. You then hash that entire string. Think of your resulting hash as a number. What we want is that resulting number to be less than a target number. So it's like rolling a billion sided die, and coming up with a number under the target number. That target number is considered "difficulty". As more people are rolling the die, we lower what that target number is to reduce the likelihood any one die-roll will hit.

So importantly, some of those things that we line up in the string that we hash are things that we're allowed to adjust. Hashing isn't exactly like rolling the die because if we has the same thing over and over we get the same result over and over. However even a minor adjustment in what we hash can have a major impact on what the resulting hash is. The primary item that we can manipulate is called the "nonce". Basically we pick a nonce to use in the string, hash the whole string, and see what we get. If the hash isn't a hit, we modify the nonce and try again. The nonce itself isn't very large so there's a limited number of variations of the nonce that you can try. The next item we can change is a timestamp. We're allowed to wiggle the timestamp too. Every wiggle of the timestamp allows us through the entire set of possible nonce values all over again. We repeat this process of exhausting the nonce possibilities, then wiggling the timestamp over and over until the resulting hash is lower than the difficulty target number.

When that happens, we then proclaim to the world that this timestamp plus this nonce works to solve the block. Others validate it to be true and it's added to the block chain. A block is considered "Validated" once it's a certain number of blocks "deep" in the block chain, meaning it's a historical block compared to the current block. Validation is a little bit of a misnomer here because it's not that the block isn't already known to be valid. What we're validating is the proof of work, meaning once that historical block is buried far enough the amount of effort involved to create that history is insurmountable for someone else to try to create a different variation of the history. They would have to create their own version of that block (the only reason being to write in their own version of the transactions, i.e. steal coins) then solve it themselves, then solve the next block and the one after and so on and "catch up" with everybody else. This means they would have to out-race the world in the dice rolling game. Maybe once in the history of the universe someone might get lucky on the nonce with two or three blocks back to back, but with the 120 blocks that most mining pools and exchanges require now? Not going to happen, ever.