Monday, June 16, 2014

I wonder if there is a sort of chaos theory at work in the Cryptographic world.
I'm not an expert, but as I understand the idea of Chaos theory is not that things don't work by rules,
but that the rules are so complex, with so many things influencing one another, that even given that you know how things look now, you cannot predict what things will look like 2 seconds in the future.
The analogy is, that maybe when designing a Cryptographic system, you cannot predict in the real world what phenomenon would arise in response to try to break it.
This would be imply, in a sense, that Cryptography inherently must be an experimental science, not just a mathematical one.

One recent example, is the emergence of huge mining pools in the bitcoin network,
a phenomenon that was not predicted in the original seminal paper.

A short explanation:
A central part of how bitcoin works is that participants in the network get
rewarded in new bitcoins for documenting the transactions.
So for example, if Alice gave 2 bitcoins to Bob,
I could get rewarded by documenting this transaction and broadcasting the message
s=`Alice gave 2 bitcoins to Bob' to the network.
..but it's not that easy. I have to do some more work for other nodes to accept this documentation
of the message s, and give me the reward.
This involves a function called SHA-2.
What is special about  SHA-2, is that although everybody has its code,
and can see how it works, it produces an output that looks completely unpredictable.
For example, I could give it the message s above, and it would return to me a crazy sequence of numbers:
6437871234876703270067821647060..
(I didn't actually apply SHA-2, just randomly wrote these numbers as an illustration)
To accept my documentation of the message s, and give me bitcoins as a reward,
the nodes in the network demand the following:
add to s, another message - called Nonce which is short for `number used only once' -
such that when we give SHA-2 s and Nonce together, it will give us a sequence of numbers with many zeros in the beginning, say 30 zeros.

So what the computers on the network, called miners, do is try many different messages Nonce, such that SHA-2(s,Nonce)
is a sequence starting with 30 zeros.

It turns out that requiring all these zeros can be used to prove bitcoin is safe to use, unless 51% of miners work together to find the right Nonce.
It seemed initially like a safe assumption that 51% of the miners, who are distributed around the world and not part of any organization, would not start to work together..
but then mining pools emerged.
They work like this. They tell you
`Look, you can either mine by yourself, and wait 5 years until you find a Nonce that gives 30 zeros and get bitcoins in reward.. or you can give your computation power to me, and I promise you, that
even if you find a Nonce that gives 5 zeros, but someone else in my pool found the Nonce that gives 30 zeros, I'll give you part of his reward. So this way, you'll get small rewards, but you'll see some revenue pretty quickly'.

and indeed, recently the mining pool GHASH obtained 51% of the mining power.



No comments:

Blog Archive

About Me

My photo

Hi! I am a computer science postdoc. For some reason google is not finding my new homepage so I added a link from this profile