Possible flaw in Ben Laurie paper on Bitcoin efficiency

[LaggedOnUser]

I think there is a possible flaw in the Ben Laurie paper on Bitcoin, called "Decentralized Currencies are Probably Impossible, But Let's At Least Make Them Efficient" (http://www.links.org/files/decentralised-currencies.pdf).

If I may summarize his argument:
1. Bitcoin is inefficient, because it may require as much as 51% of the world's computer power to protect against a 51% attack.
2. Bitcoin solves this problem by doing periodic checkpoints, which are snapshots of the currency at a point in time beyond which its history cannot be rolled back.
3. These checkpoints use some other form of consensus which is more efficient than Bitcoin, but still secure and presumably decentralized, otherwise Bitcoin is not secure and decentralized.
4. He calls this hypothetical checkpointing mechanism "efficient unbounded agreement", and then claims that a more efficient coin than Bitcoin can be built on the basis of that mechanism alone.

The flaw in his argument, it seems to me, lies in assuming that the efficient unbounded agreement mechanism can somehow be separated from Bitcoin as a separate standalone protocol.  Checkpointing is merely freezing Bitcoin at a moment in time and refusing to roll back any transactions before that time.  Checkpointing relies on the assumption that the original Bitcoin proof-of-work is robust and secure, so that it is quite unlikely that a sustained attack can be made longer than a given period of time on the original Bitcoin protocol, thus it is presumed safe to checkpoint after that time.

However, checkpointing is only a secondary protocol that is not capable of standing on its own as the basis for a coin.  Checkpointing is merely a secondary validation of a primary security model.  Thus his conclusion, which essentially seems to say that we should throw out the Bitcoin and keep the checkpointing, is false and unworkable.

An analogy might be made with credit card security.  Imagine that credit cards have all their existing security mechanisms, plus you can't do chargebacks after 30 days.  An analogy to Ben Laurie's argument would be claiming that you can do away with all other card security and simply refuse to accept chargebacks after 30 days, and that would be just as secure as before.  That of course would be false, since a limit on chargebacks would just be a secondary security mechanism that can't stand on its own.

I bring this up because the PPCoin paper references this paper and seems to rely on it (http://www.ppcoin.org/static/ppcoin-paper.pdf).  Elsewhere I have attempted to criticize PPCoin as well, along slightly different lines (an effort that I am still working on -- see https://bitcointalk.org/index.php?topic=202573.0).

I am not implying that it is impossible to make a more efficient coin than Bitcoin.  Also, I am not implying that PPCoin is insecure simply because it references that paper.  However, I did want to point out the apparent flaws in that paper's arguments, which if genuine, imply that it should not be relied on.

[1714165600]

1714165600

[1714165600]

1714165600

[melvster]

I think there is a possible flaw in the Ben Laurie paper on Bitcoin, called "Decentralized Currencies are Probably Impossible, But Let's At Least Make Them Efficient" (http://www.links.org/files/decentralised-currencies.pdf).

If I may summarize his argument:
1. Bitcoin is inefficient, because it may require as much as 51% of the world's computer power to protect against a 51% attack.
2. Bitcoin solves this problem by doing periodic checkpoints, which are snapshots of the currency at a point in time beyond which its history cannot be rolled back.
3. These checkpoints use some other form of consensus which is more efficient than Bitcoin, but still secure and presumably decentralized, otherwise Bitcoin is not secure and decentralized.
4. He calls this hypothetical checkpointing mechanism "efficient unbounded agreement", and then claims that a more efficient coin than Bitcoin can be built on the basis of that mechanism alone.

The flaw in his argument, it seems to me, lies in assuming that the efficient unbounded agreement mechanism can somehow be separated from Bitcoin as a separate standalone protocol.  Checkpointing is merely freezing Bitcoin at a moment in time and refusing to roll back any transactions before that time.  Checkpointing relies on the assumption that the original Bitcoin proof-of-work is robust and secure, so that it is quite unlikely that a sustained attack can be made longer than a given period of time on the original Bitcoin protocol, thus it is presumed safe to checkpoint after that time.

However, checkpointing is only a secondary protocol that is not capable of standing on its own as the basis for a coin.  Checkpointing is merely a secondary validation of a primary security model.  Thus his conclusion, which essentially seems to say that we should throw out the Bitcoin and keep the checkpointing, is false and unworkable.

An analogy might be made with credit card security.  Imagine that credit cards have all their existing security mechanisms, plus you can't do chargebacks after 30 days.  An analogy to Ben Laurie's argument would be claiming that you can do away with all other card security and simply refuse to accept chargebacks after 30 days, and that would be just as secure as before.  That of course would be false, since a limit on chargebacks would just be a secondary security mechanism that can't stand on its own.

I bring this up because the PPCoin paper references this paper and seems to rely on it (http://www.ppcoin.org/static/ppcoin-paper.pdf).  Elsewhere I have attempted to criticize PPCoin as well, along slightly different lines (an effort that I am still working on -- see https://bitcointalk.org/index.php?topic=202573.0).

I am not implying that it is impossible to make a more efficient coin than Bitcoin.  Also, I am not implying that PPCoin is insecure simply because it references that paper.  However, I did want to point out the apparent flaws in that paper's arguments, which if genuine, imply that it should not be relied on.

Ben's argument is quite black and white, where the actual truth is nuanced.

He's saying that the developers are a central point of failure.

My greatest fear is a controversial change that the foundation and most core devs may be in favour of, but many community members may be against.

It's not that hard to propose something that splits opinion, divide and conquer.

If the community remains robust bitcoin will grow in strength.  It's one of the strongest open source communities I've seen. 

So Ben is right, in that community and developer consensus are a potential point of failure, but same is true of linux etc.

But his mistake is that he assumes that an attack surface remains constant invariant of how many eggs you put in that basket ... ripple is a 100% consensus model, and it's unclear that it will be any more robust than btc ... and may be lest, time will tell ...

[LaggedOnUser]

That's true, he is making a black-and-white argument, where I am making a more probabalistic or practical argument.  The agreement system of checkpointing is a working agreement system, it just has different practical characteristics than Bitcoin so I don't consider it as a possible stand-alone protocol.  It lacks the strength of the original.

Also I see what you're saying about the developers.  They could either displease the majority of users, resulting in a permanent fork, or a schism could arise among the developers themselves, also resulting in a permanent fork, although they would have to be convincing to drag a significant number of users with them.  So far this has not happened.  In all of the forks in the open source world, I don't personally recall any that actually destroyed their project.

This reminds me of some new features introduced into Gnome/Ubuntu, that a loud minority of users rejected, or else the split of OpenOffice into LibreOffice.  While somewhat damaging, the community did survive.

[BubbleBoy]

However, checkpointing is only a secondary protocol that is not capable of standing on its own as the basis for a coin.  Checkpointing is merely a secondary validation of a primary security model.  Thus his conclusion, which essentially seems to say that we should throw out the Bitcoin and keep the checkpointing, is false and unworkable.

Checkpointing can be separated from the proof-of-work chains. You can just make the developers publish a checkpoint at 10 minute intervals. If the devs are to be trusted, then you lose no security. And if the devs are not to be trusted, you shouldn't accept any kind of checkpoints from them, even after 10 months, because they could easily rewrite history regardless of how much proof of work was accomplished in the real chain. So on it's face, the argument is sound.

The real failure of Ben is that he does not allows for different convergence times of complementary algorithms. Proof of work is a fast convergence algorithm that gives you some assurance against double spend in a few minutes. Community vetted checkpoints are a slow convergence algorithm which gives a stronger assurance; but it could take days or weeks until the treachery of the checkpointer is demonstrated and the community agrees to trust another dev/implementation/checkpoint provider. So by using both mechanisms you get the best of both worlds.

Another failure related to point 1 I've identified at the time, and posted a comment on his site:

The Bitcoin eligible voters are not “the majority of computing power in existence” because computing power is not a fungible, homogeneous substance. You can easily see a 10^4 performance ratio on specialized versus commodity hardware (ASIC vs CPU), so that the Bitcoin network becomes impervious to attack if it makes up only 0.01% of the “computing power of the world” as expressed in transistors*Hz. Rather, Bitcoin, like most other currencies in the world, is up against any adversary more financially powerful than it’s backers (the miners). So if you are willing to invest more than the compounded mining profit, you can take the majority vote and influence consensus, by expanding the computing power of the world in the form of efficient mining machines.

It’s pretty clear that rewriting the history is not equivalent with stealing everybody’s money, rather it means destroying the system and making the coins worthless, so the likely attackers will not be profit-motivated by any definition of profit expressed in bitcoins. We could talk about governments, banks, competing currencies, lulz etc. It’s only a matter of speculation if an attacker likely to act in such a manner exists. Furthermore, as the network expands the window of opportunity closes to exclude small scale lulz-motivated attackers, and allow only governments or large corporations. The hashing power of the network already surpasses what could be accomplished by ~10 million commodity PCs, excluding even the largest botnets as worthy attackers.

Comment by BubbleBoy — 6 Jul 2011 @ 15:39

[Etlase2]

That's true, he is making a black-and-white argument, where I am making a more probabalistic or practical argument.  The agreement system of checkpointing is a working agreement system, it just has different practical characteristics than Bitcoin so I don't consider it as a possible stand-alone protocol.  It lacks the strength of the original.

I consider it possible as a stand-alone protocol. I also think it is much stronger. See sig.

Also I see what you're saying about the developers.  They could either displease the majority of users, resulting in a permanent fork, or a schism could arise among the developers themselves, also resulting in a permanent fork, although they would have to be convincing to drag a significant number of users with them.  So far this has not happened.  In all of the forks in the open source world, I don't personally recall any that actually destroyed their project.

This is more than just your average piece of open source software. Developers should not have the power to fracture the community, it isn't good for anyone.