DoS attacks on proof-of-stake

[Gavin Andresen]

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?

[NASDAQEnema]

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.

[Revalin]

Adding a small proof of work would probably solve it.  Include a timestamp and nonce in the block, take a SHA256 of the whole thing, and set the difficulty so that it's a few million times harder to generate than to verify, and don't accept blocks that are more than a few minutes old.  The difficulty could be static because there's no need to keep up with Moore's law - it doesn't really matter if they can produce bad blocks more quickly in the future because the cost to verify will also decline.

[Sunny King]

There are different ways of designing proof-of-stake. Some of the designs do not require collecting large number of signatures. Our design will be made public by the coming Sunday so in due time we welcome the crypto-currency/Bitcoin community to examine our design.

[jl2012]

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.

Privacy is not a issue here. Although you may use multiple addresses with smaller balance, the fact that they are signing the same block reveals their common ownership

Security is a problem, even people may use multiple addresses with smaller balance. This actually requires stakeholders to put those private keys in a hot wallet. A possible solution is to have separate keys for block-signing and transaction-signing. We may use the transaction-signing private key to validate the block-signing private key.

There even could be a "pooled proof-of-stake mining" model. A pool operator will publish a transaction-signing public key. Individual workers will sign this public key with their transaction-signing private keys (which link to BTC addresses with balance).

When a block is found, the pool operator will sign it with the block-signing private key, and the contribution from his workers will be counted as proof-of-stake. The operator will then pay his workers based on their contribution. Each block will allow only one signature and that would also solve your DoS problem.

Signatures for transaction-signing public key may be stored in the blockchain. The size would be similar to normal transactions and fee is required to prevent DoS. If the worker wants to withdraw from the pool, he may revoke his signature by sending another record to the blockchain, or simply draw all BTC from that address. For lost coins, however, such revocation is not possible. Therefore, all signatures should be expired in a pre-determined manner (e.g. valid for only 10000 blocks).

[MAD_MAD]

There are different ways of designing proof-of-stake. Some of the designs do not require collecting large number of signatures. Our design will be made public by the coming Sunday so in due time we welcome the crypto-currency/Bitcoin community to examine our design.

Like I said in your other thread, it would be very nice of you to provide some kind of whitepaper, or even a mere "this is how our tech works" forum post.

Keeping people "intrigued" by your technological promise is an old and annoying marketing ploy.

Satoshi didn't start with "I have tech, but I won't show you it" publication.

[cunicula]

There are different ways of designing proof-of-stake. Some of the designs do not require collecting large number of signatures. Our design will be made public by the coming Sunday so in due time we welcome the crypto-currency/Bitcoin community to examine our design.

This is correct. The current wiki (https://en.bitcoin.it/wiki/Proof_of_Stake) lists two designs; one with lots of signatures, the other with no signatures at all.

There are many other potential ways of incorporating stake. It would be nice to hear what Sunny King implemented. Maybe add something to the wiki entry when you make the design 'public'?

[cunicula]

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.

Privacy is not a issue here. Although you may use multiple addresses with smaller balance, the fact that they are signing the same block reveals their common ownership

Security is a problem, even people may use multiple addresses with smaller balance. This actually requires stakeholders to put those private keys in a hot wallet. A possible solution is to have separate keys for block-signing and transaction-signing. We may use the transaction-signing private key to validate the block-signing private key.

There even could be a "pooled proof-of-stake mining" model. A pool operator will publish a transaction-signing public key. Individual workers will sign this public key with their transaction-signing private keys (which link to BTC addresses with balance).

When a block is found, the pool operator will sign it with the block-signing private key, and the contribution from his workers will be counted as proof-of-stake. The operator will then pay his workers based on their contribution. Each block will allow only one signature and that would also solve your DoS problem.

Signatures for transaction-signing public key may be stored in the blockchain. The size would be similar to normal transactions and fee is required to prevent DoS. If the worker wants to withdraw from the pool, he may revoke his signature by sending another record to the blockchain, or simply draw all BTC from that address. For lost coins, however, such revocation is not possible. Therefore, all signatures should be expired in a pre-determined manner (e.g. valid for only 10000 blocks).

The security issue raised by large balance hot wallets could be dealt with as follows:

1) Create special account used for signing blocks
               account restricted to two valid functions: 1) Sign blocks using coins in special account
                                                                        2) Release coins in special account to user-specified normal account (specified address set permanently when special account is created)
2) Special account is held in hot wallet.
3) User-specified normal account is held offline.

[iddo]

The security issue raised by large balance hot wallets could be dealt with as follows:

1) Create special account used for signing blocks
               account restricted to two valid functions: 1) Sign blocks using coins in special account
                                                                        2) Release coins in special account to user-specified normal account (specified address set permanently when special account is created)
2) Special account is held in hot wallet.
3) User-specified normal account is held offline.

Good idea. I've described a similar suggestion for PoS protocol design outline on MeniRosendfeld's wiki talkpage at https://en.bitcoin.it/wiki/User_talk:Holy-Fire, so I'll also quote the relevant part here:

We basically want a digital signatures scheme in which the keygen generates a triple (privkey1,privkey2,pubkey0) where privkey1 and privkey2 are unrelated to each other, you can sign either with privkey1 or with privkey2, and verify the resulting signature with pubkey0. It'd be used for PoS by using privkey1 to do actual txns and using privkey2 only for providing the PoS signatures to the signatures blocks. This means that if privkey2 gets stolen then it doesn't amount to much, you can transfer your bitcoins to another address and re-generate a new privkey2 for it, so it's ok to store privkey2 in the clear.

We cannot implement this scheme directly with ECDSA, but we can do something that's pretty close: simply by having two pairs (privkey1,pubkey1) and (privkey2,pubkey2) and linking between them, e.g. by signing with privkey1 a message that says that pubkey2 is the public key of your 2nd pair, and from then on you can start using privkey2 to provide the PoS signatures.

What it would mean for the blockchain is that when you provide a STAKEMSG, there would be an additional field that you can include in it, and this field would contain pubkey2, meaning that starting from the next checkpoint block you are allowed to use privkey2 in order to provide signatures for the address that's controlled by privkey1.

The pubkey that would be extracted from subsequent STAKEMSGs is pubkey2 rather than pubkey1, therefore in order to tell how many bitcoins are controlled by those STAKEMSGs we store in every STAKEMSG an additional field that specifies the height of B->count relative to the block in which pubkey1 and pubkey2 were linked (and then the protocol rule would be that only this particular linkage should be respected). If we use e.g. 3 bytes for the relative height field, then privkey1 will be needed to create a new linkage block after about 320 years (assuming 10min blocks).

Note: if the pubkey2 field of STAKEMSG is empty then the signature field of STAKEMSG signed just B->hash, and if the pubkey2 field of STAKEMSG isn't empty then the signature field of STAKEMSG signed "B->hash + pubkey2".

With ECDSA signatures are 512 bits and compressed pubkeys are 258 bits, so it's not so bad because the STAKEMSGs with the extra pubkey2 field would be infrequent. In fact, we can save more space by defining the protocol so that only hash(pubkey2) is put in the extra field, because of the feature of ECDSA that you can extract pubkeys from signatures. This means that the extra field can be just (say) 128 bits hash, but more computing power will be needed to verify the signatures blocks.

This means that you wouldn't need to enter your passphrase in order to provide PoS signatures, so that the client app can work automatically, as preferred.

See the rest at https://en.bitcoin.it/wiki/User_talk:Holy-Fire#Proof_of_Stake_design_outline

You said "specified address set permanently when special account is created". In case it's a protocol that extends the existing Bitcoin protocol, the linkage between this special address and its corresponding locked normal address will have to be put in the blockchain, so whenever the special address wishes to transfer some of its coins to the locked normal address, all the nodes must look at the old block where the linkage was made in order to verify it. Therefore I'm not sure whether your suggestion is more efficient than my suggestion. There could also be disadvantages from the user's standpoint, because he has to transfer his coins before he can spend them.

Regarding Gavin's DoS concerns, in the simple PoS design outline that I described it's handled by hardcoded cutoff constant, meaning that an address cannot provide a PoS signature if it holds less coins than the cutoff amount. This is need also in order to prevent bloat in the blockchain, otherwise anyone with 1 satoshi could try to provide PoS signatures...

[paraipan]

@OP, Gavin is that you? Are you ok dude? Didn't you find out what happened to solidcoin alt chain?

[MAD_MAD]

Well, it had a rather poor proof-of-stake design, didn't it?

[Gavin Andresen]

There are different ways of designing proof-of-stake. Some of the designs do not require collecting large number of signatures. Our design will be made public by the coming Sunday so in due time we welcome the crypto-currency/Bitcoin community to examine our design.

From the whitepaper:

The block chain with highest total consumed coin age is chosen as main chain.

I'd have to think about it a lot harder than I'm willing to right now to be absolutely sure, but that seems like a mistake to me.

