I’m not sure it would work to use a ZK-snark for the non-existence proofs, unless the parent chain is willing to accept ZK-snarks for the exit transactions. Otherwise, you don’t have enough information to respond to a challenger, right?
Now that I think about it, you are right. In order to be able to respond to type (iii) challenges you have the proofs for every transfer in the coin’s actual history. If there are t blocks and h transfers (history length), then this already reduces required data size from 32 * t * log(n) to 32 * h * log(n) + 288. What we can also do is make a recursive SNARK that proves the list of block numbers for which a proof exists; this would bring it down to h * \frac{log(t)}{8} + 288 bytes (\frac{log(t)}{8} because we need log(t) bits to represent each block number, and a byte is 8 bits). To see how small this is, consider a Plasma chain with one block per Ethereum block that lasts for one year, with a history 500 transfers long; the chain would have 2.2 million blocks, so the data size would be 500 * 21 bits + 288 bytes = 1600 bytes.