Hacker News Reader

Comment by eof | Hacker News Reader

To the uninitiated, bitcoin solves the byzantine general's problem by having each "general" work on a mathematical problem that is known to take a certain average amount of time; and, when they solve the problem pass their solution onto the other generals who will then incorporate the answer to the previous problem into a new problem.

The "consensus" is intrinsically linked to the "math problem" so that the generals will always "trust" the chain-of-answers which is the longest; as it would be impractical / impossible for an attacker to counterfeit the long-chain-of-answers.

Bitcoin uses sha256(sha256( x )) < `target` as its "math problem" where X contains the a hash of the previous "consensus" and new transactions which should become part of the new "consensus". `target` is adjusted over time

View on HN

Bitcoin doesn't really solve the Byzantine General's Problem, as demonstrated by the March 2012 network split [1], which was later resolved by consensus between users (lead developers and biggest miners) using communication channels outside of the Bitcoin network.

[1]: http://en.wikipedia.org/wiki/History_of_Bitcoin#The_fork_of_...

A cursory look at your link reveals that it was caused by an incompatibility between different versions of the bitcoin client; the older client wouldn't accept blocks as large as the later one. People downgraded to the older version, and then "The network reached consensus and continued to operate as normal a few hours after the split."

So I guess you could say it only solves the problem when everybody's software implements the same protocol.

So we could say, the newest version of the bitcoin software correctly solves the Byzantine General problem, though older versions faltered.

And this could be the case ad infinitum if the protocol needs to be changed due to newly discovered flaws.

In summary, unless there are no bugs in your p2p software, it's very hard to solve the Byzantine General problem without outside consensus.

No, either version alone solved the problem just fine. It was just when some people had one version, and other people had another version, that the problem arose. The solution was actually to revert to the older version. The new version wasn't buggy, but had made a small and intentional change to the protocol.

So what it showed was that it's hard to reach consensus between two groups who aren't running the same protocol. Bitcoin is pretty conservative about protocol changes for this reason, though they've worked on getting better at managing it.

Right on. So basically, Bitcoin solved part of the problem. The bigger unsolved, ie. not automated, problem would be adaptive updating with care to the intricacies of the diff between old and new behavior. And security in the process to prevent a mutiny or hostile takeover in the vulnerable split state. Obviously updates can't be atomic with so many players.

This kind of topic is worthy of a thesis. Thoughts?

Include a complete description of the protocol in `x`?

Yes, this is something above the Byzantine Generals Problem - that scenario didn't take into consideration, that the general's "agenda" is changing over time.

Another interesting angle is, that in case of Bitcoin, both groups have vested interest to cooperate with the other group and having the matter resolved as soon as possible; that's what actually happened in March. It seems to me like a variant of the "Prisoner's dilemma".

This is what I think that the "hostile takeover" is highly unlikely (in Bitcoin scenario), since that would very quickly brought the BTC value down. So like in the Prisoner's dilemma, both groups will become silent and cooperate, rather than "betray" the other.

I still don't understand how it solves it. I get that you can agree a time, but how does it solve the problem that each general needs to be certain that all the other generals are also certain? I may have seen a completed block chain for the attack and time, but how do I know all the other generals have also seen it? I know they signed part of it, but how do I know the completed chain then got back to them? If it didn't they're not going to attack and my army will be destroyed.

By proof-of-work mechanism.

Here I dug up the explanation of the Satoshi himself:

http://www.mail-archive.com/cryptography@metzdowd.com/msg099...

The time delay introduced by the proof of work is the key to all your questions.

Imagine 10 generals in the network all trying to agree on a time of attack. Each simultaneously sends 9 couriers to the other generals suggesting an attack time. That's 90 couriers with 10 different messages all pinging around the system simultaneously. Each general receives 9 messages at roughly the same time, and either has to choose one to sign and rebroadcast, or cheat and sign multiple and rebroadcast them. There are too many options available at any given time, and odds of reaching consensus aren't good.

However, by introducing a time delay you slow the rate of message passing enough to be manageable - now's there's only 9 couriers and 1 message pinging around the system at the same time. All nodes in the network work the same problem, but only one will find a solution first and broadcast it, and with the time delay there's enough time for that solution to disseminate through most of the network before another node discovers another solution and broadcasts it. By the time the second and subsequent solutions are found, the the first has disseminated to enough nodes that they've already incorporated it into the next proof-of-work, and reject subsequent solutions to the prior PoW.

I still don't see the solution - doesn't any solution have to solve the problem of messages being lost?

Say that after some time a block that is long enough is made by some general A and is distributed to generals B and C. General D doesn't get it though - his messenger is killed in transit. He helped make an earlier block, but has never seen the fully completed block.

How do the other generals know that he hasn't got the final block that is long enough?

Or is it just the case that a majority of generals know when to attack? I thought it had to be all of them, but maybe that's the two-general problem and Byzantine-general's is an easier problem. I was pretty sure there were multiple good proofs of the impossibility of a solution.

The basic idea is (based on Satoshi's explanation linked from a nearby comment) that each general i proposes some time T_i, where T_i - now > 2 hours and starts solving the problem using the value T_i. If it finds a block, it broadcasts it. After some time (e.g. after 2 hours if each block is expected to be mined in 10 minutes) there is an overwhelming probability that all generals have synchronized and are working on the problem with the same initial value T_n for some n (they synchronize by always working on the longest chain).

The key point is that after 2 hours, all of the generals can independently assess, by examining the previously mined blocks in the chain they are working on, how much CPU was spent working on the solution, and can "see" how many nodes are in the network, and hence can see if all the nodes have worked on this solution (if yes, they all know of the arranged time of attack).

This doesn't fully solve the problem (one general could be rouge, or one might be killed just before the attack, ...) but it at least raises the chances :)

Well if it doesn't fully solve the problem, does it solve it at all?

That's the thing about BG; you can keep increasing the chances, but if your requirement is that you must be certain that all the other generals will attack, and at the same time, then we know of no solution. We also have more than one good proof that this is impossible.

Right, but the assumptions of the BG problem are also a bit harsh for the real world; network exhibits latency and/or splits, which are followed by joins. If two servers cannot communicate (ever again), then you have bigger problems than simply "synchronizing attacks". For the usual problems of varying latency and some dropped messages, the proof-of-work, coupled with a cryptographic authentication, will suffice for eventual consistency.

>I still don't see the solution - doesn't any solution have to solve the problem of messages being lost?

I think what happens here is that any node that doesn't get the message due to lost message, does not advance to the next block, and hence is working on a shorter chain than the nodes that got the message. Eventually it will receive another message with a longer chain and be forced to abandon its own work and adopt the new longer chain. It's highly improbable that nodes working on shorter chains could ever catch up to those working on the longest version.

There may be some threshold of lost messages where the system begins to break down, but assuming no intelligent attacker is behind it and the losses are random, they affect the whole system, not just the prime chain. The shorter chains would be roughly equally affected.

>How do the other generals know that he hasn't got the final block that is long enough?

He keeps working on whatever he has until he receives a longer blockchain from neighbors, which forces him to abandon his shorter one and start working on the longer one right away.

>Or is it just the case that a majority of generals know when to attack? I thought it had to be all of them, but maybe that's the two-general problem and Byzantine-general's is an easier problem.

Eventually it is all of them. The big difference between bitcoin and the theoretical BGP or TGP is that the theoretical problems have an end state where it is simply good enough for a majority to decide on an attack time, they attack, win, share the spoils, and the process is over. Simple majority is all that was needed.

Bitcoin takes that a step further and never stops. As soon as it reaches a simple majority decision, all nodes abandon their own work and adapt that decision - the longest blockchain - as soon as they receive it, and the process starts over from that new point. Each solution creates a longer blockchain, which forces unaninimity.

As problems get more difficult, I think there will be less and less proof-of-work, and people will see less and less of an incentive to keep miners online. Doesn't this mean that security begins to break down as people give up on mining?

Miners are paid in two ways - from creating new bitcoins and from transaction fees. The transaction fees are small but add up to enough to make it worth mining.

If you do the math on a 1MB block that pays, say, 12.5 BTC of fees the result is pretty sobering. Like over $1 per transaction.

I would wager pretty strongly that the 1 MB limit will be raised (or removed) in the not-to-distant future.

i'm a fan of everything by cdixon -- but check out satoshi and others like bohm: Here's satoshi: http://www.mail-archive.com/cryptography@metzdowd.com/msg099... and paul bohm: http://paulbohm.com/articles/bitcoins-value-is-decentralizat...

Reply on news.ycombinator.com