An alternative way to accomplish this might be for the operator to construct a merkle tree T committing to the number of times every coinid has been spent since the genesis plasma block, and to use snarks to verify the integrity of the root hash of the tree. Then a client checking the validity of a coin can download the witness for the branch of this tree that tells him that his coin has been spent h times, and then download h inclusion proofs.
For clarity, an example of this is shown below for 2-bit coinids. The top row shows the transactions in each block, and the bottom shows T after those transactions have been applied.
This has the advantage that the prover only needs to construct one proof per plasma block (I’m not sure what the prover burden is for the scheme where a snark is constructed for each coin).
We can also place the verification on-chain, for instance both the transaction root and T would be placed on-chain for every plasma block, and the plasma contract verifies a proof that T was correctly computed. @JustinDrake points out that this is a case where we can use cryptoeconomic verification, i.e., the operator just places the proof on-chain and makes a bonded claim that the proof will verify, and anyone can collect the bond by paying the gas cost to refute the validator.
Also, we can include T once every n blocks, and just force clients to download the (at most n) exclusion proofs for the blocks that were included after the last time T was included.