It's common knowledge that Bitcoin solves (or purports to solve) the Byzantine Generals problem.

This problem kicked off thirty years of research in distributed systems. It's a fascinating field, and also a very subtle one. Variations of the problem come in a handful of basic flavors, however what's possible and what's not depends heavily on the assumptions you make and what you require from the protocol. My goals in this post are to describe the basic components of the problem, point out some of my favorite reading materials, and hopefully begin a discussion on what assumptions and requirements are appropriate for Bitcoin (or altchains). Results may be gathered into a wiki. I also want to make an overall argument: although problems of this nature have been studied for decades, the academic field has not yet settled, and Bitcoin seems to reveal a couple of blind-spots.



--------

All distributed systems face two essential challenges: latency, and failures.

• Failures: The total number of processes (aka: participants, nodes, total-hashpower) is indicated by "N". Some portion "f" of these might fail. Kinds of failure worth describing:  permanently crashing, stopping-and-restarting, and Byzantine - which means behaving maliciously in the worst possible way. The resilience of a system is usually described as "N = 2f+1", which is the same as what we mean by 51%.
      Most previous work has assumed that N is known, that every process has a unique ID, and that everyone knows all the IDs from the start. Recent research has looked at anonymous networks and large-scale dynamic networks, showing that these differences are non trivial. Some work that approaches nearer and nearer to Bitcoin:
      
  • Partially anonymous networks (homonyms) Delporte-Gallet et al, 2011
  • Computationally challenged byzantine impostors (closely related to Bitcoin in spirit) Aspnes, 2005
  • Population protocols (tiny anonymous nodes, molecule interactions) Angluin, 2006
  • Rational failures (combines game theory and distributed systems) Clement et al, 2008
• Latency: There are three popular timing models, which describe uncertain rate of message propagation in networks. The simplest case is called "synchronous communications", and it's when every message arrives within a certain known time limit, Δ (delta). Any messages that take longer than this have “timed out” and you can count them as failures. Protocols for this model often proceed in discrete rounds. The part of Bitcoin that rejects blocks based on invalid timestamps, for example, is indication of synchronicity assumptions. The hardest model is “asynchronous,” where packets can take longer and longer and longer to arrive.
      A medium-difficulty (and mostly realistic) scenario is called “partially synchronous,” where temporary partitions may occur but are eventually resolved. In this model, you don’t use any explicit time parameters. A maximum time delay Δ exists, but it is unknown. Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer won the Dijkstra prize for this 1988 paper, which turned out to be very useful. If you’ve ever dreamed of a Bitcoin mining colony on Mars, or wondered what would happen if the transatlantic fiberoptic backbone were suddenly severed, you are probably thinking about the partially synchronous model. The best possible results in this model are of the 67% (3f+1) variety, rather than the 51% (2f+1) variety. If even the 67% honest participants are able to survive a partition that splits them in half for an unknown duration, then an attacker with 33% could pretend (simulate) being on the other side of a partition and disrupt you at any time.
  
  
