Concurrent & Deterministic Batching on the UTXO Ledger

Downloadable PDF Version

Dat Duong Thanh — dat@meld.com
Hai Nguyen Quang — hai@meld.com
September 2021 — Draft v0.2

Abstract

This paper presents an eUTXO[1] smart contract architecture that allows concurrent and deterministic batching into a single state. Our solution is entirely deterministic, decentralized, and does not depend on honest or incentivized off-chain agents. While this paper uses batching swap orders into a liquidity pool on Cardano as the case study, the architecture should adapt to any frequently updated on-chain state on any UTXO blockchain that supports scripting. We hope this work will lead to a successful Cardano implementation and new smart contract architecture research in the future.

1 — Introduction

Most smart contract designs so far have been done on an account-based ledger model like on Ethereum. Due to fundamental differences on the ledger level, many of these approaches cannot be ported to the UTXO world. With the rise of UTXO smart contracts on chains like Cardano, Ergo, and Nervos, there is fertile ground for innovative new smart contract architecture research waves.

This paper presents a smart contract architecture that allows concurrent and deterministic batching into a single state. This work is essential in the UTXO world, where states are maintained in UTXOs that can only be spent once. Without a well-thought concurrent framework, there will be a race condition where different dApp users compete to consume the same UTXO. For example, multiple swap transactions want to consume the same liquidity pool UTXO, but only one succeeds per block. Our architecture allows dApp users to create multiple batch step UTXOs that are applied to the state UTXO in one single transaction. The key is to have a deterministic validation rule on-chain that enforces deterministic inputs and outputs. With that, the agent submitting this transaction cannot omit any input, rearrange the order, or change the output.

2 — The Architecture

2.1 — Overview

We start with a state UTXO that we want to apply batch steps to. We then attach a concurrency number c to its datum to determine the maximum number of batch steps it can apply in a single transaction. Every time a state UTXO is created, c reserve UTXOs must be created along with it.

A user can Reserve a step UTXO by consuming a reserve UTXO. A step UTXO must contain all data and values required to apply the step to the state. For a simplified liquidity pool interface, a step holds the Public Key of the trader and the tokens of one pair to be swapped for the other pair.

When the right phase comes, anyone can Apply the steps into the state. The validation rule of Apply requires c corresponding reserve and step UTXOs as inputs. This disallows the transaction from omitting any reserved steps from any user. The validation rule must be deterministic to guarantee a single set of outputs for a given set of inputs. For instance, this would disallow the transaction from choosing a preferred end-state by flagging a reasonable step as invalid or mixing up the ordering to front-run on a liquidity pool.

The outputs contain the new state and c new reserve UTXOs. Depending on the application, there may be user outputs such as a successful swap with the desired tokens or a failed swap with the original tokens. Alternatively, a failed step can be configured to remain for the next Apply transaction. After a certain amount of time, a step can be rejected back to a reserve.

Users can concurrently create batch steps from reserves, to be deterministically applied to the same state in one transaction.

We continue to explore key requirements and details of the architecture in the following subsections.

2.2 — Core UTXOs

2.2.1 — State
The core component in the architecture is the state that we need to concurrently consume UTXOs against. An example of this is a liquidity pool that transitions per swap order.

While the content of the state is application-dependent, there are a few key pieces of information to have:

• A concurrency level c: this is the total number of reserves and steps that exist at any given time, hence the maximum number of batch steps that can be applied in a transaction. This should be set to a number that meets the current transaction size limit and can be voted through governance to fine-tune.
• A token name t: this is a unique token name that determines the reserve and step UTXOs that belong to this state. For example, a DEX might have a currency symbol for all liquidity pools, with a unique token name for each specific pair. These tokens can only be minted with the state UTXO.
• A validity interval i: this is used to organize transaction validity intervals, which helps organize the Reserve and Apply phases. To prevent users from consuming UTXOs with the wrong redeemer, which would lead to congestion.
• A binary era e: this can be used to organize phases further. For instance, in era 0, the state is applied with steps from era 0, creating new era 0 reserves before turning into an era 1 state, with era 1 reserve UTXOs getting reserved in the same block. This allows state application in every block and effectively requires c era 0 reserves plus steps and c era 1 reserves plus steps at any given time.

The validation rule is also application-dependent, with a few foundational rules:

• Apart from the state itself, both the input and output sets must contain exactly c UTXOs that contain the t token. This ensures that no user steps are left behind and that the concurrency level cannot be compromised.
• The validation rule has to be deterministic. The same set of inputs must always result in the same set of outputs. This prevents any influence from off-chain agents that submit the Apply transaction. When step order matters, we can sort by a step attribute to still apply deterministically. For a liquidity pool, this can be the approximate submit time of each swap order step.

