Guard against 51% attack?

[hacknoid]

I was thinking about all the talk about the hashing power currently held by GHash.IO (currently, or whichever the largest pool is that starts to get close to 50% hashing power).  There is also the recurring talk about how an entity with enough cash could just create enough hashing power to take over effective control of the blockchain.  I was pondering whether this could be guarded against.

Could we not implement a change whereby any single entity that was approaching a calculated 50% of the hashing power (based on blocks found) would have to mine at an increased difficulty, increasing exponentially as they approached 50%? 

Now I am not proposing a whole solution here, just an idea.  I don't know how to exactly determine which pool found the blocks; I know blockchain.info lists that info but I assume that is based on the receiving address of the new coins. 

The downside is that any large pool would attempt to hide its size by not appearing as a single entity.  But maybe there is a way to overcome that?  Use IP address or something?  I don't know.  Is there anything else that uniquely identifies the pool that found a block?

The advantage is that it becomes less desireable for a single pool to be greater than a certain size, else its probability of finding blocks starts to go down.  This would guard against a single entity trying to add enough hashing power to just overtake the network, but would not help in the event of a distributed "attack" or collusion among pools.

Seems like this issue is one that will not go away (not surprisingly) so it needs to be addressed if it can be.  Maybe it can't. 

Thoughts?

[Olly_K]

Pools need to be competitive.

At no other pool (that I know of) offers me the option of mining 4 coins with 0% fees.

[e521]

The solution shouldn't be based on pool hashrate as a person can setup multiple pool and then switch to perform a 51%

[ButchHashidy]

Would it be beyond reason or scope for developers of bitcoin to implement a hybrid proof of stake / PoW system?  Is it too late to do this?  This gives much more security to the chain as it requires both 51% of all coins AND 51% of network hash to be owned by one person or pool.

[hacknoid]

The solution shouldn't be based on pool hashrate as a person can setup multiple pool and then switch to perform a 51%

Yeah and that's the obvious flaw I concede with this proposal.  That's why I was wondering if there is some other way to verify that blocks come from a single pool?  Maybe there is no way...

I guess an alternative would be to have "licensed" pools, so that a license would be required to have valid blocks, but that goes against the distributed and uncontrolled nature of Bitcoin. There is (and should be) nobody to issue them.

[hacknoid]

Would it be beyond reason or scope for developers of bitcoin to implement a hybrid proof of stake / PoW system?  Is it too late to do this?  This gives much more security to the chain as it requires both 51% of all coins AND 51% of network hash to be owned by one person or pool.

Interesting solution.  Apparently discussed before, for example, here.

While I have strong faith in Bitcoin and in general in the community, this issue does concern me, especially with the way mining is going.  I'm just thinking there has to be a solution, hopefully without requiring a hard fork.

[oakpacific]

Would it be beyond reason or scope for developers of bitcoin to implement a hybrid proof of stake / PoW system?  Is it too late to do this?  This gives much more security to the chain as it requires both 51% of all coins AND 51% of network hash to be owned by one person or pool.

Interesting solution.  Apparently discussed before, for example, here.

While I have strong faith in Bitcoin and in general in the community, this issue does concern me, especially with the way mining is going.  I'm just thinking there has to be a solution, hopefully without requiring a hard fork.

I haven't really taken time to look into PoS, but it sounds extraordinarily stupid to me: if I were a botnet operator who insert millions of nodes into the network to broadcast my fake PoS blockchain, which can be easily made because there is no requirement on the amount of work, how do you know which chain is real? Also what if several people controlling large stakes are kidnapped and forced into give their private keys?

[TierNolan]

I haven't really taken time to look into PoS, but it sounds extraordinarily stupid to me: if I were a botnet operator who insert millions of nodes into the network to broadcast my fake PoS blockchain, which can be easily made because there is no requirement on the amount of work, how do you know which chain is real? Also what if several people controlling large stakes are kidnapped and forced into give their private keys?

PoS needs some kind of boot-strap.  Most of the current systems are hybrids.  PPCoin has POW and POS blocks.  They aren't exactly clear on what their system is though (at least last time I checked).

You can get a mint reward by finding a POW block and you can get a POS reward by consuming coin-age.

When comparing 2 forks, only POS from before the fork should be considered.  If the fork point is at the genesis block, then POS cannot be used to distinguish between the chains.

A release strategy for a "pure" POS coin might be

- coin starts as a POW coin
- assume 50,000 blocks per year
- after 60,000 blocks have been found (14 months)
-- snapshot the 50,000th block as a checkpoint
-- release new client with that checkpoint hardcoded
-- broadcast checkpoint digitally signed by devs/trusted people (N of M rule)
- after 70,000 blocks have been found (17 months)
-- initial client will not accept blocks unless it has received the checkpoint

This generates a base of stake for the POS system.  A year should be enough time so that no one person has a large portion of the stake.

[runam0k]

Pools need to be competitive.

At no other pool (that I know of) offers me the option of mining 4 coins with 0% fees.

Which has to make you wonder, no? Maybe GHash.IO is too good to be true - maybe their motives lie not in profit but elsewhere. (Tin foil hat.)

[oakpacific]

I haven't really taken time to look into PoS, but it sounds extraordinarily stupid to me: if I were a botnet operator who insert millions of nodes into the network to broadcast my fake PoS blockchain, which can be easily made because there is no requirement on the amount of work, how do you know which chain is real? Also what if several people controlling large stakes are kidnapped and forced into give their private keys?

PoS needs some kind of boot-strap.  Most of the current systems are hybrids.  PPCoin has POW and POS blocks.  They aren't exactly clear on what their system is though (at least last time I checked).

You can get a mint reward by finding a POW block and you can get a POS reward by consuming coin-age.

When comparing 2 forks, only POS from before the fork should be considered.  If the fork point is at the genesis block, then POS cannot be used to distinguish between the chains.

A release strategy for a "pure" POS coin might be

- coin starts as a POW coin
- assume 50,000 blocks per year
- after 60,000 blocks have been found (14 months)
-- snapshot the 50,000th block as a checkpoint
-- release new client with that checkpoint hardcoded
-- broadcast checkpoint digitally signed by devs/trusted people (N of M rule)
- after 70,000 blocks have been found (17 months)
-- initial client will not accept blocks unless it has received the checkpoint

This generates a base of stake for the POS system.  A year should be enough time so that no one person has a large portion of the stake.

Thanks, so they can't get rid of that "trusted/centralization" part right?

Also your ISP maybe playing con tricks on you and you never get the right checkpoints, with Bitcoin you simply verify if your most recent blocks took millions to produce by checking if the hash is right(you need to have a rough idea of the height of the chain as well), and if you only ever going to spend several thousand USDs, most likely nobody will try to attack you this way.

[TierNolan]

Thanks, so they can't get rid of that "trusted/centralization" part right?

It is just a once off thing.

A better way to think of it is that the POW stage is an initial "fair" giveaway stage.  Once it is done, the checkpoint is part of the protocol.

The chain is defined as having a particular hash as genesis and that block 50000 hashes to <checkpoint hash>.  The only difference is that it takes a while to find the 50000th block.

If you joined after the 50000th block, there is no difference between the hard-coding the genesis block into the client (which Bitcoin does too) and hard-coding the 50000th block.

It is fully p2p after the 50000th block.

Also your ISP maybe playing con tricks on you and you never get the right checkpoints

There is only 1 checkpoint and it has to be signed by the original developer (or group of trusted individuals).  They promise to only sign one checkpoint.

The ISP can't fake that signature.  The checkpoint signature would be part of the protocol.

They can't really stop you from getting the signature.  It only happens once, and they would have to scan everything that goes to you to block it.  This would require blocking you from making any encrypted connection at all.  That isn't feasible.

[NewLiberty]

Another guard against 51% that has been suggested is hash alternation.
In this method, alternating blocks would use different hash functions.  This would limit the ability to mine sequential blocks with consolidated ASICs.
Forseeably this may need more than two hash functions eventually if further concentration of computing occurs.

It would be good to see an alt-coin do this with scrypt+sha256^2 so that we can see how it works in the wild.

Such a coin could be merge mined with litecoin and bitcoin.

[gmaxwell]

"Hash alternation" doesn't do anything interesting except if no one cares about the coin in question... a single part can be made that does N functions, and you even can get some density advantages since part of the circuit will be power gated half the time.

Most of these "51% problem" posts and their laughable "solutions" seem to stem from really having no concept of what Bitcoin is actually doing.  Bitcoin decides virtually everything trustlessly, but there is no way to have a autonomous, decentralized, and universally consistent view of ordering— it's physically impossible because your view of what order events happen depends on your relative positions— so in Bitcoin we compromise autonomy and use an election to determine transaction ordering (and only ordering!).

