Here’s the famous diagram from the original paper:

One fundamental flaw of the original plasma design is that every user on a plasma chain needs to download and check every single transaction on that chain in order to keep their funds safe. This puts a cap on the total number of transactions that an individual chain can process every second! Nested chains were supposed to solve this problem (and thereby make the design more scalable) by putting plasma chains inside of plasma chains.

The purpose of plasma is really just to bundle a bunch of transactions together in a very efficient way. People can move funds into the plasma chain by depositing those funds into the chain’s smart contract, and people can move funds out of the plasma chain by going through some withdrawal process (the “exit game”). Although we usually think of this smart contract as a piece of code running on top of a blockchain like Ethereum, the plasma white paper proposed that we could also put this code on a form of smart contract sitting on another plasma chain.

Let’s demonstrate with pictures (just the original duplicated with some added color):

Whenever a user wants to deposit funds into the yellow plasma chain, they first need to send funds to the blue chain. To do this, they’ll send money to a smart contract running on Ethereum (green). Next, now that the user has funds on the blue chain, the user sends those funds to a special address on the blue chain that acts as a smart contract for a yellow chain. The user now has funds on the yellow chain!

To get funds out, the user can repeat the process in reverse — they’ll first move their funds from the yellow chain back to the blue chain, and then move their funds from the blue chain back to Ethereum. That’s pretty simple, but it does mean that users have to pay some (probably minimal) fees whenever they’re moving funds between chains.

Of course, this is a simplified, high-level version of the actual process. There’s a lot of hidden complexity that I’m handwaving for the sake of brevity.

Again, the reason why this design was proposed is because each individual plasma chain (as originally designed) could only handle 100–200 transactions per second. By nesting chains within other chains, you could increase total throughput significantly.

The problem with the idea was that it was simply too complicated to be implemented right away. It quickly became apparent that putting the EVM on a plasma chain is really hard. Without any great framework for putting smart contracts on plasma chains, we’re generally stuck with adding a bunch of really complex rules to the root chain (Ethereum) smart contract. Unfortunately, if you modify the architecture of the child chains in any significant way, you’re also forced to rewrite most of the root chain smart contract. So it made more sense to focus on a very solid base layer before starting to think about adding more layers.

The idea of nested plasma chains hasn’t died, but it’s become much less necessary. Research advancements like Plasma Prime have shown that there are simpler (and easier!) ways to scale by significantly reducing the amount of data that end-users need to process in order to keep their funds secure. These designs don’t reduce the computational load on validators compared to nested chains, but that’s a trade-off we’re willing to make (because dealing with that load is exactly what validators get paid for and they can can set fees commensurate with their costs).

That said, I still think there’s room for research into nested plasma chains, but they’re definitely not an immediate priority (because we have better and simpler options we can explore first!).

Hopefully that was helpful! Feel free to leave comments if you have other questions/feedback/inevitably find a typo.

Status Quo

First, let’s talk about how Ethereum deals with state, and particularly the representation of ownership. Every smart contract on Ethereum can manage a store of persistent state using storage variables. Storage in Ethereum is basically just represented as a key-value database, and variables can be modified whenever the contract is called.

I’ll explain some of my points by going through the main CryptoKitties smart contract, KittyCore. This contract stores information about which user owns which kitty in a mapping. This is pretty much the standard way to represent ownership. Let’s take a look:

/// @dev A mapping from cat IDs to the address that owns them. All cats have
/// some valid owner address, even gen0 cats are created with a non-zero owner.
mapping (uint256 => address) public kittyIndexToOwner;

This mapping is a critical part of the CryptoKitties contract! Whenever you transfer a kitty from one user to another (e.g. by using the transfer function), the contract updates this mapping:

/// @dev Assigns ownership of a specific Kitty to an address.
function _transfer(address _from, address _to, uint256 _tokenId) internal {
    … // stuff

    // transfer ownership
    kittyIndexToOwner[_tokenId] = _to;

    … // more stuff
}