A state UTXO may also store values, like tokens of both pairs for a liquidity pool.

2.2.2 — Reserve
A reserve is a UTXO that dApp users consume to produce a step UTXO. It is used to guarantee that no steps are left behind in an Apply transaction.

If users can create steps directly without going through this reserve process, steps will be left behind when there are more steps than a transaction size limit can include. Furthermore, malicious off-chain agents can omit steps by choice because no on-chain validation guards this.

A reserve is application-dependent, with a few foundational rules:

• Store a t token for validation against its corresponding state and step.
• Have a binary era e that can be used to organize non-blocking phases.
• Have enough data to create a valid step. For example, a liquidity pool reserve should know what assets can be deposited to create a swap order step and a potential limit on the amount.
• Have an approximate creation time to prevent an Apply consumption during the Reserve phase and vice-versa.

2.2.3 — Step
A step is a UTXO that dApp users create to apply to the state UTXO. For instance, this can be a swap order for a liquidity pool.

A step is application-dependent, with a few foundational rules:

• Store a t token for validation against its corresponding state.
• Have a binary era e that can be used to organize non-blocking phases.
• Have enough data to make a valid state transition. For example, a liquidity pool step should store the deposited assets and attach the swapped assets to a Public Key.
• Have enough data to ensure a deterministic state transition. For instance, a liquidity pool step should have an approximate reserve time for the steps to be applied in that order.

2.3 — Timing

Timing is vital to address the congestion problem of the UTXO model. For example, we cannot allow a Reserve consumption of a reserve UTXO when an Apply transaction also happens for that reserve in the same block.

To solve this problem, we add a validation interval i to the state that is used to control the validation interval of created reserve UTXOs. Before a certain threshold, only a Reserve transaction can consume a reserve. After that threshold, only an Apply transaction can consume a reserve. This essentially creates two non-conflicting phases to avoid congestion.

To avoid the one-block-one-phase problem, we can introduce a binary era e to the state. For instance, in era 0, the state is applied with steps from era 0, creating new era 0 reserves before turning into an era 1 state, with era 1 reserve UTXOs getting reserved in the same block.

Validation intervals and timing are not just great tools to fight congestion; they can also be utilized for deterministic validation.

2.4 — Deterministic Validation

Deterministic validation is the key characteristic that prevents any influence from off-chain agents. Any state should have a deterministic validation rule that can be shared both on-chain and off-chain.

This means designing a pure transition function to iteratively apply to the state with each step.

Sample transition function signature

Each iteration should validate the step. If it is valid, update the state and append the corresponding valid output to the Output list. If it is not, append the corresponding invalid output to the Output list.

When ordering affects determinism, we have to sort the steps through an attribute before the iterative fold. For example, ordering matters for a liquidity pool state because it changes the price after each swap. Also, the off-chain agent can select any of the two similar steps that mark the end of liquidity for further swaps without order. Certain applications like voting might accept these problems when order does not matter. Others will have to find a unique attribute for each step to sort on.

A powerful attribute that can be assigned to most cases is the approximate reserved time of each step. This can be acquired through the off-chain timestamp supplied through the Reserve redeemer. This timestamp is then padded and guarded by an on-chain MustValidateIn constraint. A dishonest timestamp will fail to reserve.

With this deterministic validation rule, the on-chain script first calculates the outputs, including the new state, then compares them to those supplied through the transaction. Only transactions that provide this correct answer validate. Then off-chain agents can only use the same validation rule to construct the only valid Apply transaction.

2.5 — UTXO Discovery

For a specific dApp with a specific endpoint like https://api.dapp.com, it is straightforward for its backend to track all reserves, steps, and state UTXOs of a single state. This can be done by tracking all UTXOs that store the t token, with a minting policy that guarantees these UTXOs to store it at any given time, and only those can.

To avoid congestion, this backend can queue requests so that no two requests target the same UTXO in the same block. Congestion might still happen from external users, which is hard to prevent in a fully decentralized system. Luckily, this only happens for reserving the same UTXO during the Reserve phase. Steps and states only have one deterministic Apply redeemer in the Apply phase. We will continue to research a solution for this specific congestion.

At the time of writing, we recommend customizing the Chain Index component of the Plutus Platform for UTXO discovery and management.

2.6 — Scalability

The architecture’s scalability is very well-defined through the concurrency level c in the state. Since up to exactly c steps can be applied to a state in a single transaction, we can update this number to fine-tune the concurrency level.

An intuitive solution is to keep raising this number until we hit the transaction size limit. Then further update it with each ledger transaction size update.

Note that states with low traffic can keep this number low to reduce transaction fees and the number of non-used UTXOs.

