Quick Overview

Let’s start with some intuitions for how optimistic rollup works end to end on mainnet Ethereum, then dive in deep.

The following is a chronicle of the life of an optimistic rollup smart contract… named Fred:

1. Developer writes a Solidity contract named Fred. Hello Fred!
2. Developer sends transaction off-chain to a bonded aggregator (a layer 2 block producer) which deploys the contract.
    — Anyone with a bond may become an aggregator.
    — There are multiple aggregators on the same chain.
    — Fees are paid however the aggregator wants (account abstraction / meta transactions).
    — Developer gets an instant guarantee that the transaction will be included or else the aggregator loses their bond.
3. Aggregator locally applies the transaction & computes the new state root.
4. Aggregator submits an Ethereum transaction (paying gas) which contains the transaction & state root (an optimistic rollup block).
5. If anyone downloads the block & finds that it is invalid, they may prove the invalidity with verify_state_transition(prev_state, block, witness) which:
    — Slashes the malicious aggregator & any aggregator who built on top of the invalid block.
    — Rewards the prover with a portion of the aggregator’s bond.
6. Fred the smart contract is safe, happy & secure knowing her deployment transaction is now a part of every valid future optimistic rollup state. Plus Fred can be sent mainnet ERC20’s deposited into L2! Yay!

That’s it! The behavior of users & smart contracts should be very similar to what we see today on Ethereum mainnet, except, it scales! Now let’s explore how this whole thing is possible.

Optimistic Rollup In Depth

To begin let’s define what it means to create a permissionless smart contract platform like Ethereum. There are three properties we must satisfy to build one of these lovely state machines:

1. Available head state — Any relevant party can download the current head state.
2. Valid head state — The head state is valid (eg. no invalid state transitions).
3. Live head state — Any interested party can submit transactions which transition the head state.

You’ll notice that Ethereum layer 1 satisfies these three properties because we believe 1) miners do not mine on unavailable blocks, 2) miners do not mine on invalid blocks*; and 3) not all miners will censor transactions. However, it doesn’t currently scale.

On the other hand, under some similar security assumptions, optimistic rollup can provide all three guarantees at scale. To understand the construction & security assumptions we’ll go over each property we’d like to ensure individually.

#1: Available head state

Optimistic rollup uses classic rollup techniques (outlined here) to ensure data availability of the current state. The technique is simple — block producers (called aggregators) pass all blocks which include transactions & state roots through calldata (ie. the input to an Ethereum function) on Ethereum mainnet. The calldata block is then merklized & a single 32 byte state root is stored. For reference, calldata is 2,000 gas per 32 bytes while storage is 20,000 gas. Additionally, the gas cost of calldata will be reduced by almost 5x in the Istanbul hard fork.

Notably, we can use data availability oracles other than the Ethereum mainnet including Bitcoin Cash and Eth2. With Eth2 phase 1 all shards can serve as data availability oracles, scaling TPS linearly in the number of shards. This is enough throughput that we will hit other scalability bottlenecks before we run out of available data, for example state computation.

Security Assumptions

Here we assume honest majority on Ethereum mainnet. In addition, if we use Eth2, ETC, or Bitcoin Cash, we similarly inherit their honest majority assumptions.

Under these assumptions, using a trusted availability oracle to publish all transactions we can ensure that anyone can compute the current head state, satisfying property #1.

#2: Valid head state

The next property we need to ensure is a valid head state. In zkRollup we use zero-knowledge proofs to ensure validity. While this is a great solution in the long term, for now it is not possible to create efficient zkProofs for arbitrary state transitions. However, there’s still hope for a general purpose EVM-style state machine! We can use a cryptoeconomic validity game similar to plasma / truebit.

Cryptoeconomic Validity Game

At a high level the block submission & validity game is as follows:

1. Aggregators post a security deposit to start producing blocks.
2. Each block contains [access_list, transactions, post_state_root].
3. All blocks are committed to a ROLLUP_CHAIN contract by a bonded aggregator on a first come first serve basis (or round robin if desired).
4. Anyone may prove a block invalid, winning a portion of the aggregator’s security deposit.

To prove a block invalid you must prove one of the three following properties:

1. INVALID_BLOCK: The committed block is *invalid*. 
   This is calculated with `is_valid_transition(prev_state, block, witness) => boolean`
2. SKIPPED_VALID_BLOCK: The committed block "skipped" a valid block.
3. INVALID_PARENT: The committed block's parent is invalid.

These three state transition validity conditions can be visualized as:

There are a few interesting properties that fall out of this state validity game:

1. Pluggable validity checkers: We can define different validity checkers for is_valid_transition(…) allowing us to use different VMs to run smart contracts including EVM and WASM.
2. Only one valid chain: Blocks are submitted to Ethereum which gives us a total ordering of transactions & blocks. This enables us to deterministically decide the “head” block, and thereby require aggregators to prune invalid blocks before submitting a new block.
3. Sharded validation: This validity game can be played out at an individual UTXO basis. Instead of invalidating full blocks, we partially invalidate them — similar to Plasma Cash. Note that this does not require proving all invalid transitions up front for a single block. Partial block invalidation means we can validate only UTXOs for contracts we care about to secure our state. To learn more about how UTXOs enable parallelism check out this Cryptoeconomics.study video!

A Note on Watchtowers

One challenge to adoption of L2 has been the added complexity of watchtowers. Users contracting watchtowers adds yet another entity to manage to an already complex system. Thankfully, watchtowers are naturally incentivized by the optimistic rollup cryptoeconomic validity game! All data is available & therefore anyone running a full node stands to gain the security bond of all aggregators who build on their invalid chain. This risk incentivizes aggregators to be watchtowers, validating the chain they are building on — mitigating the verifiers dilemma.

A Note on Plasma

Many plasma constructions also rely on cryptoeconomic validity games; however, in plasma autonomous smart contract state enforcement is impossible without zkProofs or a fisherman’s game during a data withholding attack (the data availability problem). Thankfully rollup gets around the data availability problem by posting the minimal information needed to compute state transitions on-chain. Still, plasma is critical if we want to scale up to transactions per second in the hundreds of thousands (and more) — a long term necessity but not a requirement in the medium term for many smart contracts.

Security Assumptions

1. This cryptoeconomic validity game works with a single honest or even rational verifier assumption. We can say it is a “rational” verifier as opposed to “honest” because they may be economically incentivized with challenge games.
2. Additionally we assume the mainnet is live, meaning it is not censoring all incoming transactions attempting to prove invalidity. Note that the aggregator unbonding period is in some sense the liveness assumption on the mainnet (eg. if we require a 1 month unbonding period, then invalidity must be proven within that month to forfeit that bond).

Under these assumptions, all invalid blocks / state transitions will be discarded leaving us with a *single* valid head state, satisfying property #2.

#3: Live Head State

The final property we must satisfy is liveness, often known as censorship resistance. The key insights which ensures this are:

1. Anyone with a bond size above MINIMUM_BOND_SIZE may become an aggregator for the same rollup chain.
2. Because honest aggregators may prune invalid blocks, the chain does not halt in the event of an invalid block.

With these two properties we’ve already got liveness! Honest aggregators may always submit blocks which fork around invalid blocks & so even if there’s just one non-censoring aggregator your transaction will eventually get through — similar to mainnet.

A Note on Liveness vs Instant Confirmations

One property we really want is instant confirmations. This way we can give users sub-second feedback that their transaction will be processed. We can achieve this by designating short-lived aggregator monopolies on blocks. The downside is that it trades off censorship resistance because now a single party can censor for some period of time. Would love to hear about any research on this tradeoff!

Security Assumptions

With two security assumptions we get liveness:

1. There exists a non-censoring aggregator.
2. Mainnet Ethereum is not censoring.

Under these assumptions, the optimistic rollup chain will be able to progress & mutate the head state based on any valid user transactions, satisfying property #3.

Now all three properties are satisfied & we’ve got a permissionless smart contract platform in Ethereum L2!

Scalability Metrics

The following estimates are purely based on data availability. In practice other bottlenecks could be hit, one being state calculation. However, this does provide a useful upper bound.

ERC20 Transfers with ETH1 Data availability

Calculations are based on this little call-data calculation python script.

Note that these ERC20 transfers are calldata optimized. Additionally note that the nice thing about Optimistic Rollup is we aren’t limited to ERC20 transfers!

ECDSA Signature
~100 TPS without EIP 2028
~450 TPS with EIP 2028 (coming in October 2019)

BLS Signature / SNARK-ed Signatures
~400 TPS without EIP 2028
~2000 TPS with EIP 2028 (coming in October 2019)

With external availability oracles (eg. ETH2, Bitcoin Cash)

~linear in relation to the amount of throughput the availability oracle can handle.

That’s a lot more than 2000 TPS!

Optimistic Rollup vs Plasma

Optimistic Rollup shares much in common with Plasma. Both use aggregators to commit to blocks on mainnet with a cryptoeconomic validity game ensuring safety. The sole divergence is whether or not we have an availability receipt ensuring block availability.

The similarities between the two solutions allows for lots of shared infrastructure & code between the two constructions. In a mature layer 2 ecosystem it’s likely that we will see rollup, plasma, and state channels all working together in the same client (a smart wallet). Oh, have I mentioned the OVM? 😁

Yay Optimistic Rollup 🎉

Optimistic Rollup occupies a nice niche in the space of layer 2 constructions. It trades off some scalability for general purpose smart contracts, simplicity, & security. Plus being able to run secure smart contracts means that it can even be used to adjudicate other layer 2 solutions like plasma and state channels!

Call it “the layer 1 of layer 2s.”

Anyway, enough research — time to implement a robust, comprehensive, and user friendly Ethereum layer 2! 😍

Special thanks to Vitalik Buterin for working through these ideas with me and for coming up with much of this.

Additionally, thank you Ben Jones for much of this and Jinglan Wang, Kevin Ho & Jesse Walden for edits.

Update: Shout out to the great and related work by John Adler in his article on Merged Consensus which can be compared to optimistic rollups — Check it out here! Plus this proposal to improve Eth1’s ability to act as a data availability oracle — more tps!

Ethereum Smart Contracts in L2: Optimistic Rollup was originally published in Plasma Group Blog on Medium, where people are continuing the conversation by highlighting and responding to this story.

Happy new year, all! This week marks the first anniversary of Plasma Group. It will also be the last. We will continue performing the highest leverage actions for the community that we can. This means we will be evolving.

We see Ethereum entering a new chapter, and we’re so proud to have been able to contribute to that progress. A year ago, scalability research felt like the most pressing need to us, so we threw everything we had into accelerating it. It is amazing to see the multitude of competent teams pushing production plasma into reality now. This shift from research to implementation means that our mission as a research organization must shift as well.

Scalability is still a priority — but another critical issue has become clear to us: the problem of funding and sustaining public goods. As we solidify our vision for our next steps, this issue weighs heavily on our minds. It played a large role in our year as a nonprofit releasing un-monetized content to the public domain.

For now, a concrete step we can take toward this goal is to re-seed our remaining runway. We will be donating the entirety of what we have left to Gitcoin. We believe Gitcoin is doing some of the most critical and underrated work not only in the blockchain space but also in the greater space of public goods.

Finally, we’d like to present to you our final research contribution as Plasma Group, reflect on a year of scalability progress, and share our outlook for the future.

Optimistic Game Semantics

