Absolutely love this quote from the article: "Money is like gas in the car – you need to pay attention or you’ll end up on the side of the road – but a well-lived life is not a tour of gas stations!" - Tim O'Reilly

Great article. There is a lot in the bitcoin protocol that is possible that the vast majority of people have never heard of, some of which this article touches on.

For an idea of some of what could be done, see the Contracts section on the bitcoin wiki:

https://en.bitcoin.it/wiki/Contracts

In the near future, we may start to see things like multi signature transactions* and the like. In theory, it could open up some very interesting options.

*Technically, I believe there exist a few of these transactions already on the blockchain.

From the article: "I don’t understand why double spending can’t be prevented in a simpler manner using two-phase commit. What drawbacks and advantages does it have compared to the full Bitcoin protocol? uppose Alice tries to double spend an infocoin with both Bob and Charlie. The idea is that Bob and Charlie would each broadcast their respective messages to the Infocoin network, along with a request: “Should I accept this?” They’d then wait some period – perhaps ten minutes – to hear any naysayers who could prove that Alice was trying to double spend. If no such nays are heard (and provided there are no signs of attempts to disrupt the network), they’d then accept the transaction."

The problem with 2PC is that a malicious node could stop somebody from being able to spend their coins by always sending nays out to the network when ever the victim sent a transaction. To prevent this, you would need to be able to detect when a node is faulty/malicious which would require implementing a costly Byzantine Consensus Protocol [1]. In practical systems that can withstand Byzantine faults, the number of messages required to agree on a log entry (e.g. a transaction) would be O(n^2) in the number of nodes in the network, which would greatly limit scalability.

The genius of Bitcoin's Proof of Work protocol is that:

1) it is more resilient than Byzantine agreement. Byzantine agreement with 3f+1 nodes can handle at most f faulty nodes, while Bitcoin can tolerate 49% of the network hashing power being malicious. (though this is being debated currently due to theoretical strategies like selfish-mining)

2) it is much more efficient than Byzantine agreement in the number of messages sent, which has allowed the network to scale to thousands of nodes, although they have been running into issues with the blocksize/block limit, but their are currently research efforts [4] underway to remedy this.

The main problem with Bitcoin's proof of work scheme it is that it is extremely expensive in terms of CPU cycles, but this is solved by compensating miners for their efforts through coin generation and transaction fees.

[1] - http://www.cs.cornell.edu/courses/cs614/2004sp/papers/lsp82.... [2] - http://pmg.csail.mit.edu/papers/osdi99.pdf [3] - http://arxiv.org/pdf/1311.0243v5.pdf [4] - http://www.cs.huji.ac.il/~avivz/pubs/13/btc_scalability_full...

The smallest of nits to pick, but Readability has issues with the "images as text" behavior of the variables and numbers in the crypto parts of the post.

Otherwise, I'm very sorry that I didn't find this until after Thanksgiving. As many of you are likely similarly tagged, I'm the "computer" guy in the family, and so whenever something happens in the news that's got anything to do with computers, I'm the guy people bug for answers.

Bitcoin was the topic de jour this Thanksgiving, and my explanations would have benefitted greatly from this plain-English run-through.

Fortunately, after having read this, I now will be able to give people the deluxe explanation, should they make the fatal mistake of asking. :) Thanks.

Amazing post. I thought I had a pretty good understanding of Bitcoin, yet this is the first time I've even heard of an associated scripting language. I can't wait for the post detailing that. Here's the wiki article for now: https://en.bitcoin.it/wiki/Script

  OP_2DUP OP_EQUAL OP_NOT OP_VERIFY OP_SHA1 OP_SWAP OP_SHA1 OP_EQUAL

Here's two dumb questions you might want to answer in a follow-up (and I encourage you to write more articles).

1. If it's a principle that "everybody" has a copy of the block chain, and the block chain records every transaction ever, isn't that going to be a storage problem? How big is one person's copy of the block chain now, and how many petabytes might it grow to be in a few years?

2. The way to spend a fractional coin is to have one input and two outputs, one back to yourself with the unspent change. But doesn't one's wallet begin to be cluttered with lots and lots of little fractional items? Like having a pocketful of small coins... So is there an automated way to every so often, do a many-small-input, one-big-output payment to yourself to consolidate the change?

In answer to the question:

"Suppose Bitcoin mining software always explored nonces starting with x = 0, then x = 1, x = 2,\ldots. If this is done by all (or even just a substantial fraction) of Bitcoin miners then it creates a vulnerability."

The reward for mining the block includes the miner's account, so each miner is hashing a unique block.

