Probing for Community Interest

[cunicula]

In theory, the threat of a 51% attack is always present.  At what hash rate would you guys consider the risk pretty well mitigated?  I know it depends on the coin, as they're slightly different.  But just looking for a ballpark number.  

At proof-of-stake. I wouldn't accept any plausible hash rate as adequately safe. Wait a few years and bitcoin will start getting ravaged too.

So what's the answer to the problem?  

The root problem is secret mining. Secret miners can replace the public chain with their own secret attack chain. A simple solution is to prohibit secret mining.

Here is a basic outline:
1) Miners search for tentative blocks. Tentative blocks must meet the PoW difficulty target.
2) The PoW solution in a tentative block maps to a sequence of 5 randomly selected satoshis. (i.e. just hash the solution five times and use these five hashes to select random satoshis)
3) Miners publish their tentative blocks and holders of the 5 random satoshis are invited to sign the blocks using their private key. (there are some omitted steps to minimize bandwidth requirements here)
4) If all 5 satoshi holders sign a tentative block, it becomes a valid block and enters the blockchain. (i.e. the only feasible way to get your block into the chain is by publishing it)
5) If not, the tentative block is ignored. Go back to (1). Some other tentative block will be found and enter the blockchain.

Now think about secret mining. Suppose I own 1% of all coins. In order to mine a block AND keep that secret, I need to find a PoW solution for which I own all five randomly selected satoshis.
The chances of a PoW solution satisfying this criteria is 1 in [1/(0.01)]^5 or 1 in 10 billion. Therefore, mining secret blocks requires 10 billion times the hashing power of mining public blocks.
With these rules, a small chain with say 1 cpu worth of hashing power protecting it (say 3 megahash) requires 30 Terahash of computing power to successfully attack. That is one single CPU would be a sufficient defense against an attacker controlling the entire bitcoin network. One GPU could defend against 100 bitcoin networks simultaneously.

[Another solution is PPCoin. It is nowhere near this robust, but it might be good enough.]

[Meni Rosenfeld]

Not according to the wiki:

Code:

The wiki is simply wrong about this (I'll try to edit it sometime). No amount of confirmations is enough to prevent double-spending by someone with more than 50% of the hashrate. 6 confirmations is a completely arbitrary number considered secure enough against an attacker with "typical" hashrate (say, 10%).

[c4n10]

If there are quite a few nodes running, and they are running updated code that includes a checkpoint that happened since you got your coins, then possibly your coins might be reasonably safe as long as an attacker does not publish a different copy of the node code that contains a different set of checkpoints that feature their fork of the chain instead of the version of the chain in which you got your coins.

Consider for example an Open Transactions server that obtained a bunch of coins many many months ago, and several new versions of the client have come out since then, each one adding another checkpoint which favours the chain in which those coins were obtained.

To reverse those coins would involve going massively far back in time and would be refuted by the last several checkpoints that are already hard-coded into the current batch of nodes that are currently running.

Possibly in that circumstance the tokens the Open Transactions server is backing with those ancient well established coins can be considered to be fairly securely backed by actual coins. Such tokens could even in some ways be considered more secure than any recently mined actual coins.

Still though if a time ever came when there was no more demand/need for the tokens, so that it was time to liquidate, deleting the tokens and sending out the actual coins they represent, an attacker would at that point have an opportunity to try to mess up the actual transfer on the blockchain of those coins. So the liquidation could take a while, involving sending out the coins then waiting a few hardcoded checkpoints before regarding them as having been reasonably securely sent to their new owners.

This is basically why I try to release new versions of node software from time to time with new checkpoints coded in. I hope that over time doing so will eventually make it reasonable to consider the coins backing my tokens as actually fairly secure in their cold wallets so that the tokens are somewhat securely backed by actual coins.

-MarkM-

You know, perhaps I overlooked your idea too soon, if there were some way to make bitcoin and all the alt-coins automatically update and write in "landmark" blocks where everything that the chain has followed up to that mark is considered permanent no matter what alt-chain is introduced. It would need to be automatic though because the checkpoints would need to be frequent, maybe every 10-12 blocks. Maybe less for some coins.

I apologize for not considering your idea more deeply the first time around...

[Meni Rosenfeld]

You know, perhaps I overlooked your idea too soon, if there were some way to make bitcoin and all the alt-coins automatically update and write in "landmark" blocks where everything that the chain has followed up to that mark is considered permanent no matter what alt-chain is introduced. It would need to be automatic though because the checkpoints would need to be frequent, maybe every 10-12 blocks. Maybe less for some coins.

I apologize for not considering your idea more deeply the first time around...

Having frequent, automated, temporal checkpoints leads to exactly the same chaos and vulnerabilities that made the blockchain needed in the first place.

Bitcoin has infrequent, hardcoded checkpoints - this works. Checkpoints based on PoS (as in my proof of stake system) might work. I haven't read up the probabilistic PoS discussion yet, but that could work too.

[cunicula]

Having frequent, automated, temporal checkpoints leads to exactly the same chaos and vulnerabilities that made the blockchain needed in the first place.

Bitcoin has infrequent, hardcoded checkpoints - this works. Checkpoints based on PoS (as in my proof of stake system) might work. I haven't read up the probabilistic PoS discussion yet, but that could work too.

You should definitely read the updated PoS wiki. I think my proposed probabilistic system, an elaboration of Colbee's PoA, has very nice properties.
I need input from smart people. I may have made mistakes. Unless you point them out, I may not notice and fix them.

Even if I didn't make mistakes, I still need feedback so I can improve the exposition (I'm bad at that).

[Insu Dra]

if there were some way to make bitcoin and all the alt-coins automatically update and write in "landmark" blocks where everything that the chain has followed up to that mark is considered permanent no matter what alt-chain is introduced.

And how would that work, how would you decide when a automated "landmark" is valid or not ? If you automate and decentralize the "landmark" creation you end up with same problem you started with.

If the attacker and manages to get 51% of the hashing power to setup his chain + his landmarks then what ? If he can't convince other peers he can still pretend by making sure he has 51% of nodes (network communication) as well. The result would fork the whole network and every new client would accept his longer chain ...

Web of Trust ? again you risk forking the chain between web's ...

"Landmarks" sound cool but unless there is a central authority managing them they don't solve anything.

You should definitely read the updated PoS wiki.
Even if I didn't make mistakes, I still need feedback so I can improve the exposition (I'm bad at that).

I'm lazy, if you tell people to read at least add a link plz

Edit:
for other lazy people https://bitcointalk.org/index.php?topic=127314.0

PoS ? Looks like a interesting and feasible option to me.

To get back on topic you would need to make sure every alt chain on the exchange is secured against double spend and atm I don't trust any of them. (Btc (maybe Ltc) is (are) the only one(s) that has (have) the hashing power to be semi secure.)