Before we go, we have one last research contribution to pass on. This time, we are sharing our work on Optimistic Game Semantics, formerly known as the Optimistic Virtual Machine — a set of conceptual underpinnings which motivates the possibility of a single piece of software that can run many L2 constructions under a single, unified theory. For us, this represents a “culmination of generalizations” — from the dozens of plasma flavors to composable L2s, Optimistic Game Semantics shows how one day, all L2 constructions might build on the same foundation. In other words, even when the flavors vary, the ingredients are shared.

You can find the paper here.

An Eventful Year…

The path was not always straight — not without the occasional red herring — but every misstep makes the way forward clearer, and overall we are thrilled with the progress that L2 has seen in the past year.

Some of Plasma Group’s own finest moments included:

• Creating the first ever Plasma Cashflow implementation
• Opening the door for applications on plasma with our generalized plasma spec
• Organizing the premier Scaling Ethereum conference from which many research breakthroughs emerged for lots of teams
• Coining Optimistic Rollup and demonstrating the viability of fully fledged smart contracts on L2 with our Unipig demo

The Future: Public Goods

After a year of progress, we are incredibly optimistic about the future of scalability. The biggest trend we see today is a shift towards implementation. Many hard problems have been solved, and viable, production-ready implementations are finally on the rise. Across the ecosystem, the efforts are too many to count.

We’re eager to get to work on the next urgent problem facing the community we love. We still have a lot that we need to figure out! But we’re not done working for this community, so stay tuned — you’ll be hearing from us again very soon. It’s certainly not a problem we’ll be sleeping on.

Thank you all for a tremendous year.

Importantly, none of this was done in a vacuum! We have many people to thank and recognize for their contributions to both our work and the general L2 effort:

Donors

Ethereum Foundation
The EF has and continues to do incredible work for the ecosystem. They are a backbone of one of the greatest communities ever. We have benefited greatly from the resources that the EF has provided to us — the leadership of Aya, experienced words of wisdom from Albert, and the many brilliant folk who work at the EF whom we have had the opportunity to learn from.

OmiseGO
OmiseGO was among our earliest supporters, and without them we wouldn’t have had the start that we did — not just their financial and moral support for Plasma Group, but also the groundwork they laid in manifesting and memeing plasma and their continued conviction in moving it forward. Audits on the first version of the OMG Plasma Framework, which took inspiration from Plasma Group’s [work on predicates], are nearly finished. It’s exciting to see our work being used in the wild, and it’s also a testament to OmiseGO’s commitment to the kind of cross-pollination that makes this space so special.

Pandia Jiang, Founder — EDCON, Linktime, Unitimes
Pandia was our very first donor. She has been a pillar in the global Ethereum community and a valuable resource to us — from making introductions to advising us on managing dynamics in a distributed team. We have benefited greatly from the community work she has done across borders and it was her faith in us that bootstrapped the team and propelled us into our very first testnet release of Plasma Cashflow. She has been a tireless advocate of decentralization and a great inspiration to our own mission.

Consensys
As a fellow NYC based company, Consensys have been unbelievably supportive, warm and welcoming. They’ve lent us space, dev time, and constant encouragement. That a company could grow to such a scale without ever straying from the philosophy that contributing to the success of the whole doesn’t negate the success of the individual is really extraordinary.

Consensys has done so much legwork to bringing visibility and talent into ethereum and we thank them for that.

Gitcoin
Gitcoin’s CLR grant rounds brought many people together to support Plasma Group and lots of other worthy projects. Those donations helped keep us going, but it’s not just the money: it’s a sense of community and a show of support. The validation that we received from seeing so many members of the community contribute was just as valuable as the money they gave. As leaders in exploring and executing novel strategies for sustainably funding public goods, we believe Gitcoin is doing critical work for the community that every single person benefits from.

Matic
Besides being our biggest CLR donor, Matic has been incredibly supportive of our work on predicates. They helped spread the word about our predicates framework and included it in an implementation of their own. We’re so grateful for their contribution to the L2 scalability effort through their word on sidechains, and proud to have worked alongside such a fantastic team for the past year.

Status
Status was another one of our earliest backers. The support of a project that so embodies the open source ethos means a great deal to us. Status has never wavered from their commitment to individual sovereignty, freedom of expression, and open infrastructure. These values and the tools that put them into practice are exactly what we work so hard to build strong foundations for.

Collaborators & Contributors

Uniswap
We’ve always loved the Uniswap team and their incredible style. It was a blast to collaborate with them on UniPig. We are so proud of our friends for the work they’ve done and the ethos they embody.

Whiteblock
We were fortunate enough to contract Whiteblock’s unbeatable team of fantastic engineers. Their incredible responsiveness and lightning grasp of the architecture earns a big gold star from us. We highly recommend Whiteblock to any blockchain team that wants access to some big brains.

Abbey Titcomb
Between gigs at a VC firm and Radicle, Abbey crushed heaps of research with us. Nobody throws a more powerful punch than Abbey. We miss having her firepower close to us, but we are all so lucky to have her as part of the community.

Alex Attar
We first got the opportunity to work with Alex at ETH Denver where he blasted through contracts for the first Generalized Plasma implementation with us. He has been an incredible friend to all of us, and we can only hope to match the level of support he has shown.

Cryptoeconomics Lab
Whether it’s the pure dev firepower of Syuhei, or Yuriko’s clean research and writing, we’ve been impressed time and time again by the brilliance of the members CEL team. We have thoroughly enjoyed working with them to hone our understanding of plasma and we have high hopes for their bright future.

Dan Robinson
The Karoke King and Poppin’ Polymath. We can’t believe that we had the stupendous fortune of having him as an advisor this past year. The breadth and depth of his knowledge astounds us every day.

Eva Beylin
We asked Eva to help organize the premier Scaling Ethereum conference. She ended up pulling the entire thing together in record time. Because of her deep expertise in crypto and her penchant for efficiency, many attendees stated it was the best conference they’d ever been to. We agree ❤

Georgios Konstantopoulos
Georgios the Greek Enigma has always been a source of invaluable feedback and inspiration for our research work. He doesn’t just hustle, he is Hustle itself and we aspire to get on his level.

Megan Knab
If anybody needs a crypto tax accountant or bookkeeper, Megan’s company Veriledger will be your holy grail. We are thankful to Megan for subduing our tax and financial panic with ease, patience, and obvious expertise.

Mikerah Quintyne Collins
Mikerah was also critical to the success of the Scaling Ethereum conference, and she’s always been an inspiration to us with her grit, candor, and creativity. You can check out some of her awesome work on mixnets here.

Tas Dienes
Thanks to our advisor Tas, we made far fewer boneheaded decisions than we would have otherwise. He’s been a rock of wisdom for us, and we are deeply grateful for his support.

Meeseeking & Other Anonymous Twitter Friends
We’re not sure who you are, but every time you all tweet about our work, donate to our gitcoin grant, or encourage others to support us, the whole team gathers around one screen to read your words and we attack the day with renewed vigor.

You
Thank you for your support, for following our work, engaging with our posts, and giving us words of encouragement. Random acts of kindness and support have been critical to our motivation. Even the little likes and re-tweets on our posts have brightened our days significantly, as we’ve slogged through complicated research problems that sometimes felt insurmountable.

We hope that we can continue to earn your support. Cheers to the future!

On To New Beginnings was originally published in Plasma Group Blog on Medium, where people are continuing the conversation by highlighting and responding to this story.

A little over a month ago, we enthusiastically announced the OVM, now known as OGS, a general-purpose layer 2 (L2) solution to scaling blockchains, while inheriting all of the security of the base chain (L1). This work, while extremely promising, was purely theoretical… until today!

We’re excited to announce that the rubber has hit the road in the form of a proof-of-concept State Channel implementation on the OVM . This work demonstrates how State Channels can function seamlessly on the OVM and, if you’ll extrapolate with me a bit, shows how all L2 solutions can be built on the OVM for better standardization, security, and interoperability with less development effort.

Hold up. What’s the OVM again?

The OVM is a general purpose framework for completely inheriting the benefits of the slow and costly base chain in cheap, light-speed L2 applications. Its differentiator is that it is blockchain-agnostic and L2-solution-agnostic, creating a standard that users, wallets, developers, etc. can follow to support many different L2 applications instead of a separate paradigm for each L2 approach.

How does it do this? We’ll dive deeper in a bit, but like many proposed scaling solutions, the OVM only uses L1 for what L1 is good at: achieving immutable, unanimous consensus based on a clearly defined set of rules. The mental model I always go with is that L1 is the judge and jury, and it is far more efficient to use it to retroactively handle claims that the law has not been followed than to proactively oversee everything to ensure that the law is always followed.

Ben Jones 🔮 on Twitter

Key axiom of layer 2: "Processing disputes for all unsuccessful transactions is cheaper than processing all successful transactions." You don't go to court to cash a check. You go to court when the check bounces.

The OVM takes this approach a step further, realizing that if all of these claims of bad behavior can be expressed in the same way, we can use the same justice system (L1 dispute contract) for all cases (L2 implementations).

State Channels PoC Overview

What it is

1. An example that has the minimum functionality necessary to demonstrate that full-blown State Channels are possible on the OVM.
2. Code that optimistically evolves L1 state through mutual agreement in L2, completely agnostic of L1, in a way that is verifiable and disputable by participants, thereby completely inheriting L1 security.
3. One of the many scaling ideas that can be implemented on top of the generic OVM L2 client.

What it is not

1. Special-purpose code that only does State Channels.
2. A production-ready demo of State Channels, free of bugs and small cryptoeconomic holes.
3. Something that actually interacts with L1 (we will discuss here how this would happen and demonstrate how that part works in a later post).

High-level OVM Workflow

Enter L2: Lock funds (and/or state) into a dispute contract on L1, referencing the [L1] adjudication contract. In this case, we will reference a State Channel contract containing logic that defines what constitutes a valid exitable state. The State Channel contract, and presumably all OVM adjudication contracts, will depend on the dispute contract for standard exit request and exit dispute processing.

Use L2: Interact efficiently in L2, completely inheriting L1 security.
Exchange light-speed updates of mutually-agreed-upon state in L2, following the rules specified in the L1 State Channel contract without actually interacting with it.

Exit L2: Exit with a valid claim for which there are no valid challenges during the challenge period. For State Channels, this claim will be that the state being exited is valid, as defined by the L1 State Channel contract. In using the L2 State Channel, the parties necessarily collect proof capable of disputing invalid exit claims.

Deep-dive into L2 with State Channels

L1 Adjudication Contract

If we’re going to use L1 as judge and jury, we need to define a clear set of laws that it will use to make rulings on claims. This will include, at a minimum, defining valid exitable states. For State Channels, a valid exitable state can be defined in English as “The most recent mutually-signed state of a channel.”

To make this statement evaluable by a general purpose judge, a valid exit claim for party A to exit State Channel C, and update its L1 state to match the state of L2, contains two assertions:

1. Message M with State S, for Channel C has been signed by all channel participants.
2. There exists no Message M’ for Channel C such that M’ has a higher nonce than M and M’ is signed by all channel participants.

If such a claim is made, 2 possible scenarios can result:

1. The claim is validated by the dispute period lapsing without a valid challenge.
2. The claim is invalidated during the dispute period if either of the following happen:
   a) The L1 contract evaluates message M and determines that it is not signed by all participants of channel C.
   b) The L1 contract receives, from any party, a message M’ that disproves the claim that such a message doesn’t.

The logic to evaluate such claims must be present in the L1 contract. While this will not be demonstrated in this post, hopefully the reader is sufficiently convinced that Smart Contracts can be built to associate addresses with a channel ID, determine if specific addresses have signed a specific message, compare the nonceproperty of different messages, take action after a specified time delay, etc.

L2 Interaction

