How will the lightweight node know the path hashes are incorrect and to reject that part of a block?
All of these "links" are hashes -- they're self-validating just like the previous-block (prevblock) hash that Bitcoin currently uses. These are just "extra prevblock pointers", but they're in the coinbase instead of in the headers and they point to an arbitrary ancestor instead of the immediate predecessor. I'll call these new pointers
non-prevblock pointers to distinguish them from the pointers we already have.
I can see how the thick clients can verify this, but an incorrect path would require all of the thick clients to reject the block if it contained a false tree.
I
definitely do not propose adding any new block validity criteria. You're right: hostile miners can add blocks with broken non-prevblock pointers.
Otherwise, we'd have ignorant thick clients forwarding malicously crafted "tree transactions" to the light clients.
If a hostile miner gets a block with broken non-prevblock pointers into the chain, it will amount to -- at worst -- a DOS attack on thin clients until the next block is found by friendly miners. As long as the hostile block is at the top of the chain, all thin clients will believe that all servers are lying to them. But they won't be compromised -- they'll simply twiddle their thumbs saying "Nobody has been able to convince me of what reality ought to look like".
As soon as the next {non-prevblock-pointer}-aware miner finds a block, they will add a block which
refrains from creating any new paths through the malicious block. Thin clients resume operation as normal. In effect, blocks with broken non-prevblock pointers get excluded from the "DAG-within-the-blockchain".
Thin clients which were connected before the malicious block arrived won't be affected.
There are ways to make the cost of the DOS attack above very large (like >99% hashpower) but they add complexity.
I think this means another protocol decision point like P2SH.
Definitely not! I believe the trustless thin client problem can be solved without another hardfork (or even miners-only fork).
I also don't understand why you think these could be added without the "51%."
Right, so, suppose I control 1% of the network hashpower. That means I create 1% of the blocks. If the radix of the non-prevblock-pointer tree is, say, 200 (i.e. each block can have 200 non-prevblock pointers) that means that my block will be reducing the average path length in the tree more rapidly than the other 99% of the network is adding new blocks. So the average path length will gradually converge to log(height), even if only 1% of the miners are adding the new pointers -- it's just that each block they add has to include more than 100 new pointers. Of course, the more miners you have the more rapidly we get to the ideal log(height) situation…