• Variations of the problem statement: The original Byzantine Generals problem (Leslie Lamport, 1978) featured asynchronous communications between a known set of deterministic processes with secure channels between every pair. The requirement is that the processes eventually make an irrevocable “final answer” decision, and when they do, they all agree. If something like the “confirmed after 6 blocks” rule were built into the Bitcoin protocol, then it would match this problem.
       There are several aspects of Bitcoin that make the problem harder, in particular anonymous/unknown-size networks. There are also many reasonable ways to make it easier.
  
  
  • Randomness, an essential part of Bitcoin, is enough of an addition to make otherwise-impossible things possible. Randomness is a way of breaking-symmetry (see the short story at the top of this post). If the puzzle difficulty is high enough, Bitcoin can break symmetry at any time scale. However, to use randomization, you must relax the problem so that either a) failure is possible, but with probability zero, or b) failure could occur with some negligible probability.
    
    
  • Random oracles (non-invertible cryptographic hash functions with uniform random outputs).
    Hash functions are something we accept with faith, at least for the time being. It has been proven that no hash function behaves perfectly. On the other hand, some simple properties (like collision-resistance) are provably attainable. I doubt anyone would argue that Bitcoin relies on untenable properties of hashes. Nonetheless, this is a reason why their use has not been so widely explored in distributed systems (counter example) - from a very traditional point of view, they are too strong an assumption. Any protocol using hashes will incur at least a positive but negligible chance of failure. Many consensus protocols have assumed perfect authenticated channels, yet any instantiation of these with primitives from modern cryptography is likely to introduce a random oracle at some point. I find it interesting that the original use of hash-based puzzles was by Dwork and Naor, two of the leading figures in distributed consensus, yet they have not considered using such puzzles in consensus algorithms. Even stranger, Naor and Nissim were the first to suggest balanced merkle trees for use in transaction systems (certificate revocation).
    
    
  • Stabilizing consensus - this is what you get when you remove the “final decision” requirement from the Byzantine Generals problem. The protocol guarantees you will eventually converge, but you can’t say for sure when it has happened. Dijkstra defined “self-stabilization” in 1974, and Angluin adapted it to the consensus problem in 2006. The term “eventually consistent” is relevant here. This, I think, the most appropriate problem definition for Bitcoin. We will eventually stabilize to a single agreed-upon value for each block, no matter what. But at any particular time, there is no way to rule out the possibility of a larger fork showing up. If this happens, then you take the larger fork and deal with it, and the protocol continues. Any irrevocable decisions (e.g., I wait for 6 confirmations and give you a bar of gold) are made according to a user’s personal risk analysis - if they get forked, it doesn’t count as a protocol failure.
    

---- Some final thoughts -----


It was this post by Ben Laurie that led me to read up on distributed systems. I suspect he’s wrong. At the very least, it’s possible to rearrange the problem statement in such a way that Bitcoin solves it. Anyone who has followed the development of this field over several decades will acknowledge that there is no single correct set of model assumptions for every application. Subtle variations have led to unexpected outcomes, for both possibility and impossibility.

It surprises me that as of yet, no one from distributed systems has said anything about the underlying consensus mechanism of Bitcoin. (Although Bitcoin and Red Balloons comes close, they focused on a red herring related to the gossip layer rather than the core.) I hope this changes soon, as distributed systems researchers and the Bitcoin community should have a lot to learn from each other. Like many areas of computer science, distributed systems theory was developed long before actual networks and internet were widespread. Many of the theoretical contributions have been dismissed in practice.



Therefore I think distributed systems folks would find it extremely exciting that an open source community has taken up the task of building a large-scale, high-stakes consensus network under supremely adversarial conditions. From what I’ve seen, the average Bitcoin user has an understanding of distributed systems to match that of a grad student, and could at least walk through the FLP impossibility result in terms of competing blockchain forks with equal strength.

The problem Satoshi described is not quite the Byzantine generals problem, for two reasons I mentioned in my post. First, the Byzantine Generals problem is specifically about asynchronous communications, in which you cannot assume that messages are delivered within a bounded amount of time, let alone a bounded time known a priori. This is at least half the challenge, and likely the more difficult half. Second, the original form of the problem is about deterministic protocols that are correct with absolute certainty. Even most randomized algorithms are expected to succeed with probability 1. The "expected" part there implies a non-zero probability of failure.

The differences between these models may seem a bit pedantic, but that's what I'm hoping to discuss.

Also, the particular model described in Satoshi's problem description (synchronous communications, known number of processes) is nearly identical to Exposing Computationally Challenged Byzantine Impostors (Jackson and Aspnes 2005)

A good reason to take time being precise/pedantic about the problem statement is that it makes it possible to bring in and compare results from other work. By far the most enjoyable survey on the (first ten years of study on) the problem is 100 Impossibility Proofs in Distributed Computing by Nancy Lynch, which made the argument that much effort was wasted in rehashing the same results in slightly different models that would later turn out to reduce to one another.