Alice and Bob have deposited funds into the L1 contract, successfully initiating a State Channel. Now what? The OVM leaves this part entirely up to them.

Messages
If Alice and Bob want to evolve the state of their initial deposits in L2, they’ll need to sign and exchange messages that fit the format that the L1 contract can verify and make sure not to break any of the rules set out in the L1 contract. Let’s say this is the message format (as described in our repo here and here):

{
  "channelId": "1234567890", // L1 ID
  "nonce": 1,                // The first message
  "data": {
    "addressBalance": {
      "0x0a": 100,           // Alice's initial balance
      "0x0b": 100            // Bob's initial balance
    }
  }
}

If the messages exchanged do not follow this format, the L1 contract will not be able to interpret them, and they’ll be useless.

Sending, Signing, and Countersigning
Let’s say Alice is paying Bob 5 from her balance for some good or service. She can do this by simply signing and sending him the following message (logic here in our repo):

{
  "channelId": "1234567890",
  "nonce": 2,      // Most recent message
  "data": {
    "addressBalance": {
      "0x0a": 95,  // Alice -5
      "0x0b": 105  // Bob +5
    }
  }
}

If Bob accepts the message as valid, he will countersign this message and send it back to Alice (let’s ignore the scenario in which he doesn’t countersign a valid message for now because that is a solved problem in State Channels).

If the message is not valid, Bob will not sign it, and the previous state will continue to be the valid state.

They can continue to evolve the state by signing and exchanging messages in this fashion, increasing the nonce for every new message.

Message Storage
Just as the OVM doesn’t dictate how messages are exchanged, it doesn’t dictate what Alice and Bob need to store, but they know what information the L1 contract needs to process an exit and what they need to present to dispute any invalid exits that arise. As such, they’ll need to store the most recent countersigned message as well as any pending (meaning not countersigned) messages that either party has signed and sent.

If Alice or Bob want to exit, they will submit to the L1 contract the most recent countersigned message as the state they would like to exit. If either party tries to exit a previous state’s message, the other party will submit the most recent countersigned message as proof that the other message is invalid.

An example datastore for State Channel messages is here within our repo (note that it extends the functionality in our base MessageDB).

Exiting and Challenging Exits

Each exit and exit challenge will not only need the data that the L1 adjudication contract needs to evaluate it but it will also need to be presented in a way that the general L1 dispute contract can understand.

👷Here’s where we really learn how the OVM functions. Fasten your seatbelt.👷

Let’s say that Alice wants to exit the State Channel after the above message with nonce 2. Here’s the structure of the State Channel Exit Claim that she would send to the L1 adjudication contract. It won’t make much sense right now but will become much clearer as we walk through it below:

{
  "decider": AndDecider,
  "input": {
    "left": {
      "decider": SignedByDecider,
      "input": {
        "publicKey": "0x0b", // Bob's Address
        "message": { // Most recent message
          "channelId": "1234567890",
          "nonce": 2,
          "data": {
            "addressBalance": {
              "0x0a": 95,
              "0x0b": 105
            }
          }
        }
      }
    },
    "leftWitness": {
      "signature": "0xbbbbbbbbbbbbbbb" // Bob's msg signature
    },
    "right": {
      "decider": ForAllSuchThatDecider,
      "input": {
        "quantifier": SignedByQuantifier,
        "quantifierParameters": {
          "publicKey": "0x0a", // Alice's address
          "channelID": "1234567890" // Our Channel
        }
        "propertyFactory": (message) => {
          return {
            "decider": MessageNonceLessThanDecider,
            "input": {
              "messageWithNonce": deserializeBuffer(
                signedMessage,
                deserializeMessage,
                stateChannelMessageDeserializer
              ),
              "lessThanThis": 3,
            },
          }
        }
      }
    },
    "rightWitness": undefined
  }
}

I read this far so you could hit me with this gibberish?
I can explain…

First, let’s go back to our State Channel exit claim definition above:

1. Message M with State S, for Channel C has been signed by all channel participants.

2. There exists no Message M’ for Channel C such that M’ has a higher nonce than M and M’ is signed by all channel participants.

If we disregard the funky format for a moment, we can see that Alice’s claim sort of follows this claim structure.

The first part lists something called a SignedByDecider, and while we don’t know what that means yet, we see it is listed right by Bob’s address, our most recent message, and Bob’s signature of our most recent message. We can see that this has all of the info necessary to prove that Bob signed the most recent state.

The second part is more intense, but we see a ForAllSuchThatDeciderthat we don’t fully understand, a SignedByQuantifierthat has Alice’s address and our Channel ID parameters, and a MessageNonceLessThanDecider right by lessThanThis: 3. If we just read parts of that in order, we see ForAll... SignedBy...Alice’s address and our Channel ID, MessageNonceLessThan...3. It’s a stretch, but maybe this is claiming that all messages Alice has signed for this channel have a nonce less than 3?

Lastly, these two parts are nested inside an AndDeciderblock. It has a left part and a right part, so maybe it means left AND right?

The VM in OVM means Virtual Machine

The OVM is a virtual machine, and virtual machines need to execute instructions to be useful. In order to do that, the OVM has to define a base interface for an instruction. Since the OVM is based entirely on claims and disputes of those claims, its instructions must all follow the form “decide whether or not input N is valid according to rule set S.”

In order to do this, the OVM has the concept of a Property. Properties consist of a Decider, which maps directly to a simple L1 smart contract capable of making very specific true/false decisions, and inputinto the decider to be evaluated. For instance, the AndDecider decides trueif and only if its input.leftproperty evaluates to trueAND its input.rightproperty evaluates to true.

Deciders may also require a witness, which is proof associated with the input. For example, the SignedByDecider decides if a message has been signed by a public key. Its input (the messageand the publicKey) defines what is being decided, and its witness (the signature) is the proof used to make the decision.

The last piece of the puzzle is Quantifiers (other simple L1 smart contracts). Quantifiers are able to list all applicable information, given a specific set of constraints. For example, the SignedByQuantifier is able to list all messages signed by a given public key.

Above, you can see that the ForAllSuchThatDecider uses the SignedByQuantifierto get all messages signed by Alice for the channel in question. The ForAllSuchThatDecideralso takes a property factory function that it calls, passing in each result from its quantifier, to get all of the properties that it will evaluate*. As you might imagine, the ForAllSuchThatDeciderdecides trueif all of the properties it is evaluating evaluate to true.

Putting it all together
Alice’s exit claim demonstrates how these granular properties can be nested together to represent complex statements. We can also see that, just like with other VMs, assembling different permutations of a small set of granular instructions (deciders), we should be able to represent every claim possible.

Please have a look at our StateChannelClient and associated tests that demonstrate L2 message exchange, exit claim generation, disputing exit claims, and more!

*Note: PropertyFactoryfunctions work for this example, but they will not ultimately be used in the claim that is passed to the L1 contract because they cannot be generically represented. This is not a blocker, as it is easily solved by simply passing a Decider, and optionally a transformer to transform Quantifierresults, to the ForAllSuchThatDeciderto enumerate the Properties itself, but we’re looking into the best approach to use.

Extrapolating

Now we know how the OVM enables State Channels. I won’t yammer on about how the OVM supports other scaling solutions, leaving it as an exercise to the reader how L1 adjudication contracts and exit claims might be structured for these other implementations. One thing I will touch on, however, is how this approach provides other valuable benefits such as security, compatibility, and chain agnosticism.

In standardizing the L1 dispute contract that actually holds all L2 funds, the OVM will offer excellent security by providing a reusable, extensible, battle-tested contract analogous to the ERC-20 standard. This standardization, and the universal nature of OVM operations, will offer compatibility between otherwise disparate scaling solutions as a byproduct, allowing better wallet integration and UX. Lastly, despite the fact that we’re targeting Ethereum for initial implementation, I haven’t mentioned a specific L1 chain for a reason — the OVM should work on any L1 that supports smart contracts. Taking this a step further, with the OVM, the same scaling solution can be implemented on incompatible L1 chains and share almost all L2 code.

This is just the beginning; the future is bright for the OVM! Thank you for reading, and we look forward to sharing more progress along the way.

The OVM ❤️s Your Scaling Solution: State Channel Edition was originally published in Plasma Group Blog on Medium, where people are continuing the conversation by highlighting and responding to this story.

Update: This article describes what we now call OGS or Optimistic Game Semantics. For an in-depth exploration of OGS check out the paper! For up-to-date information on the OVM, visit Optimism.io ❤️

Introducing the OVM

A Correct-by-Construction Approach to Layer 2

In this post we describe the Optimistic Virtual Machine (OVM): a virtual machine designed to support all layer 2 (L2) protocols. Its generality comes from a reframing of L2 as an “optimistic” fork choice rule layered on top of Ethereum. The formalization borrows heavily from CBC Casper research, and describes layer 2 as a direct extension to layer 1 consensus. This implies a possible unification of all “layer 2 scalability” constructions (Lightning, Plasma, etc) under a single theory and virtual machine: the OVM.

This post will:

1. Introduce the language of the OVM.
2. Describe how a class of L2 applications can be compiled end-to-end using a universal dispute contract.

Part 1: Describing L2 With a Unified Language

Layer 1 (L1) gives us a trusted, but expensive, virtual machine (VM). Layer 2 provides an interface for efficiently using the expensive L1 VM — instead of transactions directly updating the L1 state, we use off-chain data to guarantee what will happen to L1 state. We call this guarantee an “optimistic decision.”

Three steps to making an optimistic decision:

1. Look at L1, and figure out what could possibly happen in the future.
2. Look at off-chain messages and what they guarantee if used in L1.
3. Restrict our expectation of future L1 state based on those guarantees.

We will soon describe this process as part of the OVM’s state transition function. However, first let’s build intuition for what we mean by “restrict expectation of future L1 state” with a few key concepts.

🔑 Concept 1: The Ethereum Futures Cone

One can imagine future Ethereum states as an infinite expanse which contains everything that could ever happen to the blockchain. Every transaction that could be signed, every DAO that could be hacked — all possible futures. To avoid cliché this post will not mention the word: “quantum.”

However, even in the face of infinite futures we can still restrict possible futures based on the Ethereum Virtual Machine’s rules. For example, in the EVM, if 5 ETH has been burned to the address 0x000…, we know that all future Ethereum blocks will still have 5 ETH burned. This parallels CBC’s future protocol states (great illustrations by Barnabé Monnot here!).

We can visualize the process of gradually restricting possible futures as an infinitely large “cone” of possibilities that shrinks every time we mine & finalize a new block.

Note that in L1 all restrictions of possible future states are done by mining and forming consensus around (finalizing) a new block — a process which produces an irreversible state transition within the EVM.

🔑 Concept 2: Local Information

L2 extends the consensus protocol with local information (eg. off-chain messages). For example, a signed channel update, or an inclusion proof for a plasma block.

The OVM uses this local information to make optimistic decisions —we call a new decision an OVM state transition. But first, the OVM must define assumptions which it uses to derive possible future Ethereum states.

🔑 Concept 3: Local Assumptions

OVM programs define assumptions which, based on local information, determines what Ethereum states are possible. This can be expressed as a function satisfies_assumptions(assumptions, ethereum_state, local_information) => true/false. If satisfies_assumptions(...) returns true then the ethereum_state is possible based on these particular assumptions, and our local_information.

In many L2 solutions, this takes the form of a “dispute liveness assumption.” For example, participants in a channel assume that they will dispute any malicious withdrawal. So, we return false for any Ethereum state which contains a malicious, undisputed withdrawal.

🔑 Concept 4: Optimistic Decisions

