Quote from: DeathAndTaxes on May 20, 2014, 03:35:09 PM

A 51% attacker would be the one generating the previous block generation signature. If the signature doesn't produce an output that allows him to sign the next block he just changes the k value and generates a new signature. A good CPU can do 40,000 ECDSA signatures a second (per core). When he finds one that allows one of his accounts (51% of the stake) to sign the next block he moves on to the next block.

The attacker doesn't even need a 51% stake. They only need a small stake, once you can forge once, you can ensure that you will always gets to forge the next block (if you have enough computational power), regardless of how small your stake is. I can easily see this attack being possible with 0.1% stake and a standard processor.

Quote from: DeathAndTaxes on May 20, 2014, 03:35:09 PM

As a side note: deterministic (or quasi deterministic) signing/minting/forging is an interesting idea. It has some advantages (outside of a 51% attack) if combined with a PoW. It would make long reorgs with a minority of the hashrate more difficulty to achieve which means confirmations have more "weight". It also allows "legit" miners to achieve consensus quicker. In the case where two miners produce blocks at the same block height it could provide a fair and deterministic manner for all nodes to choose one over the other. If miners are confident that 51% of the network follow these rules then they would be best served by working on the "best" block not just the first one. It is beneficial in a split to get the network behind a single chain as quickly as possible (orphaned work is simply wasted work and reduces effective network security). The full implications both good and bad should be looked at more closely. It isn't however some magical 51% proof shield and the "nothing at risk" issue around PoW remains unchanged when compared to other PoS systems.

The problem is that you are still vulnerable to historic attacks. Whilst doing analysis for conceptcoin I have found that deterministic proof of stake (even where the mechanism to select who gets to sign each block is unaffected by the actions of the forgers/miners) is still vulnerable to people signing two blocks at a given block height and releasing one of those blocks whilst keeping one hidden to build an attacking chain in the future. Whilst clients who are always online can tell the difference between the real and fake chain, new clients can't.

One way to tell them apart is by assigning work to the chain, this work does not decide who gets to sign blocks. I have proposed a scheme where when a block is being signed it must optionally include a piece of work which is as close to the previous block hash as possible. This work doesn't have to be produced by the signer themselves, everyone submits work to the network to show that they endorse a particular block. It is in the interest of the honest block signers to include the maximum amount of work in their blocks in order to prevent attacks.

Now new clients can see which chain is more likely to be the real one by measuring the cumulative work included in each chain. This successfully decouples proof of work from the rewards handed out, people do work as they feel necessary to secure the network. The problem is without direct economic incentives, the amount of work done and hence security may be very low.