Concurrency, State, & Cardano.

Sundae Labs
11 min readSep 4, 2021

--

After months of testing with smaller groups, the Cardano public testnet was recently upgraded to support smart contracts. The surge of activity that followed included many dApp tests and experiments, with developers eager to perform a large-scale test and show off their hard work. This effort has created a ferocious discussion around some of the design decisions behind Cardano. Many critics are using this discussion as an opportunity to point to Cardano, misrepresent the problem, and ultimately underestimate the potential of one of the giants of the crypto industry. Misconceptions are now floating around suggesting that Cardano only supports one transaction per block, only one user can interact with a smart contract at a time, and that cardano is ultimately destined for centralization. All of these are inaccurate, and we present below a new framing and the start of a few solutions that dApp builders might choose.

It seems to be a good time for the SundaeSwap team to weigh in on some of the more common issues being raised — especially the design and accounting decisions that led Cardano to choose the eUTXO model over Ethereum’s approach, as well as the impact that this choice has on concurrency on the Cardano blockchain.

Although we see a lot of intensity to this discussion, we hope to dispassionately explore some upsides, downsides, misconceptions, and finally, present some potential solutions. This article is rather technical from here on out, but we’ll close with a non-technical summary.

The art of system design is often the art of choosing between trade-offs. Often, you can track the career growth of a software engineer by how well they recognize and employ these trade-offs to solve a problem. Of note to all of us in the Cardano community, it’s worth analyzing what trade-offs Cardano has chosen to make, and a useful point of comparison is Ethereum.

Many people have pointed out that Cardano’s choice of eUTXO can create issues when porting protocols. This is certainly true; we alluded to this in our whitepaper many months ago. Similarly Lars Brünjes, the Director of Education at IOG, has tweeted about it, and many others along with him.

To fully understand the impact of this decision, let’s discuss some background.

History

Bitcoin introduced the world to the notion of tracking user funds via a list of “unspent transaction outputs,” or UTXO for short. Each transaction between users consumes some inputs, and produces some outputs, with each output representing a bundle of value (some bitcoin) and a declaration of who can spend it.

Thus, if someone sent me 1 bitcoin, there would be a transaction with an output of 1 bitcoin, with the owner being my public key. I could then send that 1 bitcoin to someone by publishing a transaction that consumes that input, proves I have the right to do so, and declares a new output with a new owner.

This has a number of benefits:

  • It is incredibly simple and secure to validate. It becomes very obvious if value is being created or destroyed: compare the total bitcoin in to the total bitcoin out.
  • It is very easy to validate transactions in a block in parallel; simply check the signature on each transaction in separate threads.
  • It is highly deterministic. When a user creates and submits the transaction, they are explicitly declaring what their section of the ledger should look like after the transaction is accepted

However, this emphasis on local, single transaction concerns comes at the cost of systems which have global concerns. Bitcoin has had a difficult time introducing smart contracts because many applications naturally want access to some global state: for example, a list of authorized users, a current price or a total supply.

Ethereum, in contrast, chose to keep track of a (global) set of account balances: the ledger state is a mapping from address to balance, and a simple transaction increments and decrements account balances in pairs. More complex transactions can do more complex things, and have access to their own global state. An ERC-20 token, for example, is nothing more than a smart contract that implements this accounting model and provides an interface for minting, burning, and transferring these tokens.

The difference between these two can be analogized to the difference between the cash in your pocket and the balance in your bank account.

Access to global information, such as price, is trivial in these models. However, there are a lot of downstream negative side effects of this choice.

First, every transaction must be sequenced and processed in some order, since it is difficult if not impossible to determine which transactions may try to touch the same piece of state. If one transaction updates your account balance at the same time as another one, you could inadvertently destroy tokens, double-spend, and other nasty bugs.

Second, as a consequence of the above, the ordering of transactions matters, which fundamentally gives the entity ordering those transactions a lot of power. This leads to undesirable phenomena including Miner Extractable Value (MEV) and front-running.

