On Sun, Jul 5, 2015 at 12:33 AM, Justus Ranvier <justus@openbitcoinprivacyproject.org> wrote:

I think the problem is tractable if some reasonable assumptions are made
about the ability of SPV clients to perform validity checks that don't
involve any state outside a single transaction (or block):

https://gist.github.com/justusranvier/451616fa4697b5f25f60

I agree, it is definitely tractable.

If Bitcoin was being designed from scratch, it could be made even easier.

As things stand, the extra commitment information needs to be added to extra trees, which themselves need to be checked.

The "prover", in your example, should ideally store additional meta-data along with each block.

If P2SH was made mandatory, then much of the transaction validation could be performed on the transaction alone.

Both the signature and the public key would be included in the spending transaction.