Notes: More Viable Plasma

More Viable Plasma was proposed by Kelvin Fichter. Essentially, it modifies:

the priority queue, to process exits of transactions with the oldest youngest input first. This is very much mind fuckery, but it will be explained in detail below.
the exit game, wherein even inputs of non-canonical transactions can be exited. The game is also extended to a 2-phase process.

While this sounds like unnecessarily added complexity, it comes with a big UX win: confirmation signatures are no longer needed.

Note that this extends MVP, and there is therefore some repeated content, to reduce the need for cross-referencing. This duplication is intentional, and not a mistake.

There currently exists no reference implementation for this spec. Therefore, it is likely that Campfire will go with the MVP implementation, for a start. It is equally safe (with confirmation signatures), but may not provide as good a UX as this spec.

Definitions, Components & Actors

Root Chain (RC): refers to a smart contract on the Ethereum (or any other general compute blockchain with a Turing-complete VM).
Plasma Chain (PC/Operator): refers to Campfire (in our case). The Plasma Chain is where most of the action happens. Its blocks are compressed and recorded on the RC's smart contract.
Validator Nodes (Vals): a set of nodes that have the privilege to propose blocks to be written to the canonical blockchain. They each have a keypair. 2/3n + 1 validators are required to sign off on a block before it is committed, but once they do, the block is final.
Watchers: these are auxilliary off-chain light clients that are responsible for checking (corroborating) the blocks that appear on the RC smart contract with blocks received from the PC. In the event that there is Byzantine behaviour, it is their responsibility to alert users to exit their UTXOs.
Competitor (CMP): a transaction that shares >= 1 inputs with another transaction. A given transaction can have > 1 CMP, including itself.
Canonical Transaction (CTX): the transaction in a set of CMPs that has the oldest output.
Double spent/Double spend: within a set of transactions, an output that has been used as an input in >= 2 transactions.
Exitable Output: any txo (whether used as input or output in the set) in the set of canonical transactions that have not been spent or double spent.

Plasma Chain (Tendermint)

In Campfire, we implement the PC using Tendermint core (TMC). TMC is a consensus engine that uses a variant of what is known as pBFT. TMC was chosen because:

It offers a unique architecture (ABCI) that offers app-specific blockchains a high level of flexibility with a rock-solid consensus approach.
It has finality. This means that once a block is confirmed, it will never be reorganised or otherwise changed.
It is almost trivial to layer a staking mechanism through the ABCI on top of TMC, which can be a vital game used to keep the token economy stable while discouraging dishonest behaviour from validator nodes.

UTXO Set

The UTXO set is the most crucial component of the PC. UTXO stands for Unspent T(X)ransaction Output. This is because it amounts to the record of which addresses (20-byte hashes of public keys) "own" a given number of coins (TRB, in our case).

Example

Actors: Alice and Bob

Alice owns a UTXO worth 5 TRB (UTXO1). Bob does not own any TRB at all.
Bob wishes to sell Alice an Apple. Alice "spends" UTXO1 by creating a SendMsg, signing it with her private key.
UTXO1 has become an input to the transaction. It is "spent". In its place is an output (UTXO2), that belongs to Bob.

This mechanism is crucial to the functioning of MVP. This is because it is cheap to prove that a given person "owns" a UTXO on the RC by exploiting Merkle proofs. By comparison, account balances do not by themselves have such a concept of "history", since its balance is adjusted as a side effect of a transaction.

"Coinbase" Transactions

It is worth noting that in the case of Campfire, we make use of "Coinbase" transactions to reward network participants (writers, validator nodes, watchers, etc). A coinbase transaction is simply one in which there are no inputs, and only outputs: the outputs are "created from thin air" as an intrinsic reward for those who contribute to the network.

Similarly, deposit (explained below) transactions are treated in the same way. Since they are included in the PC based on deposit events occuring on the RC smart contract, they do not have inputs.

Root Chain (Ethereum, RC)

Smart Contract

This section describes the barebones interface of the RC Smart Contract. Note that bonds are not part of the method signatures for now.

Methods