This is how everyone knows who owns which kitty. But if you think about this for a few minutes, it’s a little weird. It’s kinda like you’re transferring a representation of a CryptoKitty instead of the kitty itself. There is no kitty “object” that you can move around and send from one account to the next, just the some data that sits in the KittyCore contract. Whenever you transfer a kitty, you’re really just updating the CryptoKitties contract to change the owner of that kitty.

This weirdness becomes even more clear when we look at the pattern for sending a kitty to a smart contract.

Here’s what I might expect: some user has a kitty, they send that kitty to the smart contract along with some extra data, the smart contract reacts by doing something.

Here’s what actually needs to happen: some user has a kitty, they first give the receiving smart contract approval to transfer the kitty on the user’s behalf, then the user calls a smart contract function with some data and the smart contract transfers the kitty to itself before doing anything else. wat?

Why?

First note that we have the exact same annoying approve/transfer pattern when it comes to transferring ERC20s. If you’re somewhat familiar with Ethereum, you probably understand why this is necessary — there’s basically no other good way to do it. You just can’t do the first (simpler) flow. But interestingly we don’t have this problem when moving around ETH. Smart contract developers will know that you can have users send ETH along with a transaction, and that the amount transferred can be accessed with msg.value. This is exactly the type of behavior that makes sense. What gives?

It’s really about how Ethereum handles state, especially state that represents value. ETH is the only “first class citizen” in this regard — that is, ETH is the only thing that Ethereum really recognizes as an asset that can be owned. Everything else is relegated to the land of “virtual” ownership. This might seem like a minor annoyance when you’re designing smart contracts, but it can have serious impact, especially with some new developments on the horizon.

Rent

Take, for example, the current conversations around rent in Ethereum. It’s been widely known that smart contract storage isn’t really being accurately priced. The EVM is charging a lot for storage up-front, but charging nothing afterwards. As a result, it’s just way too cheap to put data on Ethereum for long periods of time. Even worse, the incentives to remove data (like the gas refund) aren’t strong enough, and projects like GasToken are making this problem painfully obvious.

People are talking about new schemes to fix these issues by charging rent for storage. Generally, this makes storage cheaper up-front, but requires that someone make regular payments to keep that storage alive. If you ever fail to pay your contract’s rent, your contract’s data gets “evicted.” This isn’t deleting the entire contract data forever. Instead, the clients will keep a very small Merkle root that of all the data in your contract, which you can use to recover your contract by providing the original data (and paying your rent).

Now let’s see what this means for something like CryptoKitties. The CryptoKitties contract stores a lot of data — the search page on cryptokitties.co claims that it lists over a million kitties. Each kitty is represented by two 32 byte words, plus another word for the kittyIndexToOwner mapping:

/// @dev The main Kitty struct. Every cat in CryptoKitties is represented by a copy
/// of this structure, so great care was taken to ensure that it fits neatly into
/// exactly two 256-bit words. Note that the order of the members in this structure
/// is important because of the byte-packing rules used by Ethereum.
/// Ref: http://solidity.readthedocs.io/en/develop/miscellaneous.html
struct Kitty {
    uint256 genes;
    uint64 birthTime;
    uint64 cooldownEndBlock;
    uint32 matronId;
    uint32 sireId;
    uint32 siringWithId;
    uint16 cooldownIndex;
    uint16 generation;
}

That’s 96 bytes per kitty, about 100 megabytes for the entire contract. The storage rent on that much data is likely pretty expensive. Using one estimate from a few months ago, it’s probably about 100 ETH (currently ~$20k) annually.

Imagine that the maintainers of CryptoKitties stopped paying rent on the contract for some reason, and the contract data goes poof. How would you go about getting your kitty back? Well, you’d have to pay the rent to recover the contract… If you’re the only person who cares about their kitty, that’s 100 ETH a year. Even if you crowd funded the rent, you’re still paying a lot of money to support other people’s kitties. This makes zero sense. You should only have to pay for your kitty — not everyone else’s!

Sharding

