Last month, Marc Andreessen wrote a thought-provoking article on bitcoin for the New York Times. Interestingly, early in the article he mentions Byzantine agreement (albeit by the more colorful name of the Byzantine Generals Problem):
“Bitcoin is the first practical solution to a longstanding problem in computer science called the Byzantine Generals Problem. To quote from the original paper defining the B.G.P.: “[Imagine] a group of generals of the Byzantine army camped with their troops around an enemy city. Communicating only by messenger, the generals must agree upon a common battle plan. However, one or more of them may be traitors who will try to confuse the others. The problem is to find an algorithm to ensure that the loyal generals will reach agreement.“
When Marc Andreessen mentions Byzantine agreement in the New York Times, it gets my attention. I’m far from an expert on bitcoin, but from what I can tell, the system is faced with a Byzantine agreement (BA) problem when maintaining logs of currency transactions. This BA problem occurs over a huge network, so a solution that uses all-to-all communication is infeasible. To circumvent this, bitcoin uses an algorithm that trades off computation for communication.
In particular, bitcoin’s algorithm for BA uses proof-of-work. Instead of each node sending out a vote, only those nodes that are able to solve a computational puzzle send out their votes. If the puzzle is hard enough, only a small number of nodes send out votes and communication is low. Of course, each vote contains a small proof that the node solved an instance of the puzzle. This approach works provided that the computational effort exerted by the “good” nodes is twice the computational effort exerted by the bad nodes.
However, there are two issues with using proof-of-work. One is ensuring there is an incentive for the good nodes to work to solve a large fraction of the puzzles. Bitcoin uses a clever approach: reward users that solve puzzles with their own bitcoins. However, this is very application-specific, and it’s unclear if bitcoin’s BA algorithm would work for other systems where there is no obvious way to incentivize computational work.
Second, proof-of-work wastes computational resources. Arguably, many BA algorithms waste communication resources, so maybe this is a fair tradeoff. However, one has to wonder if there is a more efficient way to tolerate bad nodes. In particular, it’d be nice to have a scheme where the computation done by the good nodes is some function of the computation done by the bad nodes. One could hopefully show this via something like resource competitive analysis. Resolving whether or not this is possible is I think one of the more interesting research problems related to bitcoin’s approach to Byzantine agreement.
 See also this rebuttal to Andresseen’s article