I think it might be possible to support merging of arbitrary coins without any challenge/response period or activity on the parent chain, and without any significant overhead or sacrifices as far as I can see.
The simple solution for splitting has already been discussed: creating new tokens that represent a piece of a previously unified token (such as by adding decimal points to its token ID). The simple solution for merging would involve creating a new token that represents a “list” of previously separate tokens. These tokens would not have to be consecutive in the Patricia Merkle tree (which we had worried might have been a constraint).
A merge transaction lists the coins that are being merged (and provides signatures from the public keys that currently control those coins). It specifies a token ID for the new coin (or it’s deterministic, like a Merkle root of the token IDs being merged).
The key is that the merge transaction needs to be included in all of the positions in the Merkle Patricia tree corresponding to the inputs being merged. As a result, a proof-of-non-spend for a coin is also a proof-of-non-merge for that coin, so this adds no overhead to proofs that don’t involve merged coins. (For merged coins, you only have to provide one chain of history—the one corresponding to the merged token ID—for their post-merge history. This is much more efficient than having to carry around and provide proofs for all of the coins throughout their entire histories.)
Merged coins can be split using a transaction that declares that the merged coin is being split back into its individual coins, each of which inherits the public key of the merged coin. Merged coins do not have decimal places and cannot be split in the way unmerged coins are. (It is probably possible to support arbitrary combinations of merges, splits, and transfers in a single transaction, but for simplicity let’s skip that for now and assume a single transaction can only either merge unmerged coins into one, split a single merged coin into its individual coins, or transfer some coins). This split transaction only needs to be included in one place in the Merkle Patricia tree (corresponding to the token ID of the merged coin).
An attempted withdrawal of a merged coin is similar to an attempted withdrawal of all of its coins simultaneously. I haven’t mapped out the full protocol for challenge/response, but I think it will work as long as you require that, every time a merged coin is used in an attempt, challenge or response, you must also provide the paths to the merge transaction that created that coin. Challengers can then challenge the merge transaction in much the same way they’d challenge any other transaction.
One might be afraid this will lead to a blow-up ok the size of history proofs for coins that have been involved in many merged. However, I thiiiiiink merged coins do not entangle the histories of the coins they merge. That is, if you are only concerned with the validity of a single coin, you don’t have to look at the histories of every coin it’s ever merged with; the coin’s history can be invalid even if it was at some point merged with a coin with invalid history. If this works, that would mean that history proofs will be linear (as they are today) at worst, and if you’re proving histories for multiple coins that have any overlap in their history it will be better than linear.
Anyone see any problems in this design?