This same problem pops up when we’re talking about sharding. One of the more interesting things in the world of sharded blockchains is the train-and-hotel problem. It’s actually pretty simple — let’s say the contract to buy train tickets is on one shard, but the contract to buy hotel rooms is on another. You’d like to book both a train ticket and a hotel room simultaneously — a hotel room but no train ticket is pretty useless (and vice versa). What do we do?

Well, one proposed solution is called “yanking” — you can temporarily move a train seat into the shard that contains the hotel contract, book both simultaneously, then move the seat back to its original shard. However, if train tickets were represented the same way CryptoKitties are, then you’d need to move the entire train contract onto the other shard temporarily. That also makes no sense (and annoys everyone who needs the train contract to stay still so they can somehow get to work on time, looking at you MTA).

Plasma

There’s even some applicability to plasma! If you read my previous story about why EVM-on-Plasma is so hard, then you might have an idea why: it’s not always clear who gets to move a contract from the plasma chain to the root chain. As a result, plasma smart contracts probably need to break things down to a point where ownership of each “state object” (e.g. kitty) becomes clear. I have no clue who should have control over the whole CryptoKitties contract, but I do know who should have control over my individual kitty.

This sort of state model is definitely useful when trying to design general computation inside a plasma chain. Some people are already working on a model based on this sort of theory. It might actually not even be possible to get close to general state transitions any other way.

What do we do?

This, again, is a symptom of the way state (specifically ownership) is represented. CryptoKitties could modify their contract so that each kitty is represented as its own contract, but that only helps so much. You still wouldn’t get to send kitties (or any other asset, besides ETH) along with function calls. It’s also much harder to manage this sort of system (upgradeability becomes much more complicated).

I’d like to see more systems where we get the best of both worlds. Ideally, each kitty should be represented as an individual object that can be modified in certain ways. It seems fine to have the controlling logic for each kitty handled by a single piece of upgradeable code, but each kitty should be a thing that’s separate from all other kitties. A lot of the theory here comes from the bitcoin UTXO model, but I think it could be more elegantly adapted for stateful applications.

It also makes sense to have all (standardized) representations of value, not just ETH, treated as a first class citizens. I should be able to transfer a kitty to a contract along with a function call instead of going through the whole approve/transfer flow. msg.kitty plz.

Unfortunately I’m not really an expert in the inner workings of the EVM. I’m sure there are plenty of annoying reasons why this is non-trivial for any blockchain, let alone a retrofit onto the EVM. If you, or other people you know, are thinking about this sort of stuff, I’d love to chat! Links to additional conversations or resources on this topic are always much appreciated.

Merkle Trees

First, let’s start with a quick refresher on Merkle trees. Merkle trees give us a way to cryptographically commit to a set of data. We start by hashing each piece of data in the set, and then keep hashing our way up the tree until we get to the root node.

That ends up looking like this:

Proving Inclusion

The root of this tree is just a hash — it tells us nothing about the contents of the tree. We can use something called a “Merkle proof” to show that some content is actually part of this tree. For example, let’s prove that A is part of the above tree. All we need to do is provide each of A’s siblings on the way up, recompute the tree, and make sure everything matches.

I went ahead and highlighted the siblings in blue. With just A, H(B), and H(H(C)+H(D)), we can recompute the original root hash. This is an efficient way to show that A is part of this tree without having to provide the entire tree!

Proving Non-inclusion

So we can easily prove that something is part of the Merkle tree, but what if we want to prove that something isn’t part of the tree? Unfortunately, standard Merkle trees don’t give us any good way to do this. We could reveal the entire contents, but that’s sort of defeating the point of using a Merkle tree in the first place.

Sparse Merkle Trees

Here’s where sparse Merkle trees come into play. A sparse Merkle tree is like a standard Merkle tree, except the contained data is indexed, and each datapoint is placed at the leaf that corresponds to that datapoint’s index.

Let’s say we have a Merkle tree with four leaves. We’ll populate this tree with some letters (A, D) to demonstrate. The letter A is the first letter of the alphabet, so we should put it at the first leaf. Similarly, we can put D at the fourth leaf.