As each state has its own concurrency level, it is possible to have a higher c for liquidity pools with higher traffic and a lower c for those that do not.

All these datum updates can be applied to live states through decentralized voting.

It is to be noted that our architecture is a general solution to a big problem. More specialized techniques might be needed to scale different dApps further. We also mention more dimensions to scale in the Related Work section.

3 — Experiments

We are prototyping multiple smart contracts using this architecture:

• Concurrently mint MELDed Fiat like mEUR against a governance state that tracks what fiat can be minted and collateral prices. Concurrently deposit/withdraw collateral, mint/burn mFiat at a CDP against a single oracle state that tracks prices.
• Concurrently lend and borrow against a MELD lending pool.
• Concurrently stake MELD to a governance state for validating governance proposals.
• Concurrently apply swap orders against a single MELD Vault (single-sided liquidity pool).

We have collected valuable findings along the way, especially on more techniques that work better in a few specific instances. We hope to demonstrate them in the upcoming versions and papers.

After a few different working prototypes, we will start generalizing the architecture into a library that can be reused anywhere. We might need to use Template Haskell to keep as many components reusable as possible. Library users can then focus on writing only their application-specific logic. This endeavor should yield more exciting ideas for us to raise and implement on Cardano public repositories as well.

We intend to open-source this library as soon as we reach a stable state.

4 — Related Work

There have been several proposals to solve the concurrency problem on a UTXO ledger. We summarize a few common ideas here.

4.1 — Divide & Conquer

If only one state UTXO can be consumed per block, we can break it down into smaller UTXOs to be spent concurrently. For instance, we can have multiple lending pools for lenders and borrowers to interact with per block.

This solution, however, is usually not capital efficient. One lending pool might not have enough assets for a big borrower to borrow from. When lenders want to withdraw their supplied assets, they have to consume all lending pool UTXOs they have lent to. Both these cases require consuming multiple UTXOs to process a request, which requires more UTXOs to avoid congestion, which again lowers the number of assets at each pool. This does not seem like an easy balance to solve.

This design also only works for applications with no shared state among the sub-states. It is tough to fit applications that do and those that require synchronization or accumulation of the sub-states.

Not all states contain capital to suffer from this problem. In certain applications like oracle price consuming, it may be plausible to have multiple similar datum-only UTXOs.

Note that this design is not exclusive to our architecture. One can break down a state into smaller states, then use our concurrent architecture on each sub-state. Since the maximum size of a transaction limits our architecture’s concurrency level, this approach can add another dimension to scale.

4.2 — Batching

Our architecture belongs to this group of solutions. The main advantages we have identified at this time are:

• Deterministic on-chain validation rule. Off-chain agents can only submit the only correct output. This means no influence whatsoever from any off-chain agents.
• Security. No edge exploitation from off-chain agents.
• Capital efficiency. We do not have to pay more for off-chain agents to act with good intent.
• Simplicity. The architecture is well-scoped. The off-chain infrastructure is minimal. We do not have to design complex incentive functions that may be affected by market conditions and require further governance to tune right.

There are still many exciting ideas that we can learn from other solutions, like chaining transactions in the same block. Since the transaction size limits our architecture, more extended dimensions to scale are still desired.

4.3 — Lazy Update

Lazy update is another line of techniques that we have been studying. The idea is to reserve to create update UTXOs like the batch steps in this architecture. However, instead of constantly applying the updates into a state, we wait until such a state is required on-chain.

For example, in a governance voting process, we only need to consume the votes when we consume their proposal to decide if it passes or not. Constantly applying votes to the proposal state risks congestion and unnecessary transaction fees. The off-chain world is unaffected, as it can still find the vote UTXOs and show users the state of the proposal.

Another instance is to store just enough data to calculate the interest a borrower has to pay at any given time instead of constantly updating this interest on-chain.

The key questions to ask when designing on-chain states are then:

• When do we have to consume the state on-chain?

• How often do these events occur?

• How do we design the contract to do less on-chain and do more off-chain?

• How do we design the deterministic validation rule and transition function for the state?

If this line of study continues to flourish, we will write another research paper and open-source library for it.

5 — Conclusions

This paper presented a general solution to the concurrency problem on UTXO ledgers, especially for on-chain states that require constant updates. The architecture is still in its early form. More specialized techniques are needed to scale different dApps further. We have, for example, been designing extended and different architectures for different MELD components.

We have a massive backlog of innovative ideas to explore and expect to publish many new versions and research efforts soon. It is now indeed the best time to do R&D on Cardano and the UTXO ledgers in general.

References

[1] M. Chakravarty, James Chapman, K. Mackenzie, Orestis Melkonian, M. P. Jones, and P. Wadler. The extended UTXO model. In Financial Cryptography Workshops, 2020.