With our local assumptions eliminating impossible futures, we may finally make “optimistic decisions” about the future. The following would be a common optimistic decision in a payment channel:

Optimistically Decide Balance (with our 3 step process defined above):

1. Look at L1 and determine that Alice is in a payment channel with Bob.
2. Look at off-chain messages determine that: a) Alice has the highest signed nonce, sending her 5 ETH; b) Alice may withdraw her 5 ETH after a dispute period; and c) Alice can respond to any invalid withdrawals based on her “dispute liveness assumption.”
3. Restrict our expectation of future L1 state to ONLY states in which Alice has been sent 5 ETH.

Alice may now optimistically decide she will eventually have *at least* 5 ETH in all future states of Ethereum. — without an on-chain transaction to boot!

The Last 🔑: The Optimistic Futures Cone

Remember that the “Ethereum futures cone” was only restricted by finalizing blocks — an entirely retrospective process. In the last section we reviewed an optimistic approach which restricts futures based on local information and local assumptions about the future — a prospective process. These two approaches may be “layered” on top of one-another to get the best of both worlds: the security of blockchain consensus, plus the speed, efficiency, & privacy of local message transfer.

We can visualize this hybrid process with a futures cone that not only restricts future Ethereum states after each block, but also restricts future states between blocks based on local information. Deciding on a new restriction is considered a “state transition” in the OVM.

A Unified Language

The above concepts may be used as the basis of a shared language and execution model for layer 2. This includes:

- Zero Confirmation Transactions
- The Lightning Network
- Cross-shard state schemes
- Plasma, Channels, Truebit
 …and more — all within a shared notation.

In part 2 of this post, we will expand upon this language and show how the correct-by-construction approach motivates a specific OVM runtime. Based on first-order logic, it supports existing L2 designs —including those for ETH2.

But first, if you’re weird like us and want to see some fancy maths, the following is a formalization of the key concepts we just reviewed:

A Step Further: Building an OVM Runtime

Excited by the realization that L2 can be described in a unified language, we soon found ourselves asking: how do we make this useful? Can we create a generic L2 runtime environment, supporting different L2 designs?

It turns out, for a broad class of OVM programs, we can. The trick is to build a dispute contract which interprets the same mathematic expressions the OVM is based on. This enables a high-level language written in predicate logic.

The Universal Dispute Contract

To do this, we create an arbitration contract handling user-submitted “claims”–expressions which evaluate to true/false. For example, “the preimage to hash X does NOT exist.”

Disputes involve counter-claims which logically contradict. For example, “the preimage to hash X DOES exist” would contradict the first claim. This generalizes L2 “challenges”: at the end of the day, all disputes are logical contradictions (they can’t both be true).

After a dispute timeout, the contract can decide true for an unchallenged claim. However, if a contradiction is shown, it needs to make a choice. The logic of decisions about true/false statements is called predicate calculus.

Predicates 2.0

In developing generalized plasma, we realized that pluggable “predicate contracts” enabled custom optimistic execution. What we now understand is that a pluggable system of predicates isn’t generalized plasma — it’s generalized layer 2. In this light, a plasma contract is just a composition of predicates.

Predicate contracts are the logical “evaluators” — deciding true or false on inputs. Critically, they can decide based on other predicates. This means a small set of interacting predicates can arbitrate a vast number of L2 systems.

Example Predicates

Let’s go over some example predicates used in first-order logic.

NOT
This predicate performs a logical negation: NOT(aPredicate, anInput). It can be contradicted by claiming aPredicate(anInput).

AND
This predicate is the logical AND operator, taking the form AND(predicate1, input1, predicate2, input2) . It can be contradicted by either NOT(predicate1, input1) or NOT(predicate2, input2) .

WITNESS_EXISTS
This predicate claims some witness data exists: WITNESS_EXISTS(verifier, parameters) . It is a fundamental building block blockchains give to L2 systems using a liveness assumption. It decides true only if it receives some witness such that verifier.verify(parameters, witness) returns true.

UNIVERSAL_QUANTIFIER
This predicate represents universal quantification (“for all”) based on some quantifier (“such that”)— UNIVERSAL_QUANTIFIER(aQuantifier, aPredicate) . It contradicts with NOT(aPredicate, someInput) if and only if aQuantifier.quantify(someInput) returns true.

Composing a State Channel

A class of widely-understood layer 2 systems is state channels, so let’s compose a state channel with predicates. Withdrawing from a state channel is like claiming the following: “For all state updates with a higher nonce than this withdrawn_update, there does not exist a unanimous signature by all channel participants.”

To the universal dispute contract, then, we would claim the following:

UNIVERSAL_QUANTIFIER(HAS_HIGHER_NONCE_QUANTIFIER(withdrawn_update), NOT(WITNESS_EXISTS(VERIFY_MULTISIG, withdrawn_update.participants)))

For Math folks, this might look more familiar as the following expression:

Thus, state channels can be built by composing four simple predicates.

An Optimistic Future

With very few predicates, this universal dispute contract can arbitrate many L2 systems: plasma flavors, state channels, optimistic cross-shard state schemes, Truebit, and so on. The predicate runtime provides a shared platform for each approach — enabling improved developer tooling. It effectively cuts the work of L2 developers in half because the predicate expressions are interpreted both on-chain and off-chain.

Beyond the predicate runtime, the OVM has broader implications:

1. Communication — Mathematical models for previously bespoke concepts.
2. Interoperability — Shared memory for all optimistic execution.
3. Security — Formal proofs for L2 & the predicate runtime.

Stay tuned for our paper detailing the OVM and the predicate runtime. In the meantime, you can further satiate your appetite with early drafts of the contracts.

Please tweet questions @plasma_group, or better yet join in the discussion at the plasma.build forum–onwards!

PG would like to thank the following individuals for their comments and edits on the structure of this post: V, Will Meister, & Akhila Raju.

Introducing the OVM was originally published in Plasma Group Blog on Medium, where people are continuing the conversation by highlighting and responding to this story.

We recently published an article that describes our new work on a more generalized plasma architecture. This post goes into more detail about the architecture for those who are interested in how things work under the hood. We’ll go over how everything fits together at a high level, then we’ll jump into the sample implementation in Python. You can scroll forward to the diagrams if you’re already very familiar with plasma.

Introduction

The main takeaways from our previous article are:

1. It’s hard to keep up with plasma research: those who are familiar with plasma have likely heard of all the different plasma flavors. Each flavor has a different sent of tradeoffs, and keeping up with rapidly evolving research is a full time job.
2. Most developers just want simple and easy ways to scale their dapps. People want good tools and well documented libraries. They certainly don’t want to build entire blockchains from scratch to run a single app.

So we set out to create a platform that makes it easy to build scalable blockchain applications without having to be a plasma expert. We ended up with a general purpose plasma chain you can build apps (or “plapps”) on. Sound weird yet? Plapp. Plaaapp. Plappp. Yup.

Layer 2: Claims about State

The core idea behind “Layer 2” is that we can use data outside of a main blockchain (“off-chain data”) to provide guarantees about assets sitting on the main blockchain (“on-chain data”). For example, that off-chain data might give you the right to withdraw an asset held in an on-chain escrow contract on Ethereum. But the ownership of that asset changed hands without touching Ethereum.

Of course, the off-chain data isn’t useful unless it’s possible for something to eventually happen on the main blockchain. This is usually achieved by allowing users to submit “claims” about the off-chain data to an on-chain smart contract where the assets being claimed are held. This claim might be something like “I have this signed message that says I’m allowed to withdraw asset X.”

But what happens if after submitting the claim, the person making the aforementioned claim also sings a message sending asset X to someone else? This would invalidate the above withdrawal. To ensure that any such invalid withdrawals are unsuccessful, we add a dispute period to every claim. Anyone may challenge the claim before the end of the dispute period. Otherwise, the claim is considered valid. Simple enough!

Let’s quickly relate this back to plasma. Plasma chains consist of a series of blocks, and each block consists of a series of transactions. Whenever a new plasma chain block is created, a cryptographic commitment to that block is published to the main chain. These commitments can be used to prove that something was inside that block. In our case, this commitment is a merkle root created from all state updates in the block.

The plasma smart contract on Ethereum records the order in which plasma blocks are committed by the operator, and prevents commitments from ever being overwritten. Thus, these block commitments give us a sense of time. When users want to make claims about something that happened on plasma chain, they have to also reference when that thing happened through the block number. For example, a user might say, “Here’s transaction X in block Y that gave me asset Z.” This extra time dimension is also important for disputes because you sometimes want to know whether something happened before or after something else!

Abstract Offchaindataism

So as we’ve just seen, Layer 2 is primarily about using some off-chain data to affect things sitting on-chain. So far, off-chain data has mostly been used to represent ownership — who owns what, and whether it changed hands.

Alice will deposit an asset into a smart contract on Ethereum and she will become the owner of that asset. She can then sign an off-chain message that transfers ownership of the asset to Bob. Bob can then withdraw the asset back on Ethereum by making a claim using that signed message.

We can also represent more complex things than ownership. Let’s say Alice deposits a CryptoKitty and signs a bunch of messages that change the kitty’s fur color. Just like in the example above, she can eventually make a claim on Ethereum about the kitty’s fur color using the last message she signed!

Whether it’s changing the kitty’s fur color or eye color, the smart contract back on Ethereum needs to have a way of understanding these changes. Each new piece of functionality — or new type of “state transition” — requires a change to the logic followed by the plasma contract. In previous plasma specs, adding a feature like this meant that one would have to re-deploy the *entire* plasma contract and migrate everyone’s assets from the old plasma chain to the new one. This is not secure, scalable, or upgradeable.

Predicates: Making Plasma Useful

We ran into this upgradeability problem once we got far enough into our plasma chain design that we wanted to add new functionality. After some brainstorming, we realized there was an easy way to add new functionality without changing the main plasma chain contract.

All of the various scenarios we’ve talked about so far have something in common — the off chain data is always for the purpose of “disputing” incorrect on-chain claims. The dispute for a particular claim is basically just some proof that the state referenced in the claim is outdated. A dispute about ownership proves that the user making the claim later transferred ownership to someone else. A dispute about kitty fur color requires proving that the kitty’s fur color has been changed.

Our primary breakthrough was realizing that dispute conditions don’t need to be checked in the main smart contract. Instead, we could have other smart contracts implement a function that would tell us if the dispute was valid or not. We could add new functionality by creating a new contract that implemented the necessary logic for that functionality and then have our main contract reference the new one. We call these external contracts ‘predicates’.

Now it was really easy to add new functionality, but we still needed a way to know which predicate to use for a particular state update. A claim about a kitty’s fur color can’t be disputed by a change in the kitty’s eye color. So how do we know which predicate to use?

Simple! We just add the requirement that the state update also says which predicate it’s subject to. Now the update message that changes a kitty’s fur color could be, “I’m making this kitty’s fur color blue and disputes can be handled by the predicate sitting at (0x123…)”

Since users can specify any predicate address they want, anyone can add new functionality to the plasma chain at any time by deploying a new predicate on Ethereum. There’s a little more to predicates than just handling disputes, but we’ll get into that later. What’s important is that predicates just have to implement a standard interface, defined in this next section.

Predicates in Practice

State Objects

Now let’s dive into the details of how this all works in practice. The building block of our plasma chain design is the ‘state object’. A state object is just a piece of data with two attributes:

• predicateAddress: The on-chain address that controls the object.
• parameters: Some arbitrary blob of data that describes the object.