submitBlock(bytes32 root): submits a block, which is basically just the Merkle root of the transactions in the block
deposit(): generates a block that contains only one transaction, generating a new UTXO into existence with denomination equal to the msg.value deposited
startExit(uint256 plasmaBlockNum, uint256 txindex, bytes tx, bytes proof): Requires as input (i) the Plasma block number (ii) tx index , (iii) the transaction containing that UTXO, (iv) a Merkle proof of the transaction being exited.
joinExit(uint256 plasmaBlockNum, uint256 txindex, uint256 oindex): Allows a user to "piggyback" on the inputs or outputs of an already-started exit. oindex is the index of the input or output being exited. E.g.: in the transaction ((7, 11), (24, nil)), oindex of 0 refers to txo 7 (input).
presentCompetitor(uint256 plasmaBlockNum, uint256 txindex, bytes tx, bytes proof): allows presentation of a competitor to some existing exit. The purpose is to prove that the latest competitor is non-canonical (blocks outputs of latest competitor from exiting). The competitor must (i) be a transaction that shares >= one input with the current competitor, and (ii) must have come before it. Open in phases 1 and 2.
presentDoubleSpend(uint256 plasmaBlockNum, uint256 txindex, bytes tx, bytes proof): allows presentation of any transaction in which any input or output of the latest competitor was spent. Potentially blocks both inputs and outputs.
presentNonCanonicalInput(uint256 plasmaBlockNum1, uint256 txindex1, bytes tx1, bytes proof1, uint256 plasmaBlockNum2, uint256 txindex2, bytes tx2, bytes proof2,): requires (i) the transaction that resulted in the UTXO being used in a currently-exiting transaction; (ii) an earlier competitor to that transaction (the one being presented). Blocks non-canonical inputs from exiting.

Properties

queue: priority queue where every element of the queue is an exit stemming from a call to startExit. The queue is ordered in descending order of the age of the UTXO being exited. The age is represented as follows: (blknum * 1000000000 + txindex * 10000 + oindex)

Note: the RC smart contract keeps "custody" of all the coins received through deposit (including ERC20). When a UTXO is exited, the smart contract returns the money from this pool of tokens that it "owns". Note that ERC20 support is WIP, but well on the way.

Exit Game (a.k.a. return my money on Ethereum please)

Conditions

The following conditions must be met in order for an exit to be finalised on the RC:

A UTXO included in a transaction in a block that is recorded on the RC;
that is >= 14 days old;
The UTXO is either (i) unspent and part of a canonical transaction, OR (ii) not double spent.
The contract "owns" enough tokens to effect the exit.

The semantics of the exit game are somewhat convoluted. Instead of describing it in abstract, an abridged example is provided. These examples omit some implementation details to make them easier to follow.

Ex. 1: Non-Byzantine Exit

Actors: Alice

Alice has UTXOs worth 500 TRB on the PC (Campfire). She wishes to liquidate her TRB by trading it for ETH via Kyber. Therefore, she must "convert" her Campfire TRBs to ERC20 TRBs.
Using the Tribe Wallet, she initiates an exit by calling startExit, pointing to her 500 TRB UTXO.
Her exit is is inserted into queue.
After the UTXO she is exiting reaches an age of 14 days, she is given 500 TRB on Ethereum, and her 500 TRB on the PC (Campfire) is burned.

Ex. 2: Out-of-nowhere attack

Actors: Alice, Bob, Watcher, Operator

# tx has the shape ((input1, input2), (output1, output2))

tx_set := [
  ((0, 1), (2, 3)), # tx0
  ((2, 3), (4, 5)), # tx1 - outputs belong to Alice
  ((nil, 6), (7, 8)), # tx2 - UTXO 6 is "out of nowhere"
  ((4, 5), (9, nil)), # tx3 - Alice spends (4, 5) to 9
]

youngest-input (i.e. more viable plasma)

Operator has been compromised. Attacker makes up a fake UTXO and uses it as an input, spending it to indices (7,8). The attacker immediately starts exit and piggybacks on outputs (7,8).
Alice is an honest user. After the "out of nowhere" transaction, she spends UTXOs with indices (4, 5) to Bob, creating UTXO with index 9.
A Watcher notices the fake UTXO because it does not exist in campfired.
Bob begins an exit and piggybacks on UTXO 9.
Since the youngest input of tx3 has index 5 and the youngest input of tx2 is 6 (the "out of nowhere" utxo), Bob's exit has higher priority even though the containing transaction is after the fraudulent one!

