Plasma Cash: Plasma with much less per-user data checking

I think the problem Karl is describing falls into a similar category to the one he describes earlier about recovering from an invalid block—it’s about recovering from operator failure or misbehavior. If the chain operator permanently withholds a block from everyone, then the chain cannot make progress or recover after that point, precisely because of those safety rules you’re referring to. It would arguably be nice if there were a way for the parent chain to come to consensus that the block is unavailable, so the chain could continue without everyone having to withdraw their coins. (I think this may be impossible because of fisherman problems.)

I have many problems. I need to bookmark this and re-edit this post when I have more time and clarify with this.

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?

2 Likes

Different topic:

I think type (ii) challenges, and the provision of P( C ) in the withdrawal attempt, might be superfluous? An attacker could always turn a type-(ii)-challengeable transaction into one that can only be challenged by a type (iii) challenge, simply by spending the coin once (so that its immediate parent is not a double-spend; only its grandparent is). Seems simpler and more efficient to have all double spends handled by type (iii) challenges.

Does this imply that tokens can only split once?

No—you can have arbitrarily many decimal places. Each time a coin splits in two, you could add another binary digit. But I don’t think this has to be limited to dividing coin denominations by two each time, the way it is in One proposal for plasma cash with coin splitting and merging. You can define arbitrary denominations at the time of splitting. If someone tries to lie about a coin denomination when they’re withdrawing, anyone who has the actual split in their history is able and incentivized to challenge it by revealing the actual split.

This does probably mean that you can’t merge two adjacent coins to get one coin with the ID of the pre-split parent, because that would allow coins to be resplit with different denominations, potentially causing a lot of confusion. But I’m sort of skeptical you’ll really be able to reverse coin-splitting entropy that often. And I think the method I describe above for merging is adequate as well as much more general.

(such as by adding decimal points to its token ID)

Each time a coin splits in two, you could add another binary digit.

Merged coins do not have decimal places and cannot be split in the way unmerged coins are.

It is hard for me to understand the spec you are proposing. Suppose I deposit a coin and it is assigned coin id 4. Am I allowed to split it into two coins? Into three coins? In both cases, what do the new coin ids look like? Are they formed by extending the old coin id by a single decimal digit or a single binary digit? Are they still integers? If I have coins A, B, C, D could I merge A, B to form AB and C, D to form CD, and then merge AB and CD? Are coin ids which are integers and coin ids which are not integers distinguished in the protocol?

Yeah, sorry—I’m describing inconsistent versions of the proposal, and not in very much precision. Let me try to describe splitting in a way that optimizes for clarity rather than efficiency. And I’ll focus on splitting rather than merging in this post (since the latter has a different mechanism).

Every coin has a 32-byte token ID (derived from, say, the block in which it was originally deposited), and a variable-length bitstring representing the digits after the decimal point, which starts out (when the token is deposited) with length 0. I’ll call these bitstrings “telomeres” (even though technically telomeres work the opposite way).

A coin can be split in two with a split transaction. In a split transaction, each of the two outputs has the same token ID as the input. Their telomeres of each are one longer than the input’s—the first output has added a 0 to the end, the second has added a 1 to the end. The split transaction specifies how much value goes into the first output and how much into the second. So a coin worth 4 ETH can be split into one worth 3 and one worth 1.

The location of the split coins in the Patricia Merkle tree is as children of the location where the parent coin was.

When you see someone attempt to withdraw a coin that shares a token ID with one of your coins, you check the closest shared ancestor. If the amount they are asserting in the withdrawal is greater than the amount that their ancestor received in that split, then they are trying to cheat, and specifically they are trying to cheat you. So you can challenge by revealing their ancestor. Since their ancestor had fewer coins than they are asserting the descendant had, you’ve proven that their coin is invalid.

Regarding atomic swaps, could you do something similar to merges, where the swap transaction contains a signature for both coins, and is included in the tree at both of their token IDs for the block in question?

At the time of deposit/minting, you’d associate metadata in addition to the value of the coin – in this case the contract address for the ERC20 token being represented, which could then be looked up at the time of withdrawal (for whoever now owns the coin).

Then you’d keep track of the metadata/token-type for proving ownership, similarly to that of the values of split coins (or really just all coins in general :stuck_out_tongue: )

Totally—with one caveat. You don’t want one party (with the cooperation of the block operator) to be able to double-spend their coin before the atomic swap hits the chain, and still receive their counterparty’s coin. But you also don’t want the transaction’s validity to depend on the entire history of every coin involved in it, because that would lead to an blowup in history proofs as coins get entangled with each other.

The solution, I think, is to have a rule that the whole transaction is invalid if any of the inputs have been double spent since block number N, where N is specified in the transaction. That way everyone can verify the history of the coin they’re receiving in the transaction up to block N, and then sign the transaction confident that their counterparties can’t cheat without invalidating the whole transaction. (Note that this invalidity rule is just the one that applies to atomicity. The individual coins involved in a transaction can still be invalidated by showing a double spend in their history from before block N.)

1 Like

Thanks, this gives me a better idea of the spec.

I assume that the withdrawal of a splitted coin needs to provide the withdrawer’s claim of what each ancestor’s split amount was? So assuming you are withdrawing a coin with id X.01110, the plasma contract stores how much ether was deposited to create X, and during a withdrawal you have to specify the denominations of X.0, X.01, X.011, X.0111, and X.01110.

Another thing I assume is true in this spec: the plasma contract enforces that for al P, B, after X.P is exited X.PB cannot be exited, and after X.PB is exited X.P cannot be exited.

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:

  1. 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)

  2. 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.

1 Like

What if A is deposit on root chain that is supposed to create a new coin? Do deposits on root-chain have parents?

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

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.