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

Layer 2 Plasma
42

Plasma cash and all the coin splitting mechanisms can be generalized into Sharded Plasma.

Idea is somehow similar to tree of Plasma chains but offers izolation of deposits like Plasma Cash and it might be possible to combine those two.

Sharded Plasma consists of Root Plasma blockchain, smart contract on Ethereum and Plasma Shards.

  • Root Plasma blocks has merkle tree mapping shardId \rightarrow shardDataHash
  • Ethereum Smart Contract maintains shardId \rightarrow deposits. Every deposit and withdrawal is constrained to a shard. There can be additional rules enforced like for Cash there can be only one deposit per shard.
  • Plasma Shards for each block are empty or hold some data. In case of Plasma Cash data is a signle transaction. If each shard is like an “Original Plasma” it would be a merkle tree of transactions.

Only thing sharding adds to withdrawal process is specifying shardId and providing proof inclusion of each referenced shard data in Root Plasma.
Like in Cash user only needs to keep track of history of shards it has a stake in.

This way basically any Plasma design can be sharded as long as there is no need of inter shard communication. Also shards can be heterogeneus, for example person making first deposit to a shard could choose if it’s a single coin, can it be split or should it have Original Plasma in it.

43

See more at Roast this Concept: One big off chain shard

Generalizing the proof of publication concept here, what if the inclusion in the main chain requires n-number of random validators to reconstruct a root.

  1. Main chain signs a root and commits to it.
  2. Main chain distributes a list of included transactions.
  3. Randomly selected validators reconstruct the root.
  4. Validators sign root commit to it.
  5. Main chain calls commit with hash, all unwound hashes must match.

Result: proof that tx list / collation is available across the network.

Attack; main chain cheats and distributes hash in network so validators don’t have to retrieve data and do work.

Mitigation: Some kind of slashing game where validators can be slashed if the main chain lies to them and they believe the main chain. Ie. Main chain gets more than commit reward if it can trick validators therefore no validators trust artificial hashes.

44

Edited: merging does not guarantee a slot knowledge beforehand and thus user has to monitor more aspects.

Edited #2: simplify, provide reasoning

Most likely there is some flaw in this idea, but something similar should allow merging. @vbuterin Vitalik, would you have a look?

User deposits a coin and attaches a public key P_1 = r_1 x G. Hash of P_1 is a slot number in a Plasma Cash. To spent it user takes two points H_0 = v x G and H_1 = (v+1) x G, where v is hash of the P_1, and to make a split provides signatures over P_1 + H_0 and P_1 + H_1. New slot numbers are known before spending and the user only has to monitor a chain once a week by asking an operator for a Merkle proof that such leaf is empty, so there was no spending, otherwise exit. To merge the two outputs with associated public keys P_2 and P_3 he would have to provide a signature over P_2 + P_3 (or some other combination that also includes info about merged outputs, but doesn’t expose private keys).

User deposits a coin and attaches a public key P = r x G. An output has hash v and is placed in some slot. To spent it user makes two points H_0 = v x G and H_1 = (v+1) x G, where v is hash of the the output as mentioned above. Another options to have v equal to a slot number of the output. To make a split the user provides signatures over P_0 = P + H_0 and P_1 = P + H_1 and Plasma Cash operator places an output to the slot numbers hash(P_0) and hash(P_1) . New slot numbers are known before spending and the user only has to monitor a chain once a week by asking an operator for a Merkle proof that such leaf is empty, so there was no spending, otherwise exit. This allows splitting, and scales linearly with the number of outputs: every user has to monitor 2 x N slots where N is number of his outputs. An output itself has P = r x G somewhere inside the data for further checks. Of course if user sends a part of his output to some other key P’ = r’ x G, than a new key P’ is included into output.

To merge the two outputs with associated hashes (or slot numbers) v_1 and v_2 (and the same public keys for both) a user has to provide a signature over P’’ = P + v_1 x G + v_2 x G. Such form of merging adds another N^2 / 2 slots for user to monitor once a week.

Effectively user checks an “ownership” on ~ N^2 / 2 + 2N “slots” in a global sparse Merkle tree. Merging is up to the user, but having smaller number of outputs is more convenient.

This looks a lot like UTXO model, so may be one can make some kind of hybrid model with Minimal Viable Plasma and force an operator to commit not only to block Merkle root hash, but also to the global state tree enumerating all taken slots.