State objects are effectively assets — a generalization of the concept of the non-fungible “coins” in Plasma Cash. Just like each unique coin had a coinID in Cash, each state object has a stateID .

That’s it! The stateIDs are assigned sequentially based on deposits into the plasma chain, but there aren’t any rules about what parameters or predicate can be. Each plasma block is a collection of “state updates,” which define new stateObjectss at particular stateIDs.

Because we use a range-based Cash variant, stateUpdates are actually specified over ranges of stateObject IDs:

stateUpdate = {
   start: uint,
   end: uint,
   plasmaBlockNumber: uint,
   stateObject: stateObject
}

The plasma chain contract on Ethereum, where the operator submits plasma blockhashes, implements a verifyUpdate(update: stateUpdate, updateWitness:bytes[]) -> bool which checks a Merkle inclusion proof (updateWitness) that the state update was indeed committed.

The Predicate Interface

Predicates need to implement a standard contract interface. Let’s go over those functions.

The most important thing thing the plasma contract does is determine the validity of state updates. Particularly, we need to prevent the operator (who has full control over blocks) from being able to “sneak in” a valid state update which has its stateObject.parameters.owner == operator — this would be theft!

To accomplish this, we introduce the concept of “state deprecation.” We say that the valid state for a given stateID is that of the earliest update which has not yet been “deprecated.” State deprecation is analogous to an Unspent Transaction Output becoming a Spent Transaction Output for UTXO blockchains.

This way, even if the operator sneaks in a later update where stateObject.parameters.owner == operator, an earlier update with stateObject.parameters.owner == alice will prevail, as only she can deprecate the state.

Thus, the most important function in the predicate defines the grounds by which its state may be deprecated:

verifyDeprecation(stateID: uint, update: stateUpdate, deprecationWitness: bytes)

verifyDeprecation returns true or false depending on whether the committed stateUpdate has been deprecated for a particular stateID. deprecationWitness is any arbitrary data that the predicate uses to check whether or not the stateObject has been deprecated. For example, by requiring that the deprecationWitness includes a valid signature from the update.stateObject.parameters.owner, we guarantee only the owner can approve a deprecation.

Remember, this function doesn’t actually do any deprecation as it regards to plasma’s exits games, disputes, and so on. Rather, the plasma contract calls the function when it needs to know whether a stateObject is deprecated to evaluate a dispute.

There are three other functions in the predicate interface — in order of importance, they are:

finalizeExit(exit: bytes)

When an exit is redeemed, the plasma contract sends any assets associated with the claim to the predicate address and then calls this function.

canInitiateExit(stateUpdate: bytes, initiationWitness: bytes) -> bool

This function allows the predicate to restrict who may initiate a claim on the committed state. For example, an ownership predicate probably wants to restrict canInitiateExit to the owner of the asset.

getAdditionalDisputePeriod(stateUpdate: bytes) -> uint

This function allows the predicate to increase the dispute period of a claim. We only really use this for complex predicates (e.g. atomic swaps) that might require a longer dispute resolution process. This function usually just returns 0.

Predicates by Example: Ownership Predicate

Everything is easier with examples, so let’s take a look at one. The simplest predicate is the ownership predicate. This state allows its current parameters.owner to exit at any time, or approve any state update.

The first step to creating our predicate is to design our state object. Luckily that’s pretty simple, the only data inside the object’s parameters is the address of the current owner. A state object using the ownership predicate might look like this:

OwnedByAlice = {
  parameters: {
    owner: '0xAliceAddress...',
  },
  predicate: '0xOwnershipPredicateAddress...'
}

The most important function to implement is verifyDeprecated, which receives some arbitrary deprecationWitness. In the case of the ownership predicate, a valid deprecationWitness consists of:

1. A signature from state.parameters.owner agreeing to a new stateUpdate.
2. A proof that the new stateUpdate was committed in a later plasma block.

verifyDeprecated needs to check that these things are valid, which means checking a signature and a Merkle proof.

Putting it all together, we see how the owner can deprecate its ownership state by approving a new update:

The remaining functions are pretty simple. canInitiateExit needs to check that the claimant is the owner, finalizeExit forwards the assets over to the owner, and getAdditionalDisputePeriod can return 0.

Here’s what that actually looks like in code! Below we’ve included a Python implementation of the simple ownership predicate. We wrote it in Python for simplicity, but it’s pretty easy to do in Solidity or Vyper as well.

As you can see, we’ve implemented the entire interface described above. Not too difficult :-).

And there we have it! A predicate that represents transferable ownership of an asset. Most of the logic here is identical to what was already being done in plasma contracts. We even managed to prototype the change over the course of ETHDenver. It was mostly a matter of moving around code that we’d already written.

Back to the Future

This architecture is a significant step forward in our understanding of plasma. It is analogous to the jump from payment channels to generalized state channels–we are able to fit new features and functionalities in the plasma architecture without upgrading the plasma protocol itself.

Further, we believe the predicate design space presents a rich new area of research for plasma. It’s still early days, but some of the predicates we think are possible include:

• State channels
• DEX predicates of various types
• Defragmentation predicates
• Nested plasma (predicate is itself a plasma contract)
• P2P options and CDP contracts

However, it’s important to remember that predicates are not a panacea–they are still constrained within the plasma design space. More generalization is likely yet to be found. Nevertheless, predicates are very powerful, and seem useful for pretty much all plasma implementations–including those which are not based on Plasma Cash.

We think this represents an opportunity for standardization within the entire plasma ecosystem. Any plasma implementation which shares this state-deprecation architecture can share predicates and interoperate in new ways.

Layer 2 scaling solutions are all about using off-chain data to guarantee future on-chain state. Whether old state is deprecated through signatures (state channels), commitments (plasma), or something else, these tools are ultimately accomplishing the same thing. We hope that this advancement is a step towards a unified, shared language which encompasses all layer 2 solutions. We envision a future where wallets can connect to any layer 2 solution through utilizing a standard interface, rather than writing custom integration each time. All for interoperability, and interoperability for all!

Resources

Python simulation:
https://github.com/plasma-group/research/tree/master/gen-plasma
Technical specification: https://pigi.readthedocs.io/en/latest/src/specs/generalized-plasma-state.html

Join our Plasma Contributors telegram chat: https://t.me/plasmacontributors

Our Thanks to:

Alex Attar
Dan Robinson
Dan Tsui
Georgios Konstantopoulos
Jeff Coleman
Mark Tyneway
Matt Slipper
Vitalik Buterin
Xuanji Li

Plapps and Predicates: Understanding the Generalized Plasma Architecture was originally published in Plasma Group Blog on Medium, where people are continuing the conversation by highlighting and responding to this story.

TL;DR We created a general purpose plasma design that allows you to build a broad class of smart contracts on plasma. Reach out to learn how: https://t.me/plasmacontributors

Imagine a world where every time you wanted to build a dapp, you had to build Ethereum from scratch… including the entire client, all of the networking, all of the data structures, and everything else.

Until now, that’s what plasma app development was like. Each deployed plasma chain was application-specific due to constraints in the old plasma architecture. Not upgradeable, not generalizable.

What we really needed was a way for people to build applications on top of a general-purpose plasma chain in the same way you build dapps on a general-purpose blockchain like Ethereum.

Clap for the Plapps

We’ve devised a new architecture for building plapps (plasma apps) on one generalized plasma chain. It establishes a clean separation between the plasma layer and the application layer.

Writing a new plapp is as simple as writing a special type of smart contract, called a predicate contract, and deploying it to Ethereum. Anyone can use your plapp by interacting with your predicate contract, and it all happens on the plasma chain — where it’s much, much cheaper.

Of course, these applications still live in the plasma design space. Plapps need to implement a standard predicate contract interface, and individual transactions must still fit within the ethereum gas limit.

In other words, plasma isn’t magical infinite Ethereum. However, most existing dapps (bounties, games, decentralized finance…) easily fulfill the above requirements. And, as a plapp, they get the benefits of plasma: low cost scalability, and frictionless onboarding — new users can join without ever touching Ethereum.

Where We‘re At

At ETH Denver, we used this new framework to create bitcoin lightning contracts in a predicate contract on our plasma chain:

Plasma Group 🔮 on Twitter

Check it out: We implemented payment channel contracts on plasma at ETH Denver. And it's not just any channel... it's a 🔮⚡️Bitcoin Lightning channel⚡️🔮! https://t.co/2LSnxVfOu9 @EthereumDenver

Since then, we built a python proof-of-concept that demonstrates how things work under the hood.

We then upgraded our existing client code to support plapps. It uses a new library we built that allows clients to run predicate contracts.

Where We’re Going

Come build a plapp! We need your help. As we implement various parts of the architecture and distill our learnings into a detailed writeup, we need early adopters like you to help us understand your needs. We are building this for you, and we want to make it everything it can be.

We designed all of this with the goal of making plapp development as easy as possible, but implementation always teaches you something new. This understanding will allow us to build better tooling for developers.

Build a plapp. Reach out to us on:

• Twitter
• Telegram
• Email

We’d love to hear from all of you. ❤

Towards A General Purpose Plasma was originally published in Plasma Group Blog on Medium, where people are continuing the conversation by highlighting and responding to this story.

Introduction

The vision of a network of blockchains as a scalability solution has been spreading rapidly. A multi-chain approach for parallelizing transactions is a promising way to increasing throughput… unfortunately, it also imposes significant challenges:

• We don’t want to divide security, e.g. 100 chains with 1% of total security each.
• Advanced solutions like sharding are promising, but not yet ready.

We need a solution to scalability that:

• Provides similar levels of security to the Ethereum mainnet, without paying millions of dollars in mining fees.
• Can be implemented on Ethereum as it exists today.

We believe that the strongest candidate to meet these criteria is a network of chains, each secured to mainnet via the Plasma framework.

Plasma is a family of protocols which allow individuals to easily deploy high-throughput, secure blockchains. A smart contract on Ethereum’s main chain can ensure that users’ funds are secure, even if the “plasma chain” acts fully maliciously. This eliminates the need for a trusted pegging mechanism like that of sidechains. Plasma chains are non-custodial, allowing the prioritization of scalability without sacrificing security.

We envision a future with many Plasma chains, giving users choice over where they transact. So, along with releasing our plasma chain implementation, we have created a PlasmaRegistry.vy. The registry allows new chains to join the network by listing their IP/DNS address, a custom “name” string, and their contract address. The registry contract does the verifies trusted deployment, so users can be assured that any contract on that registry is safe to deposit into — even if its operator is malicious.

Properties of our Plasma Chain Implementation

This post specifies Plasma Group’s current protocol and implementation, which draws from recent developments within the research community.

Our specification has the following properties:

• Single transactions over large ranges of coins, solving the “fixed-denomination” problem in Plasma Cash.
• Block size which scales with the number of transactions, not the number of deposits.
• Light client proofs which scale in the logarithm of the block size and linear in blocks since deposit, making the operator the system’s only (computational) bottleneck.
• A simplified, optimistic exit procedure that allows exits to specify only the most recent transaction, instead of both a transaction and its parent.
• Interchain atomic swaps, which lay the groundwork for decentralized exchange protocols.
• Unlimited deposit capacity.

Our implementation follows the above specification, providing the following:

• A command line plasma chain operator written in Javascript.
• A plasma client implementation written in Javascript with a command-line wallet.
• A smart contract supporting ETH and ERC20 tokens written in Vyper.
• An integrated JSON RPC which allows clients to download and verify light client proofs and transact.
• A block explorer hosted by the plasma operator.
• A simulated client swarm which generates transactions to load test.
• A Plasma “registry” contract which lists a set of verified-as-safe contracts and operator IP addresses for users to explore.