Elections online aren't secure— especially not if they're anonymous—, someone will just adopt N identities and stuff the ballot. So instead we give up the pretext of being "fair" and instead require the voter to sacrifice something scarce and valuable (electrical power) to build a cheaply verified proof in order to participate in the election... then hope than an economic alignment is created: people spend their valuable power only on the one chain that is most likely to be the surviving consensus.  Of course, any time you have an election you permit the majority to overrule the minority— the alternative is that the minority overrules the majority.

PoS, sadly, doesn't appear to be workable for providing the scarcity in such a system. The problem with proof of stake is that, ironically, there is nothing at stake: if your stake mining doesn't make it into the longest chain you've lost nothing. So you get attacks like stake miners considering all possible forking histories in order to computationally search out histories where their stake is selected every block (how lucky!) and these attacks have actually been performed against deployed systems. You can try to patch around this (e.g. by bringing PoW back and using PoW to do the stake election) but it's really just disguising a far more fundamental shortfall that in PoS because you lose nothing in mining forks (or at least any possible fork that doesn't reverse payments to you and yours) thats the overwhelmingly best rational way to mine... so in a hypothetical world where users were short-term-rational PoS would instantly fail, and even in the real world there turn out to be ugly attacks.

Sure, if you want to do things like having a developer broadcasting block signatures you can get something that is hard for an anonymous party to attack— of course it's then at the whim of the developer to trigger a huge reorg, partition the network, etc... and if you want that kind of centralization you can create a far far more efficient system than a blockchain.

[TierNolan]

PoS, sadly, doesn't appear to be workable for providing the scarcity in such a system. The problem with proof of stake is that, ironically, there is nothing at stake: if your stake mining doesn't make it into the longest chain you've lost nothing.

You could get around this by incorporating failed stake back into the main chain.  Stake from after the fork point would have to be ignored when comparing forks.  This makes the comparison more computationally intensive.

Each stake "credit" gets to sign exactly one block header.  If you sign a block header, it gets added to the header tree, even if orphaned.  If you sign a 2nd block header, then both signatures get added to all leaves. 

[oakpacific]

Thanks, so they can't get rid of that "trusted/centralization" part right?

It is just a once off thing.

A better way to think of it is that the POW stage is an initial "fair" giveaway stage.  Once it is done, the checkpoint is part of the protocol.

The chain is defined as having a particular hash as genesis and that block 50000 hashes to <checkpoint hash>.  The only difference is that it takes a while to find the 50000th block.

If you joined after the 50000th block, there is no difference between the hard-coding the genesis block into the client (which Bitcoin does too) and hard-coding the 50000th block.

It is fully p2p after the 50000th block.

Ah, I see, so no mining will happen after the 50000th block right? The only way to get any coin afterwards would be to obtain from those who already have it?

Also your ISP maybe playing con tricks on you and you never get the right checkpoints

There is only 1 checkpoint and it has to be signed by the original developer (or group of trusted individuals).  They promise to only sign one checkpoint.

The ISP can't fake that signature.  The checkpoint signature would be part of the protocol.

They can't really stop you from getting the signature.  It only happens once, and they would have to scan everything that goes to you to block it.  This would require blocking you from making any encrypted connection at all.  That isn't feasible.

While hardcoding in the Bitcoin client remains the status quo, I would have no problem telling a fake chain from the real one without such hardcoding, as I could always check if the difficulty of the newest blocks meet the right target, assuming no one is attacking me with a hundred million-dollar farm of  course, it is on the other hand much easier to just change the content of a software as the cost for hijacking a communication channel is much lower, also the developer may have difficulty proving himself to be the...developer without an external authority, similar things happened in the countless cases of internet scams.

[TierNolan]

Ah, I see, so no mining will happen after the 50000th block right? The only way to get any coin afterwards would be to obtain from those who already have it?

It could be.  In theory, "interest" payments could be made to stake holders who find POS blocks.  It would depend on the specifics.

The main point is that you need stake ownership to be distributed or you are back where you started.  If one person has 51% of the stake, you could be back where you started.

While hardcoding in the Bitcoin client remains the status quo, I would have no problem telling a fake chain from the real one without such hardcoding, as I could always check if the difficulty of the newest blocks meet the right target, assuming no one is attacking me with a hundred million-dollar farm of  course, it is on the other hand much easier to just change the content of a software as the cost for hijacking a communication channel is much lower,

The reason for checkpoints in the client is that you could spam someone with lots of low difficulty blocks to use up their bandwidth.  Each block can be 1MB.  As long as 2016 blocks takes at least 2 week, the difficulty per block will remain at the lowest possible.  Bitcoin was launched 3rd January 2009.  That is roughly 5 years.  At 1008 blocks per week, that is 262080 blocks.  In practice, there are more blocks and that is the reason difficulty rose.

This means that you could send someone 262080 fake blocks of padded transactions without the difficulty rising.  It would be reasonably cheap to create them.  That is 262GB of data that you can flood a node with and it is a perfectly valid chain.

With "headers-first", that is less of a concern.  When syncing the client asks for headers first.  This allows the client find the best chain first and then start downloading the data.  Headers are only 80 bytes, so 262080 fake blocks would only result in a download of around 20MB.

If a client connected to 7 hostile nodes and 1 honest node, the total download spent on headers would be 160MB instead of the normal 20MB.  Once the client had all the headers, it would know which node was the honest one.

also the developer may have difficulty proving himself to be the...developer without an external authority, similar things happened in the countless cases of internet scams.

The developer would just hardcode his public key into the software.  The client could just check that the message is signed by him.

In practice, it would be better if there was multiple people with the keys.  Those people should be trusted and distributed over the planet (for protection against court orders).

The checkpoint would have to be signed by M of N of them.  For example, there could be 9 public keys hard coded into the client at lauch and the checkpoint has to be signed by at least 6 of them.

[oakpacific]

also the developer may have difficulty proving himself to be the...developer without an external authority, similar things happened in the countless cases of internet scams.

The developer would just hardcode his public key into the software.  The client could just check that the message is signed by him.

In practice, it would be better if there was multiple people with the keys.  Those people should be trusted and distributed over the planet (for protection against court orders).

The checkpoint would have to be signed by M of N of them.  For example, there could be 9 public keys hard coded into the client at lauch and the checkpoint has to be signed by at least 6 of them.

Then there must also be some authoritative, central places for distributing the client as well, these sites have to stay up and running as long as the network is, when billions of dollars are at stake or the governments get involved I don't think they will hold up so well. Yeah Bitcoin uses checkpoint too, but as you have pointed out with a "headers-first" approach we probably can get rid of that, and I can even download the blockchain and check the difficulty first using torrents, without connecting to any node.

[TierNolan]

Then there must also be some authoritative, central places for distributing the client as well, these sites have to stay up and running as long as the network is, when billions of dollars are at stake or the governments get involved I don't think they will hold up so well.

That is true for bitcoin too.  The point of signing the checkpoint is so that v1.0 clients will accept blocks after the checkpoint time.

The software could simply be set to refuse to accept new blocks after a certain height.  This would fork everyone to update at the same time, which has security implications. 

There is no difference between having the dev sign a new client and simply sign the checkpoint.  Signing the checkpoint used up much less bandwidth.

Once the checkpoint has been passed, all clients, from the original dev or others, will simply hardcode the same checkpoint for the 50,000th block.

The checkpoint is part of the protocol.

Yeah Bitcoin uses checkpoint too, but as you have pointed out with a "headers-first" approach we probably can get rid of that, and I can even download the blockchain and check the difficulty first using torrents, without connecting to any node.

I think they will probably leave them in though.

With headers first, they could change them to a lower limit on work. 

If the current chain has a certain amount of POW built in to it, then any possible future chain (including chains which fork) must have more POW than that chain.  Any chain which doesn't is, by definition, a low POW chain.

If the client downloads a chain with 1% of the POW threshold, then the client will assume that it isn't a valid chain.  It would display "syncing to network" or something similar.

[gmaxwell]

If you're willing to accept a system who's "consensus" is determined by some guy's cryptographic signature fiat you can build something _far_ more efficient than a Bitcoin like system.

Basically nothing in this thread has been on-topic for Bitcoin, a system predicated on eliminating— or at least greatly reducing— trust from money like goods. Since no one seems to feel about discussing bitcoin, off to the alt-currencies subforum this goes.

[Wilhelm]

What about a system that rejects blocks if >N blocks in a row go to the same address (minted by the same pool) ?
Basically limiting any pool from finding too much blocks in a row which would only happen if you are either extremely lucky or have a majority of hashingpower.
Pools will want to limit their hashrate due to the fact that they will become inefficient. This will contribute to more pools and an even spread of mining.

Don't know if this can be done or will work...