Third, this model fundamentally requires a sacrifice of determinism, and thus demands greater trust. Because the state of the blockchain could change between when you construct your transaction and when you submit it, the smart contract needs to be trusted to do “what’s in your best interest” when it runs, even if that isn’t what you intended. For example, a DEX needs to know that if the price has moved by a certain large percentage, then you are no longer interested in the trade. A huge amount of development effort, source of bugs, and attack surface area for hacks comes from this, as each smart contract needs to be trusted to check all of the “right” invariants.

The main problem is that Ethereum makes this choice of globalizing state for every dApp, and so all of them suffer the increased transaction costs, vulnerability to front-running, and additional development burden.

Three words you might see enter the discussion a lot are “concurrency,” “parallelism,” and “contention”. This can be a subtle concept, and in case you only have a vague sense of what these mean, it’s worth setting down some definitions: Concurrency is the ability for multiple actors to make progress on a task, without interfering with each other. Parallelism is the ability for multiple actors to make progress on a task at the same time, without interfering with each other. Contention is when multiple actors do actually interfere with each other.

To understand this better, let’s use an analogy: chefs in the kitchen. A single skilled chef can work on preparing multiple dishes at a time, switching between them at just the right time. This chef is highly concurrent. Multiple chefs can each work on different dishes at their own workstation. These chefs are highly parallel. A well run kitchen, though, can have many chefs working on many dishes together, and be both concurrent and parallel. If they start bumping into each other when reaching for a common ingredient, they are suddenly experiencing contention.

Inspired by a diagram from Introduction to Concurrency in Programming Languages

In the context of this discussion, Ethereum is decent at concurrency, terrible at parallelism. The UTXO model is fantastic at parallelism, but could face contention, making it not very concurrent, for some protocol designs.

Cardano and eUTXO

Finally, we can talk about Cardano. Cardano chose, instead, to improve on the UTXO model enough that dApps themselves could make these tradeoffs between independent operation and centralization. The eUTXO model that Cardano led the research on introduces three new primitives for smart contracts: The datum, the redeemer, and the validator.

The datum is an arbitrary piece of data attached to a single UTXO. This represents a piece of internal state relevant to that UTXO. You might use it to track the unlock time and return address for a vesting contract, for example.

The redeemer represents the signal for what to do, when there are multiple options. For example, you could use this to represent whether you are redeeming your vested tokens, or exercising the clawback because the terms of the vest have been broken.

Finally, the validator represents the conditions under which the UTXO can be spent, including validating whether the new state is correct. It has access to the entire transaction to make that decision.

The only state that a smart contract can depend on is those pieces of state included as inputs, and the only state a smart contract can produce is those declared as outputs of the transaction.

Transactions in Cardano are partially ordered by their dependencies, and a stake pool operator reordering things has no impact on the outcome, so MEV disappears.

Similarly, every Cardano transaction is deterministic: The user constructs, declares, and signs off on the new state of the world. The only way to change state is by spending UTXOs, and a given UTXO can only be spent once, so you are guarded from the state changing out from under you.

For many purposes and protocols, this is entirely sufficient to build an incredible amount of value. A vesting contract, for example, does not need access to any global state. The fact that Alice’s tokens are sitting in one UTXO locked by the vesting contract has no bearing on the fact that Bob’s tokens are sitting in another UTXO locked by the same vesting contract.

Some protocols, however, are much harder to divorce from their global state. A DEX like Uniswap, for example, fundamentally relies on pooling liquidity for capital efficiency, and creating a single unified view of the exchange rate between two tokens.

If many people need to access this global state, and that state is stored in the datum of a single UTXO, it creates a race among users to be the first to spend that UTXO. Each time someone wins that race, it resets everyone else back to square one: they have to find the new UTXO, construct a new transaction, and submit it.

Whether transactions are limited to only referring to UTXOs from previous blocks, or whether they can be chained within a block, this fundamental contention poses a serious challenge to the user experience and throughput of a protocol.

Thus, some clever engineering is needed when designing your protocol.

Misconceptions

Before talking about solutions, it’s worth addressing some misconceptions about the issue:

Misconception 1: Cardano is flawed because it only allows 1 transaction per block.

