On Sat, Jul 4, 2015 at 5:01 PM, Justus Ranvier <justus@openbitcoinprivacyproject.org> wrote:

How do we know if a committed UTXO set is valid? If a majority of the
hashing power is willing to extend an invalid branch, it's reasonable to
assume they'd be willing to commit an invalid UTXO set as well.

You can prove that it wasn't updated correctly.

For each transaction, the UTXO tree root before and after is committed.

You show the root before, and the root after and show that the after root is wrong. You also need to include some merkle paths to prove the transform.

If items in the the proof tree are required to be sorted, then it's easy
to proof that an item is missing.

Yes, you can mostly get short proofs for each step, but you have to make sure your proofs are also provable.

It means going through everything that needs to be proved for a block to be valid.