Bitcoin Mining (by alaric)
A few folks lately have asked me what Bitcoin mining is all about, and how it works, and I've not seen an explanation that focusses on this at the right level, so I'm writing my own.
Bitcoin Mining for Dummies
The security of the Bitcoin network - by which I mean, the fact that you can't spend bitcoins you haven't earnt, either by creating them from nowhere or by spending other people's - relies on vast amounts of maths being performed across the globe.
So in order to encourage people to do that work - other than just doing it for the benefit of the Bitcoin economy as a whole - the precise workings of the maths and how they relate to verifying Bitcoin transactions has been chosen so that the people who do the maths have a chance of winning some free bitcoins - in effect, they are allowed to create themselves some bitcoins out of nothing, as long as they are the first to find the correct solution to a complex mathematical puzzle involving the transactions awaiting validation. The amount of bitcoins they are able to award themselves from nothing is set by the system, and will steadily decrease with time. However, people's transactions are competing to be verified by the miner (as getting your transaction verified sooner means your money gets moved sooner), so transactions can also have an optional "transaction fee" attached to them, which the winning miner gets to keep for all transactions featured in the puzzle they solve, as well as the mining bounty. In the long run, the transactions fees will be more valuable than the bounty, as it keeps decreasing.
At the time of writing (early 2013), the bounty is 25 bitcoins every puzzle (with about one puzzle up for grabs every ten minutes), and transaction fees amount to a bitcoin or so per puzzle.
This kills two birds with one stone: it also controls the initial allocation of bitcoins as the currency takes off. Making people work to get them gives them value, and provides a fair way to randomly hand them out.
More detail please. What is this maths puzzle, exactly?
At this point, you can go and read the original paper, "Bitcoin: A Peer-to-Peer Electronic Cash System", and the mining page on the Bitcoin wiki - but if that doesn't appeal to you, here's my description.
At any point in time, there's a heap of unverified transactions begging to be verified. A miner will grab as many of them as they feel like considering (generally, those with enough of a transaction fee to deem worth processing, and rejecting any that they think are invalid on the grounds of spending money from nonexistant accounts, or accounts whose balance is insufficient, or just being malformed) and form a candidate "block" from it.
At this point, they are claiming that they think this block of transactions is valid and should be recorded in the global ledger of valid transactions, known as the "blockchain". The blocks form a chain, as every block references the previous block it builds on top of; the most current block that all the computers in the network agree on is the head of a chain of blocks going back to the "genesis block" that bootstrapped the system, and provides the global consensus on what transactions are valid.
But their statement of this fact is pretty worthless on its own, as anybody who wanted to make a fraudulent transaction could just become a miner and include their transaction in a block. The block won't be accepted unless everyone in the network accepts it; when that block is broadcast from the miner, unless the other miners accept it, and it won't get into the blockchain. Also, we want to avoid the chain forking - multiple perfectly valid blocks forming that have the same parent block.
So the network consensus on what the "latest valid block" is must be defined in some way that breaks ties, and isolates corrupt miners from the network.
So the way Bitcoin works is to take the block with the longest chain of blocks behind it as the most current one, and to trust a transaction's validity more the older it is.
Because any miner could successfully broadcast the "next block", and the first one to do so is accepted, somebody who creates a bad block and broadcasts it is ignored by the honest miners - who will then create a new block based on the block BEFORE the invalid one. And so the chain will grow from that block in turn, and the bad block is left as an orphan, ignored and alone.
The only way to get a bad transaction into the system is to become the system. Have a pool of miners who accept your transaction as valid, so that you can create a block with it in, and have blocks build on top of that one, growing your own chain faster than the honest miners can. The longest block chain wins.
But that's at risk of flooding, as it's cheap to create a node. An attacker could just create a whole load of mining nodes on some cloud provider and swamp the network, creating their bad block then piling valid blocks on top of it in a rapid extension of the block chain, creating a new global consensus on a new longest chain.
So, we must make the creation of blocks expensive in some way. Also, we must limit their rate of creation to control the rate at which new bitcoins are introduced into the system, and to avoid spamming the network with block creation messages.
The way around this is to add an extra condition to a block being accepted: it must have a "proof of work" attached. This is a simple-to-test proof that the generation of the block involved a lot of work. In the case of bitcoin, the block is hashed (with SHA256) and the result of the hash function - in effect, a seemingly random 256-bit number that depends solely on the contents of the block - must be above a limit defined as the "difficulty". The miner is allowed to embed a small random string in the block, so that they can keep trying small variations upon it until they hit one whose hash exceeds the difficulty limit, which they can then broadcast (earning themselves the bounty and the transaction fees from the block).
And what difficulty must a block hash exceed to be accepted? That's a function of the real-time rate at which blocks have been generated over the last two weeks (which every node can agree on, as it depends on the timestamps in the blockchain), chosen so that one block is generated every ten minutes on average. If the number of hashes per second that miners are capable of worldwide gets higher, then blocks meeting the difficulty target will be found more frequently, so at the next difficulty adjustment the difficulty will be increased - and if mining power reduces, the opposite will happen.
So now we have block creation being a function of processing power. In order to get a bad transaction accepted, you need to be able to create blocks faster than the honest miners working together can, meaning you need more processing power available for computing SHA256 hashes of dodgy blocks until one meets the difficulty target than they do.
Numbers of nodes can be accumulated by cheating; but you can't cheat to fake having more processing power (otherwise, companies that make CPUs would have a hard time selling their products). You have to spend actual money on electronics to do more maths per second.
Mining today
Well, that's the theory. How's it working in practice?
As the value of a bitcoin has risen, and more people have been competing to mine them (thereby pushing up the difficulty), we quickly reached the stage where making your desktop PC mine blocks would not earn you enough bitcoins to pay for the electricity your computer used in the process.
This was possible because people had already migrated away from using CPUs to mine; they were using the GPUs found on high-end graphics cards to do it. With their specialised SIMD ALUs, they were able to do more SHA256 attempts per joule of electrical energy consumed. Particular GPUs were particularly good for this, so the serious miners bought PCs with lots of PCI slots and popped lots of video cards in them, creating specialist "mining rigs"; basically, SIMD integer supercomputers, built to race to be the first to find a valid block meeting the difficulty target.
However, at the same time, as the number of miners grew, each miner represented a smaller and smaller portion of the global hashing capacity. As such, their chance to win a block's bounty became smaller and smaller, even as the value of each block rose. This tended to make their income rather lumpy - a few times a year, you might win a block and earn a thousand pounds. Or you might be unlucky and not win anything for years.
And if you have the kind of hashing capacity that might win you a thousand pound block every decade, then you'd probably get nothing until you gave up trying.
In order to smooth the flow of mining rewards out, mining pools formed. In a mining pool, there is only one "miner" in the sense described above; the pool operator, who forms a candidate block of transactions. But they then distributed that candidate block to the members of the pool, who focus on the hashing: they take that block, change the random string within it, hash it, and see if it meets the difficulty target. They keep doing this until they come up with a winning block, in which case they send the random string they used to make it to the pool operator to be turned into a block and broadcast to the network, or until somebody else does and the pool operator sends out a new candidate block for the pool to mine on.
In return for this, when the pool wins a block, then its bounty (minus a small cut for the operator) is shared between the members of the pool, based on how much hashing they did. And how can the pool operator tell that, without anyone cheating? Each member of the pool can periodically send the "best" (producing the largest hash) random string they've found so far. The pool operator can use a statistical model of the expected number of hashes required to reach each difficulty level to approximate how much hashing each pool member has done per time period, and thus distribute the bounties fairly.
At the time of writing, pools of GPU miners dominate the mining community, but a new generation of hardware based on custom SHA256 processing chips (known as ASICs) is coming to market - promising a significant increase in hashes per joule compared to the GPUs. As such, it is predicted that GPU-based mining rigs will not be paying for their electricity consumption for much longer - unless the price of bitcoins continues to soar!
Cryptocurrency | alaric | 
Wed 27th Mar 2013 1:08 pm
Subscribe