I don't think that bitcoin is going to be very useful, academically speaking.  It really isn't for that.

Bitcoin is more like a "good enough" system, one intended to be used in the real world.  It produces approximations to perfection, but never is perfect.

For example, bitcoin doesn't prove, or even attempt to fully prove that a block is final, but as more blocks pile up, we can become increasingly confident that it won't be overruled.  But never totally sure, because every block back to the last checkpoint in theory could be replaced if a better chain is found tomorrow.

By the way, "good enough" isn't a bad thing.  Engineering is the art of understanding tolerances, and of understanding that nothing is absolute, to make things that are "good enough" for the real world.  Bitcoin is an outstanding example of engineering in that sense.

Bitcoin appears to solve certain well-studied problems in the academic field of distributed computing in a novel way. So I don't think I agree with you here.

There is a reason nobody working on digital currency (academics or otherwise) had been able to come up with a truly robust digital currency (until Bitcoin). The reason is that Bitcoin really does solve some very hard, old problems in novel ways.

Here's a way of describing the computational requirements in Bitcoin. This is intended to clarify and focus the technical discussion in other threads that discuss particular data structures and implementations.

Bitcoin is all about efficient validation.

There are two kinds of validation tasks in Bitcoin: transaction validation and fork validation. These are closely related, since validating transactions is at least a subcomponent of fork validation. The most important difference between the two is their relationship to the proof-of-work scheme, which affects the way we need to state the security and complexity requirements.

Stabilizing Input (Bounded UTXO Assumption)

Assumption: The set of unspent-outputs at any given time is bounded by some (possibly unknown) maximum size, M. This means that the txinputs catch up with the txoutputs at some point, trailing behind by no more than M. This also implies M is a maximum "fanout" in a transaction. In Bitcoin, the size is certainly bounded by M < 2.1e14, since that's the largest possible number of unique coins. This number is related to the number of bits in our hashes, since log M < 50 < 256 = k.

Transaction Validation

• Assumptions: you're given a current block head to start with
• Correctness requirement: deterministic accept/reject
• Supporting data structure: the UTXO-set
• Key performance quality: worst-case cost of a decision (as a function of the size of the UTXO-set)
• Examples:  
  • clients validate transactions before deciding to relay them
  • miners validate new transactions before including them in work
  
  

Transactions are created by anonymous users of the network. Worst-case cost for rejecting an invalid transaction is important for DDoS resistance. On the other hand, worst-case cost for accepting a valid transaction is also important so that transactions propagate quickly.

The best asymptotic result so far is a balanced Merkle tree, which gets average-and-worst-case O(log M) validation effort per TXInput, and requires O(M) of untrusted storage (for example a DHT, or a cloud-storage provider, or a local disk). Other strategies include:

• UltraPrune(without Merkle hashes), which requires O(M) of trusted storage (a local disk)
• A hash trie, which has O(k) in the worst case (k > log M is a security assumption about hash-functions) but matches O(log M) in the average case

Fork Validation

• Assumptions: 67% of all work is performed by honest nodes on valid chains
• Correctness requirement: deterministic accept/reject
• Supporting data structure: the blockchain
• Key performance qualities:  
  • average accept cost, as a function of the size of the fork, N (total number of txins/txouts)
  • average rejection cost, as a function of W, the total amount of work (hashes) computed in order to assemble this fork
• Examples:
  • If a larger valid fork appears, miners eventually switch to working on it
  • New nodes on the network must "bootstrap" themselves by choosing the largest valid chain from scratch (or since the last checkpoint)

Validating a fork means validating every txinput in the fork. Since the best Transaction Validation procedures require average O(log M) effort (per txinput), the optimal complexity for full validation is O(N log M). However, the average time it takes to reject a work-deficient fork can be improved using the "Hash-Value Highway".

The reason we are able to switch from "worst-case" to "average" costs for fork validation is that the proof-of-work scheme eventually reaches the "average-case" in a long enough streak, no matter what algorithm you use. Forks are validated work-first.


-- Conclusion --

