UTXO commitments - Possible Problems?

[onelineproof]

I read a few descriptions recently about UTXO commitment schemes. But is this idea really robust? To prove the UTXO status of an output, you need a branch of hashes from the merkle tree that stores the UTXO state of all outputs. So yes, this branch would be O(log n) in size where n is the size of the UTXO database. But...what gives incentive to nodes to relay these branches to people? How do you know they will not deny the service?

[TierNolan]

How do you know they will not deny the service?

If you connect to 10 different nodes, you only need one of them to send you the branch. 

Secondly, if the UTXO tree is sorted, it is possible to prove that UTXOs aren't in the tree (by giving the path to the leaf before and after where the leaf would have been inserted).

[onelineproof]

How do you know they will not deny the service?

If you connect to 10 different nodes, you only need one of them to send you the branch.  

Secondly, if the UTXO tree is sorted, it is possible to prove that UTXOs aren't in the tree (by giving the path to the leaf before and after where the leaf would have been inserted).

Well this seems like a subtle (but serious) flaw. What you could end up with is a small number of big nodes that have the tree, or the branches you're interested in, and you would have to rely on them to relay the parts of the tree, and they may not, and what will you do? Download all the blocks when the blocksize is huge? Once Bitcoin is big, people may notice this, but it will be too late to do anything except "protest" and hope people change things.

Another reason why bigger blocks are a problem, and this gives me more confidence in (tree-structured) subchains, which actually lets you prove the UTXO state of your wallet (or someone else's wallet you're tracking) without having to deal with DOS attacks: https://bitcointalk.org/index.php?topic=1083345.0.

[TierNolan]

Well this seems like a subtle (but serious) flaw. What you could end up with is a small number of big nodes that have the tree, or the branches you're interested in, and you would have to rely on them to relay the parts of the tree, and they may not, and what will you do? Download all the blocks when the blocksize is huge? Once Bitcoin is big, people may notice this, but it will be too late to do anything except "protest" and hope people change things.

UTXO commitments are for SPV nodes.  It is assumed that full nodes will download the entire block chain.