That is somewhat similar to what Vlad Zamfir's sharding is doing (https://medium.com/nearprotocol/so-what-exactly-is-vlads-sha...)

For a given transaction you'd only need to verify log(n) chains, but the problems from the top level post remain. The question is how you verify the transaction in a given chain. If you verify the entire chain, than you are expected to end up verifying all the chains (since ultimately cross shard transactions will be coming from all shards), removing any benefit from sharding. If you somehow trust that the shards were doing their job properly, then you need to somehow deal with shards being corrupted.