This is a first attempt at a statement of Bitcoin's computational requirements. Now in technical discussions, we can ask whether a different problem statement makes weaker or stronger assumptions, or if it has weaker or stronger requirements. My goal is to eventually make an argument that satisfying these requirements leads directly to a successful stabilizing consensus protocol, but I'll save that for later.

Sure. Assume the distributed consensus protocol works as intended. This paper asks whether a global Proof-of-Work system with a fixed budget could withstand three attack scenarios. The budget is based on an estimate of the current costs of our global digital transaction networks (e.g., debit cards): $283 billion per year.
So Bitcoin would defeat all three attacks, and under budget, too!

However, the attack model isn’t too compelling.
No, Bitcoin is designed to withstand disruptive behavior from a minority of the network. Against a sustained majority attack, Bitcoin’s only hope is to be an unappealing target. Zooko already asked "What Would You Do With >50% of the World's Bitcoin Mining Power?" It turns out that the sort of maneuvers that become available at this level (e.g., stubbornly blacklisting addresses) aren’t directly profitable.

Although the attacks considered in this paper are not required to be profitable, neither are they “worst-case scenarios” for Bitcoin. Hash-power alone can not harm the network, although it can penetrate our shields. To actually inflict damage on Bitcoin’s users, the attacker should use the hash-power to deliver a payload containing massive double-spends.

Here are two components I recommend for a more realistic attack model:

(Computationally Bounded Adversary): The attacker has a budget, B, for a total amount of work (i.e., hashes, hash-energy, rather than hash-power). This is the expected number of hashes needed to build a fork B blocks long. The attacker can use these hashes all at once, or spread over any amount of time.

The bounded (rather than sustained) versions of the attacks from this paper are immediately more realistic. The sentient supercomputer that mines uncooperatively eventually gets reprogrammed. After a few weeks, most of “Occupy Bitcoin” have packed up their tents and gone home. The sharks with frickin’ GPUs attached to their heads will overheat and die.

(Mining as a commodity): Think of mining as something to purchase, rather than something to do. For example, you could hire a mercenary mining provider to work on a header containing the transactions of your choice. You could evaluate quality-of-service by asking the mining-provider to show you blocks-that-didn’t-quite-win, in addition to the winning blocks - similar to shares in p2pool.

The point of these two assumptions is that an attacker can purchase a quick “burst” of B blocks worth of hash-energy for the same price it would cost a miner at the normal rate. In this model, the attacker might temporarily wield much more hash-power than the rest of the network. Using the same $283 billion annual mining budget from the paper, a 7-block attack would cost an expected $30 million.

What would you do if you could summon a 7-block fork on demand? Well, MtGox (and pretty much everyone else) waits for 6-blocks of confirmation before making an irreversible decision. A profitable attack target might be to deposit $33 million worth of bitcoin into MtGox, withdraw it after 6 blocks, then rewind the network and double-spend the original $30 million back out. Expected profit: $3 million (%10 return). Since the attacker has a finite budget, then any attempt at producing a fixed number of blocks has a chance of failure. Potential downside: -$B if the attacker spends the entire budget without finding a 7th block. Potential upside: up to $33 million if the 7-blocks are found much faster than expected. This is the model of “gambler’s ruin”. Attacks of this nature might be profitable in the long run, but a losing streak leads to bankruptcy.

Here’s a different worst-case scenario. Dr. Evil announces that Dec 21, 2012 shall be “Double-Spend Doomsday.” He calls upon the entire population (e.g., 10% of Facebook users?) to participate by buying gold and cash with Bitcoins and sending a message with a double-spend to Dr. Evil’s email address. At 11:59pm, he will unleash a One Billion Dollar fork (about a day’s worth of transactions) containing all the double-spends he receives - harnessing the world’s collective greed to wreak havoc. If the threat is plausible, then perhaps business will grind to a halt for that day. Mutual suspicion combined with a loss of trust in the effectiveness of the PoW shield could result in economic damage, even if the attack is not realized.

Conclusion

