Topic: Inflation-proofing via fraud notices (Read 5049 times)

The list by Mike Hearn for what needs to be checked is:

    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).

I think the 2 hard ones are the non-existent input and the inflation one.

The inflation one can be solved with the sum-tree.

However, non-existent inputs are harder to prove.  Just because a peer doesn't have a transaction doesn't prove that it doesn't exist.

If we are talking hard forks, then extra info could be added to the merkle-sum tree.

Leaves would be

Hash(path_in1, path_in2, ..., transaction, fee)

For each input, you need to include a path.  With a 20 deep merkle tree, the path is 640 bytes per input.  That is a little expensive, even if blocks were being increased anyway.

A more compact form, would be
,

A one would mean right child and a zero would be left child.  I think this is already supported for bloom filtering (or something similar anyway)?

Full nodes don't currently allow random transaction access.  With proper indexing, providing a transaction from (block hash, path) would be much less of a problem.

With pruning, they may simply not have the older transactions.  How does pruning work at the moment?  I assume it doesn't delete the block chain from the disk?

Maybe there could be different levels?

Storage_Node
- serial block download

Pruned_Node
- serial block header download
- new transactions (and notification)
- new blocks (and notification)

Fast_Header_Node
- random access block header download (by height)

Transaction_Node
- random access transaction download

Network_Node
- provides Pruned_Node | Storage_Node

True.

As I said in the other thread on the header, it is probably worth reserving 32 bytes in the coinbase as hash of the auxiliary header.

The auxiliary header can then include any extra info needed at any time in the future, rather than chipping away at the extra nonce.

It is a pity to have 2 merkle trees to calculate.  It would be better to change the merkle tree to a fee tree, but that wouldn't be backwards compatible.

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

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).

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?

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.

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?!

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.

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.

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, 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.

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.

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.

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.

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.

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.

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.

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...

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.

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...