If you’re interested in checking out the protocol and the code implementation, you’ve come to the right place!

However, a few disclaimers before we dig in:

• Our plasma implementation is beta software currently only suitable for testnet use. There are surely critical bugs at this time.
• The main difference (explained below!) between this protocol and other Plasma implementations is the block structure: a Merkle sum tree. This has significant benefits, but adds complexity. Plasma is already complex in comparison to sidechains.
• Code has yet to be audited or formally verified, and has not undergone any optimization.
• While the operator is the only computational bottleneck, the primary performance limit today remains bandwidth. Custody proofs require downloads which are linear in the number of blocks. Our code is an improvement per block, but still linear. This active area of research is yet unready for implementation.
• Though our safety mechanisms and exit games are both implemented and tested, we have not yet built an automated guard service, meaning challenges and responses must be manually constructed.

With that out of the way, let’s jump in! The rest of this post will take comprehensive dive into our spec, where the code lives, and what it does.

Table of Contents

1. General Definitions and Data Structures
   a. Coin ID Assignment
   b. Denominations
2. Transactions over ranges of coins
   a. Transfers
   b. Typed and Untyped Bounds
   c. Multisends and Transfer/Transaction Atomicity
   d. Serialization
3. Block Structure Specification
   a. Sum Tree Node Specification
   b. Parent Calculation
   c. Calculating a Branch’s Range
   d. Parsing Transfers as Leaves
   e. Branch Validity and Implicit NoTx
   f. Atomic Multisends
4. Proof Structure and Checking
   a. Proof Format
   b. Transaction Proofs
   c. Transfer Proofs
   d. Proof Steps
   e. Snapshot Objects
   f. Deposit records
   g. TransactionProof Validity
5. Contract and Exit Games
   a. Keeping track of deposits and exits
   b. Exit games’ relationship to vanilla Plasma Cash
   c. Blocknumber-specified transactions
   d. Per-coin transaction validity
   e. How the contract handles transaction checking
   f. Challenges which immediately cancel exits
   g. Optimistic exits and inclusion challenges
   h. Invalid History Challenges
6. The Future
   a. Missing pieces in implementation
   b. Missing pieces in the spec

Repos & Architecture

Our Github offers all of our implementations under the MIT License:

• plasma-chain-operator: spin up your own plasma chain and deploy to testnet.
• plasma-core: Core plasma client functionality —portable meat of the logic.
• plasma-node: Node.js wrapper for plasma-core implementing a CLI
• plasma-js-lib: JS helper for building web applications integrating plasma transactions.
• plasma-contracts: The PlasmaChain.vy and PlasmaRegistry.vy Vyper contracts.
• plasma-explorer: A block explorer hosted by the operator.
• plasma-utils: Shared utilities for building on our plasma spec.
• plasma: Integration testing for the above components.

Here’s the architecture that plasma-core implements:

Here’s the architecture that plasma-chain-operator implements:

1. General Definitions and Data Structures

This section will cover terminology and intuitions for the protocol’s components. These data structures are encoded and decoded by plasma-utils’ library serialization. The exact byte-per-byte binary representations of all data structures for each structure can be found in schemas.

Coin ID Assignment

The base unit of any plasma asset is represented as a coin. Like in standard Plasma Cash, these coins are non-fungible, and we call the index of a coin its coinID, which is 16 bytes. They are assigned in order of deposit on a per-asset (ERC 20/ETH) basis. Notably, all assets in the chain share the same ID-space, even if they are different ERC20s or ETH. This means that transactions across all asset classes (which we refer to as the tokenType or token) share the same tree, providing maximum compression.

We achieve this by having the first 4 bytes refer to the tokenTypeof a coin, and the next 12 represent all possible coins of that specific tokenType.

For example: the 0th tokenType is always ETH, so the first ETH deposit will give spending rights for coin 0x00000000000000000000000000000000 to the depositer.

The total coins received per deposit is precisely (amount of token deposited)/(minimum token denomination) many.

For example: let’s say that tokenType 1 is DAI, the coin denomination is 0.1 DAI, and the first depositer sends 0.5 DAI. That means its tokenType == 1, so the first depositer will recieve the coinIDs from 0x00000001000000000000000000000000 up to and including coin 0x00000001000000000000000000000004.

Denominations

In practice, denominations will be much lower than 0.1. Instead of storing denominations directly in the contract, it stores a decimalOffset mapping for each tokenType which represents the shift in decimal places between the amount of deposited ERC20 (or wei for ETH) and the number of received plasma coins. These calculations can be found in the depositERC20, depositETH, and finalizeExit functions in the smart contract

//Note: decimalOfsets are hardcoded to 0 for this release, as we lack support in the client/operator code.

2. Transactions over ranges of coins

Transfers

A transaction consists of a specified block number and an array of Transfer objects, which describe the details of each range of the transaction. From the schema in plasma-utils (lengths in bytes):

We can see that each Transfer in a Transaction specifies a tokenType, start, end, sender, and recipient.

Typed and Untyped Bounds

One thing to note above is that the start and end values are not 16 bytes, as coinIDs are, but rather 12. This should make sense in the context of the above sections on deposits. To get the actual coinIDs described by the transfer, we concatenate the token field’s 4 bytes to the left of start and end. We generally refer to the 12-byte versions as a transfer’s untypedStart and untypedEnd, with the concatenated version being called typedStart and typedEnd. These values are also exposed by the serializer.

Another note: in any transfer the corresponding coinIDs are defined with start inclusive and end exclusive. That is, the exact coinIDs transferred are [typedStart, typedEnd). For example, the first 100 ETH coins can be sent with a Transfer with transfer.token = 0, transfer.start = 0, and transfer.end = 100. The second 100 would have transfer.start = 100 and transfer.end = 200.

Multisends and Transfer/Transaction Atomicity

The Transaction schema consists of a 4-byte block number (the transaction is only valid if included in that particular plasma block), and an array of Transfer objects. This means that a transaction can describe several transfers, which are either all atomically executed or not depending on the entire transaction’s inclusion and validity. This will form the basis for both decentralized exchange and defragmentation in later releases.

Serialization

As exemplified above, plasma-utils implements a custom serialization library for data structures. Both the JSON RPC and the smart contract use the byte arrays as encoded by the serializer.

The encoding is quite simple, being the concatenation of each value fixed to the number of bytes defined by the schema.

For encoding which involve variable-sized arrays, such as Transaction objects which contain 1 or more Transfers, a single byte precedes for the number of elements. Tests for the serialization library can be found here.

Currently, we have schemas for the following objects:

• Transfer
• UnsignedTransaction
• Signature
• SignedTransaction
• TransferProof
• TransactionProof

3. Block Structure Specification

One of the most important improvements Plasma Cash introduced was “light proofs.” Previously, plasma constructions required that users download the entire plasma chain to ensure safety of their funds. With Plasma Cash, they only have to download the branches of a Merkle tree relevant to their own funds.

This was accomplished by introducing a new transaction validity condition: transactions of a particular coinID are only valid at the coinIDth leaf in the Merkle tree. Thus, it is sufficient to download just that branch to be confident no valid transaction exists for that coin. The problem with this scheme is that transactions are “stuck” at this denomination: if you want to transact multiple coins, you need multiple transactions, one at each leaf.

Unfortunately, if we put the range-based transactions into branches of a regular Merkle tree, light proofs would become insecure. This is because having one branch does not guarantee that others don’t intersect:

With a regular Merkle tree, the only way to guarantee no other branches intersect is to download them all and check. But that’s no longer a light proof!

At the heart of our plasma implementation is a new block structure, and an accompanying new transaction validity condition, which allows us to get light proofs for range-based transactions. The block structure is called a Merkle sum tree, where next to each hash is a sum value.

The new validity condition uses the sum values for a particular branch to compute a a start and end range. This calculation is specially crafted so that it is impossible for two branches’ computed ranges to overlap. A transfer is only valid if its own range is within that range, so this gets us back our light clients!

This section will specify the exact spec of the sum tree, what the range calculation actually is, and how we actually construct a tree which satisfies the range calculation. For a more detailed background and motivation on the research which led us to this spec, feel free check out this post.

We have written two implementations of the plasma Merkle sum tree: one done in a database for the operator, and another in-memory for testing in plasma-utils.

Sum Tree Node Specification

Each node in the Merkle sum tree is 48 bytes, as follows:
[32 byte hash][16 byte sum]
It’s not a coincidence that the sum’s 16 bytes length is the same as a coinID!

We have two helper properties, .hash and .sum, which pull out these two parts. For example, for somenode = 0x1b2e79791f28c27ed669f257397e1deb3e522cf1f27024c161b619d276a25315ffffffffffffffffffffffffffffffff, we have
node.hash == 0x1b2e79791f28c27ed669f257397e1deb3e522cf1f27024c161b619d276a25315 and node.sum == 0xffffffffffffffffffffffffffffffff.

Parent Calculation

In a regular Merkle tree, we construct a binary tree of hash nodes, up to a single root node. Specifying the sum tree format is a simple matter of defining the parent(left, right) calculation function which accepts the two siblings as arguments. For example, a regular Merkle sum tree has:
parent = function (left, right) { return Sha3(left.concat(right)) } Where Sha3 is the hash function and concat appends the two values together.

To create a Merkle sum tree, the parent function must also concatenate the result of an addition operation on its children’s own .sum values:

parent = function (left, right) { 
 return Sha3(left.concat(right)).concat(left.sum + right.sum) 
}

For example, we might have

parent(0xabc…0001, 0xdef…0002) ===
hash(0xabc…0001.concat(0xdef…0002)).concat(0001 + 0002) ===
0x123…0003

Note that the parent.hash is a commitment to each sibling.sum as well as the hashes: we hash the full 96 bytes of both.

Calculating a Branch’s Range

The reason we use a Merkle sum tree is because it allows us to calculate a specific range which a branch describes, and be 100% confident that no other valid, overlapping branches exist.

We calculate this range by adding up a leftSum and rightSum going up the branch. Initializing both to 0, at each parent calculation, if the inclusion proof specifies a sibling to the right, we take rightSum += right.sum, and if to the left, we add leftSum += left.sum.

Then, the range the branch describes is [leftSum, root.sum — rightSum). See the following example:

In this example, branch 6’s valid range is [21+3, 36–5) == [24, 31). Notice that 31–24=7, which is the sum value for leaf 6! Similarly, branch 5’s valid range is [21, 36-(7+5)) == [21, 24). Notice that its end is the same as branch 6’s start!

If you play around with it, you’ll see that it’s impossible to construct a Merkle sum tree with two different branches covering the same range. At some level of the tree, the sum would have to be broken! Go ahead, try to “trick” leaf 5 or 6 by making another branch that intersects the range (4.5,6). Filling in only the ?s in grey boxes:

You’ll see it’s always impossible at some level of the tree:

This is how we get light clients. We call the branch range bounds the implicitStart and implicitEnd, because they are calculated “implicitly” from the inclusion proof. We have a branch checker implemented in plasma-utils via calculateRootAndBounds() for testing and client-side proof checking:

as well as in Vyper for the smart contract via

Note that the ranges are typed starts and ends, the full 16 bytes.

Parsing Transfers as Leaves

In a regular Merkle tree, we construct the bottom layer of nodes by hashing the “leaves”:

In our case, we want the leaves to be the transactions. So, the hashing is straightforward, but we still need a .sum value for the tree’s bottom level.

Given some txA with a single transferA, what should the sum value be? It turns out, not just transferA.end — transferA.start. The reason for this is that it screws up branches’ ranges if the transfers are not touching. We need to “pad” the sum values to account for this gap, or the root.sum will be too small.