So what happens in the second and third leaves? We just leave them empty. More precisely, we put a special value (like null) instead of placing a letter.

The tree ends up looking like this:

Proving Inclusion

Just like in a standard Merkle tree, we can use a Merkle proof to prove that A is part of this tree. This proof looks just like your standard Merkle proof:

Again, we’re just providing the siblings, H(null) and H(H(null)+H(D)), and checking that it matches the root.

Proving Non-inclusion

Here’s where the magic happens. What happens if we want to prove that C is not part of this Merkle tree? It’s easy! We know that if C were part of the tree, it would be at the third leaf. If C isn’t part of the tree, then the third leaf must be null.

All we need is a standard Merkle proof showing the third leaf is null!

This looks just like a standard Merkle proof, except that we’re proving the leaf contains null instead of C.

The best part of a sparse Merkle tree is that they’re really representing key-value stores, inside of a Merkle tree!

Drawbacks

Sparse Merkle trees are really cool because they give us efficient proofs of non-inclusion. However, this can also mean they get really, really big. 26 letters isn’t much, but most of the time we’re talking about 2²⁵⁶ hashes! That’s just way too many indices to generate a tree manually.

Luckily, there are some techniques to efficiently generate Merkle trees. The key to these techniques is that these giant sparse Merkle trees are mostly… sparse. H(null) is a constant value, and so is H(H(null)), etc. etc. Huge chunks of the tree can be cached!

Use Cases

Sparse Merkle trees are already being used in the wild to do some cool blockchain stuff.

Plasma Cash makes use of sparse Merkle trees to store information about deposited assets. Every Plasma Cash asset has a unique ID. Whenever an asset is transferred to a new user, a transaction is included in the sparse Merkle tree at the asset’s index! Proofs of inclusion (or non-inclusion!) are used to prove that a given transaction history is valid.

Sparse Merkle trees might even make their way into Ethereum! Ethereum researchers are looking into sparse Merkle trees as a replacement for the Merkle Patricia tries currently used to store Ethereum state.

As always, feedback/comments/questions are more than welcome. If you spot any typos, or you think anything needs clarification, let me know!

Most of the current work around Plasma basically just makes use of very simple UTXOs or non-fungible tokens. Lots of people want to know if it’s possible to create a Plasma chain that allows users to deploy EVM smart contracts. Unfortunately, this is a lot more complicated than it might seem for reasons that probably aren’t obvious if you don’t spend a lot of time working with Plasma. I wrote this to quickly outline why full EVM support on Plasma is non-trivial and then give some suggestions for what could be done to create a Plasma chain capable of running more general smart contracts.

Let’s talk a little bit more about Plasma before we start picking apart exactly why EVM-enabled Plasma chains are hard to build. One fundamental property of Plasma is that state represented on a Plasma chain must be able to be withdrawn to the root chain (e.g. Ethereum) in a way that maintains the integrity of that state. You should be able to freely move assets from the Plasma chain to the root chain, and vice versa. This functionality is particularly important when a Plasma consensus mechanism goes “bad” and users are forced to withdraw their assets from the Plasma chain.

To understand what this means in practice, let’s imagine a simple Plasma chain where users have accounts with which they can transfer or receive funds. You’re one of the users on this Plasma chain and you’d like to withdraw your funds. How do you do that? Well, you effectively tell the contract sitting on Ethereum that you have some funds on the Plasma chain and that you’d like to withdraw those funds. Of course there’s a catch — you shouldn’t be able to lie about how much is in your account. This is why we introduce something called a “challenge period” during which an invalid withdrawal can be blocked.

Now let’s extended this idea to the type of EVM smart contracts you might be familiar with, like a simple multisig account. If this account currently sits on the Plasma chain, then we need to provide some way for the wallet to be “withdrawn” to the root chain. However, we still want to keep the funds in a multisig — we effectively want to move the entire smart contract back onto the root chain. Remember that each EVM contract has state, balance, and code. So what we’re really doing is moving the state, balance, and code of this multisig contract from the Plasma chain to the root chain. The contract should then be able to operate normally on the root chain.

