[Computational Complexity] Making Money the (Computationally) Hard Way

Expand Messages
• Digital cash systems have come and gone but Bitcoin seems to be doing okay. By request I am giving a lecture about Bitcoin in my crypto class. Most of the
Message 1 of 1 , Nov 9, 2011
• 0 Attachment
Digital cash systems have come and gone but Bitcoin seems to be doing okay. By request I am giving a lecture about Bitcoin in my crypto class. Most of the material I find about Bitcoin is either very high level for a typical user or very low-level detail for the implementer. In this post I'll try to hit the middle ground.

Bitcoin tries a different approach to digital case. Their goal is not anonymity but more a cash system that works in a peer-to-peer network without a central authority.

The basics of Bitcoin come from a paper by the mysterious Satoshi Nakamoto. The Bitcoin systems doesn't use encryption but it does make strong use of secure hash functions and digital signatures. A user establishes an account by creating public and private keys for an elliptic-curve based signature scheme. A hash of the public key serves as the account number.

A transaction from person A to B roughly consists of the amount, a link to an earlier transaction where A received bitcoins, B's account number, A's public key and A's signature of all of the above. Transactions are transmitted to everyone. More general transactions are also possible.

Transactions aren't accepted until they appear in a block. A block consists of a hash-tree of transactions, an extra transaction giving 50 bitcoins to the block creator (this will decrease over time), a hash of the previous block, a time stamp and something called a nonce. The nonce is just an extra number chosen so that the hash of the block has a certain number of zeros in the right place.

You create money by creating blocks which requires finding the right nonce, a computationally difficult task. The number of zeros is set so that a new block is created on average every ten minutes. A transaction is accepted when there is a chain of six block starting with the one where the transaction occurs. This prevents double spending as that firmly establishes this chain as the "official" one.

There's a lot more details but the idea is a clever use of computation to mine money like one can mine gold with considerable effort. Or you can get money by trading goods or services (or real currency).

Not clear to me that it could scale for wide-spread use but still quite a clever and so far working system.

--
Posted By Lance Fortnow to Computational Complexity at 11/09/2011 11:51:00 AM
Your message has been successfully submitted and would be delivered to recipients shortly.