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


#5

It’s worth mentioning that crypto-economic aggregate signatures impose a weak synchrony for safety assumption on clients.

Clients must be able to synch the root chain within the challenge period to detect false checkpoints and challenge them. Otherwise they could loose the ability to withdraw their coins.


#6

Plasma Cash (like Plasma and indeed all state-channel-like designs) already depends on a synchrony assumption for safety—you have to be online to respond to attempted withdrawals of your coins. We could sync up those delay periods so that it doesn’t impose any additional synchrony requirements on the user.


#7

This is a really good observation. Anyone could aggregate checkpoints, as long as they put up the required bond!

The nice thing about this as that the EVM doesn’t even have to “understand” what the bitmaps represent. Someone could publish a bitmap along with the string “every coin ending with 2 or 3”, and it would (theoretically) work. Of course we’d rather have some semantics that the Plasma Cash client can understand, but it shows what options we have.


#8

I think it eventually has to—you need to prove that the recipient of the checkpointing was on notice, so in the event of a challenge, the EVM needs to be able to evaluate whether the published representation of the set being checkpointed included a particular coin.

(Another reason evaluating these needs to be computationally simple is of course that every coinholder needs to interpret every checkpoint, at least sufficiently to know that their coins are not included in it.)


#9

Makes sense, recipients must be able to know whether their coins are being checkpointed or not.


#10

Actually, you could probably use this for a mass move from one Plasma chain to another that doesn’t require the cooperation of the first chain operator. So you could maintain the liveness of your Plasma Cash coins even if the operator goes rogue, at the on-chain cost of only around 1 bit per coin. So efficient mass checkpointing, mass exit, and moving could all be enabled by basically the same mechanism.


#11

I am just curious what would happen or how would one handle the situation/attack when for example there are more people, who own their coin in the plasma chain and are malicious, than the max number of challenges (256) and submit invalid challenges at the same time. They might be able to invalidate the correct checkpoint by doing.


#12

Yeah, unfortunately this is a part of the design. The cost of this attack is 256 * bond, so we just need to parametrize the bond such that this attack isn’t worth it.


#13

What about using a bloom filter?
Users are only allowed to checkpoint their coins, maybe limited at 200 coins at a time. With a bloom filter of 8000 bits and 10 hash functions, the collision rate is 1/3000000. If the total number of coins is less than 1 billion, I think this is usable.


#14

My main problem with bloom filters here is that we could get an accidental “1” (false positive). In that case, the operator would lose a bond. I need to check the math on how to parameterize the bloom filter to be more efficient than 1bit/exit, but I have a feeling it might not be worth it.


#15

Assume that the submitted Merkle root is from a Sparse Merkle Tree like in Plasma Cash, in case of a false positive, the operation just need to submit a non-inclusion proof for that, isn’t it?


#16

I think the design can be changed a bit.

Only users can checkpoint their own coins. The plasma contract will stored successful checkpoint, one per address, as [blockNumber, merkle_root, bloomfilter, exceptions]. Then user only need to store history of their coins from blockNumber, start with a Merkle proof for the checkpoint.

The drawback is the cost for checkpointing might be high. Especially if there are too many false-positive in the bloomfilter.


#17

I would worry that this loses performance in the case where there are say 2^{20} \approx 10^6 users each owning one coin; ideally one would like them all to create a checkpoint with 1 merkle root and a 20-bit aggregate signature, but with the new restriction you must create 2^{20} checkpoints on-chain


#18

Allowing users to checkpoint their own coins will probably be a special case of the checkpoint anyway. There’s no reason why someone else (not the operator) can’t submit a checkpoint, so it makes sense that if the operator is misbehaving, then users might submit checkpoints for themselves. This gets more efficient as the number of coins per user increases.


#19

I just realized that a similar mechanism is alluded to on page 5 of the original Plasma paper as a mitigation to the mass exit problem:

These fraud proofs enforce an interactive protocol of fund withdrawals. Similar to the
Lightning Network, when withdrawing funds, the withdrawal requires time to exit. We
construct an interactive game whereby the exiting party attests to a bitmap of participants’
ledger outputs arranged in an UTXO model which requests a withdrawal. Anyone on the
network can submit an alternate bonded proof which attests whether any funds have
already been spent. In the event this is incorrect, anyone on the network can attest to
fraudulent behavior and slash the bonds to roll back the attestation. After sufficient time,
the second bonded round allows for the withdrawal to occur, which is a bond on state
before a committed timestamp. This allows for a withdrawal en masse so that a faulty
Plasma chain can be rapidly exited. In coordinated mass withdrawal events, a participant
may be able to exit with less than 2-bits of block space consumed on the parent blockchain (i.e. root Ethereum on-chain in worst case scenarios).

This design still does have the problem that someone can be forced to respond on-chain to an off-chain challenge without receiving a bounty (which isn’t a problem for Plasma XT if it’s just used for checkpointing on Plasma Cash).


#20

My suggestion would be to invert the bloom filter. First provide a description of all coins allowed for inclusion into a certain checkpoint.
For example: all coins or coins which id starts with 00 etc…

Then provide a bloom filter that contains all coin ids from the set for which no signature is present. This has the benefit that on a false positiv in the bloom filter a valid signature is discarded (instead of the generation of an invalid one) which is indistinguishable from the situation where the owner has never created it and as such, no problem arises from a false positiv.

Another aspect is that the bloom filters size is related to the coins that are not signed (but could have been) in a checkpoint instead of to the ones that are meaning if their is a high participation rate then the bloom filter can be very small


#21

Yep, this could be an interesting optimization. I’d be very curious to see what kind of participation checkpoints have! My guess was we’d actually see pretty limited participation.


#22

I be interested in learning how you sync up those delay periods. As we have developed offline mobile payment solutions based on Raiden, though like any development works, it’s forever improving and problem solving.


#23

I think there is a slight change in assumptions. With Plasma MVP, the user can delegate the task of watching the chain and initiating withdrawals to someone else, so the user does not actually have to be online regularly. The delegate could grief the user by initiating unnecessary withdrawals, or could fail to do their job, but could not steal the user’s coins.

In Plasma XT, it seems like a user could not delegate the checkpointing task while they are offline to an untrusted entity, because they would have to provide their private key to that entity for the purpose of signing off on checkpoints.

Do you see a solution that would enable checkpoints to be made while the user is offline, or would they just have to allow the coin history to grow and then make a new checkpoint when they do eventually come online?


#24

I would agree that there is a change of assumptions w.r.t Plasma MVP. I don’t believe that this changes any assumptions w.r.t Plasma Cash, particularly because of the discussion here: Watchtowers may not work in Plasma (Cash).

Although I think it’s probably fine for a first implementation if users have to be online, it would definitely be very useful for users to be able to outsource this. I haven’t thought about it a lot - one solution off the top of my head would be for users to make an on-chain transaction that somehow specifies a third party that can sign off on the checkpoint instead. This would basically look like a 2of2 multisig with a special key (for the third party) that can sign off alone. The third party could then be sure that they haven’t signed off and challenge whenever they see a false positive.

Of course, this means that the third party could temporarily grief the user by refusing to sign the signature. Maybe this isn’t the worst thing if users can easily submit another transaction changing their third party provider.