So who actually gets to decide to move stuff from the Plasma chain to the root chain? Well, if we’re talking about something simple like an account, it makes a lot of sense to say that the owner of the account should be able to withdraw the balance at any time. If we’re talking about a multisig account, then we could design a few different mechanisms to determine when the multisig is moved to the root chain. Maybe every user in the multisig needs to sign off, maybe n-of-m users need to sign off, or maybe only one user needs to sign off. All of these are potentially valid mechanisms — we start to see that it makes sense for the designers of the multisig to decide which mechanism is most appropriate.

But here’s the problem — it’s not always clear who gets to move a contract from the Plasma chain to the root chain. Imagine we have a smart contract (on some Plasma chain) that represents lots of virtual kitties. Let’s say the consensus mechanism goes “bad” and everyone needs to leave the Plasma chain to keep their funds safe. What do we do about our virtual kitty contract? As we just discussed, we need to move the contract back onto the root chain. Unfortunately, if we allowed just anyone to withdraw the contract, then (rude) users would almost definitely just withdraw as many contracts as possible to make the Plasma chain unusable. We have to come up with a better mechanism.

We could probably think of a few mechanisms, but it’s likely that they’d be too centralized or too expensive. One seemingly obvious mechanism might be a voting mechanism that decides when the contract can be withdrawn. A small set of eligible voters would highly centralize control over the contract. However, the more users eligible to vote, the more expensive the voting mechanism.

Let’s quickly go back to the process for withdrawing stuff from the Plasma chain. Remember that we can block an exit if we show that the state being withdrawn is somehow invalid. Imagine our virtual kitty contract says that I’m the owner of kitty 123. Now we want to withdraw the contract, so we need to specify the current state of the contract. Part of that current state is “Kelvin owns kitty 123.” What happens if I make someone else the owner of the kitty right in the middle of the contract’s challenge period? The “real” state is now “user X owns kitty 123.” The state being withdrawn is now invalid (and can therefore be challenged). This is our second big problem — if anyone can modify the state of the contract, then anyone can block an exit.

This leads us to our final problem — we need to validate that the state change presented in a challenge is actually a valid state change and validating EVM state changes inside the EVM is hard. For basic contracts like accounts, a valid state change just requires a signature from the owner of the account and is simple enough to check inside the EVM. However, for complex EVM contracts, things get much more expensive. One way to validate EVM executions is to use something like TrueBit. This might be the simplest option, but it basically kills the security properties of Plasma by making it dependent on an external system. Ideally, if we want to validate single EVM steps in a trustless way, then we need to implement the EVM inside the EVM 🤯. People have been thinking about this for a while and Vitalik even created an EIP to start discussing this. I really recommend checking out the EIP to understand why it’s so difficult (gas limits inside gas limits, hmm…).

All of this is why it’s so hard to create a Plasma chain that operates a lot like Ethereum does today. Let’s quickly recap:

1. It’s not always clear who gets to move a contract from the Plasma chain to the root chain.
2. If anyone can modify the state of the contract, then anyone can block an exit.
3. Validating EVM state changes inside the EVM is hard.

So where do we go from here? Well luckily we’ve started to come up with a few concepts that basically involve breaking typical smart contracts down to a level where these questions don’t matter as much. To illustrate, let’s go back to our virtual kitty contract. It might be more clear who’s responsible for moving stuff to the root chain if everyone were moving their own kitty instead of moving the entire contract. We can do this if we represent each kitty as its own mini smart contract that can only be modified by the kitty’s owner. This simple shift in design makes the first and second problems almost entirely irrelevant.

I’ll be publishing some initial thoughts that came out of discussions with Dan Robinson about this sort of design and how to make it usable for developers. The gist is that it’s probably easiest to use something like TXVM and a high-level language that feels like writing EVM smart contracts but automatically breaks things down in the way I just discussed. We’re calling this “Plasma VM” because it makes sense and it’s also MVP backwards.

Of course, feedback/questions/comments are always more than welcome. Let me know if anything is still confusing and I’ll try to make it a little more clear!