Quote from: Gavin Andresen on August 17, 2012, 03:59:25 AM

So while driving across Wyoming today my mind wandered to proof-of-stake. And whether or not it would be possible to attack a proof-of-stake system by repeatedly sending expensive to verify but invalid proofs of stake.

I think you could.

Example: if the proof-of-stake involves creating a bunch of valid signatures using private keys that you own, then an attacker could buy or create a few thousand keys (e.g. buy 10,000 units of currency and then split them into 10,000 addresses) and submit a proof-of-stake where 9,999 signatures are valid and the last one is invalid.

The proof-of-stake will fail, but it will cost the victims approximately the same CPU time to find that out as it takes the attacker to generate the signatures. If the attacker can repeatedly send the same proof-of-stake, and the victims don't cache the work of checking the signatures, then you've got the basis for a great denial-of-service attack.

Proof-of-work doesn't suffer from this attack, because it is MUCH easier to validate proof-of-work (one hash operation) than to generate it. I haven't thought deeply about whether or not you could come up with a proof-of-stake that has the same "hard to generate, easy to validate" property. I suppose you could require that a proof-of-stake have a small, limited number of signatures-- requiring that stakeholders maintain a small number of large-balance addresses. That's bad for privacy and security, though.

You could disconnect/ban peers that submit invalid proofs-of-stake; an attacker would have to mount a Sybil attack using lots of IP addresses to get around that. That might be a problem in an IPv6 world of essentially infinite IP addresses, though...

A hybrid system that requires proof-of-work AND proof-of-stake might work. You'd have to be careful to tie the proof-of-stake to the proof-of-work, though, otherwise an attacker might be able to re-use the same proof-of-work over and over.

I'm curious: if you've been working on a proof-of-stake system, is this kind of attack the kind of thing you've already thought about and solved?

I'm proposing a 4 point proof-of-substance system:
http://litecoinforums.org/index.php?/topic/22-cartel-wars/

Proof of work corresponds to mining.
Proof of stake corresponds to 'hoarding'.
Proof of reach corresponds to pools.
Proof of value corresponds to exchanges.

Each of these contexts has a weakness deeply connected to its fundamental nature.

There is a solution but it will be a combination of all these proofs.

Work prevents inflation without substance. This is solved.
Stake prevents massive attacks on the network. However, quite a few idio... individuals think low balance holders should not be able to participate. Any pool of people carrying a given load of coins should be able to participate in proof of stake.
Proof of reach would encourage pools to branch out and serve different kinds of communities.
Proof of value would help demonstrate initial value to new cryptocurrencies without the initial 2 to 4 year lead time.

I'm particularly concerned that there's an attitude here that high balance is equivalent to the productive potential of the individual, a fallacy even Ayn Rand didn't subscribe to. I sometimes think it's an innate fear that beyond the high asset holdings there's nothing to stop a smarter person from becoming more prominent, and that scares some people.

This is why I choose to support litecoins. Aside from the technical superiority, the infinitely smaller degree of paranoia among litecoiners makes litecoin a saner community.