This paper is peculiar, since its title and stated goals are completely mismatched to the actual analysis.
I agree with you: cutting costs is not the main reason to use a proof-of-work system. The main reasons are to reduce risk by eliminating central points of failure and providing transparent, objective security claims.

Although this paper begrudgingly acknowledges that Bitcoin may achieve these goals, the attack models should be improved. I suggest a variation that involves bounded (rather than sustained) attacks, equal cost per block for both miners and attackers (though the attackers get their blocks as rapidly as they like), and estimating the damages caused by reordered transactions.

What’s next? At the microeconomic level, I would like to have a risk analysis model for Bitcoin transactions. What’s the optimal number of blocks to wait before giving you an ounce of gold? At the macro level, we should ask whether an attack on Bitcoin would inflict more economic damage than a similar-sized attack on an alternate system like debit cards. I’d expect these to be related, since user behavior will determine the potential damages for a given attack.

Finally, I’m glad these authors mentioned that Bitcoin may replace other systems besides (or in addition to) consumer card transactions. They omitted large transactions between governments and corporations from their model - but those seem like an ideal kind of transaction to require Bitcoin in order to take advantage of public transparency. Bitcoin could replace the postal service for official legal correspondence - instead of a registered mailing address, you could receive subpoenas to a Bitcoin address. The mining budget grows with the more roles Bitcoin can serve. I don’t know how the attacks and risks would be affected.

You're right, it's important to understand the distinction: Bitcoin clearly does not solve Byzantine Generals, but hopefully it solves a related weaker problem instead. Is the weaker problem useful? I disagree with your point about the common sense interpretation - I think Bitcoin users have the correct intuition about how the system behaves.

Here's the crux of the distinction. If Bitcoin were a deterministic Byzantine Generals solution, then it would provide a claim like the following: "If you wait 6 blocks before making an irreversible action (e.g. handing over a bar of gold to a stranger), then you're 100% guaranteed not to get double-spent."

This is not one the services that Bitcoin offers to its users. Instead, as you say,

The generally accepted language for randomized consensus algorithms is that they "eventually converge with probability 1," mostly for the reason that this is a mathematically friendly statement work with. (See for instance Stumbling over Consensus Research: Misunderstandings and Issues) But this isn't necessarily what users want. Certainly the 100% deterministic version would be more user friendly, but it's not possible on an anonymous network. My opinion is that Bitcoin is the perfect balance - strong enough to satisfy demand, just weak enough to be viable. Here's a way of closing the gap between what we have and what we might want:

(Fork Insurance) Imagine there is a market for Bitcoin insurance. A pawn shop that wants to accept Bitcoin payments would probably want to purchase a fork insurance policy. The insurance policy would offer the 100% deterministic option to its customers: if the merchant dutifully waits for 6 blocks before letting the customer walk out with a gold bar, then the merchant is insured for up to $1000.

If you use Bitcoin directly, you're responsible for your own risk assessment and management. What's excellent about Bitcoin is you can do this anonymously yet benefit from the worldwide amortization of mining work. If you are incapable or unwilling to make your own risk assessment, then you can hire someone to make this sort of decision for you. Note this is an individual decision - there's no such thing as an official Bitcoin insurer. Also note that payment processors like BitPay already provide this interface to their customers. They put money in your account right away. Double-spends are their problem. So is evaluating the health of the network.

What's the price of Bitcoin insurance? If you were going to insure a Bitcoin exchange, how would you calculate that risk? And would you put more effort into auditing the exchange's php scripts for silly vulnerabilities or would you focus on shoring up against the dreaded 51% doomsday attack? Are there any Bitcoin actuaries who have started on this sort of modeling? I have no idea what the legal and regulatory environment is for this kind of insurance - is it more or less intimidating than money transmitting?

Even among the theoretical idealizations, the "deterministic 100%" requirement is so unrealistic that it has (somewhat) fallen out of favor. "Converges with probability 1" is also a platonic ideal, but it's much more useful and a much better fit for Bitcoin.