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

new-extension
#3

If a user is being griefed this way, exiting and re-deposit his coin is equivalent to “manual on-chain checkpointing” for a single user. The challenge would be to amortize this cost over multiple users.

#4

This makes me wonder why it should even be a requirement that Plasma XT checkpoints can only be operator-initiated. It makes plenty of sense for the operator to initiate checkpoints (because they have all the information about the state), but users (or anyone) could also conceivably initiate them, by doing the same thing—putting up a bond, and revealing a state commitment and a cryptoeconomic aggregate signature.

If that works, then operators can’t even prevent users from checkpointing their state (although, since they can prevent users from transacting, this isn’t a particularly significant win).

This might be a good reason to look at alternative ways of expressing the bitmaps in cryptoeconomic aggregate sigs. The only requirement is that you somehow identify all the coins that assent to the checkpoint. This can be done via bitmaps (if there are many adjacent coins involved in the checkpoint), but if participating coins are much sparser, a list of indices might be more efficient; indeed if they’re much denser, a list of the unincluded coins could be more efficient, or some kind of runlength encoding. It’s a pretty straightforward compression problem. (These alternative forms could be useful for operator-initiated checkpoints as well, although those are likely to be dense and random enough for bitmaps to be the most efficient representation).

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

Plasma Cash defragmentation, take 2
#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.