earliest-first (i.e. minimal viable plasma) without confirmation signatures

Operator has been compromised. Attacker makes up a fake UTXO and uses it as an input, spending it to indices (7,8). The attacker immediately starts exit and exits outputs (7,8).
Alice is an honest user. After the "out of nowhere" transaction, she spends UTXOs with indices (4, 5) to Bob, creating UTXO with index 9.
A Watcher notices the fake transaction because its input does not exist in campfired.
Bob begins an exit for UTXO with index 9. He can start an exit, since, in this version of the RC contract, he does not have to provide confirmation signatures.
Since the "out of nowhere" outputs came earlier, they have priority in the queue, and Operator is able to steal money that actually belongs to Bob!

Ex. 3: Double Spend Attack / Exit Game

Actors: Alice, Bob, Charlie, Watcher, Operator Assumptions:

Alice and John are honest users.
Bob and Charlie are colluding hackers who have compromised Operator and can create any block they wish on the RC.

# tx_set := [
  ((0, 1), (2, 3)), # tx0 - 2 belongs to Bob, 3 belongs to Alice
  ((2, nil), (4, nil)), # tx1 - Bob spends output 2 to Charlie - canonical
  ((2, 3), (5)), # tx2 - Alice spends 3 and Bob double spends 2 to Charlie. non-canonical && witheld
]

Bob owns UTXO2 and Alice owns UTXO3 (outputs to tx0).
Bob spends UTXO2 to Charlie, who now owns UTXO4 (output to tx1).
Alice and Bob co-sign a transaction to spend UTXO2 and 3 to Charlie (double spend of UTXO2).
Operator is evil, and does not insert tx2 into the PC, but includes it in the RC, so that Charlie can exit. tx2 is considered "in-flight".

earliest-first without confirmation signatures

Charlie exits UTXO4 and UTXO5.
Alice cannot challenge either of the exits, as none of the outputs (UTXO4,5) were spent!
Alice cannot exit UTXO3, as it can be challenged by UTXO5. Charlie "steals" the value of UTXO2, which is double-spent. Alice gets nothing back.

youngest-first exit game

A Watcher notices the double spend and alerts Alice. Alice starts an exit, piggybacking on her input (UTXO3) to #tx2. Charlie is evil and piggbacks on UTXO2 and UTXO5.
Alice challenges by presenting tx1. Since tx2 is non-canonical, UTXO5 cannot be exited. UTXO2 is a double spend, and cannot be exited.
Alice gets back UTXO3. Bob loses the the value in UTXO2. Charlie cannot exit UTXO5, but can exit UTXO4 (legitimate output).

Watchers

Overview

Since users of a Plasma chain can never be online at all times, or may not be alert enough to notice anything fishy going on (particularly in the case of Ex. 3, where the Operator conducts a fairly sophisticated scheme), we introduce the idea of a "Watcher": light clients that track both the RC and PC, reconciling the chains as they are updated.

Components

campfired - Campfire client that keeps a local copy of the blockchain.
geth - Ethereum client responsible for tracking state of Plasma blocks.
validatord - checks Plasma blocks against the blocks from campfired

Implementation Notes

NOTE: THIS IS WIP

validatord maintains a buffered set of blocks (blockset) received from campfired. This data structure is buffered because it is very likley that campfired will process blocks at a far higher throughput than the RC. Each time it receives a Plasma block published to the RC from geth, it looks for the root hash in the set of blocks.

If a matching block is found in blockset, it should check the previousHash of the block's header, and check if the last submitted Plasma block matches the block pointed to by previousHash. If not, this means that the RC smart contract's records are no longer in the correct order, and an exit should be triggered. Otherwise, the block is simply removed from blockset.

If the Plasma block is not found in the set, it should retry on the next published Plasma block, and perform the same check. If no matching block from campfired is forthcoming, it should assume that the RC blocks have been tampered with, and all users should exit.

iantanwx/morevp.md