I don’t think it needs to. The challenger can just watch to see if a withdrawal exceeds the amount they know was allocated to the ancestor, in which case they know and can prove the withdrawal is fraudulent.

Yes, but I think this can be enforced cryptoeconomically. An attempt to spend a ancestor or descendant of a previously withdrawn coin can be challenged by revealing the withdrawal. The contract just keeps track of the remaining balance in X.

This still seems underspecified. What I am worried about is this scenario: say there are coins X.00, X.01, X.10, X.11, each with 2 eth, and I own X.00. Let’s say X.01, X.10 and X.11 are colluding. X.11 exits 2.1 eth, and I don’t notice anything wrong (since our LCA is X, and 2.1 < 8). After that confirms, X.01 and X.10 both submit withdrawals. I must be able to somehow prevent all of them from succeeding. In this case, I can prove to the contract that X.1 was worth 4 eth, and the confirmed exit of X.11 and the in-flight exit of X.10 total more than 4 eth. This does imply that I have to watch every single exit of X.something, which means that a coin with t telomeres each belonging to a separate owner the overhead is t^2, which is suboptimal.

Dang, you’re completely right. To do it cryptoeconomically, users would need
to keep track of running balances of their siblings and uncles, and store all those withdrawal transactions (only like N log N total though, I think, so not TOO bad) in case they need to reveal them to challenge something. There are maybe other ways to do it that involve tracking the balance in a Merkle sum tree on the parent chain… would have to think about the tradeoffs.

We are implementing an exchange using plasma and we bumped into some issues:

Its unclear how an exchange could use plasma cash without fungibility. If I want to buy size 3 but there are only sellers of size 2 and 5, there is no match. This implies we cannot write a matching engine that works as expected (ie price-time priority, etc)

Challenge of type (iii) is unclear. From my understanding, an invalid output A can be created and spent into B and then into C (all owned by same user colluding with operator) i.e A->B->C. C is withdrawn providing B and C. A may be withheld (not published). How would challenge (iiii) be made? Even if A were published, can the challenge be blocked by providing B?

I see a few sharding proposals here. I think they are fundamentally flawed if coins from shard A cannot be sent to shard B. The network effect of money is lost completely. I have no interest in coins that I can only spend at certain places. This will make shards the equivalent of gift-cards.

The right sharding approach should shard the processing but not the network.

The idea is that most people would deposit with coins of a specified size, similar to existing real-world denominations (1, 2, 5, 10, 20, 50…)¸ and there would be specialized exchangers that can convert many small-denomination coins into larger-denomination coins.

How would challenge (iiii) be made?

As I am understanding, the idea is that the chain creates an invalid output A, then a child of A, B, then a child of B, C, and then tries to exit C.

I would challenge by providing the parent of A.

I think they are fundamentally flawed if coins from shard A cannot be sent to shard B.

Our sharding proposals definitely don’t have that property; there’s an entire line of research around how to make cross-shard transactions maximally efficient.

If A is a deposit on the root chain, then A can’t be invalid.

Im just claiming A exists. Lets say there are 20 different coins from real deposits on root chain. Im claiming A is the 21st coin (doesn’t really exist on root and not published). How can challenge (iii) be submitted?

I’m guessing that naive way out of this is to require the root chain entry and entire coin history MUST be provided for every withdrawal.

Of course A,B,C is the shortest chain but nothing prevents the operator from creating 10K transfers before attempting a withdrawal. This would create a very large withdrawal tx.

The point is that the first invalid or unavailable transfer in the chain is not a deposit, and so it has a parent (which is valid and available), and so a challenge can be done based on that.

Late response, I think the merged token ID is an issue here. If each merged token has a unique ID, then (I think?) we have \sum_{r=2}^{n}{C(n,r)} unique IDs. This is only an issue if the Merkle tree is sparse. We can still prove non-existence in the tree if the leaf nodes are sorted, but the proof becomes more involved.

Sorry, I don’t follow. If two given coins are not currently merged, then the given slot in the sparse Merkle tree is blank. (It doesn’t even have to be blank—it’s just irrelevant). So it doesn’t matter any more than future deposits do.

I think the tree would have to be extremely large if it’s sparse and contains every possible unique ID. Did you have ideas for storing the unique IDs efficiently?

In a sparse Merkle tree most of the leaves are empty, so you can precompute them and their parents, grandparents, etc. So it’s no trouble to have a sparse Merkle tree with 2^32 elements.

I just looked back at this, and I think it’s a very good idea.

The size of the bloom filter will still have to be linear with the number of transactions. However, this probably works extremely well for a medium-low throughput Plasma Cash chain.

Not only does this work very well on its own, it’s even possible to have the bloom filters be relayed off the root chain. Here’s a mechanism for that:

Operator publishes hash(bloom filter) to the root chain along with every block.

User receives bloom filter from operator and trusts it if hash(received filter) == hash(filter).

For ~5000 txs per block and a 1/100000 false positive rate, this scheme requires the user store 119814 bits per bloom filter. In exchange, the user only needs to ask for the proof of non-existence for any false positives. Users will, for the most part, never have to ask for non-existence proofs.