Plasma Cash verification cost

[ldct]

There are two proposals to alleviate this, what do you think of them?

Compression

Most of the coin validity proofs are exclusion proofs, and those can be compressed using SNARKs/STARKs. For e.g. if we use constant-sized proofs this means that a coin validity proof will only increase in size when a coin is spent.

Back-of-the-envelope calculation: if a coin is spent once per day, the proof size becomes 1.2 MB per coin.

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

I’m not sure it would work to use a ZK-snark for the non-existence proofs, unless the parent chain is willing to accept ZK-snarks for the exit transactions. Otherwise, you don’t have enough information to respond to a challenger, right? Now that I think about it, you are right. In order to be able to respond to type (iii) challenges you have the proofs for every transfer in the coin’s actual history. If there are t blocks and h transfers (history length), then this already reduces required da…

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

An alternative way to accomplish this might be for the operator to construct a merkle tree T committing to the number of times every coinid has been spent since the genesis plasma block, and to use snarks to verify the integrity of the root hash of the tree. Then a client checking the validity of a coin can download the witness for the branch of this tree that tells him that his coin has been spent h times, and then download h inclusion proofs. For clarity, an example of this is shown below fo…

Checkpointing

We know that withdrawing and re-depositing a coin will “reset” the length of the coin validitiy proof; this construction allows you to do this at an amortized cost of 1 bit of storage (SSTORE) per coin.

Back-of-the-envelope calculation: if we do this every 3 months would make the proof size is upper-bounded at 0.4 GB per coin at the cost of a few cents per year.

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

Plasma XT embraces Plasma Cash’s original vision of simple, reliable, low-cost transactions for everyone in the world.* Special thanks to Dan Robinson for discussion and coming up with much of this, as well as David Knott, Joseph Poon, Karl Floersch, and Vitalik Buterin for ideas and feedback that led to this design. Another special thanks to Justin Drake for the gorgeous construction of cryptoeconomic aggregate signatures and to Sunny Aggarwal for the Plasma XT name. (enough memes now) Reall…

Combinations Thereof

We can combine these two techniques by doing a checkpoint when even the compressed proofs get too big. Analysis: with checkpoints, we can have the coin validity proof grow as O(f(n)) and the per-unit-time cost of owning a coin grow as O(g(n)) with the constraint that fg \in O(n) where n is the total number of plasma blocks (i.e. increases by 1 per minute).

Three points on this tradeoff space are

1. Bounded proof sizes, constant rent (e.g. 1 cent/year/coin)
2. Constant cost to own a coin, but proof size grows linearly (e.g. 1.7gb /year)
3. Both cost and proof size are O(\sqrt n)

By combining them we relax the constraint to fg \in O(s) where s is the number of spends of the coin (i.e. increases by 1 every time the coin is spent).