Inflation-proofing via fraud notices

[Peter Todd]

(cleaned up repost of https://bitcointalk.org/index.php?topic=106449.msg1469608#msg1469608, 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:

Code:

txA - 0.0001
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

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

[d'aniel]

Here's sort of a recent continuation of that discussion gmaxwell pointed you to as well: https://bitcointalk.org/index.php?topic=131493.0

[Peter Todd]

Here's sort of a recent continuation of that discussion gmaxwell pointed you to as well: https://bitcointalk.org/index.php?topic=131493.0

Nice! That's exactly what I'm proposing, and you guys beat me to it by a few weeks.

I should have read the forums more over Christmas...

[Mike Hearn]

The devil is in the details. For instance, currently peers will not allow you to look up arbitrary transactions that are in the block chain. It requires a full tx->diskpos index. Pieter has submitted a change that will allow users to build such indexes with a command line switch, but he's pretty against making it queryable from the network (see his pull req for the arguments).

https://github.com/bitcoin/bitcoin/pull/2168#issuecomment-12236562

This leaves the question of how you can check a fraud alert that says tx A in block B connects to a non-existent transaction C. Nodes won't let you look up C, and you don't know which block it would be in.

The only way I can see to resolve this is to have some nodes advertise their tx indexes in the addr messages. So sipas arguments would need to be addressed.

After that, it's just a long painful slog through the code to spec out and implement every kind of fraud alert there could be.

And it's not enough to just do the crypto/protocol work. What happens when such a fraud alert is received and found to be valid? How do you communicate what that means to the end users? It can mean, technically, that there is a rolling upgrade taking place and the user should upgrade. Or it could mean that the rules are changing against the users best interests, but most people will never be able to verify for themselves. So it's got a social dimension too.

[Peter Todd]

SPV can't check fraud challenges at all other than to assume they are valid unless proven otherwise; it's why I'm calling them challenges rather than alerts. However so long as the network as a whole is connected - a core assumption of Bitcoin - any invalid fraud challenge can be rebutted cheaply by any validating node. (you need access to transactions in the recent past, but that's required for reorganizations anyway) The problem is large numbers of fraud challenges getting issued then just becomes one of anit-DDoS techniques, and I think hashcash for them is pretty reasonable, especially if the hashcash uses the same algorithm as the Bitcoin block hash so it's easy to reason about the value of that hashcash. (you could have used it to mine block after all) If a SPV client for some reason missed the rebuttal, at worst they can rebroadcast the challenge themselves to get someone to rebut it again, and if needed caching rebuttals and an inventory for them can be implemented.

A fraud challenge going un-rebutted can be treated pretty much like any reorganization - invalidate the blocks and return the transactions to the mempool - except that the length of the best chain can now decrease. For an SPV client I don't think this changes much; they don't have visibility to the full mempool anyway, and just see that since the best chain isn't what they thought it was and possibly some transactions they thought were confirmed actually aren't. You'll probably want to give some interval before you accept a challenge as valid, but SPV clients already have to wait awhile for confirmations to pile up anyway. In addition for some applications the SPV client might actually only care that the best chain is valid; they might not actually be doing Bitcoin transactions directly. Timestamping is an example that doesn't even involve any transactions at all.

Regarding rolling upgrades, I don't think that case is really much different from what happens with a rolling upgrade anyway. You do add more cases where the SPV clients need to be upgraded, but no more cases than is true for fully validating clients.

I agree that speccing out every form of fraud will be a long painful slog...

[Mike Hearn]

SPV can't check fraud challenges at all other than to assume they are valid unless proven otherwise;

I think the conclusion of the other forum thread is that for many types of fraud notice/alert, SPV clients could theoretically verify them, if the alert contains enough information. Bear in mind you can still run scripts, check that transactions are included in the best chain, verify double spends etc if you're provided the right data.

[Peter Todd]

SPV can't check fraud challenges at all other than to assume they are valid unless proven otherwise;

I think the conclusion of the other forum thread is that for many types of fraud notice/alert, SPV clients could theoretically verify them, if the alert contains enough information. Bear in mind you can still run scripts, check that transactions are included in the best chain, verify double spends etc if you're provided the right data.

Yup, you're absolutely right. For the particular case of a valid transaction with non-existent txin's a SPV can't verify the fraud themselves, but other cases like invalid script execution are detectable. On the other hand they must be detected anyway as part of verifying a fraud rebuttal, or otherwise you could give rebut with a transaction with, for instance, invalid signatures but valid txin's. This is annoying because SPV clients don't need script validation machinery at all otherwise; they can only accept confirmed transactions safely so validation can be nothing more than checking the merkle path leads to a block in the best chain. To process fraud challenges and rebuttals they need to have validation code identical to that in validating nodes, including all the difficult to get right edge cases that lead to network splits.

[Mike Hearn]

Yeah, being able to verify fraud means having a lot more complex code for sure. bitcoinj does have it these days, at least.

For transactions with no connectable inputs, I guess you'd have to assume it's valid unless some peer can give you the connected transactions and their merkle branches. But then we're back to needing nodes with an index.

[Peter Todd]

Well, the question becomes how did you find out about the transaction in the first place anyway? The SPV node could be informed about the incoming tx through a payment protocol, and that protocol could provide the node with the merkle branch required. Payment becomes "prove to me a transaction in the block chain exists that only I can spend". If you assume x% of mining power is honest, that proof is just the tx and the merkle path to a block with a sufficient number of confirmations.

[m0mchil]

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.

Excuse me for commenting so late on this topic. I just wanted to note that even if miners perform this, they can't inflate above the predetermined issuance schedule, i.e. at block N 'never greater than' money in circulation is easily calculated. Effectively, it's only possible to reassign already destroyed funds.

[Mike Hearn]

m0mchil, that statement was in relation to clients that do simplified payment verification (see Satoshis white paper). They don't validate all the transactions so cannot know how big the coinbase should be, making them open to arbitrary inflation - those blocks won't be recognized as valid by other full nodes, but users/merchants who don't run full nodes can still be tricked.

[m0mchil]

Mike, I obviously failed to explain it properly. Whatever headers and coinbases are presented to an SPV client, there is a rule  stating that at block 100 000 there should be strictly  5 000 000 BTC or less in circulation. So, a chain of headers which sums above that should be considered invalid.

[Sukrim]

Mike, I obviously failed to explain it properly. Whatever headers and coinbases are presented to an SPV client, there is a rule  stating that at block 100 000 there should be strictly  5 000 000 BTC or less in circulation. So, a chain of headers which sums above that should be considered invalid.

If I have the first 4 blocks with the following coinbases: 10 BTC, 20 BTC, 30 BTC, 40 BTC - how many BTC are in circulation - 100 or 40 or something in between? Did "my" block chain rules just generate 10 more BTC each block, or did it only generate 10 BTC per block, but all of these were used as fees in every block? Without looking at transactions you can't tell.

Currently it CAN be possible that there is a block mined with a few million BTC in it's coinbase that is valid, if at once everyone with loaded addresses decides to pay these out to miners. Still only 25 out of these millions of fees are actually "new", the rest is from fees.

The only impossible values would be everything larger than (all_coins_mined_so_far + reward_for_current_block), maybe one can also factor in coins held by oneself (not that this makes it any easier to show anything). Everything else is possible, recently someone did mess with handmade transactions probably and ended up paying 94 BTC in fees which is a huge value in current USD prices. Before that there were also (accidentially/willingly) fees paid that ended up multiple times larger than the then current block reward.

[Mike Hearn]

I see what you mean now, but it still makes no difference. SPV clients validate NO transactions. Even if SPV clients add up all the coinbases, you can just create new money in a non-coinbase transaction and they'll accept it just the same.

[Peter Todd]

I see what you mean now, but it still makes no difference. SPV clients validate NO transactions. Even if SPV clients add up all the coinbases, you can just create new money in a non-coinbase transaction and they'll accept it just the same.

No, the coinbase transactions will always sum to more Bitcoins actually in circulation because of fees. After all, a coinbase is allowed to have up to subsidy + total fees in it's output, the subsidy part sums to the total Bitcoins in circulation, and the total fees can be as high as you want in a valid block. Thus the way to pull of the fraud is with the coinbase transaction, because proving the fraud (currently) requires every transaction in the block, and every input to every transaction in that block.

[Sukrim]

What can you do with that money though? If you control all connections of a SPV client you can feed him spoofed data (but you still have to mine the blocks, something that will not give you any benefit on the main chain), so far so bad. Now you can in one block create a million coins in a faked coinbase transaction, then in the next block send it to the client (which might ask for it's origin, and you just claim "coinbase"). What now? As soon as the client gets out of your "bubble" and sees the real chain, it will be much longer or you'd be anyways better off 51%ing the main net.

Generating a handful of headers in some reasonable time frame (if it takes much longer than 2-3 hours for 6 blocks your user might get suspicious) is not easy and you still need a quite high hash rate.

Since SPV clients anyways need to trust full clients, ensuring a good (whatever that means) selection of several full clients connected should be one of the more important points in that area.

I don't understand who would send out these challenges when let's say EvilMiner has taken over all connections my light client has to the Bitcoin network, but I'm unaware of that. He then proceeds to generate a fork of the block chain I have and builds a fake block that grants me 1 million coins from a transaction (not coinbase otherwise he'd need to build 100 more blocks). Then he extends that fork by spitting out 2 more blocks on top of that, claims my million coins have now been delivered an I should better pay up on Paypal. I grow suspicious and send out a challenge for that transaction to the network. Since EvilMiner _is_ my network (otherwise I'd already have learned of the 8 legit blocks that were mined in the meantime) he does not relay that request, but does what exactly?!

[gmaxwell]

Since SPV clients anyways need to trust full clients,

The point of this is fixing it so that they don't. It would allow the network to remain secure even if there were fairly few full nodes (because running one had become too expensive). Otherwise, the few full-nodes may find it in their economic or political interest to lie and inflate the currency and if nothing has been done to make it easy to SPV nodes to automatically catch and reject these lies then everyone else may feel that they have to go along with it. An important thing about trust is that its easier to trust when the number of things the trusted entities could get away with is reduced.

The important things to check are:
* No scriptsigs are invalid.
SPV nodes could randomly check them today and send out compact proofs (fragments) showing signature problems.

* No double-spends.
SPV nodes could randomly check with reduced effectiveness, or a single honest full node could send out compact proofs of doublespends (fragment pairs).

* No subsidy inflation.
Needs the proof described in this thread, with it SPV nodes could randomly check and send out compact proofs (fragment plus input txn) showing bogus subsidy.

* No spending non-existing coin.
Requires committed UTXO set to produce a compact proof.
(Also, committed UTXO isn't quite sufficient, because a txn can spend coins created in the same block. So this would also need a separate search tree of utxo created in the current block committed)

If these things can be proven then Bitcoin could be made robust against rules violation even if most nodes were SPV by the existence of only one non-isolated honest full node and/or spot-checking by SPV nodes.

[d'aniel]

Since SPV clients anyways need to trust full clients,

The point of this is fixing it so that they don't. It would allow the network to remain secure even if there were fairly few full nodes (because running one had become too expensive). Otherwise, the few full-nodes may find it in their economic or political interest to lie and inflate the currency and if nothing has been done to make it easy to SPV nodes to automatically catch and reject these lies then everyone else may feel that they have to go along with it. An important thing about trust is that its easier to trust when the number of things the trusted entities could get away with is reduced.

The important things to check are:
* No scriptsigs are invalid.
SPV nodes could randomly check them today and send out compact proofs (fragments) showing signature problems.

* No double-spends.
SPV nodes could randomly check with reduced effectiveness, or a single honest full node could send out compact proofs of doublespends (fragment pairs).

* No subsidy inflation.
Needs the proof described in this thread, with it SPV nodes could randomly check and send out compact proofs (fragment plus input txn) showing bogus subsidy.

* No spending non-existing coin.
Requires committed UTXO set to produce a compact proof.
(Also, committed UTXO isn't quite sufficient, because a txn can spend coins created in the same block. So this would also need a separate search tree of utxo created in the current block committed)

If these things can be proven then Bitcoin could be made robust against rules violation even if most nodes were SPV by the existence of only one non-isolated honest full node and/or spot-checking by SPV nodes.

This overall upgrade strikes me as quite important for scaling beyond the current block size limit, but due to its hard-forking nature it needs to be ready and well-tested long before the block size limit is actually lifted.  This looks like a pretty Big Job - especially the authenticated UTXO set stuff.

I saw in IRC that Gavin stated he isn't "philosophically opposed" to this.  Though as Mike said here, "the devil is in the details," if they can be worked out and a concrete implementation plan developed, I'm thinking that with the recent exchange rate run up people might be feeling generous enough to fund work on this.  Maybe I'm being overly optimistic, but if all the devs got behind a funding campaign and did a good job of conveying its significance (and maybe how unimpeded scaling will make their bitcoins worth more, and their mining revenues worth more down the road), I think money would be forthcoming, especially now.

I guess such a campaign would be the job of Bitcoin Foundation to organize?

[gmaxwell]

This overall upgrade strikes me as quite important for scaling beyond the current block size limit, but due to its hard-forking nature it needs to be ready and well-tested long before the block size limit is actually lifted.  This looks like a pretty Big Job - especially the authenticated UTXO set stuff.

Two of these things are pure p2p messages and client behavior. Those should get done first.  They'll setup a lot of the infrastructure like avoiding the proofs being a DOS vector and reorging off a bad chain.  Bluematt suggested he might work on this some— it would put some of his bitcoinj full node code to work even in SPV clients.

UTXO stuff can be done as a non-enforced thing first for development and then testing. Then deployed as a soft forking change. So thats "easy" in that the deployment won't be hard once its done, and the development can be done and tested on the production network in advance of making it mandatory. I don't think anyone brought up the problem of proving spends within blocks in any of the UTXO conversations before my message above, so someone will actually need to figure out how to do that. (/me puts on pondering hat)

The non-inflation subsidy stuff is harder, I don't see an efficient way to do that without a hardfork.  Maybe an altcoin can be talked into doing it first. At least the code is fairly simple (compared to the UTXO stuff).

[jl2012]

This could be done with a soft-fork: create a fee merkle hash and put it to the coinbase.