Topic: DoS attacks on proof-of-stake (Read 2809 times)

From the whitepaper:

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.

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.

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

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

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

From the whitepaper:

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.

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.

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

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.

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.

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

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.

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.

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.

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?