Interestingly, this is a non-deterministic choice because you can pad either the node to the right or left of the gap. We’ve chosen the following “left-aligned” scheme for parsing leaves into blocks:

We call the bottommost .sum value the parsedSum for that branch, and the TransferProof schema includes a .parsedSum value which is used to reconstruct the bottom node.

Branch Validity and Implicit NoTx

Thus, the validity condition for a branch as checked by the smart contract is as follows: implicitStart <= transfer.typedStart < transfer.typedEnd <= implicitEnd . Note that, in the original design of the sum tree in “Plasma Cashflow,” some leaves were filled with a special “NoTx” transaction to represent that ranges were not transacted. With this format, the coins which are not transacted are simply those in the ranges [implicitStart, transfer.typedStart) and [transfer.typedEnd, implicitEnd). The smart contract guarantees that no coins in these ranges can be used in any challenge or response to an exit.

Atomic Multisends

Often (to support transaction fees and exchange) transactions require multiple transfers to occur or not, atomically, to be valid. The effect is that a valid transaction needs to be included once for each of its .transfers — each with a valid sum in relation to that particular transfer.typedStart and .typedEnd. However, for each of these inclusions, it’s still the hash of the full UnsignedTransaction — NOT the individual Transfer— that is parsed to the bottom .hash.

5. Proof Structure and Checking

Unlike traditional blockchain systems, full plasma nodes don’t store every single transaction, they only ever need to store information relevant to assets they own. This means that the sender has to prove to the recipient that the sender actually owns the given range. A complete proof contains all the information sufficient to guaranteed that, if the Ethereum chain itself does not fork, tokens are redeemable on the main chain.

Proofs primarily consist of the inclusion and non-inclusion of transactions, which update the chain of custody for those coins. The inclusion roots must be checked against the block hashes submitted by the operator to the smart contract on the main chain. By tracing the chain of custody as verified in the proof scheme, from a token’s initial deposit into the contract through to the present, ability to redeem is guaranteed.

plasma-core follows a relatively simple methodology for verifying incoming transaction proofs. This section describes that methodology.

Proof Format

History proofs consist of a set of deposit records and long list of relevant Transactions with corresponding TransctionProofs.

plasma-utils exposes a static checkTransactionProof(transaction, transactionProof, root) method, which is used by plasma-core here via calls to the ProofService.

Transaction Proofs

A TransactionProof object contains all the necessary information to check the validity of a given Transaction. Namely, it is simply an array of TransferProof objects. As per the above section on atomic multisends, a given TransactionProof is valid if and only if all its TransferProofs are valid.

Transfer Proofs

TransferProofs contain all the necessary information required to recover the inclusion of a valid branch corresponding to the given Transfer in the Transaction at the correct block number. This constitutes:

• The actual nodes of the Merkle sum tree which represent the branch’s full `inclusionProof`
• The index of the leaf to calculate the binary path traced by the branch
• The parsed bottom .sum as described in the sum tree spec above
• The signature for that particular sender.

Right from the plasma-utils schema:

Note that the inclusionProof is a variable-length array whose size depends on the depth of the tree.

Proof Steps

The core of the verification process involves applying each proof element to the current “verified” state, starting with the deposit. If any proof element doesn’t result in a valid state transition, we must reject the proof.

The process for applying each proof element is intuitive; we simply apply the transactions at each block as the contract’s custody rules dictate.

Snapshot Objects

The way in which we keep track of historically owned ranges is called a snapshot.
Quite simply, it represents the verified owner of a range at a block:

{
  typedStart: Number,
  typedEnd: Number,
  block: Number,
  owner: address
}

Deposit records

Every received range has to come from a corresponding deposit.
A deposit record consists of its token, start, end, depositer, and blockNumber.

For each deposit record, the verifier must double-check with Ethereum to verify that the claimed deposit did indeed occur, and that no exits have happened in the meantime.

If so, a verifiedSnapshots array is initialized to these deposits with each snapshot.owner being the depositer.

Next, we apply all given TransactionProofs, updating verifiedSnapshots accordingly. For each transaction and corresponding transactionProof, the verifier performs the following steps:

1. Verify that the given proof element is valid. If not, throw an error.
2. For each transfer in the transaction, do the following:
   a. “Split” any snapshots which were updated above at transfer.typedStart, transfer.typedEnd, implicitStart, and implicitEnd
   b. Increment the .block number for all resulting verifiedSnapshots which have a block equalling transaction.blockNumber — 1
   c. For each split snapshot which fell between transfer.start and transfer.end:
   i. verify that snapshot.owner === transfer.from. If not, throw an error.
   ii. set snapshot.owner = transfer.sender.

The TransactionProofs must be applied in ascending blockNumber.

Once this operation has been recursively applied for all TransactionProofs, the client may check for herself which new coins she now owns, by searching for all elements in verifiedSnapshots with a blockNumber equalling the current plasma block, and the owner equalling her address.

TransactionProof Validity

The transaction validity check in step 1. above is equivalent to checking the smart contract’s validity condition. The basic validity check, based on the sum tree specification above, is as follows:

1. Check that the transaction encoding is well-formed.
2. For each transfer and corresponding transferProof:
a. Check that the signature resolves to its transfer.sender address
b. verify that the inclusionProof has a root equal to the root hash for that plasma block, with the binary path defined by the leafIndex
c. calculate the implicitStart and implicitEnd of the branch, and verify that implicitStart <= transfer.start < transfer.end <= implicitEnd

4. Contract and Exit Games

Of course, the proof for a chain of custody isn’t useful unless it can also be passed to the main chain to keep funds secure. The mechanism which accepts proofs on-chain is the core of plasma’s security model, and it is called the “exit game.”

When a user wants to move their money off a plasma chain, they make an “exit”, which opens a dispute period. At the end of the dispute period, if there are no outstanding disputes, the money is sent from the plasma contract on the main chain to the exiter. During the dispute period, users may submit “challenges” which claim the money being exited isn’t rightfully owned by the person exiting. The proofs described above guarantee that a “response” to these challenges is always calculable.

The goal of the exit game is to keep money secured, even in the case of a maximally adversarial operator. Particularly, there are three main attacks which we must mitigate:

• Data withholding: the operator may publish a root hash to the contract, but not tell anybody what the contents of the block are.
• Including a forged/invalid transaction: the operator may include a transaction in a block whose sender was not the previous recipient in the chain of custody.
• Censorship: after someone deposits their money, the operator may refuse to publish any transactions sending the money.

In all of these cases, the challenge/response protocol of the exit game makes sure these behaviors do not allow theft, in at most 1 challenge followed by 1 response.

Keeping track of deposits and exits

Deposits mapping
Each time a new set of coins is deposited, the contract updates a mapping which each contain a deposit struct. From the contract:

Note that this struct contains neither the untypedEnd or tokenType for the deposit. That’s because the contract uses those values as the keys in a mapping of mappings. Accessing, for example, accessing the depositer of a given deposit looks like this: someDepositer: address = self.deposits[tokenType][untypedEnd].depositer

This choice saves a little gas, and also makes some of the code cleaner since we don’t need to store any sort of deposit ID to reference a deposit.

Exitable ranges mapping
In addition to adding self.deposits entries each time there’s a deposit, the contract needs to somehow keep track of historical exits to prevent multiple exits on the same range. This is a little trickier because exits do not occur in order like deposits, and it would be expensive to search through a list of exits.

Our contract implements a constant-sized solution, which instead stores a list of exitable ranges, updating the list as new exits occur. From the smart contract:

Again, we use a double-nested mapping with keys tokenType and untypedEnd so that we may call self.exitable[tokenType][untpyedEnd].untypedStart to access the start of the range. Note that Vyper returns 0 for all unset mapping keys, so we need an isSet bool so that users may not “trick” the contract by passing an unset exitableRange.

The contract’s self.exitable ranges are split and deleted based on successful calls to finalizeExit via a helper function called removeFromExitable. Note that exits on a previously exited range do not even need to be challenged; they will never pass the checkRangeExitable test called in finalizeExit. You can find that code here.

Exit games’ relationship to vanilla Plasma Cash

At heart, the exit games in our spec are very similar to the original Plasma Cash design. Exits are initiated with calls to the function

beginExit(tokenType: uint256, blockNumber: uint256, untypedStart: uint256, untypedEnd: uint256) -> uint256:

To dispute an exit, all challenges specify a particular coinID called into question, and a Plasma Cash-style challenge game is carried out on that particular coin. Just a single coin needs to be proven invalid to cancel the entire exit.

Both exits and the two types of respondable challenges are given an exitID and challengeID which are assigned in order via an incrementing challengeNonce and exitNonce.

Blocknumber-specified transactions

In the original Plasma Cash spec, the exiter is required to specify both the exited transaction and its previous “parent” transaction to prevent the “in-flight” attack where the operator delays including a valid transaction and inserts an invalid one in the block between.

This poses a problem for our range-based schemes, because a transaction may have multiple parents. For example, if Alice sends (0, 50] to Carol, and Bob sends (50, 100] to Carol, Carol can now send (0, 100] to Dave. But, if Dave wants to exit that, both the (0, 50] and (50, 100] are parents.

Though specifying multiple parents is definitely doable, this specification would be gas-expensive and seemed more complex to implement. So, we opted for the simpler alternative, in which each transaction specifies the `block` its senders intend for it to go in and is invalidated if included in a different block. This solves the in-flight attack and means the contract does not need a transaction’s parents. For those interested in a formal writeup and safety proof for this scheme, it’s worth giving this great post a look.

Per-coin transaction validity

An unintuitive property of our exit games worth noting up front is that a certain transaction might be “valid” for some of the coins in its range, but not on others.

For example, imagine that Alice sends (0, 100] to Bob, who in turn sends (50, 100] to Carol. Carol does not need to verify that Alice was the rightful owner of the full (0, 100]. Carol only needs an assurance that Alice owned (50, 100] — the part of the custody chain which applies to her receipt. Though the transaction might in a sense be “invalid” if Alice didn’t own (0, 50], the smart contract does not care about that for the purposes of disputes around exits for the coins (50, 100]. So long as the received coins’ ownership is verified, the rest of the transactions don’t matter.

This is a very important requirement to preserve the size of light client proofs. If Carol had to check the full (0, 100], she might also have to check an overlapping parent of (0, 10000], and then all of its parents, and so on. This “cascading” effect could massively increase the size of proofs if transactions were very interdependent.

Note that this property also applies to atomic multisends which describe multiple ranges being swapped. If Alice trades 1 ETH for Bob’s 1 DAI, it is Alice’s responsibility to check that Bob owns the 1 Dai before signing. However, after, if Bob then sends the 1 ETH to Carol, Carol need not verify that Bob owned the 1 DAI, only that Alice owned the 1 ETH she sent to Bob. Alice incurred the risk, so Carol doesn’t have to.

From the standpoint of the smart contract, this property is a direct consequence of challenges always being submitted for a particular coinID within the exit.

How the contract handles transaction checking

Note that, to be used in exit games at all, Transactions must pass the TransactionProof check described in the proofs section above(valid signatures, branch bounds, etc). This check is performed at the contract level in the function

def checkTransactionProofAndGetTypedTransfer(
   transactionEncoding: bytes[277],
   transactionProofEncoding: bytes[1749],
   transferIndex: int128
 ) -> (
   address, # transfer.to
   address, # transfer.from
   uint256, # transfer.start (typed)
   uint256, # transfer.end (typed)
   uint256 # transaction plasmaBlockNumber
 ):