Rules for recipients do not change, they would have to ask for a full history since the beginning. Unfortunately with merges history of every subchain has to be provided. May be some reasonable limit of the month of history in time or in number of blocks should be established.

Flaw #1: recipient can not be sure that user didn’t double-spent his output by doing a merge over two outputs and a split over one of them.

Exit rules also do not change with the additional difficulty of having to follow branches on merge points.

45

Hello,

many people are claiming that plasma cash is a great protocol for decentralized exchanges. I am currently trying to design one with plasma cash and running into a fundamental problem.

Here it is:
Assume I posted an order and someone trade against this order and hence sends his coin with AttackerID to me. In order to get the full possession of coin with AttackerID, I want to download all historical data and verify all merkle proofs that this received coin is legit. But what happens, if I can not download the data?

If we design the protocol that anyone can just claim, “uh there is not data, I want to reverse the trade”, then people would call so, everytime they are making a bad trade.
If we design the protocol so that we can challenge the attacker to publish all the data to the rootchain, then the attacker will just sometimes also make legit data not available and a user is required to pay the whole challenge process.

Does anyone sees a way how to solve this issue? Or do we have to request the guy posting an order to first check the whole chain against data unavailability?

46

I imagine it would need to either be interactive (both parties need to agree to the trade before it’s executed, in which case they would both verify availability before signing the transaction for the trade) or facilitated by a semi-trusted third party (the chain operator is a good candidate, since they’d be able to pull off a data unavailability attack anyway), in which case that third party can verify the availability of the data and provide it to the users after the trade has cleared.

47

Thanks for your answer. I am not sure how pratical these solutions are:

  • Iterative process: If I post a order and then someone will want to trade against this order and posts his orderProcessRequest, I will first check the price on other exchanges and only if the price is still good, I will confirm the deal. That feels like build in frontrunning for everybody.
  • semi-trusted process: I want to understand the required trust better. Imagine the chain operator first double-spends his own coin without publishing the double spend data (imagine no one notices this, since everyone is just verifying his own coins) and then sends the doublespend several times around between his accounts and lastly uses the doublespend output to trade against you. Now if you do not get the data of the chain operators coin, you don’t know whether he has double spend the coin or not. You can only check that the coin was not withdrawn from the plasma chain. Now you would need to require the chain operator by challenging him to publish all transactions of his coin between the doublespend and the trade with you. This would be huge process and in the end you would only know that your coin was doublespend. This would be huge deal with much harder proofs than in the usual plasma, right? Or are there simpler solutions? I think this would require quite some trust in the operator.
1 Like
48

I believe you are always going to have a free option / last-look problem no matter how you structure it. Whoever is responsible for trade matching (probably the chain operator) could mitigate it in various ways (such as by starting users off with a low trading limit, only raising it over time, and closing their accounts if they cancel too often).

You never need to challenge someone to reveal the whole history of a coin—you just attempt to withdraw, and it’s the responsibility of whoever they double-spent that coin to to challenge it.

But thinking about it, there is a problem here—the operator could fulfill your trade and not give you any data at all about the completed transaction. You could force them to provide it by attempting to withdraw your offered coin, but if they submit an attempted withdrawal for the other coin before your attempted withdrawal, they can finish withdrawing it first, then provide the trade transaction to successfully challenge your withdrawal, thus getting both coins. So I take it back; I don’t think open-ended offers work. Only the interactive process works; you need to know what coin you’re trading with before you authorize the trade (so you know you can challenge any withdrawal of that coin). In which case you verify its history before you authorize the trade. (Although they might still double-spend it before the transaction hits the chain, so if the chain operator refuses to give you that data, you need to attempt a withdrawal to get certainty as to which coin you own.)

1 Like
49

On the normal plasma we can hopefully build a small auction exchange and thereby eliminating the problem. Let’s see the mechanism is still to be fleshed out.

Yes this was what I meant. It is very tricky. It seems like there is no simple solution.
Thanks for thinking this through.

50

in the blogpost Karl describes a case with block withholding, where 3rd tx was withheld and can be revealed after block with 4tx will be submitted on a root chain.
and it is stated that 4th tx is valid from the user perspective, but why?
if hash of the block with 3rd tx was submitted on root chain then by design user who receives 4th transaction must also receive non-membership proof for every block without a coin.
if 3rd block wasn’t submitted - how it can affect anything?

51

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

52

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

53

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
54

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.

55

Does this imply that tokens can only split once?

56

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.

57

(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?

58

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.

59

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: )

60

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
61

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.