<p dir="ltr"></p>
<p dir="ltr">Den 18 aug. 2016 00:31 skrev "Jerry Leichter" <<a href="mailto:leichter@lrw.com">leichter@lrw.com</a>>:<br>
>><br>
>> Just like how Bitcoin solved the unsolvable Byzantine General's problem by ignoring the original problem statement and going for a probabilistic approximation, Bitcoin's got a solution here too.<br>
><br>
> Wow.  How many false statements can we pack in here in an attempt to make Bitcoin into some bit of magic?</p>
<p dir="ltr">Not trying to make it seem magic. Just emphasizing that the approach is unique. </p>
<p dir="ltr">> 1.  The Byzantine Generals problem was never considered unsolvable.  In fact, the very paper that introduced it also provided a solution.</p>
<p dir="ltr">I guess I should have added more detail. </p>
<p dir="ltr">All previous solutions required gatekeepers, because they all failed if the adversary could perform a Sybil attack (flood the network with nodes). Even the more recent Ripple type systems use centralized gatekeepers, and proof-of-stake merely distributes the role of the gatekeeper across more nodes (the nodes representing the economic majority within the system), and the classical concensus systems (not designed for cryptocurrencies) mostly rely on a centralized PKI. </p>
<p dir="ltr">Even then it isn't solved in the mathematical sense in most circumstances (always having all nodes reach the same conclusion) because of information asymmetry - everybody must know the same thing, because if they don't then you'll lose determinism and any guarantee of a resolution. This requires stable networks and near perfect uptime for the majority of nodes. </p>
<p dir="ltr">Malicious nodes doesn't have to stick to just voting maliciously, they can even attack the network connectivity and withhold messages. Then what? Now you have *no* guarantees. In fact your network could get completely stalled despite having functional honest nodes still running and talking, something which wouldn't happen to Bitcoin. </p>
<p dir="ltr">Those systems that manage to guarantee a *quick and useful* resolution using objective metrics of the messages themselves will typically also strictly require that *all* nodes are trusted (for example by completely trusting timestamps of all messages, with highly precise calibrated clocks). That makes them much less useful in most circumstances, because it just isn't practical or even safe to most people. </p>
<p dir="ltr">Bitcoin took proof-of-work (and hooked incentives to it, too keep it alive) to much more reliably achieve a quick resolution (chained proof-of-work makes for a very quickly verifiable objective metric, so you don't get long lasting netsplits because of disagreements), and it doesn't need gatekeepers. Instead it relies on game theory to attempt to assure an honest majority of computing power. </p>
<p dir="ltr">There's no collection of all votes from all online peers during every round / for every decision to settle on the same result. Just shared knowledge of one chain with accumulated proof-of-work exceeding all others. Bitcoin has a completely deterministic selection mechanism, given a set of chain forks with different accumulative proof-of-work. No need for individual crosstalk, just a series of global broadcasts. </p>
<p dir="ltr">Without network instability you have a beyond 99.99% chance of resolution before any competing forks both reaches 2 blocks length from after the last shared block. Even with most kinds of real life severe network instability you'll usually get the supermajority onto the same chain within ~3 blocks, as long as it gets propagated to the miners. </p>
<p dir="ltr">> 2.  Ignoring the problem statement doesn't solve a problem.  It may or may not solve a different problem, but let's stick to reasonable use of language here.</p>
<p dir="ltr">I was hoping my intent was clear;</p>
<p dir="ltr">The original problem statement often makes implicit (or sometimes explicit) assumptions that are false, for example by having overly strict requirements, or not actually being representative of the real environment. </p>
<p dir="ltr">Bitcoin rejected the need of a gatekeeper, rejected the need for a 100% mathematically guaranteed solution (can't have that without gatekeepers anyway, so no use of fancy selection / voting math), rejected the method of identifying individual nodes and shifted to proving computing power instead, etc... </p>
<p dir="ltr">So that's at least 3 things it did very differently as a result of changing the underlying assumptions. And as a result of these changes it eclipsed absolutely all other cryptocurrencies, because this combination of features proved more desirable in practice. </p>
<p dir="ltr">> 3.  The original paper shows that a deterministic solution in a completely general model had no solutions if 1/3 of the participants were traitors.  That's just true, and no amount of "probabilistic approximation" (whatever exactly that is) changes it.</p>
<p dir="ltr">In Bitcoin you need 51% malicious computing power for that (assuming no network isolation attacks, although even those can be circumvented by all miners broadcasting their blocks over radio), otherwise it will with very high probability settle on one single globally shared chain. </p>
<p dir="ltr">There's a lot of talk about "selfish mining" that would lower the percentage to ~33% in the worst case in theory, but it requires that the other miners are naive, that *nobody else does the same thing* (if everybody does it as it nearly cancels out itself when everybody does it (with the exception for marginally improving the profitability for larger miners/pools) and requires that those doing it are well connected in the network (which is difficult if you chose to not participate in the efficient relay networks that most big miners participate in, or if you get blacklisted from it due to abuse). </p>
<p dir="ltr">Even 3x 33% selfish mining pools will be somewhat stable and equal in power, still advancing the blockchain. A continous dance of two steps forward, one step back, still advancing the blockchain over time with a 99.99% probability.</p>
<p dir="ltr">Thus as I said, Bitcoin goes for a probabilistic solution. </p>
<p dir="ltr">Even a +45% selfish mining pool can be defeated by the rest of the network who'd quickly detect it and who could coordinate to reject its blocks, or who could temporarily act as a larger pool that selfish mines against the smaller pool which initiated selfish mining. By simply responding in ways that makes it unprofitable / counterproductive to do selfish mining it wouldn't last. </p>
<p dir="ltr">> 4.  The original paper also shows that given the assumption of unforgeable message signatures, a deterministic solution exists with any number of traitors. </p>
<p dir="ltr">This still requires both gatekeepers and total information symmetry, because otherwise not everybody will know about the entire set of nodes and all of their messages for certain. This is just basic physics / information theory as you need to know the exact same things to always reach the same conclusion, and without gatekeepers you can Sybil attack the system trivially and roll it back however much the system will let you in order to alter old decisions arbitrarily (deterministically guaranteed successful malice also isn't very desirable). </p>
<p dir="ltr">As a contrast see proof-of-stake with its nothing-at-stake problem, in which the lack of an objective chain selection metric + not having any ability to effectively prevent cheap re-voting / rollbacks leads to unstable concensus. It is even easier to attack when you add network based attacks (given that there's no way for all nodes to be aware of all other online nodes), as you can abuse netsplits to build up power to approach an unassailable 51% economic majority. </p>
<p dir="ltr">In fact, most proof-of-stake selection mechanisms can even be gamed such they start to resemble a poor-man's CPU-bound proof-of-work mining mechanism. </p>
<p dir="ltr">> It's not clear what cryptographic assumptions whatever parts of Bitcoin you want to use actually need, but if they include enough to have unforgeable message signatures, a complete solution without any kind of approximation is at hand - and has been for years.  </p>
<p dir="ltr">I should have emphasized the requirement of avoiding gatekeepers. </p>
<p dir="ltr">Because with cryptocurrencies, you don't want something that can be trivially taken down permanently with a few lawsuits or criminal charges. </p>
<p dir="ltr">Or have it die because of a lack of VC funding. </p>
<p dir="ltr">Or being regulated to death. Or die because it can't be used across borders. </p>
<p dir="ltr">And you absolutely DO NOT want netsplits with currency (just see the poorly managed Ethereum hardfork!), you want automatic global and consistent resolution to occur quickly. </p>
<p dir="ltr">Bitcoin on the other hand lives as long as there's enough interest.</p>