An important note here is the transferIndex argument. Remember, a transaction may contain multiple transfers, and must be included once in the tree for each transfer. However, since challenges refer to a specific coinID, only a single transfer will be relevant. So, challengers and responders gives a transferIndex — whichever of the transfers relates to the coin being disputed. The check decodes and checks all the TransferProofs in the TransactionProof, and then checks inclusion for each with the function

def checkTransferProofAndGetTypedBounds(
 leafHash: bytes32,
 blockNum: uint256,
 transferProof: bytes[1749]
) -> (uint256, uint256): # typedimplicitstart, typedimplicitEnd

Once all TransferProofs are verified, the dispute-relevant values for the transferIndexth Transfer are returned to the exit game functions: namely the sender, recipient, typedStart, typedEnd, and plasmaBlockNumber.

With that out of the way, we can specify the full set of challenge/response games for exits.

Challenges which immediately cancel exits

Two kinds of challenges immediately cancel exits: those on spent coins and those on exits before the deposit occurred.

Spent coin challenge
This challenge is used to demonstrate that the exiter of a transaction already sent the coins to someone else.

@public
def challengeSpentCoin(
 exitID: uint256,
 coinID: uint256,
 transferIndex: int128,
 transactionEncoding: bytes[277],
 transactionProofEncoding: bytes[1749],
):

It uses checkTransactionProofAndGetTypedTransfer and then checks the following:

1. The challenged coinID lies within the specified exit.
2. The challenged coinID lies within the typedStart and typedEnd of the transferIndexth element of transaction.transfers.
3. The plasmaBlockNumber of the challenge is greater than that of the exit.
4. The transfer.sender is the exiter.

The introduction of atomic swaps does mean one thing: the spent coin challenge period must be strictly less than others, because of an edge case in which the operator withholds an atomic swap between two or more parties. In this case, those parties must exit their pre-swapped coins, forcing the operator to make a a spent coin challenge and reveal whether the swap was included or not. BUT, if we allowed the operator to do that at the last minute, it would make for be a race condition where the parties have no time to use the reveal to cancel other exits. Thus, the timeout is made shorter (1/2) than the regular challenge window, eliminating “last-minute response” attacks.

Before deposit challenge
This challenge is used to demonstrate that an exit comes from an earlier plasmaBlockNumber than that coin was actually deposited for.

@public
def challengeBeforeDeposit(
 exitID: uint256,
 coinID: uint256,
 depositUntypedEnd: uint256
):

The contract looks up self.deposits[self.exits[exitID].tokenType][depositUntypedEnd].precedingPlasmaBlockNumber and checks that it is later than the exit’s block number. If so, it cancels.

Optimistic exits and inclusion challenges

Our contract allows an exit to occur without doing any inclusion checks at all in the optimistic case. To allow this, any exit may be challenged directly via

@public
def challengeInclusion(exitID: uint256):

To which the exiter must directly respond with either the transaction or deposit they are exiting from.

@public
def respondTransactionInclusion(
 challengeID: uint256,
 transferIndex: int128,
 transactionEncoding: bytes[277],
 transactionProofEncoding: bytes[1749],
):

...

@public
def respondDepositInclusion(
 challengeID: uint256,
 depositEnd: uint256
):

The second case allows users to get their money out if the operator censored all transactions after depositing.

Both responses cancel the challenge if:

1. The deposit or transaction was indeed at the exit’s plasma block number.
2. The depositer or recipient is indeed the exiter.
3. The start and end of the exit were within the deposit or transfer’s start and end

Invalid History Challenges

The most complex challenge-response game, for both vanilla Plasma Cash and this spec, is the case of history invalidity. This part of the protocol mitigates the attack in which the operator includes an forged “invalid” transaction whose sender is not the previous recipient. The solution is called an invalid history challenge: because the rightful owner has not yet spent their coins, they attest to this and challenge: “oh yeah, that coin is yours? Well it was mine earlier, and you can’t prove I ever spent it.”

Both invalid history challenges and responses can be either deposits or transactions.

Challenging

There are two ways to challenge depending on the current rightful owner:

@public
def challengeInvalidHistoryWithTransaction(
 exitID: uint256,
 coinID: uint256,
 transferIndex: int128,
 transactionEncoding: bytes[277],
 transactionProofEncoding: bytes[1749]
):

and

@public
def challengeInvalidHistoryWithDeposit(
 exitID: uint256,
 coinID: uint256,
 depositUntypedEnd: uint256
):

These both call a

@private
def challengeInvalidHistory(
 exitID: uint256,
 coinID: uint256,
 claimant: address,
 typedStart: uint256,
 typedEnd: uint256,
 blockNumber: uint256
):

function which does the legwork of checking that the coinID is within the challenged exit, and that the blockNumber is earlier than the exit.

Responding to invalid history challenges

Of course, the invalid history challenge may be a grief, where really the challenger did spend their coin, and the chain of custody is indeed valid. We must allow this response. There are two kinds.

The first is to respond with a transaction showing the challenger’s spend:

@public
def respondInvalidHistoryTransaction(
 challengeID: uint256,
 transferIndex: int128,
 transactionEncoding: bytes[277],
 transactionProofEncoding: bytes[1749],
):

The smart contract then performs the following checks:

1. The transferIndexth Transfer in the transactionEncoding covers the challenged coinID.
2. The transferIndexth transfer.sender was indeed the claimant for that invalid history challenge.
3. The transaction’s plasma block number lies between the invalid history challenge and the exit.

The other response is to show the challenge came before the coins were actually deposited — making the challenge invalid. This is similar to the challengeBeforeDeposit for exits themselves.

@public
def respondInvalidHistoryDeposit(
 challengeID: uint256,
 depositUntypedEnd: uint256
):

In this case, there is no check on the sender being the challenge recipient, since the challenge was invalid. So the contract must simply check:

1. The deposit covers the challenged coinID.
2. The deposit’s plasma block number lies between the challenge and the exit.

If so, the exit is cancelled.

This concludes the complete exit game specification. With these building blocks, funds can be kept safe even in the case of a maximally malicious plasma chain.

6. The Future

Plasma Group is dedicated to the creation of an open plasma implementation for the greater Ethereum community. It’s our mission to push layer 2 scaling forward by exploring the full potential of the plasma framework. There’s certinaly much more to push forward! Here are some of the things we hope to work on next.

Missing pieces in implementation

Automated Guarding
While a good start, many improvements are needed to fulfill the true potential of Plasma, for this spec and beyond. Currently, the most glaring missing piece in our implementation is guarding, the automated process which submits challenges and responses on behalf of users. Thankfully, the exit games themselves are implemented and have been manually tested, so that client software can be updated after a chain is deployed. We felt this was sufficient for a testnet release, but is the most pressing addition the code needs.

P2P History Proofs

Currently, when a user recieves a transaction, they ask the operator and re-download the full proof. This introduces a massive increase in operator overhead. What should really happen is that the sender directly transmits their locally stored proof to the recipient, bypassing the operator and making it much cheaper to run a plasma chain.

Defragmentation Strategies
Since we support atomic swaps, our current spec is compatible with any defragmentation strategy without any upgrades to the contract. However, it remains to be seen what the right approach will be, especially since we require transactions to specify a Plasma block number. We hope the plasma community can build an extensible defragmentation abstraction library which allows operators and users to try out different approaches.

Front-end wallet integration
We have some designs for a front-end wallet, but currently the client only supports command-line transacting, with no support for trading different ERC20s. Having a nice UI to give to testnet users will be a major step up in terms of UX and accessibility.

Operator fees
Because we support atomic multisends, we can support transaction fees without any protocol modifications. However, we’ve not currently implemented anything for this testnet launch.

Networked operator
Something we’re not taking advantage of yet is that merkle tree construction is highly parallelizable. If the operator was deployed as a networked cluster, we could increase block size by constructing subtrees in parallel.

Code review
It’s very likely that all of the client, contract, and operator implementations have critical bugs at this time. We’re hoping that part of this public launch will be an opportunity for external contributors to help point out many mistakes!

Missing pieces in the spec

Succinct Proof Schemes
As mentioned in the introduction, the most active area of Plasma research is a scheme to reduce the history proof size. P2P or not, an old (say, 1 year+) coin might have a significant amount of associated proof data, making transactions cumbersome. This is because the history proof contains, at minimum, one branch per block.

RSA accumulator constructions and STARKS/SNARKS which batch branch proofs over many blocks are currently the most likely candidates. Both would require protocol changes: for RSA (which also introduces a trusted setup), an entirely new validity condition must be added to the exit game. For the latter, the tree needs to be constructed using a SNARK/STARK friendly hashing algorithm, which has not been implemented in EVM.

Mass Exit/Deposit Schemes
If the operator does turn malicious, users must (eventually, no rush!) exit their funds. The concept of “mass exits”, in which many users consent to exiting together via a single on-chain transaction, would be a significant scalability increase. Ideally, the exit would be able to auto-deposit funds directly into a different plasma chain via a merkle root of balances. This would enable many users to switch chains, without individual balances ever being resolved on the main chain — a significant improvement in the “networkability” of multiple plasma chains.

Multi-operator networks
Though the operator cannot steal funds, they can censor transactions at will. One mitigation to this would be to replace the single-operator model with a set of operators, so that the existence of just a single honest operator is sufficient for clients to transact.

Improved exit records
Our exitable range construction allows for constant-sized checks on exited ranges. However, since each finalization updates this mapping, we will have a race condition if exits on the same range aren’t processed in ascending order. This is because the first exit’s finalization splits the range, changing the key to the self.exitable mapping and causing checkRangeExitable to fail for exits referencing the unsplit range. Those exits will revert and have to be re-submitted in the next Ethereum block. A gas-efficient alternative may exist, possibly using some sort of tree, queue, or some batchFinalizeExits method.

State channels and scripting
Recently, there’s been some great progress in the research community which suggests state channels and scripting with covenants are feasible on Plasma. Our current spec does not support either of these features, and will require a significant upgrade to the smart contract to support.

Together, we’ll build towards realizing the vision of a more decentralized future.

Plasma Group’s Plasma Spec was originally published in Plasma Group Blog on Medium, where people are continuing the conversation by highlighting and responding to this story.

Hello world! We are excited to announce a full service plasma toolbox for deploying, transacting on, building with, and developing on plasma chains.

This implementation set foot in the aftermath of devconIV. Though it’s an unaudited beta release, we hope it will lay the groundwork for a community-driven initiative to make plasma a tool for decentralization for everyone.

You can deploy your own plasma chain from the command line or connect to a plasma chain that we’ve deployed and send transactions via a command line wallet. This implementation is written in Javascript and Vyper, and includes a library of plasma utilities for those who want to build on top of it.

About us

Plasma Group is dedicated to the creation of an open plasma implementation for the greater Ethereum community. It’s our mission to push layer 2 scaling forward by exploring the full potential of the plasma framework. Together, we’ll build towards realizing the vision of a more decentralized future.

Contributors

No matter who you are, you can be a part of this community. Anyone can contribute, and we need your expertise to make this a success. Find a list of our repositories here. Click through to each one to discover contributable issues.

Donors

We would like to give resounding thanks to our donors: OmiseGO and independent individuals within the OMG community, LinkTime, Status, ConsenSys, and Gitcoin. Thank you all so much for your contributions — we are so incredibly grateful.

Relevant Links

Plasma Group Plasma spec
Github
Twitter
Website

Introducing Plasma Group was originally published in Plasma Group Blog on Medium, where people are continuing the conversation by highlighting and responding to this story.