Financial Cryptography

Bitcoin and the Byzantine Generals Problem -- a Crusade is needed? A Revolution?

It is commonly touted that Bitcoin solves the Byzantine Generals Problem because it deals with coordination between geographically separated points, and there is an element of attack on the communications. But I am somewhat suspicious that this is not quite the right statement.

To review "the Byzantine Generals Problem," let's take some snippets from Lamport, Shostack and Pease's seminal paper of that name:

We imagine that several divisions of the Byzantine army are camped outside an enemy city, each division commanded by its own general. The generals can communicate with one another only by messenger. After observing the enemy, they must decide upon a common plan of action. However, some of the generals may be traitors, trying to prevent the loyal generals from reaching agreement. The generals must have an algorithm to guarantee that

A. All loyal generals decide upon the same plan of action.

The loyal generals will all do what the algorithm says they should, but the traitors may do anything they wish. The algorithm must guarantee condition A regardless of what the traitors do.
The loyal generals should not only reach agreement, but should agree upon a reasonable plan. We therefore also want to insure that

B. A small number of traitors cannot cause the loyal generals to adopt a bad plan.

Lamport, Shostack and Pease, "the Byzantine Generals Problem", ACM Transactions on Programming Languages and Systems,Vol.4, No. 3, July 1982, Pages 382-401.

My criticism is one of strict weakening. Lamport et al addressed the problem of Generals communicating, but there are no Generals in the Bitcoin design. If we read Lamport, although it doesn't say it explicitly, there are N Generals, exactly, and they are all identified, being loyal or disloyal as it is stated. Which means that the Generals Problem only describes a fixed set in which everyone can authenticate each other.

While still a relevant problem, the Internet world of p2p solutions has another issue -- the sybil attack. Consider "Exposing Computationally-Challenged Byzantine Impostors" from 2005 by Aspnes, Jackson and Krishnamurthy:

Peer-to-peer systems that allow arbitrary machines to connect to them are known to be vulnerable to pseudospoofing or Sybil attacks, first described in a paper by Douceur [7], in which Byzantine nodes adopt multiple identities to break fault-tolerant distributed algorithms that require that the adversary control no more than a fixed fraction of the nodes. Douceur argues in particular that no practical system can prevent such attacks, even using techniques such as pricing via processing [9], without either using external validation (e.g., by relying on the scarceness of DNS domain names or Social Security numbers), or by making assumptions about the system that are unlikely to hold in practice. While he describes the possibility of using a system similar to Hashcash [3] for validating identities under certain very strong cryptographic assumptions, he suggests that this approach can only work if (a) all the nodes in the system have nearly identical resource constraints; (b) all identities are validated simultaneously by all participants; and (c) for "indirect validations," in which an identity is validated by being vouched for by some number of other validated identities, the number of such witnesses must exceed the maximum number of bad identities. This result has been abbreviated by many subsequent researchers [8, 11, 19-21] as a blanket statement that preventing Sybil attacks without external validation is impossible.

J. Aspnes, C. Jackson, and A. Krishnamurthy, "Exposing computationally-challenged byzantine impostors," Tech. Report YALEU/DCS/TR-1332, Yale University, 2005, http://www.cs.yale.edu/homes/aspnes/papers/tr1332.pdf

Prescient, or what? The paper then goes on to argue that the solution to the sybil attack is precisely in weakening the restriction over identity: *The good guys can also duplicate*.

We argue that this impossibility result is much more narrow than it appears, because it gives the attacking nodes a significant advantage in that it restricts legitimate nodes to one identity each. By removing this restriction...

This is clearly not what Lamport et al's Generals were puzzling over in 1982, but it is as clearly an important problem, related, and one that is perhaps more relevant to Internet times.

It's also the one solved according to the Bitcoin model. If Bitcoin solved the Byzantine Generals Problem, it did it by shifting the goal posts. Where then did Satoshi move the problem to? What is his problem?

With p2p in general and Bitcoin in particular, we're talking more formally about a dynamic membership set, where the set comes together once to demand strong consensus and that set is then migrated to a distinct set for the next round, albeit with approximately the same participants.

What's that? It's more like a herd, or a school of fish. As it moves forward, sudden changes in direction cause some to fall off, others to join.

The challenge then might be to come up with a name. Scratching my head to come up with an analogue in human military affairs, it occurs that the Crusades were something like this: A large group of powerful knights, accompanied by their individual retainers, with a forward goal in mind. The group was not formed on state lines typical of warfare but religious lines, and it would for circumstances change as it moved. Some joined, while some crusaders never made it to the front; others made it and died in the fighting, and indeed some entire crusades never made it out of Europe.

Crusaders were typically volunteers, often motivated by greed, force or threat of reputation damage. There were plenty of non-aligned interests in a crusade, and for added historical bonus, they typically travelled through Byzantium or Constantinople as it was then known. And, as often bogged down there, literally falling to the Byzantine attacks of the day.

Perhaps p2p faces the Byzantine Crusaders Problem, and perhaps this is what Bitcoin has solved?

In the alternate, I've seen elsewhere that the problem is referred to as the Revolutionaries' Problem. This term also works in that it speaks to the democracy of the moment. As a group of very interested parties come together they strike out at the old ways and form a new consensus over financial and other affairs.

History will be the judge of this, but it does seem that for the sake of pedagogy and accuracy, we need a new title. Bysantium Crusaders' problem? Democratic Revolutionaries' problem? Consensus needed!

Posted by iang at November 19, 2014 08:19 PM