Cardax Dev team
By the Cardax Dev Team
The Cardano blockchain ecosystem is fast developing and constantly changing, with new and unexplored spaces appearing at dizzying rates. The stakepool business model appeared in summer 2020, cheap and easy native tokens emerged in spring 2021, and now smart contract capability has finally arrived on mainchain in fall 2021. Next up in the pipeline are decentralized identity, scalability explosion via isomorphic off-chain state channels, and the realization of the decentralized governance dream!
The current milestone of a smart contract enabled mainchain has been eagerly awaited in particular by the community, heralding the emergence of new and exciting decentralized applications (dApps) on Cardano. The Extended UTXO (EUTXO) model is expected to provide unprecedented determinism in smart contract interactions, with transaction results and fees predictable before their submission to the blockchain [IOHK No Surprises]. However, realizing these potential benefits has required a new generation of smart contract developers to be trained-up in record time. These developers often had to throw overboard their pre-conceived notions and established patterns from other smart contract models (e.g. Ethereum Solidity), and engage deeply with the design challenges and patterns inherent to the EUTXO model.
These challenges can be frightening and fascinating at the same time. Recently, the issue of concurrency on Cardano has received widespread discussion, and caused some in the community to worry about the feasibility of dApp development on our blockchain platform. We at Cardax would like to share our experiences so far with this challenge, and the principles that we are using to overcome it in our designs.
Our first encounter with the concurrency challenge
Along with several of our fellow Plutus Pioneers, we in the Cardax Dev team encountered the concurrency issue in the very first lecture of the Program (Cohort 1) in early May [Auction]. That lecture presented an auction smart contract as an example of what a minimal Plutus codebase of that scale could look like, and how the pieces that we would learn about—on-chain validators and off-chain handlers—fit together. The example was helpful as a mental map of the anatomy of a Plutus contract, but a critical issue quickly became apparent to anyone who spent enough time simulating the contract’s behaviour in responding to multiple interacting parties’ varied actions—due to the simplified/naive design of the contract, if multiple bids were submitted by different people in the same time slot, then only one arbitrarily-chosen bid would succeed and all others would be ignored. Only a significant re-design of the example would allow it to more gracefully handle simultaneous bids, but first the Pioneers had to learn why this was happening.
The EUTXO model requires that every transaction be validated with only the information that is contained in its inputs’ data fields, the redeemer provided by the transaction submitter, and the specific context of the transaction (outputs, fee, certificates, signatures, validity time range) [Extended UTXO]. This latter requirement restricts the validation procedure to a well-defined local scope, and thus provides Cardano smart contracts with the amazing determinism property—if a transaction is properly constructed and its UTXO inputs are available to be consumed by it, then the result of its validation will always be the same on the blockchain network as it is when you simulate the validation locally on your machine. This means that if it works on your machine, then you have absolute confidence that it will work on the blockchain and you know how much it will cost, before submitting the transaction, as long as the transaction inputs can still be consumed by it.
Mindful of the local scope restriction in the EUTXO model, the auction example took the simplest approach—hold all of the smart contract’s state (e.g. the highest bid so far) in a single UTXO and require any new bidding transaction to consume the state UTXO and update it with a higher bid. In other words, the design modelled the bidding process sequentially, whereby a new bid overrides the previous bid, if it is higher.
In addition to the local scope restriction, the EUTXO model enforces the rule that no UTXO may be consumed more than once in subsequent transactions, after it is produced by its transaction. This “no double-spending” rule lies at the heart of blockchains’ integrity guarantees, from the earliest Bitcoin days; without it, nothing would stop you from spending the same coin on several simultaneous purchases, and the value of the coin would lose any meaning as it multiplies into more and more copies on the network. Most, if not all, blockchains prohibit “double-spending” of their resources.
Unfortunately, the local scope restriction and the “no double-spending” rule combine into a significant challenge for any developer that seeks to create a dApp where an unlimited number of people can interact with each other via smart contracts simultaneously. Locality forces every interaction to explicitly include all relevant information on the state of the dApp, which must be contained in the UTXOs consumed by the interaction’s blockchain transaction. However, if any of the shared state is concentrated in a single UTXO that is open for all to consume, then there will be contention among dApp participants for that UTXO—eveyone will try to consume it, but only one will succeed in any given time slot.
That first Plutus auction example failed to handle simultaneous bids because it put the auction’s state (i.e. highest bid and bidder to-date) into a single UTXO that was open for anyone to consume in a bid.
Contention for UTXOs
Contention for UTXOs can be poisonous to any dApp design. In the best case scenario, the race to consume a dApp’s state UTXOs would be resolved randomly with unbiased odds, based on which transaction is the first to be included into a new block on the chain by an indifferent validator.
In the worst case, dApp participants may seek to gain advantage in the dApp by seeking out validators (e.g. stakepools) and enticing them to bias their selected transactions for the new block. It is exceedingly hard to bribe validators on the Cardano blockchain—there are too many of them, they are independent of each other, there is no direct mechanism to pay them more than the deterministic transaction fee, and no one knows in advance which validator will produce the block in any particular time slot. Nonetheless, the more variation in impact on people’s livelihoods that a dApp design leaves up to UTXO contention, the stronger the corrupting incentives may be.
In short, UTXO contention in a dApp design will lead to indeterminism in how participants’ interactions are resolved, and may introduce corrupting incentives to the wider ecosystem, though the ecosystem is quite resistant to these incentives. Our main objective as developers is to eliminate or mitigate all impactful UTXO contention from our designs, while still providing the dApp with all the information that it needs to function within the local scope restriction of the EUTXO model.
Reducing UTXO contention
The EUTXO concurrency challenge has sparked many interesting techniques to minimize UTXO contention. First and foremost, interactions in dApps should be designed in a way that minimizes their dependence on shared state as much as possible—if two interactions don’t depend on the same shared state, then they can proceed independently and in parallel of each other.
When shared state cannot be eliminated entirely from a dApp design, the split-then-merge threading pattern (first introduced by Emurgo’s research [Emurgo Research]) can be used. Indeed, many current approaches for building a Cardano DEX use some variation of this pattern. In the split-then-merge pattern, the state of a dApp can be split into multiple parallel threads that evolve independently of one another, as long as they are all merged together afterwards. Essentially, each parallel thread allows intentions to be declared independently by different participants, without explicit dependence on the whole dApp state. However, the actual effect of these intentions is only determined and executed in the merge transaction, and the merge transaction must include all the threads that were created by the split transaction, so that all activity in all threads is properly considered and not ignored. This pattern can be looped indefinitely, with new threads split out after every merge, and thus the global dApp state will evolve with each new merge.
In some cases, increasing the time resolution of interactions can reduce UTXO contention, as interactions that appear simultaneous in a coarser timescale may resolve into a sequence in a finer timescale. IO Global published papers on the Hydra scalability solution for Cardano, a set of smart contracts that allow a group of participants to lock funds on-chain, interact with each other in an off-chain channel, and then periodically synchronize the channel to the main chain, all with strong security guarantees [Hydra]. The beauty of Hydra is that it allows the sidechain to re-use smart contract designs from the main chain, and to increase the frequency at which participants’ interactions are resolved beyond the limits of the main chain.
UTXO contention and decentralized exchanges
In the simplest possible decentralized exchange (DEX), you would simply lock some amount of token A in a UTXO with the condition that it could only be consumed by a transaction that transfers at least some amount of token B back to you. Such a locked UTXO is an offer for anyone in the world to fulfill, and can only be fulfilled under the terms you outlined. However, the reciprocal side of that exchange has a much less pleasant experience than you—that person has to scan the blockchain to find liquidity UTXO like yours and then compete with others to consume them, with no certainty on if or when their trade would go through. In this free-for-all DEX, locking liquidity in a UTXO is effortless, while unlocking it is grueling work.
The difficulty of consuming locked liquidity UTXOs can be alleviated by an on-chain market coordination mechanism, by introducing incentives that nudge the market towards optimal behavior, and/or by increasing the frequency at which interactions are resolved on the blockchain.
Traditional centralized exchanges mostly use the limit order book as a market coordination mechanism. The centralized exchange operator collects limit orders (e.g. buy 10 ADA for at most 25 USDT) from liquidity providers into a global database, and then executes market orders (e.g. sell 10 immediately at the best available price) from liquidity consumers on a first-come first-served basis. These tradional finance institutions provide a smoother experience for liquidity consumers than the free-for-all DEX, via a centralized actor that has the exclusive right to match limit orders to market orders and execute the resulting trades.
One possible DEX approach is to replace the centralized actor with smart contracts that merge limit orders into a shared book stored in UTXOs, and execute trades by matching market orders against that book. However, this approach quickly runs into several difficulties: avoiding UTXO contention for the inherently global state of the limit order book, and fitting that potentially enormous global state within transaction and block size limits.
Automatic market makers (AMMs) such as Uniswap simplify the global state required to run the DEX [AMM]. Instead of a full-blown book of all not-yet-fulfilled limit orders, AMMs track the cumulative token reserves contributed by liquidity providers and the pairwise exchange rate derived from these reserves using a constant product formula (see details in [How Uniswap Works]). This global state is much easier to fit within the transaction and block size limits, but it can still lead to UTXO contention if people have to compete to access and update this global state.
Conclusion
At Cardax, we are tackling the problem from different angles, and are currently exploring several viable solution candidates with different trade-offs for user experience, determinism, scalability, market efficiency, and other criteria.
We are working intensively with partners to finalize and audit our approach and welcome collaboration with our fellow dApp builders. While it is important that different groups independently pursue different promising approaches, to ensure diversity of ideas and avoid the risk of “groupthink”, we should also support each other and collaborate where it makes sense.
Despite the worry that the concurrency challenge has caused in the Cardano community, we view it as an exciting opportunity for us to grow as an ecosystem – this is the first time that the “Bat Signal” has gone up in the sky for whole community to tackle an issue, not just a handful of core devs, and this will bring us all one step closer to the dream of decentralized block production, blockchain development, and government.
We look forward to the innovation on smart contracts that will emerge in the near future in the community, and will do our part to advance the state of the art in DEX designs. We intend to publish more in-depth posts on our approach in the coming weeks. Stay tuned! 
References
- [AMM] Automated Market Maker What Is Uniswap? | Uniswap
- [Auction] Plutus Pioneer Program, Lecture 1, Auction Plutus Pioneer Program – Lecture #1
- [Extended UTXO] IOHK Research. The Extended UTXO Model. January 2020. The Extended UTXO Model – IOHK Research
- [Emurgo Research] Emurgo Research, Parallelized Protocols Emurgo-Research/High Level Design Patterns In Extended UTXO Systems.md at master · Emurgo/Emurgo-Research
- [How Uniswap Works] Uniswap V2 Documentation. How Uniswap Works. How Uniswap works | Uniswap
- [Hydra] Hydra Paper Hydra: Fast Isomorphic State Channels – IOHK Research
- [IOHK No Surprises] IOHK Blog. No-surprises transaction validation on Cardano. September 2021. No-surprises transaction validation on Cardano – IOHK Blog
