Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
@Chandan, could you give a specific example of a mathematical problem that is divine and one that is devilish? –  Joel Reyes Noche Apr 20 '13 at 3:55
4  
Why isn't your question answered by the Wikipedia page? en.wikipedia.org/wiki/Bitcoin#Bitcoin_mining –  Ryan Budney Apr 20 '13 at 6:22
4  
In case you are interested in more detail in the subject in general, there is an entire SE site (in beta) on it bitcoin.stackexchange.com –  quid Apr 20 '13 at 10:16
1  
Isn't that truly amazing ! –  Chandan Singh Dalawat Apr 20 '13 at 10:41
3  
Solving the Riemann Hypothesis will give you 1 million dollars, which you can change immediately for 8496 bitcoins and change, at the current rate :-) –  Joël Apr 20 '13 at 15:19

2 Answers 2

up vote 19 down vote accepted

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.

share|improve this answer
5  
Is it known whether there is an algorithm using a quantum computer (i.e., qubits instead of bits) for simplifying the Bitcoin mining? –  Dick Palais Apr 20 '13 at 5:19
2  
@Dick: I am absolutely not and expert in bitcoins or computing, but I recently asked myself this very question. According to what I have read on various forums devoted to bitcoins, it seems that bitcoin mining with the SHA-256 hash function is expected to be safe against quantum computer (that is, not to be simpler than with just a normal computer). Of course, proving this is out-of-reach. And moreover, the cryptographic methods used in bitcoins transaction (as well as in many other transactions, admittedly) is provably not safe against quantum-computing. –  Joël Apr 20 '13 at 15:26
    
Quantum computers are not supposed to completely break hash functions, but Grover's algorithm doubles the number of bits that you can exhaustively search through. So you could still hold a hashing competition with quantum computers, even though classical computers would no longer be viable. But, as Joël says, there is more to bitcoin than hashing and quantum computers break the rest. en.wikipedia.org/wiki/Grover%27s_algorithm –  Ben Wieland May 13 '13 at 17:15

Perhaps the misunderstanding here is one of depth. People becoming acquainted with the Bitcoin paradigm, and asking 'what mathematical problems are being solved by my computer when I lend it for mining' do not expect a mathematical answer. They simply want to understand who is setting up these 'problems' and for what purpose. As I understand it, please somebody correct me if I'm mistaken, it works like this: whereas real-world banks have physical resources at their disposal (buildings, offices, personnel, etc) to carry out their activities, Bitcoin has none, as it is an open, distributed system. And as its nature is to be purely digital, it must feature a strong cryptographic algorithm for its transactions, otherwise it would be vulnerable to hacking, and defeated. Lending a computer for 'mining' makes it an active part of the Bitcoin infrastructure; it is now processing chunks of the very complex cryptographic functions at the core of the paradigm. The lending of the resources is then rewarded by the network with Bitcoin credit.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.