How to Prevent a 51% attack: Multiple PoW algorithms + PoS ???????

[mik3]

Posting this here from reddit as this guys idea seems really interesting:

Could we combine algorithms together?

After reading kuui1's comment[1] I had an idea, but since I'm not a programmer, it might not make sense:
Myriadcoin uses 5 algorithms running concurrently to secure a single blockchain. Each algorithm has the same chance of finding the next block reward and gpus, cpus can mine along w/ sha and scrypt asics. Using a 5 seperate algorithm in this manner means an entity would have to gain the majority of hashing power of the majority of algorithms to achieve a double spend attack which means they'd need far greater than 51%

Now what if we add PoS to this, and have proof of stake coins work as some kind of referee over the miners making sure double spends and transactions cannot be held back. This way the people owning the coins can make sure the people mining the coins are doing so fairly.
This could also work to incentivize running full nodes. What if 5% of the block reward was paid out to the full nodes? Who are also helping do the proof of stake.

The Proof of stake workers could run/oversee 50% of the network while the miners run the other 50% making coins. This way if an evil entity like ghash gets 51%, they'll only have about 25%. (not sure if this makes sense)
Or maybe even forget the whole 5 algorithm thing, stick with what we have now and just add PoS on top?

http://www.reddit.com/r/Bitcoin/comments/282b18/proposal_multiple_pow_algorithms_pos_i_hope_this/

[Raystonn]

Changing the work function of Bitcoin would render all existing mining hardware obsolete.  You will never get the miners to move to this algorithm, as it would be a major financial loss for them.

[CJYP]

Changing the work function of Bitcoin would render all existing mining hardware obsolete.  You will never get the miners to move to this algorithm, as it would be a major financial loss for them.

You don't need the miners to move - just the consensus of the network.
That makes it much harder to push through a change, but the miners don't really have much say if everyone else decides to.

[Raystonn]

Changing the work function of Bitcoin would render all existing mining hardware obsolete.  You will never get the miners to move to this algorithm, as it would be a major financial loss for them.

You don't need the miners to move - just the consensus of the network.
That makes it much harder to push through a change, but the miners don't really have much say if everyone else decides to.

The miners are the ones who process Bitcoin transactions.  Without them, there is no Bitcoin.  This will never work until Bitcoin is dead without such a change.

[venij]

I posted a similar concept that I think is a bit more streamlined and reasonable over at Reddit this morning.

http://www.reddit.com/r/Bitcoin/comments/281ws5/pow_alternatives_to_avoid_51_concerns/

I don't want to hijack this thread, but I also don't want to clutter the forum with multiple discussions for the same ideas.  If a mod feels appropriate, please move this comment or let me know to start a separate thread.

[trilli0n]

EDIT: improved based on suggestions of XertroV

To me it seems that the fundamental problem is that the entire block reward (coinbase + fees) is going to a single miner. Note I'm using the word "miner" in the strict sense of the word, i.e., the entity which decides what transactions to put in a block and gets to distribute the reward, i.e., a mining pool operator.

A solution therefore might be to have multiple PoWs and multiple rewards per block, for instance three (that's quite an arbitrary number, perhaps five would work better, but for the sake of the example I'll go with three PoWs per block).

A way to split up the PoWs could be as follows. Let there be PoW1, PoW2 and PoW3. Any one PoW is valid for only a subset of transactions (1/3 of all transactions in the case of three PoWs). However the miner must not know in advance to which subset of transactions it is searching a solution for. So, each miner selects all transactions from the mempool just as-is, and includes transactions to distribute the block reward. If a miner finds a solution (a nonce), then it is broadcast so other miners know that a PoW has been completed, so they can switch to other PoWs that have not yet been found.

The miner that finds the final PoW can broadcast the block. The protocol enforces that the first miner that broadcasts a solution locks in the reward for that PoW. This as an incentive for a miner to immediately broadcast a solution once it finds it. If two or more miners broadcast a solution for a PoW at the same time, the protocol may randomly choose one.

