It can be difficult for developers to take full advantage of the UTxO model because they have to take parallelization into account. Cardano does not allow maintaining a single global application state in the on-chain part of the smart contract. Each UTxO can represent a piece of the application's state and can be processed independently and in parallel. This theoretically allows for high throughput and scalability, but the application must deal with complexities related to managing concurrent transactions. What challenges do developers face on Cardano?
When Parallelization is Easy
In the Extended Unspent Transaction Output (eUTxO) model, each UTxO can be processed independently and in parallel. Spending of UTxO is not dependent on any global Cardano state. If the spending conditions are met, one or more output UTxOs will be created through the transaction from the input UTxO (or more input UTxOs). The input UTxO(s) must be completely consumed. Output UTxO(s) must have the same (or smaller) value as input UTxO(s).
If Alice sends 100 ADA to Bob, the spending of UTxO is dependent only on Alice's Witness. If a hundred other users send a similar transaction, 100 other unique input UTxOs are used. Each transaction sender is the owner of the input UTxO. There is no dependency between transactions and input UTxOs.
There is no dependency between transactions and input UTxOs because all senders are independent of each other. They made their own independent decision to send 100 ADA. All 100 transactions can be inserted into the same block and will be evaluated as valid.
A transaction consumes one or more UTxOs as inputs and produces one or more new UTxOs as outputs. This simple rule applies both to the transfer of value between Alice and Bob, as well as in the case of applications, as you will see later.
In the picture, you see 3 identical transactions. With 100 transactions it would look the same. Don't get confused by the fact that the sender is always Alice and the recipient is Bob. Each time it is a different Alice and a different Bob. The figure is meant to demonstrate the fact that no synchronization is required between senders of transactions. If the transactions are valid, they cannot fail and they all get into the blockchain.
You may realize the meaning of the picture later after we explain how DEX works.
The Cardano network can validate transactions in any order, as transactions are independent of each other. This is an advantage from the point of view of network throughput since the consensus is not dependent on sequential processing.
How to Create a Parallel Application?
Ideally, application developers should create such smart contract logic that behaves similarly in terms of parallelization as when 100 senders (Alices) send a transaction. However, this is almost impossible.
Let's clarify this with an example of a DEX that uses liquidity pools.
A liquidity pool is filled by multiple transactions that produce output UTxOs. These UTxOs represent the tokens in the liquidity pool. With each newly appended block to the ledger, the composition of UTxOs in the liquidity pool may change.
In the picture, you see a liquidity pool with a pair of tokens X and Y. In the liquidity pool, there are several UTxOs with tokens X and Y. In the next block, Alice, Bob, and Carol put new UTxOs with the token X into the liquidity pool, and Dave, Eve, and Frank put some UTxOs with token Y. Since no swap occurred, no UTxOs were removed from the pool.
To make a swap, the DEX must consume UTxO (or more UTxO) from the liquidity pool as input for each token type. These UTxOs must be spent completely. If the swap does not require all the tokens in the UTxO, then the remaining tokens must be returned to the liquidity pool as a new UTxO.
In the case of DEX, many operations are going on concurrently at the same time. Users send tokens (liquidity providers) to liquidity pools. Providers are senders and DEX is the recipient. At the same time, other users can send requests for swaps. They are senders who give X tokens to DEX and want to get Y tokens. Or vice versa.
Multiple participants can submit a swap request within a short period of time. These swaps may relate to a single liquidity pool. Thus, there is an interdependence between the participants.
It's also a good idea to clarify what exactly DEX is. Complex smart contracts in Cardano (like DEX) consist of two parts: on-chain logic that is executed on blockchain and off-chain logic that is executed on servers (or in local wallets).
In the picture, you can see a DEX which is composed of on-chain and off-chain logic.
While the execution of the on-chain logic is naturally decentralized as it takes place in the Cardano network, the team is responsible for the decentralization of the off-chain logic of the DEX. The off-chain part of the DEX is not composed (should not be) of only one agent, but of several agents.
In the case of DEX, these agents are called batchers. They are responsible for executing swaps. Batchers create transactions that meet the conditions of spending UTxOs in the liquidity pool and transfer assets in the ratio that both swap participants requested.
Cardano does not allow maintaining a uniform global application state in the on-chain part of the smart contract. It is technically possible, though.
If developers were to store the entire state of a DApp in a single UTXO, they would essentially be creating a global state similar to what exists in Ethereum’s account-based model. This could limit the concurrency and throughput of your DApp. This approach would not fully leverage the benefits of the EUTxO model.
In the on-chain part of the DEX, UTxOs and associated Datum represent the application state. The state is therefore distributed across UTxOs. If the DEX is to have a uniform global application state, it must be maintained off-chain across batchers.
In the picture, you can see a liquidity pool with tokens X and Y and 3 batchers. Global application state and state synchronization between batchers are indicated in blue. Application state consists of on-chain data which are Datums associated with UTxOs and off-chain application state maintained by batchers (agents). Batchers communicate with each other to synchronize a uniform global application state.
This is necessary because batchers (agents) access the same resource and that is the liquidity pool. They need to use input UTxOs from the liquidity pool (to execute the swap) and it may happen that two (or more) agents want to use the same UTxO. A contention problem may occur.
Now it's time to remember the first image in the article. When 100 senders submitted a transaction, they could not compete with each other for the same UTxO, as each sender used their own UTxO. UTxOs in the liquidity pool are a shared resource, i.e. a resource accessed by multiple agents.
Generally, contention refers to the scenario where multiple threads or processes (in our case, agents) are trying to access the same resource in such a way that at least one of them runs more slowly than it would if the others were not running.
In our case, there is a risk that two agents will construct a transaction in which they use the same input UTxO from the liquidity pool. In this case, only one transaction will be accepted by Cardano. The second one fails.
In the picture, you can see that batcher 1 and batcher 3 are trying to use the same UTxO with token X. Contention has occurred. Batchers are apparently poorly synchronized and do not know each other's intention to use this particular UTxO. If 2 swap transactions are constructed, one will succeed and the other will fail.
The goal of DEX is to enable swaps to be executed concurrently, i.e. so that individual agents can construct transactions simultaneously and contention does not occur when they pick UTxOs.
To prevent transactions from failing, there must be off-chain communication between agents or some other form of synchronization. In other words, agents must maintain a consistent global state of the DEX.
Individual agents must somehow reserve UTxOs in the pool so that the same UTxO is not used by another agent. Alternatively, it can work in such a way that within each next block (20 seconds) all transactions will be constructed by a single (randomly chosen) agent. Although this approach is decentralized, it is less concurrent.
You can see in the picture that batcher 1 and batcher 3 chose UTxOs with tokens X and Y in an exclusive fashion for swaps, so there was no contention. Swap 1 and 2 run concurrently. There was no contention because all batchers synchronized the global state with each other.
Note that token X has exactly 2x the market value of token Y and coincidentally there were suitable UTxOs in the liquidity pool for pairing. Swap 1 consumes 100 X tokens and 50 Y tokens. Swap 2 consumes 200 X tokens and 100 Y tokens. If there was no UTxO with 100 X tokens in the pool, the second most suitable would be a UTxO with 114 X tokens. This means that 14 X tokens would have to be returned to the liquidity pool as a new UTxO.
One of the other challenges, which will not be discussed further in the article, is the appropriate selection of UTxOs for swaps. With Ethereum, this is not a problem, as basically only account balances are updated.
It is possible to think about the problem in a completely different way than using a liquidity pool. Instead of putting UTxOs into one pool, it is possible to connect individual swap candidates. However, for the sake of simplicity, let's stick to liquidity pools in this article.
Designing a DEX on Cardano that can process UTxOs in parallel while maintaining decentralization involves addressing the concurrency problem. This is one of the challenges for developers.
In the article, we showed one of the possible solutions, i.e. the use of off-chain and on-chain components. The off-chain component can be used to correctly form transactions to interact with the on-chain code. Correctness is ensured through off-chain communication enabling synchronization of the global state of the application.
One of the other possible approaches is to create an algorithm that gives users exclusive access to submit the desired action. The algorithm can subsequently merge all actions together respecting timing and fairness.
Developers can maintain a single state in the on-chain part of the application or split it up across multiple UTxOs. Having a single on-chain state is easy because it's easier to maintain consistency. All parts of the application work with the same data. Splitting up the on-chain state across multiple UTxoS can increase the concurrency but it comes with several challenges. Managing multiple UTxOs adds complexity to smart contract logic. It is necessary to ensure some form of synchronization that ensures correctness (avoidance of contention).
The core of the problem lies in achieving parallelization in a decentralized environment.
The application logic is always linked to UTxOs. Each UTxO represents an independent piece of state that can be processed in parallel. As we explained in the article, this is only possible if some reliable form of synchronization is implemented.
If there was only a single batcher or off-chain agent, it could manage the state of the DEX and prepare transactions without having to worry about concurrency issues. This could potentially lead to faster transaction processing and higher throughput.
However, this approach would essentially centralize the off-chain part of the DEX, which goes against the principle of decentralization. The challenge, therefore, is to achieve off-chain decentralization while still maintaining high performance and avoiding concurrency issues.
Ethereum Developers also Face Challenges
Ethereum uses an account-based model and smart contracts have a global state that is updated by transactions. The global state is a code (functions) and data (state) that resides at a specific address on the Ethereum blockchain.
A global state of DEX could represent the current state of the order book, including all open buy and sell orders. When a new swap transaction is submitted, it represents a potential change to this global state. However, this change only becomes accepted once the transaction is included in a block and validated by the network.
Transactions in Ethereum are processed sequentially, one at a time. This means that there’s no concurrency in the Ethereum world, thus no concurrency issues. This sequential processing makes it simpler to design DEXs on Ethereum when it comes to concurrency and parallelism because developers don’t have to deal with the complexities of managing concurrent transactions.
However, this sequential validation fails to exploit the concurrency. Executing transactions in parallel would be unsafe, because there may be dependencies between contracts. If one contract depends on the results of another, then those contracts must be executed in the same order by every validator.
The order of transactions within a block is determined by validators. They can choose to sort transactions based on factors such as GAS price, nonce, and first-seen-time. Therefore, while a DEX can create a queue of many swaps, it cannot be sure in which order these swaps will be executed.
This uncertainty can lead to situations where transactions fail due to race conditions, where different transactions compete to consume the same liquidity. To handle this, some DEXs implement mechanisms such as slippage tolerance and transaction deadlines to increase the likelihood of transactions being executed successfully.
A race condition could occur when multiple users try to swap tokens at the same time. For example, let’s say two users both want to swap ETH for USDT, and there’s only enough USDT in the liquidity pool for one of the swaps to go through. Both users submit their swap transactions at roughly the same time. The Ethereum validators will decide the order in which these transactions are included in a block.
If user A’s transaction gets included first, their swap will go through and there won’t be enough USDT left in the pool for user B’s swap. When the Ethereum network tries to process user B’s transaction, it will fail because it can’t fulfill the swap.
The outcome depends on the relative timing of two or more operations (swaps). Even though Ethereum processes transactions sequentially, race conditions can still occur when multiple transactions depend on a shared resource (like a liquidity pool in a DEX) and are submitted around the same time.
Notice that a race condition can occur even if the liquidity pool is managed by only one DEX. This is because the race condition is not caused by the DEX itself but by the nature of the processing of transactions.
In other words, applications on Ethereum can prefer some order in which transactions should be processed, but this is not under their own control. In the case of Cardano, transactions are processed on a first-come, first-served basis. However, it is necessary to mention that pools do not have to follow this rule and there is no mechanism that would force the pool to select transactions from the mem-pool correctly.
Let's briefly compare the challenges for developers on both platforms.
When building a DEX or any other decentralized application on Cardano, one of the challenges is managing and synchronizing pieces of state across multiple UTXOs and agents. This allows for higher throughput and scalability but also introduces additional complexities related to managing concurrent transactions.
The application can manage and update its state off-chain, and then periodically commit the state to the blockchain. This approach can help reduce the load on the blockchain and increase the speed of transactions. Moreover, off-chain synchronization can also facilitate parallel execution of transactions on-chain. DEX can prepare multiple transactions in parallel and then submit them to the blockchain for execution.
Fast off-chain synchronization can potentially lead to high scalability and parallelism on-chain. Developers try to achieve the maximum possible parallelization through synchronization.
This is different from Ethereum's account-based model, where the state of the entire application is stored in a single global state. The global state can hold all necessary data for the DEX and changes through transactions. Since Ethereum processes transactions (calls) sequentially, developers do not have to worry about concurrency at all.
However, the problem is that some form of parallelism is represented by the behavior of users who may try to consume the same liquidity in the DEX on Ethereum. They are basically fighting for a single resource similar to batchers who may want to consume the same UTxO.
Ethereum DEX developers cannot completely prevent race conditions related to multiple users attempting to consume the same liquidity. The state of the liquidity pool (i.e., how much liquidity is available) is determined by the transactions that have been included in the blockchain. Users do not know in real-time whether their transactions will succeed because Ethereum processes transactions sequentially and the order is decided by validators.
Developers may try to create some mechanism to prevent users from submitting a transaction that has a high chance of failure. However, this is a very difficult task.
Note that Cardano behaves deterministically unlike Ethereum.
To take full advantage of the UTxO model and parallelization, it is necessary to improve the Ouroboros Proof-of-Stake. The Cardano network must be able to validate and pre-approve a large number of transactions at one time. If several tens of transactions were inserted into the block once every 20 seconds, it does not matter that it is possible to process them in parallel. Scalability would still be relatively low. Input Endorsers will bring the necessary improvement of PoS consensus in which the UTxO model will shine significantly more.