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
<block hash>, <path in bits>
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