It must be impossible for a miner to know which transactions its PoW is going to be valid for. Therefore, establishing the set of transactions approved by each PoW should be done as late as possible, so only when the block is finalized by the miner that found the last missing PoW and includes all PoWs in the block and broadcasts it. The mapping between a PoW and a set of transactions should be random, deterministic and impossible to manipulate. Since the exact value of a nonce is impossible to manipulate, the mapping should somehow be derived from it. Also, the transaction inputs and outputs can not be manipulated by the miner, so these are also useful. We could take the hash mod 3 of such immutable property of the transaction plus the final nonce, rendering 0, 1 or 2 for each transaction. So hash(tx_property, final_nonce) %3 gives 0, 1 or 2 for each transaction, which in turn dictates if a transaction belongs to PoW1, 2 or 3. This way, a PoW controls only 1/3 of all transactions.

Example
Suppose the miner that found PoW1 included transactions 1, 2, 3, 5, the miner that found PoW2 included 1, 2, 3, 4, 5, 6 and the miner that found PoW3 included 1, 2, 5. Suppose as well, after applying hash(tx_property, final_nonce) %3 to each transaction, it turns out that PoW1 is valid for tx 1, 2, PoW2 is valid for 3, 4 and PoW3 is valid for 5, 6. The set of valid transactions will then be 1, 2 (PoW1), 3, 4 (PoW2) and 5 (PoW3). Transaction 6 is not included in the block as valid, since it belongs to PoW3, and PoW3 did not include transaction 6.

The effect of this will be that controlling > 50% of the network hash rate is not enough to consistently control all transactions. Increasing the number of PoWs per block from three to five reduces the number of transactions under the control of a single large miner even further. Of course, for a large enough share all of hash power, the miner will again be able to control all blocks, but this number will be 80% for five PoWs, plus that it can never be sure it finds the PoW for a malicious self-inserted transaction before another miner, as it can not predict which set of transactions the PoW it finds is valid for. This reduces the ability to abuse its mining power.

[joshraban76]

By this, you will mess with the the concept of how bitcoin miners are operating.

Plus, many thread here are saying there is no much risk involved at that DS attack.

[venij]

To me it seems that the fundamental problem is that the entire block reward (coinbase + fees) is going to a single miner. Note I'm using the word "miner" in the strict sense of the word, i.e., the entity which decides what transactions to put in a block and gets to distribute the reward, i.e., a mining pool operator.

A solution therefore might be to have multiple PoWs and multiple rewards per block

Snip...

The effect of this will be that controlling > 50% of the network hash rate is not enough to consistently control all transactions. Increasing the number of PoWs per block from three to five reduces the number of transactions under the control of a single large miner even further. Of course, for a number of hash power large enough, the miner will again be able to control all blocks, but this number will be 80% for five PoWs, plus that it can never be sure it finds the PoW for a malicious self-inserted transaction before another miner, as it can not predict which set of transactions the PoW it finds is valid for. This reduces the ability to abuse its mining power.

The idea of a 51% isn't that the majority shareholder finds all blocks ever. It's that he can mine ahead/around any short fork that is created by the rest of all miners. At that point, he rebroadcasts his version of a sidechain which then overwrites that shorter fork.

With this multiple PoW system, it's just a more elaborate version of the same system. Eventually a 51% miner would just overwrite the chain after taking a side fork.

[bluemeanie1]

Changing the work function of Bitcoin would render all existing mining hardware obsolete.  You will never get the miners to move to this algorithm, as it would be a major financial loss for them.

not true.

you can combine PoS with PoW, the most obvious method is setting the hash difficulty according to how much BTC the miner owns.  This will also have a significant appreciative effect on BTC because it will require miners to own BTC to mine effectively(will reduce the supply).  Of course this might also be viewed as being elitist(excludes poor miners) - but IMHO the cost of mining gear already poses a significant barrier to entry.  The positives would outweigh the negatives.  Also there are significant theoretical issues regarding PoS that need to be addressed.

Also this proposal practically eliminates the incentive for a malicious 51% attack.

-bm