Validity Proofs + Plasma Cash = Simpler Exit Game/Coin History?

#1

I wanted to repost [0] from ethresear.ch in case people on this forum are interested as well.

Currently it seems most direction of zk-plasma is toward rollup-style. The issue with this is that as a user I need to trust a party that the data of the entire state up to the point I care about is available. In contrast, I believe there are wins to be had from a similar construction that’s still set up for every user to be responsible for only their data’s availability (ie. transaction won’t roll back once it’s available).

The tl;dr of the post is that requiring validity proofs for each Plasma block reduces history size requirements to O(#coinslots).

[0] https://ethresear.ch/t/validity-proofs-plasma-cash-simpler-exit-game-coin-history/5333
[1] There’s some more conversation about this here: https://ethresear.ch/t/minimal-fully-generalized-s-ark-based-plasma/5580/6

#2

This is in the long-term research roadmap for us, after we implement the most vanilla version of Plasma Cash (for an NFT trading use case) and work through what optimizations exist (there are so many!)

Would love to chat more at some point!

#3

You’re right that this construction simplifies a lot of the plasma design. In fact we just validated that our block structure (outlined here http://spec.plasma.group/en/latest/src/01-core/double-layer-tree.html ) is SNARKable.

The best part of this sort of approach is we don’t need to change anything about our current plasma designs. These snarks can be added incrementally to a generalized plasma implementation by creating predicates which accept zkSNARKs as deprecation proof. Plus, we can even keep snarks fully off chain and only use them for exclusion proofs. That means our history is linear in the number of transactions, not blocks.

There’s no “flavor” of plasma for this design, instead it is simply a key component to a good generalized plasma implementation.

#4

linear in the number of transactions

You mean, for a given coin, the number of transactions that the coin has had? I think what I’m describing actually gets you history that’s linear in the number of coinslots, which should be strictly less, and require less data transfer for a send. Happy to discuss further to clarify, as I may be missing a key bit that you’re accounting for :smile:

There’s no “flavor” of plasma for this design

I’ve this dubbed this sort of thing (plasma cash + validity proofs posted for each block) as “Plasma Max Cashflow” (to only myself). “Max” as in, maximally viable, since the history size is so “reasonable”, as well as the synchrony assumptions (imo).

#5

Sorry I wasn’t clear. What I was describing was breaking this approach down into two phases:

  1. SNARK exclusion proofs – this gets you down to history linear in the number of transactions (because we haven’t SNARKed the actual transactions, we still need to download and validate all transactions for a coin slot). This is relatively easy & we already figured out how to do this with our block structure.
  2. SNARK exclusion proofs & tx validity – this is what you’re doing. It’s super awesome, but it means that we need SNARK-able circuits for our state transitions which at this time is a bit annoying to build. That said, in the long term this is the way to go & actually requires no hard “upgrade” to the generalized plasma smart contracts because this logic can be included in a predicate.

Breaking it up into these phases means that we can release generalized plasma sooner & then improve it over time as SNARK tooling gets better.

Am I correctly representing your idea/making sense?

#6

Ah, thanks for clarifying, I think I’m following what you’re saying. To reiterate in my own words, so you can correct any misunderstandings:

SNARK exclusion proofs

Basically Plasma Cash, but a coin’s history’s validity is ensured by a zkproof over blocks proving that no txn of that coin occurred. This makes the history a lot faster to validate, since all the blocks between txns collapse into the single zkproof of exclusion across all of those blocks.

I like this idea for the near-term, I agree that it’s much closer to reality than a proof over the entire state transition. Although I’m unsure that this design is “viable enough” to be used out in the wild by tons of people-- do you think this would be enough? Maybe with some kind of checkpointing-- otherwise there may be too much data to transfer from sender to receiver for each txn.

tx validity

Once we have these proofs, I’m pretty sure we won’t need the exclusion proofs anymore; a txn’s inclusion along with its validity proof imply its valid history. It seems like we’re on the same page on this. I haven’t dug into how predicates could fit in to this kind of system, but my guess is we could have a transfer of a token be validated by a proof over an arbitrary predicate nearly as easily as just by a signed message from current owner.

Admittedly I haven’t actually gotten my hands dirty with the zkproof implementations yet, and it’s easy for me to say “just snark the whole state lol” vs actually implementing and running it in reasonable time. My gut feeling is that some kind of batching or aggregating of proofs[0] will be a leap forward in enabling magic stuff like this, and without any kind of batching it may be difficult-to-impossible.

Thanks for the conversations Karl! Excited to see the progress of this work inching towards production :grinning:

[0] https://ethresear.ch/t/batching-of-zk-snark-proofs/5626

#7

Perfect! I think we’re on the same page :slight_smile:

Although I’m unsure that this design is “viable enough” to be used out in the wild by tons of people-- do you think this would be enough? Maybe with some kind of checkpointing

Let’s actually calculate the feasibility of this history size here-- our assumptions:

  • user receives a coin which has been transferred 10 times – seems reasonable?
  • each SNARK exclusion proof is 300 bytes – this is based on what @barrywhitehat told me a few days ago
  • each transaction is 200 bytes – this seems pretty reasonable
  • transaction inclusion proof is 300 bytes – our block height grows in the number of txs, so a tree of height 10 seems reasonable.

With this we can say for each spend the size is 300+200+300=800 so the history size is 800*10 == 8 kilobytes. Not bad! At all! Even if it’s transferred 100 times we’re at 80 kilobytes! Still reasonable.

Ok so I’m not concerned anymore that the history will be too big for a simple coin validation. The only history that gets really big is if we bind a lot of coin histories together. So if a state requires validating 100 coin slots, and then all 100 have been spent 100 times, we get to 8MB which is getting a little scary and 1000x that would be totally infeasible (8GB).

Anyway, thanks for bringing this up! It’s a great point and your thoughts are on point!