Topic: Inflation-proofing via fraud notices - page 2. (Read 5049 times)
Here's sort of a recent continuation of that discussion gmaxwell pointed you to as well: https://bitcointalksearch.org/topic/way-for-spv-clients-to-cheaply-prove-when-a-miner-has-cheated-on-his-fee-reward-131493
(cleaned up repost of https://bitcointalksearch.org/topic/m.1469608, minus the ideas about merkle hashing within a transaction itself)
It's been pointed out before that SPV clients are susceptible to miners colluding to inflate the currency, essentially by creating blocks whose block header is valid and meets the required PoW, but whose coinbase includes fees for non-existent transactions. In particular SPV clients have no way of preventing a 51% cartel of miners from defrauding them this way as there is no proof of fraud a SPV client can be given other than the whole block chain itself. At the same time the existence of any transaction is easy to prove, just provide the merkle branches in the path from the tx to the merkle root in the block header. What we need is to extend that existence proof to proof of the fees associated with that transaction.
Lets suppose we have an honest block with the following transactions and fees:
We include the sum of each sub-trees total fees in the intermediate nodes in the merkle tree. Thus the first level of hashes would be H(0.0011 | H(txA) | H(txB)), H(0.11 | H(txC) | H(txD)) and the second, and final, level H(0.1111 | H(0.0011 | H(txA) | H(txB)) | H(0.11 | H(txC) | H(txD)))
Now suppose the above block has been created by a dishonest miner, and it included a fraudulent transaction with a hefty fee:
Any honest node can now publish a fraud challenge, consisting the path from faketxA to the block header. The length of this path, and thus the overall fraud notice, scales by O(log2(n)) Of course, if the fraud challenge itself is fake it can be trivially rebutted by simply replying with the actual transaction. (for fraud multiple blocks deep, just publish the first fake tx input)
These fraud challenges can be posted on the P2P network itself and broadcast. For DDoS protection they should be delayed a bit so rebuttals can spread faster than notices. Similarly nodes should keep track of where the challenges came from, so rebuttals can be directed appropriately. In addition challenge rate can be limited if required by hashcash, and if the hashcash uses the same algorithm as mining itself reasoning about the value of the hashcash compared to txfee-based anti-DDoS is simple: it's the same as the profit mining would create for an equal amount of hashing.
The big advantage to this proposal is in the scenario where the maximum block size limit is lifted; scalability studies comparing Bitcoin to, say, Visa, imply block sizes and transaction volume so large that even just the cost of maintaining a full txout set will become prohibitive. In this scenario a 51% cartel of miners has a chance of getting away with undetectable inflation fraud. If proofs of such fraud can be cheaply broadcast around the network, even just a single honest validating nodes, which doesn't have to mine, can resist the attack by causing SPV nodes to simply reject the fraudulent blocks, and, for instance, refuse to accept transactions in those blocks in exchange for non-Bitcoin goods and fiat currency. This would take away the incentive for the attack, leaving the attackers with the well known ability to launch double spend attacks with are both detectable and can be cheaply proven.
Similarly even without a changed hash algorithm fraud challenges can protect SPV clients from large miners creating chains of blocks with entirely fraudulent transactions that don't exist, but are sufficiently deep in the (fraudulent) chain to look confirmed. Note that you do not need a 51% majority to do this; a majority guarantees the attack, but having, say, 25% just makes it probabilistic so you have to wait awhile to get lucky and produce a sufficient number of blocks in a row to defraud SPV nodes trusting some given number of confirmations. With fraud challenges anyone can cheaply warn those nodes that the blocks are fraudulent simply by publishing a merkle path challenge to the fake transaction input.
EDIT: gmaxwell pointed out this relevant conversation on the email list: http://sourceforge.net/mailarchive/message.php?msg_id=29450793
It's been pointed out before that SPV clients are susceptible to miners colluding to inflate the currency, essentially by creating blocks whose block header is valid and meets the required PoW, but whose coinbase includes fees for non-existent transactions. In particular SPV clients have no way of preventing a 51% cartel of miners from defrauding them this way as there is no proof of fraud a SPV client can be given other than the whole block chain itself. At the same time the existence of any transaction is easy to prove, just provide the merkle branches in the path from the tx to the merkle root in the block header. What we need is to extend that existence proof to proof of the fees associated with that transaction.
Lets suppose we have an honest block with the following transactions and fees:
Code:
txA - 0.0001
txB - 0.001
txC - 0.01
txD - 0.1
txB - 0.001
txC - 0.01
txD - 0.1
We include the sum of each sub-trees total fees in the intermediate nodes in the merkle tree. Thus the first level of hashes would be H(0.0011 | H(txA) | H(txB)), H(0.11 | H(txC) | H(txD)) and the second, and final, level H(0.1111 | H(0.0011 | H(txA) | H(txB)) | H(0.11 | H(txC) | H(txD)))
Now suppose the above block has been created by a dishonest miner, and it included a fraudulent transaction with a hefty fee:
Code:
faketxA - 1.0
txB - 0.001
txC - 0.01
txD - 0.1
txB - 0.001
txC - 0.01
txD - 0.1
Any honest node can now publish a fraud challenge, consisting the path from faketxA to the block header. The length of this path, and thus the overall fraud notice, scales by O(log2(n)) Of course, if the fraud challenge itself is fake it can be trivially rebutted by simply replying with the actual transaction. (for fraud multiple blocks deep, just publish the first fake tx input)
These fraud challenges can be posted on the P2P network itself and broadcast. For DDoS protection they should be delayed a bit so rebuttals can spread faster than notices. Similarly nodes should keep track of where the challenges came from, so rebuttals can be directed appropriately. In addition challenge rate can be limited if required by hashcash, and if the hashcash uses the same algorithm as mining itself reasoning about the value of the hashcash compared to txfee-based anti-DDoS is simple: it's the same as the profit mining would create for an equal amount of hashing.
The big advantage to this proposal is in the scenario where the maximum block size limit is lifted; scalability studies comparing Bitcoin to, say, Visa, imply block sizes and transaction volume so large that even just the cost of maintaining a full txout set will become prohibitive. In this scenario a 51% cartel of miners has a chance of getting away with undetectable inflation fraud. If proofs of such fraud can be cheaply broadcast around the network, even just a single honest validating nodes, which doesn't have to mine, can resist the attack by causing SPV nodes to simply reject the fraudulent blocks, and, for instance, refuse to accept transactions in those blocks in exchange for non-Bitcoin goods and fiat currency. This would take away the incentive for the attack, leaving the attackers with the well known ability to launch double spend attacks with are both detectable and can be cheaply proven.
Similarly even without a changed hash algorithm fraud challenges can protect SPV clients from large miners creating chains of blocks with entirely fraudulent transactions that don't exist, but are sufficiently deep in the (fraudulent) chain to look confirmed. Note that you do not need a 51% majority to do this; a majority guarantees the attack, but having, say, 25% just makes it probabilistic so you have to wait awhile to get lucky and produce a sufficient number of blocks in a row to defraud SPV nodes trusting some given number of confirmations. With fraud challenges anyone can cheaply warn those nodes that the blocks are fraudulent simply by publishing a merkle path challenge to the fake transaction input.
EDIT: gmaxwell pointed out this relevant conversation on the email list: http://sourceforge.net/mailarchive/message.php?msg_id=29450793
Jump to: