Tuesday, March 04, 2014

Game theory: cheating at bitcoin mining

My mining rig: 10-gigahash/sec, 0.001 BTC/day
I think I’ve come up with a way to cheat a little at Bitcoin mining.

Bitcoin “mining” is the process in which new transactions are officially entered into the running ledger. Every 10 minutes, the current outstanding transactions are combined together in a “block”, then a "miner" calculates the SHA256 hash for the block.

The wrinkle here is that Bitcoin is decentralized, so no one person is responsible for calculating the hash. Miners must compete to create a hash. Therefore, the hash must have certain properties, namely, the first 64 bits of the hash must be zero (the current difficulty level is 63.8 bits, it changes over time to accommodate more mining power). A little bit of random data is added to the block before hashing, and the miner keeps changing that random data until the resulting hash has the proper number of leading zeros. Currently, that requires 18 quintillion calculations, or 18 billion billion, or 18,446,744,073,709,551,616 – or in technical terms, a boatload.


The first miner to find the lucky hash wins the lottery and gets the 25 bitcoin (roughly $10,000 at current exchange rates), plus transactions fees, associated with the block. After this point, everyone starts working on the next block.

Because of the lottery system, it’s unlikely that any one person will win. For example, I have a little mining rig that does 10-billion (233) hashes-per-second. This gives me a roughly one in 8-million chance of winning this bitcoin lottery every 10 minutes. Calculated another way, it’ll take me roughly 160 years before I ever win – assuming everything stays the same.

Instead of trying to win the mining lottery alone, I can instead pool my resources with others. With thousands of other people with small rigs like mine, our pool can win one of the lotteries every day, and then split the bitcoins among all the participants. Instead of taking 160 years to win the lottery of 25 bitcoins, I can win 0.001 bitcoins per day.


The natural question with Bitcoin pools is “how can I cheat?”. As it turns out, cheating is really hard.

One way of cheating might be to lie about how much work I do, pretending to calculate hashes without actually doing the work.

To counter that, pools have their own “difficulty levels”. For example, a pool might require that whenever I find a hash with 33 leading zeroes, that I submit the result back to the pool. Remember: it takes me billions of hashes to find such a result, but takes them only a single hash to verify that it’s correct. My little mining rig would generate such a hash every second, thus proving that it’s busy working as hard as it can doing real work, rather than cheating. Thus, the technique wouldn't work.

Another way of cheating might be that if my machine is the one in the pool that wins the lottery of 25 bitcoin, that instead of distributing the winnings to everyone else in the pool, that I keep the winnings for myself.

This doesn’t actually work. The final transaction in any block is the Bitcoin address that receives the 25 bitcoins, which is the pool’s address, not my own. If I were to find the lucky hash, I couldn’t then go back and change the Bitcoin address that receives the payout -- because that would then change the hash.

Thus, pools work, without anybody being able to cheat – in theory.

In practice, there are other things you can cheat. The operators of one pool might try to DDoS the URLs of other pools. This would prevent those pools from sending out work to their members, lowering their hash rate, and making it more likely that non-DDoSed pools would win the lottery. People do this, and this has lead to arms races among pools. They are under frequent DDoS attacks, and are frequently having to upgrade their server infrastructure to cope with the attacks. Overall, it’s been a nuisance and hasn’t dramatically enabled anybody to significantly win at the mining game.



I propose a different way of cheating.

Let’s assume that I’ve got a pool that has roughly 1% of the compute power of all pools. This means it’ll win one (sometimes two) lotteries per day.

What I do is this: I offer to pay members of other pools for their winning hashes. If your miner finds the lucky hash, and you send it to me instead of your own pool, I’ll pay you for it.

This would require you running a hacked version of mining software. For example, I might alter the open-source “cgminer” program so that when it finds a winning combination, it sends it to me instead of its pool.

I would pay in one of two terms. If I win that block, then out of my 25 bitcoin winnings I’ll pay you 10 bitcoin (possibly shared, in case multiple people send me a winning number). Or, if you prefer, instead of that, I’ll pay you 0.01 bitcoin, whether or not I win the round, and whether or not other people send winning entries.

This winning block is useless to me, of course, since the embedded winning address doesn’t belong to me. Instead, what I’m doing is a sort of denial-of-service. By denying your pool of the winning number, I increase my own chances of winning.

Paying 10 bitcoin for you to discard a winning number seems like a lot to pay, but as far as I’m concerned, I could pay the full 25 bitcoin (keeping only the roughly 0.1 bitcoin in transaction fees associated with the block). Because you had the winning number otherwise, I would’ve won 0 from the current block. If your discard of a winning number gives me the win, then everything I win is pure profit.

Since you, a small miner, would only win 0.0001 bitcoin from a winning block, anything I offer you greater than that is a win for you. If you get a winning number, a 1% chance of 10 bitcoin is still a thousand times greater than 0.0001 bitcoin from submitting the block to your pool.

Because my pool wins more lotteries, the amount I pay out to members of my pool increases. That means more miners will sign up for my pool. This in turn means the worth of my payout increases. If 30% of miners sign up for my pool, that means you have a 30% chance of winning 10 bitcoin by giving me the winning number instead of using it yourself.

But, on the other hand, if my pool pays out more, wouldn’t you rather just switch pools? In other words, the technique only works if cheaters are working for other pools, but if they all sign up my pool, then that leaves fewer cheaters out there working for me, lowering the added profit my pool makes.

Thus, while I can get an edge over other pools, there seems to be a limit to that edge. If I knew more game theory and math, I could probably calculate exactly how much this would be.

An even worse problem is this: other pools might adopt the same cheating strategy. Imagine there now exists two cheating pools, the members of which use the cheating software from the other pool. Whenever the a member of the first pool gets a winning number, it sends it to the other pool, and vice versa. That means neither pool ever wins.

This creates a case similar to the prisoner’s dilemma. If you are small miner, and somebody offers you the cheating version of “cgminer”, it’s in your best interest to do so – but if too many people start doing that, it destroys the system for all small miners. The only people who would then be able to mine are the big miners, those who have made a massive investment in mining equipment who can win the full lottery on their own about once a week.

Sadly, my knowledge of game theory and mathematics is lacking. It would be fun to try to figure this out, starting with assumptions about what percentage of miners would be willing to cheat, and assuming pure self interest, how the whole thing would play out.

Conclusion

This is probably a known cheating method, already discussed by bitcoin enthusiasts. However, since I've never heard of it, I thought I'd write it down on the off chance it's novel.

5 comments:

lucia said...

Not to go off on a tangent... But since you understand this bitcoin stuff, I wanted to ask questions related to news about stolen bit coins. The question(s) (is)are:

Can the thief who stole bitcoins sell them? Or are they too identifiable to do him any good and so, for all practical purposes destroyed?

Note they are really sort of the same question.

Steven Roose said...

A hacker that has stolen bitcoins from you can sell them without a problem. If you are talking about very large amounts (like 10-100kBTC), though, it's a lot harder. But still, it's possible. There exist services called Bitcoin Mixers or Launderers that can anonymize your bitcoins.
PS: Next time you have a question, consider asking it here: http://bitcoin.stackexchange.com

Robert Graham said...

Yea, the hacker can "sell" them.

Bitcoins aren't really anonymous, so if the hacker exchanged them directly for cash, it's possible they might be tracked down. The hacker would probably launder the bitcoins first.

Bwanshoom said...

Just curious - what is pictured in the image? What are those cards?

lucia said...

Steve Roose,
I trust Robert to give answers in language I will understand. People at stackexchange sometimes do, but other times... not so much.