If peers have to fetch inputs and compute coin age to determine whether or not a chain is longest then it seems like that could be leveraged into a denial-of-service attack. Because an attacker could do minimal proof-of-work (or proof-of-stake) but then broadcast a chain with JUST a little-less consumed coin age than the current best chain.

Their chain will be rejected, but their peers will waste time figuring out that it should be rejected.

Also note that Bitcoin does NOT use total proof-of-work-performed to determine the best chain; it uses total proof-of-work-target. That's deliberate; if it used proof-of-work-performed, then if you happened to get lucky and found an extremely small block hash you could hold on to it, build on top of it, and only announce your "more proof of work" chain when the network chain's work started to catch up with your secret chain.

[cunicula]

There are different ways of designing proof-of-stake. Some of the designs do not require collecting large number of signatures. Our design will be made public by the coming Sunday so in due time we welcome the crypto-currency/Bitcoin community to examine our design.

From the whitepaper:

The block chain with highest total consumed coin age is chosen as main chain.

I'd have to think about it a lot harder than I'm willing to right now to be absolutely sure, but that seems like a mistake to me.

If peers have to fetch inputs and compute coin age to determine whether or not a chain is longest then it seems like that could be leveraged into a denial-of-service attack. Because an attacker could do minimal proof-of-work (or proof-of-stake) but then broadcast a chain with JUST a little-less consumed coin age than the current best chain.

Their chain will be rejected, but their peers will waste time figuring out that it should be rejected.

Also note that Bitcoin does NOT use total proof-of-work-performed to determine the best chain; it uses total proof-of-work-target. That's deliberate; if it used proof-of-work-performed, then if you happened to get lucky and found an extremely small block hash you could hold on to it, build on top of it, and only announce your "more proof of work" chain when the network chain's work started to catch up with your secret chain.

To avoid the potential problem raised by Gavin, you might consider a mixed proof-of-work, coin-age target.
(see the proof of stake wiki for my outline of this) 

[paraipan]

...
To avoid the potential problem raised by Gavin, you might consider a mixed proof-of-work, coin-age target.
(see the proof of stake wiki for my outline of this) 

Care to share the link with us Paul? Have some spare time to read on it right now

[cunicula]

Care to share the link with us Paul? Have some spare time to read on it right now

lol, https://en.bitcoin.it/wiki/Proof_of_Stake

[paraipan]

Care to share the link with us Paul? Have some spare time to read on it right now

lol, https://en.bitcoin.it/wiki/Proof_of_Stake

Very kind of you, thanks

[Sunny King]

I'd have to think about it a lot harder than I'm willing to right now to be absolutely sure, but that seems like a mistake to me.

If peers have to fetch inputs and compute coin age to determine whether or not a chain is longest then it seems like that could be leveraged into a denial-of-service attack. Because an attacker could do minimal proof-of-work (or proof-of-stake) but then broadcast a chain with JUST a little-less consumed coin age than the current best chain.

Their chain will be rejected, but their peers will waste time figuring out that it should be rejected.

Also note that Bitcoin does NOT use total proof-of-work-performed to determine the best chain; it uses total proof-of-work-target. That's deliberate; if it used proof-of-work-performed, then if you happened to get lucky and found an extremely small block hash you could hold on to it, build on top of it, and only announce your "more proof of work" chain when the network chain's work started to catch up with your secret chain.

Meeting the hash target is supposed to be hard (once every 10 minutes in the network). Even though it did not consume energy, you are not supposed to come up with these with ease. If you do come up with some kernel meeting the target, it's probably deserved to be checked by everybody.

[iddo]

From the whitepaper:

The block chain with highest total consumed coin age is chosen as main chain.

I'd have to think about it a lot harder than I'm willing to right now to be absolutely sure, but that seems like a mistake to me.

If peers have to fetch inputs and compute coin age to determine whether or not a chain is longest then it seems like that could be leveraged into a denial-of-service attack. Because an attacker could do minimal proof-of-work (or proof-of-stake) but then broadcast a chain with JUST a little-less consumed coin age than the current best chain.

Their chain will be rejected, but their peers will waste time figuring out that it should be rejected.

DoS attacks is only a secondary problem with this proof-of-stake proposal, the main problem is that this protocol is unsound because it's susceptible to easy double-spending attacks by stakeholders, simply by releasing a forked branch with higher total consumed coin age.
As discussed earlier:
https://bitcointalk.org/index.php?topic=99735.msg1112992#msg1112992
https://bitcointalk.org/index.php?topic=101820.msg1115868#msg1115868