[Cryptography] Electronic currency revived after 20-year hiatus

[Natanael]

Den 18 aug. 2016 00:31 skrev "Jerry Leichter" <leichter at lrw.com>:
>>
>> 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.
>
> Wow.  How many false statements can we pack in here in an attempt to make
Bitcoin into some bit of magic?

Not trying to make it seem magic. Just emphasizing that the approach is
unique.

> 1.  The Byzantine Generals problem was never considered unsolvable.  In
fact, the very paper that introduced it also provided a solution.

I guess I should have added more detail.

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.

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.

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.

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.

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.

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.

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.

> 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.

I was hoping my intent was clear;

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.

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...

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.

> 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.

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.

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).

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.

Thus as I said, Bitcoin goes for a probabilistic solution.

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.

> 4.  The original paper also shows that given the assumption of
unforgeable message signatures, a deterministic solution exists with any
number of traitors.

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).

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.

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.

> 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.

I should have emphasized the requirement of avoiding gatekeepers.

Because with cryptocurrencies, you don't want something that can be
trivially taken down permanently with a few lawsuits or criminal charges.

Or have it die because of a lack of VC funding.

Or being regulated to death. Or die because it can't be used across
borders.

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.

Bitcoin on the other hand lives as long as there's enough interest.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160818/fc58fd7b/attachment.html>