[semi-extrinsic]

> The problem that Bitcoin solves and private blockchains do not is called the Byzantine generals problem which did not have a known solution until Bitcoin came along.

I'm not an expert in any way, but the Wikipedia page for Byzantine Fault Tolerance suggests a solution to this problem was known as early as 2001, used in the Boeing 777 avionics software. See abstract of the paper below. That significantly predates Bitcoin. Or am I misunderstanding something?

http://ieeexplore.ieee.org/document/963311/?arnumber=963311

[wmf]

There were known solutions given a fixed set of generals. Nakamoto consensus handles the case of an unknown number of anonymous generals (miners) who may come and go when they please.

[semi-extrinsic]

Out of curiosity: were there known solutions for an arbitrarily large number of fixed generals? Could a similar solution as with Nakamoto consensus be obtained by having a huge, fixed number of generals, setting some as occupied and using live inputs for those, and then using an alternating series of yes/no votes for the unoccupied generals? (Maybe you'd have trouble with off-by-one errors in the alternating series, but you could ad-hoc fix that.)

Come to think of it, why does the variable number of generals make a difference? When you are making a single decision, is that decision not an atomic operation such that the number of generals influencing it is fixed? Otherwise, wouldn't necessarily the outcome of the vote be (marginally) affected by the order in which you evaluate the votes cast? (That seems like a very bad property for a consensus algorithm to have.)

[wmf]

I assume protocols like Paxos can work with any odd number of generals. Since the generals are anonymous, consider a Sybil attack. If there are N total generals, what's to prevent me from claiming that I am all N generals? If there are N total generals but M entities try to each spam the system with fake generals, how does the system decide?

[semi-extrinsic]

So you're saying blockchains prevent this because proof-of-work? I.e. that you literally can't run a Sybil attack, because the only way to impersonate N miners is to actually run N miners?

[wmf]

Yes. (Modulo arguments about the definition of "blockchain".)

[riprowan]

How can you know a general is not a sybil?