Which hard mathematical problems do you have to solve to earn bitcoins ?

Question

A virtual currency called bitcoins has been in the news recently. It is said that in order to "mine" bitcoins, you have to solve hard mathematical problems.

Now, there are two kinds of mathematical problems. The difference is best explained by the following beautiful quotation from Langlands :

[T]here is an appealing fable that I learned from the mathematician Harish-Chandra, and that he claimed to have heard from the French mathematician Claude Chevalley. When God created the world, and therefore mathematics, he called upon the Devil for help. He instructed the Devil that there were certain principles, presumably simple, by which the Devil must abide in carrying out his task but that apart from them, he had free rein. Both Chevalley and Harish-Chandra were, I believe, persuaded that their vocation as mathematicians was to reveal those principles that God had declared inviolable, at least those of mathematics for they were the source of its beauty and its truths. They certainly strived to achieve this. If I had the courage to broach in this paper genuine aesthetic questions, I would try to address the implications of their standpoint. It is implicit in their conviction that the Devil, being both mischievous and extremely clever, was able, in spite of the constraining principles, to create a very great deal that was meant only to obscure God’s truths, but that was frequently taken for the truths themselves. Certainly the work of Harish-Chandra, whom I knew well, was informed almost to the end by the effort to seize divine truths.

Question Which kind of mathematical problems do you have to solve in order to mine bitcoins ?

Let me clarify that I'm not interested in mining, only in knowing whether the problems are divine or devilish.

Answer 1

Bitcoin mining is based on hash functions. Specifically the SHA-256 hash function, which maps arbitrary bit strings to 256-bit outputs in such a way that nobody knows how to find a collision (two inputs with the same output), although the pigeonhole principle implies collisions exist. Bitcoin mining doesn't involve finding collisions, which would be way too hard. Instead, one has to find inputs that lead to outputs with special properties, namely a lot of consecutive zeros. This is a scaled-down version of inverting the hash function. Of course there's no proof that any of this is actually computationally difficult, and some earlier hash functions have turned out to be weaker than expected (for example, MD5 and SHA-1), but it certainly seems to be.

SHA-256 is not a nice or simple function - it was designed to be hard to analyze - so I'd say this is a devilish problem.

Answer 2

Another way to earn bitcoin is not to mine them, but to have them wired to you from other bitcoin accounts. The transactions are signed using ECDSA. So if you solve the discrete logarithm problem in an elliptic curve (for bitcoin this is the curve Secp256k1), then you potentially can earn many bitcoins (illegally of course...)

Personally I find this problem much more beautiful than finding lot of zeroes in the SHA-256 hash function.

Answer 3

The problem that have to be solved is called Proof of work which is basically a brute force.

So you need to know what hash functions are to understand the problem, don't worry its easy and anyone can understand it because solving this puzzle doesn't require intelligence but patience.

A hash function is just a function that when you give it an input of X byte size (data, image, text, anything ...) it produces a fixed length of bytes, for example you give it 5gb video it will produce a string that is 256 byte long(the output size can change from function to function).

Hash functions have some properties and one of them is when you give it different input it always produces a completely different output, so if change only one bit in that 5gb video the output of the hash function is going to change radically. same rule applies when concatenating the video with some random bits.

So in bitcoin, miners keeps listening for transactions and from these transaction they create a block but in order for all participating nodes to accept this block they have to change a specified region in the block and see if the resulting output starts with x number of zero's (because in computers everything is ones and zeroes).

If the result is not correct(output string does not start with 30 zeroes) they change that region again and check the output, until they finally find the right combination of bits in that region that when you pass that block to the hash function it will produce a string that starts with 30 zeroes.

To explain more i will give you a real example:

1. miner listens for incoming transaction

2. I create a block that contains all these transaction

3. inside the block there is specified region that is 32 bit long that is independent from the transaction (for the sake of simplicity lets say all bits in this region is set to 0)

4. miner hash that block and check the output, if it is a string that starts with 30 zeroes it quickly broadcast it to the network and say i win I found the solution to the puzzle it is a block with these transaction that i selected and that contains this region, you can check it yourself

5. if the result is not a string that starts with 30 zeroes, the miner changes that region increments it for example (00000.....001) and hashes the block one more time and check if the output starts with 30 zeroes , this step is repeated until the miner can finally find a correct combination of ones and zeroes in that block region so that when he hashes that block with the hash function it will produce a string that starts with 30 zeroes (notice this number changes).

and he has to do this fast because there are lots of miners and the first one to find the block is gonna win. so you can see that the term puzzle is quite (juuust a little bit) misleading. if you have any question i'm at your service.