special thanks to YOUR NAME HERE for WHAT YOU DID HERE :D

SNasma

Abstract

We define a SNARK implementation of Plasma where different users can select the security of their accounts. It is possible for a user to ensure that no one will ever be able to withdraw their leaf unless they allow it.

Introduction:

Plasma currently works by allowing a centralized operator to create state transitions. If they create an invalid state transition anyone can challenge them and revert it. However, if the operator refuses to publish information about the new state, users are unable to know if the state transition was valid or not.

This is solved by requiring that all users exit their funds once data unavailability is detected (also known as "mass exits"). This results in timeouts for deposits and withdrawals and limits the number of unspent outputs that can safely exist inside the system.

SNARKs can be used to disallow invalid state transitions. In this document we describe one such system called SNasma.

State transitions:

We start with a UTXO model. Each output is hashed with the owner's public key and that is a leaf in the Merkle tree.


                                          LEAF
                        +----------------^----------------+
                       LHS                           Unspent Output
               +----------------+                
           Public_key_x    Public_key_y

Each leaf is stored in the same Merkle tree:

                                     Merkle Root
                        +----------------^----------------+
                      Node1                               Node2
               +----------------+                  +----------------+                
           Leaf1              Leaf2            Leaf1            Leaf2

If a user wants to transfer ownership of a UTXO they provide a signature to the operator. We define Snark 1 batch_transfer which aggregates signatures and updates the merkle root accordingly. The EVM then verifies the SNARK and updates the merkle root if that SNARK constitutes a valid state transition.

The operator handles state transitions by batching together multiple transactions into a chain

State1 -> State2 -> State3 -> State4 -> State5 -> State6 -> State7 -> State8 -> State8

Where each state transition has multiple transactions which updates multiple leaves.

The above construction prevents invalid state transitions. This significantly lowers the attacks the operator can make since they are now unable to steal funds from the users of the SNasma chain. They can however make data unavailable and deprive users of their funds permanently.

Data availability guarantees

To over come this we tried a bunch of EVM based data availability guarantees which ultimately limited our scaling ability with costs of ~5000 gas per transaction (not including SNARK verification). That is better than current in EVM batched transactions but we want to do better.

Plasma does not provide any data availability guarantees, however it introduces an exit game which allows users to exit from the latest known valid state. In order to prevent invalid exit requests, there is a dispute period during which other users can challenge invalid exit requests.

If there is data availability, users should still be able to exit. Due to the usage of the above SNARKs, there is no way to have an invalid state transition, which gives us the following advantages over plasma:

  1. Only the people who used to own your leaf can try withdraw it. A malicious operator cannot try to exit your leaf unless she already owned it. And even then you can stop her by proving that you own it now.

In order to improve these guarantees we define SNARK_prevent_withdraws_before_block that disallows withdrawal of leaves before state X. We have a SNARK to validates multiple signatures and confirms they owned the leaf at the state they selected. Then we create an EVM mapping between the leaves and the min_withdraw_block of the leaf defined by the aggregate signature.

We have to save this in the EVM which is kind of expensive but we need to be able to check this at withdraw time.

Note:

We can probably do better than just locking the tx on the "unavailable chain" I think we can actually do an exit to another provider from a point when data is still available. I will add more on this tomororw.

EVM withdraw

  1. User requests withdraw from old state Y. They prove that they own a given leaf and try to exit with it.
  2. Check that the min_withdraw_block for that leaf is less than Y.
  3. They wait a timeout period X which others can use to contest it.
  4. During the timeout anyone can come forward with a newer state than Y where the leaf is different and prevent the withdrawal.
  5. After the timeout has elapsed a user can withdraw their leaf but the EVM notes its address in the tree and prevents any other withdrawals.

This way a user can disallow withdraws of their leaf before they received it. Taking complete ownership of it. This way there is no way anyone can take this output unless the user allows them to. At this stage the users funds are not at risk and we can wait for the opportune moment to exit.

Transactions in SNARK after withdraw

After withdrawing via the EVM method the leaf is still a valid in the SNARK's leaf. However no one should be able to withdraw from it as the EVM knows that that leaf has already been withdrawn. It's important users do not accept payment from leaves that have been withdrawn.

In the future it may be required to pour transactions to change the number of inputs and outputs. This is probably possible using this method but you need to update the ownership of multiple leaves.

Select a repo