Channelising MixEth with the Counterfactual framework

Chris Buckland
Dec 11, 2018 · 10 min read

Last week I visited the L4 team in Canada with the intention of learning about the Counterfactual framework they’re contributing to, and whether it is compatible with the PISA watching service I’m working on. The Counterfactual framework is still being developed, but enough of the smart contract layer is there to start designing a state channel application. So I decided to try to channelise an existing application and get some first hand experience with how the framework works.

Counterfactual is not the only state channel framework. I know of at least two more, Magmo and Celer, and I’m sure that there are others I don’t know about. This article is about the Counterfactual framework as it’s the only one I’ve had the chance to build an application with so far, but I look forward to trying out the others when I get a chance!

MixEth

Image for post
Image for post
Harry Clark’s illustration of Edgar Allan Poe’s “Descent into the Maelstrom”. A fisherman witnesses the power of a mighty mixer and is never the same again ;)

In MixEth, senders deposit funds and name a public key whose private counterpart can unlock those funds. When enough deposits have been made to form a large enough anonymity set, participants — senders, receivers and anyone interested — are given the chance to perform a verifiable Neff shuffle on the public keys. After each shuffle any party can provide a proof that the shuffle was made incorrectly. When all interested parties have shuffled the the receivers can then withdraw their funds by providing proof of ownership of one of the shuffled keys.

The current gas costs incurred for a participant are 138,653 + 10,000*n gas for a shuffle and 227,563 gas for a challenge, where n is the number of receivers/senders. These are the steps which we hope to remove by the channelising the app, thereby reducing the gas costs of the application. Channelising the app will also reduce the amount of time required on the part of each participant since state updates in channel are faster than those on-chain.

Counterfactual

Image for post
Image for post
The Counterfactual stack: an off-chain application library, a generalised state channel protocol, and a set of on-chain contracts.

The documentation states that the AppDefinition should conform to an interface of the following four pure functions:

getTurnTaker: AppState => uint256

getTurnTaker imposes the concept of turns upon an application. Applications that do not already have a strong idea of proceeding turn-by-turn will have to adopt this if they are to use the framework.

applyAction: (AppState, Action) => AppState

isStateTerminal: AppState => bool

resolve: AppState => Transfer.Transaction

These functions are leveraged by the framework to allow participants to verify what the application would do were it to be deployed on-chain. If this were to be the case the challenge logic defined in AppInstance would be used to progress the application.

Counterfactual’s challenge logic is as follows: To begin a challenge a participant needs to provide a state signed by all channel participants. From there the next turn taker can progress the application by applying an action. Subsequent participants can progress the application in the same way. If at any time the application transitions to a terminal state, resolution logic will be executed. Also, at any time another participant my submit a newer state than the one originally provided. This challenge process can also be exited and the application continued off-chain, if at any time all participants sign an order to cancel the dispute.

Image for post
Image for post
A state diagram of the Counterfactual challenge logic implemented in AppInstance. The channel transitions from states ‘on’ to ‘dispute’ when the a co-signed state is submitted. From there state is advanced by supplying actions. The channel can transition back to on if a cancel is signed by all participants. Or to off, if a final state is reached or a timeout occurs.

Channelising MixEth

Some points to consider

The participants in MixEth have different interests at different stages of the protocol. In the on-chain version a sender submits funds, and optionally shuffles, after that their involvement is not required to complete the application. In state channels all participants must sign state updates, which means the senders will need to be involved until the end (and likewise the receivers from the beginning). Will the turn taking constraint adapt well to this, or will it force senders to take turns even when non are required?

MixEth has a timing assumption baked into the protocol. Participants are given time after each shuffle to submit a challenge. Given that these timings are measured with block.number, how can this be handled by the pure applyAction function?

The on-chain only application is a monolith, in that a single contract is used globally for all mixing. How can this be adapted for a fixed set of participants, and how can a terminal state be imposed to allow these participants to exit?

Observations and discussion

Overall

Happy case terminal state

A fixed participant state diagram

Image for post
Image for post
A state diagram of MixEth with the fixed number of participants. Each sender deposits funds. Then a shuffle occurs, followed by a challenge. A correct shuffle proceeds to the next shuffle, an incorrect shuffle reverts to the last shuffle. When all shuffles have taken place, each of the receivers withdraws funds.

State machine diagrams are a useful way to visualise the possible transitions in smart contract applications, they’re also a nice way to inspect the flow for mistakes and stuck states.

This state machine diagram represents the transitions for MixEth with a fixed set of participants. A state diagram also helps us to recognise a sensible order on turns. The senders each deposit and name a key, then shuffles occur, after each shuffle there is the chance to challenge, and finally each receiver withdraws.

Time based constraints

Mitigating O(n²) complexity

Image for post
Image for post
A state diagram of the final MixEth with a single challenge round after all shuffles. Each sender deposits funds. Then all shuffles take place. After all shuffles take place each participant is given the chance to challenge any shuffle. If a shuffle is proved incorrect the application transitions to fraud, and all participants except the one at fault are refunded. If all shuffles are accepted each of the receivers submits withdrawal proofs. After this the application transitions to a final state and distributes funds.

This article shows that, in the worst case, state channel applications will have to be executed on-chain. Having an explicit move for each participant after each shuffle means that the application would scale at O(n²), for n participants.

To reduce the possible number of challenge rounds the state transitions were adjusted to not have a challenge after each shuffle. Instead, after all shuffles have taken place each participant is given the opportunity to challenge any shuffle. Now the application state will have to store all the shuffles — not just the last two — but the number of transactions would scale as O(n) for the application (and O(1) for each participant). This also gives rise to another terminal state — fraud. The resolve functionality for the fraud state is to revoke the deposit of the cheater, and refund all other participants.

Msg.sender

Application state

Passing a struct to applyAction requires the use of the experimental ABIEncoderV2, which doesn’t allow for mappings to be included in the struct. Given that the original MixEth contract held almost all of its state in mappings, this constituted a significant part of the refactoring effort as the underlying data storage changed structure.

Setup constraints

Summary

There are challenges in learning the Counterfactual framework and adapting an application to meet its constraints. But the constraints are in place to help avoid some of the pitfalls of building a state channel app. In writing the application I didn’t have to consider a safe protocol for allowing users to deposit funds, and still get refunded if another party didn’t respond in the setup phase. I also didn’t have to write any of my own challenge logic for when cooperation breaks down in a channel.

Developers building with the framework will benefit from other complex components in the stack — the communication layer between participants, the off-chain installation that allows end users to install any application without an on-chain transaction, the engine that monitors for blockchain events and compatibility with other applications built on the Counterfactual stack.

Many thanks to Liam Horne from L4 for help in adapting the application to the Counterfactual framework and to István András Seres for helping me to understand the MixEth protocol.

anydot

The first skin-in-the-game and non-custodial relay service API

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch

Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore

Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store