In fact, it is quite the opposite. Cardano allows many hundreds of transactions per block.

Instead, it is accurate to say that Cardano allows a given transaction output to be spent a single time, by a single transaction, so protocols that give multiple people access to the same UTXO might face contention issues

Misconception 2: Only one user can interact with a smart contract per block/transaction.

Also not true; the point of contention is around the UTXO, but many UTXOs may be governed by the same smart contract.

This fundamentally comes down to the shift in thinking from Ethereum, where you call into a smart contract to make it do something, and Cardano where you lock outputs with a contract, which determine when they can later be spent.

Misconception 3: The only way to solve this is through centralization.

Centralization is a way to solve this problem, but it is not the only way. See below.

Potential Solutions

Today, there appear to be two categories of solutions to this problem: either design your protocol to tolerate segmentation of your state, or aggregate interactions with that state.

Let’s design some hypothetical DEX’s to explore some of these solutions.

One could design a DEX such that it didn’t require a single liquidity pool. Instead, liquidity is fractured among a number of pools, and the further it’s fractured, the more ports there are for people to interact, and the less contention over those funds there are. However, the further you fracture the pools, the less capital efficiency you have, and the greater value lost to cross-pool arbitrage. The clever part, then, is in designing solutions to those problems: Uniswap v3 style concentrated liquidity, for example.

Alternatively, an order book model for an exchange, which on Ethereum is disastrously expensive to maintain and update, seems more fundamentally suited to Cardano: each order is a separate UTXO. The tricky part, though, is that you still have contention over the orders closest to the current price, where the sand-piles meet. A viable solution would be to have market orders listed on chain, and a third party aggregator matches and executes these orders. The clever part, then, is in ensuring that the matchmaker doesn’t have too much power over the market.

Finally, you could create a hybrid exchange, where custody of funds is decentralized and stored on the blockchain, but the market-making and matching is sent through a central backend server. This solves the engineering problem, but likely makes you a heavily regulated brokerage dealer, which comes with its own set of challenges.

SundaeSwap’s Solution

We’ve chosen a solution that differs from those above; Very soon we will be ready to pull back the curtain and reveal how it works. Given the nature of the recent discussion, we want to do so with receipts, and are currently preparing load tests to demonstrate exactly how well our scaling solution lives up to the task. Stay tuned for more information!

Summary

In short, the rumors of Cardano’s death have been greatly exaggerated. There are solutions to the problems seen today, benefits to the ways Cardano has been designed, and both a bright future, and an intense design discovery phase ahead.

It is an unhealthy aspect of our industry that many people, often with prominent voices, are maximalists on one technology. This may be driven by a financial incentive, hoping one wins out over the other for financial gain; it may be a runaway commitment to only one project at the expense of all others, where it’s become impossible to back down and still save face; or it may just be a bad taste over poor interactions with members of another community. In any case, it’s not very healthy to be in a position of arguing that one project in our community has all the answers and is superior in every way, be that project Bitcoin, Ethereum, Cardano, Solana, Mac, PC, Hammers, Screwdrivers, or any number of other choices we have over tools to use.

You won’t find any Cardano maximalism on our team. We believe that, yes, Cardano has interesting solutions to hard problems, and has made trade-offs and prioritized things differently that create new opportunities in the crypto ecosystem. We certainly believe in it enough to build our product on top of it. In the long term, as builders in the crypto-space, we believe that the end user won’t care which blockchain they are interacting with. The ideal end state, in our minds, is for blockchains to become like programming languages, with different projects choosing different chains to match the strengths needed to bring their protocol to light, and end users none-the-wiser.

So to the people claiming this is the death of Cardano: unlikely. To point to one rocky experiment in the earliest of early days of an ecosystem and hold it up as the fatal omen of Cardano’s downfall is premature naïveté at best, and intellectual dishonesty at worst. We’ve outlined several creative solutions above, and we’re sure there are many more that those building on Cardano have come up with.

--

--

Sundae Labs

Building sweeter blockchain infrastructure. One scoop at a time. Website: https://sundae.fi/