This explanation is pure genius. Instead of explaining something very complicated, explain how to arrive at the complicated solution by evolving the simple solution and eliminating its flaws. Wish more explanations were like this. Someone do git.

> Of course, any still-pending transactions in A will still be pending in the queues of the miners working on fork B, and so all transactions will eventually be validated.

I don't understand this. So you have fork A and fork B, and once fork B wins, what happens to the transactions being done on fork A? Discarded? Do transactions sometimes not ever get verified?

From what I've quoted, I'm guessing no, transactions in fork A somehow get verified by work being done in fork B. How? Do these transactions exist in both forks?

Also, in general, how do p2p networks facilitate the finding of nodes? The links provided [0] describes how a node figures out what to tell other nodes about itself [0], and how to talk to other nodes once they've been discovered [1], but how does a node actually find other nodes, to begin with? Best I can tell it's just a text file with a bunch of "starter" nodes.

    [0] - https://en.bitcoin.it/wiki/Satoshi_Client_Node_Discovery
    [1] - https://en.bitcoin.it/wiki/Network

> Early in the section I mentioned that there is a natural way of reducing the variance in time required to validate a block of transactions. If that variance is reduced too much, then it creates an interesting attack possibility...

You've described a 51% attack. The security model of bitcoin assumes these are economically infeasible to mount.

> Suppose Bitcoin mining software always explored nonces starting with x = 0, then x = 1, x = 2,\ldots. If this is done by all (or even just a substantial fraction) of Bitcoin miners then it creates a vulnerability. Namely, it’s possible for someone to improve their odds of solving the proof-of-work merely by starting with some other (much larger) nonce...

No, this does not improve their odds. No miners are scanning the same ranges, because the block header is different for each miner (due to different coinbase transactions and timestamps, if for no other reason).

Two questions:

Mining bitcoins is about being the first one to generate the hash that satisfies having however many 0s. Whoever gets there first wins the prize, cool.

Does that mean that you can only get new bitcoins in blocks of 25? If my mining program gets unlucky, and never gets a hit, do I get nothing for it? Or are there schemes where I am helping, and I get a portion?

Further, is there something in the data being hashed that includes the previous block chain?

Otherwise, couldn't I make myself some free bitcoins by pre-computing the hash for a transaction I'm going to do in the future, and verifying it first? Sure it might take some computing power, but with no competition I just need to make sure that my costs are less than 25 bitcoins- and at today's prices, that's a lot cash to work with.

A bit shorter explanation from me: http://perlalchemy.blogspot.com/2011/05/bitcoin-protocol-hig...

Not so detailed - but I think it covers the main mechanics.

Nice start. Another dumb question: how do individual transactions get to the miners for addition to the blockchain? Is there some P2P-type auto discovery going on? A central server shouting out miner IPs?

How many transactions end up in a block? How big are blocks?

I'm pretty sure that for normal operation, a transaction gets broadcast to the network, and all miners see it and try to include it in their blocks. Each miner has a queue of unverified transactions to include in the blocks it's trying to build. When the miner gets a valid block from another miner, then it removes all of the transactions in that block from it's queue.

In a legit fork with no attempt at malicious action, there's no reason for the transactions in the forks to be any different, since all of the miners are seeing the same transactions broadcast to the network and have essentially the same transaction queue.

For an attempted double-spend attack, miners already check that there isn't a double-spend in the nodes in their block, so they would drop the second transaction they got trying to spend the same coins.

Since a double-spend can't happen in a single block, the double-spend attack relies on 2 miners working on different blocks, where the attacker-controlled miner is semi-isolated from the network and does not include the original spend transaction, but instead the attacker's second spend transaction. If the attack miner solves the block before any other miner on the network and broadcasts it, then the rest of the miners will accept it and reject the original spend transaction as a double-spend, leaving whoever was going to receive it with no coins.

The non incompatible transactions will be present in both forks, and they will get validated and fixed whatever fork wins. This includes most of the transactions that are not related to the double spending.

In the case of a double spending, each transaction can live in only one of the forks, and the decedents [1] transactions can be validated only in the same fork. When a fork wins, all the transactions that are incompatible can’t be added and they disappear.

[1] Sopuse that X sends the same bitcoins to A and B. Then A send these bitcoins to A1, that sends these bitcoins to A2. During the same time B send these bitcoins to B1, that sends these bitcoins to B2. Then you have two forks, one with the A, A1 and A2 transactions and another with the B, B1 and B2 transactions. Only these transactions have problems and one half of them will disappear, all the other transactions will apear in both forks.