Way for SPV clients to cheaply prove when a miner has cheated on his fee reward

[d'aniel]

It's been talked about here before that when invalid blocks exist in the longest chain, honest nodes could broadcast short error messages to SPV clients with enough information for them to be able to prove that the block is indeed invalid, and thus be able to reject it.  Unfortunately, one of the most important error messages - that a miner has cheated on his fee reward - requires that the SPV client download the entire block in order to prove it's invalid.  This would become expensive for a smartphone at high transaction rates.

It would also open SPV clients up to attack, since the error message is cheap to broadcast, but expensive to investigate.  Mike Hearn suggested that to mitigate this, these error messages should only be investigated at branching points in the block chain, since presumably there would be some honest miners out there branching off.  The block size limit will also limit the damage an attacker could do to SPV clients.  But if this limit is to eventually be lifted, the hard fork required affords us the opportunity to solve this problem altogether.

This can be done by changing the Merkle tree of transactions slightly.  Instead of taking leaf node value = hash(tx) and branch node value = hash(child 1 value || child 2 value), we would have leaf node value = hash(tx || tx fee) and branch node value = hash(child 1 value || child 2 value || tx fee of child 1 + tx fee of child 2).  Working up the tree recursively, the tx fee value of the root node will be the total fee rewarded to the miner.  An incorrect fee value must then result in an invalid branch in the Merkle tree, which could then be relayed unobtrusively in an error message to an SPV client.

Would it be something that would make it into any hard fork that raises the block size limit?  Other than this one, I can't think of any other block error messages that require the download of more than two Merkle branches to investigate.  Are there any I'm missing?

[Mike Hearn]

You can't really solve this problem. I've thought about it many times and always concluded that it's unsolvable.

The key thing to realize is that it's not a case of checking the coinbase size. SPV clients don't validate transactions .... any transactions. Even if they had a way to verify that all the fee calculations were correct and the coinbase size was valid, a bogus block can contain transactions which spend non-existant prior transactions and thus create new money that way.

SPV clients don't enforce the rules of the system. Ideally, everyone would enforce those rules because that's how you can trust the system - changing it requires global consensus, which realistically you could only get for "no brainer" decisions, like minor technical changes with no downside. But enforcing all the rules is intensive.

It may be that over time as hardware and software gets better, the number of full nodes can get higher. Perhaps one day you can even run one on a smartphone. We've been sort of assuming that Bitcoin will grow and that growth will soak up improved capacity, but at some point Bitcoin will stop growing and then any optimizations or faster hardware increases the number of people who can run full nodes 'for free'. Hey, maybe Bitcoin has already reached its final traffic levels (tx rate wise). We'd all like to think that's not the case but you never know, it could be doomed to a tiny niche forever.

[d'aniel]

The key thing to realize is that it's not a case of checking the coinbase size. SPV clients don't validate transactions .... any transactions. Even if they had a way to verify that all the fee calculations were correct and the coinbase size was valid, a bogus block can contain transactions which spend non-existant prior transactions and thus create new money that way.

If a miner tried to include such a transaction, couldn't an error message point to the exact invalid txin, and issue a challenge to go find the appropriate merkle branch to prove it's valid?  And if nobody can produce it, then they'd reject the block.  Isn't it kind of the same with full clients?  Any piece of missing data, and a block can't be verified.

I understand SPV clients can't achieve certainty that a block is valid, but it seems like the trust can at least be upgraded from "I trust the the txs in the longest chain because it's expensive to forge blocks" to this plus "I also believe that I'm not special and thus likely not being surrounded in the network to censor error messages, which would presumably be flying around in abundance in the event of cheating".  This proposal is meant only meant to bring coinbase cheating within the scope of this trust model upgrade.

[Mike Hearn]

If a miner tried to include such a transaction, couldn't an error message point to the exact invalid txin, and issue a challenge to go find the appropriate merkle branch to prove it's valid?  And if nobody can produce it, then they'd reject the block.  Isn't it kind of the same with full clients?  Any piece of missing data, and a block can't be verified.

Merkle branches prove inclusion in a block, not validity according to a certain set of rules. By definition the attack we're worried about here is miner conspiracy where they're trying to change the rules, so the transaction will be in a block and thus have a branch.

If you say, prove to me that the dependent transactions were included in a block, well, OK, so I'll make my fake transaction depend on more fake transactions (or already spent transactions). You can't prove I'm wrong unless you walk back every single transaction input which makes you into a full node.

This proposal is meant only meant to bring coinbase cheating within the scope of this trust model upgrade.

Most clients have some kind of developer backchannel. The Satoshi client has the p2p alerts system. The Android client can be updated by the developer. Other clients should have their own equivalents. In the case of a systematic attempt to undermine the system by forcing SPV clients onto a chain with alternative rules the best approach is to have the client upgraded at that point to tackle it, for instance, by warning users about what's happening and asking them to enable full validation. It's really difficult to come up with a way to prove to a client that the rules are being tampered with that is unbeatable in the general case.

[d'aniel]

If you say, prove to me that the dependent transactions were included in a block, well, OK, so I'll make my fake transaction depend on more fake transactions (or already spent transactions). You can't prove I'm wrong unless you walk back every single transaction input which makes you into a full node.

It would make me wonder why you didn't just announce the tx way back in the chain that was the root of the problem from the start.  I would definitely be ignoring your error messages after trying to send me on an obvious wild goose chase.

[Mike Hearn]

You can't check the error message is correct. If I claim a TX was a double spend, how do you check if I'm right or wrong without being a full node?

[d'aniel]

You can't check the error message is correct. If I claim a TX was a double spend, how do you check if I'm right or wrong without being a full node?

I would expect you to include a merkle branch to the other tx that spends the same txout.

Edit: In more detail, I would have different standards by which to judge different error messages as correct.  Such as the above for double spend error messages.  For the invalid txin one, I'd expect to not be able to find a merkle branch linking to the corresponding txout from any other peer upon request.  If I do find a valid one, then I ignore your future error messages.

Sorry, I don't mean to be brief, I expect I'm going wrong somewhere in my thinking - I'm just trying to get to the bottom of it.

[Mike Hearn]

I suppose you're right, maybe I'm being too pessimistic about this. If you can enumerate every possible rule violation and find an efficiently checked error message for each one, it could be possible. I haven't tried to do a full enumeration because there are so many rules that could be violated, but perhaps many of them aren't interesting in the miner conspiracy scenario.

I guess you need:

• This TX (data, branch) has an non-existent input outpoint. Response: client asks any peers it can find to provide the (TX, branch) pair for the connected tx. If one is provide then the error message is invalid.
• This TX has a connected input that doesn't satisfy the outputs script. Response: client checks both transactions are included and then runs the script for itself.
• This TX creates more value than its inputs gather (input transactions are provided along with branches). Response: verify all the data. Not hard.
• This TX double spends. Response: verify that both transactions were included on the same chain (not crossing between forks).
• The coinbase of this block creates more value than allowed. Download the whole block (or do it with your approach of a change to the merkle tree format).

Is that list complete? If so I should eat my words as it's not as hard as I thought. Now bitcoinj has a full script interpreter, perhaps it could be extended to support such a protocol with only a few months work.

Are there any other things a miner conspiracy might try to achieve, beyond the usual spending-rollback attacks? The only goal I can think of would be to increase inflation or confiscate peoples money and then re-distribute it to miners.