3 ms·
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
by chrisseaton 13y ago
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.
- greyman 13y agoBy proof-of-work mechanism. Here I dug up the explanation of the Satoshi himself: http://www.mail-archive.com/cryptography@metzdowd.com/msg09997.html http://www.mail-archive.com/cryptography@metzdowd.com/msg099...
- SkyMarshal 13y agoThe 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.
- chrisseaton 13y agoI 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.
- tomp 13y agoThe 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 :)
- chrisseaton 13y agoWell 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.