Please describe your proposed solution.
Problem
Protocols ("DApps") that build on top of Cardano can be viewed as distributed state machines that store their state in many UTXOs. A transaction is then a state transition on a subset of that state, i.e. UTXOs.
A problem that most protocols encounter is that many users often need to use the same UTXOs. This is especially a problem for the state machine abstraction from plutus-apps, as it puts all the state into a single UTXO, meaning that you must (by definition of the protocol) always use that one UTXO, since there is only one UTXO.
When multiple parties attempt to act on the same state, there is a concurrency problem. The concrete issue is that since Cardano is deterministic, a transaction references the input state via the transaction that produced it. This means that of the multiple transactions that act on the same input state, only one can be accepted. The rest will be discarded since the transaction inputs no longer exist (as they've been consumed).
The approach described here is meant to fix this problem in a generic way while still ensuring fairness.
Solution
The core issue is that consumers of the state must know the previous transaction that acted on the state to ensure a single chain of transactions that can be handled efficiently.
Assume a p2p-network of nodes (users and leader) that are interconnected each, with at most N direct connections. The solution we present here mimicks Ouroboros's selection of slot leaders. We split up our protocol into a series of slots (that have no relation to slots on Cardano), and for each slot, a leader is randomly elected according to their stake in the protocol via a verifiable random function (VRF) and a mechanism similar to that of Cardano's consensus layer. The leader advertises that they are the leader (i.e. they advertise the result of their coin toss), and lock the state machine for one slot. In this one slot, only the leader can interact with the protocol.
Users of the protocol must interact with the leader if they are to interact with the protocol. They can do this through creating and signing a transaction that outputs an action UTXO. This UTXO can be consumed by the leader if they also do the correct transformation on the state according to the action UTXO. The crucial thing to note here, is that the submitter of this UTXO does not know the exact state it is in. They can, however, express predicates as complex as the protocol allows.
The two critical properties that we desire to maximise are:
- Users actions are accepted into the ledger.
- The order of users' actions are not changed.
This notably means that the leader can not censor users, and that miner-extractable value (MEV) is minimised. The way we achieve this is by having users of the protocol cooperate, to ensure that ordering is achieved.
When a user submits an action transaction, they submit it to each of their "upstream" nodes that are closer to the leader than themself. When receiving transactions from downstream, they will submit them upstream. Yet, they will also make their own action transaction depend on this action as a dependency. The leader can only accept an action if its dependencies have already been included. This mechanism ensures that a leader can't selectively censor one user since many others would be unable to get their action in either.
The leader would get a fee from each merged action. If the number of merged actions is too low in a slot, the slot can end prematurely, such that a new leader can be elected. The measure of "too low" depends on the average, which is also affected by slots that are too low.
The important thing to note, is that each action is known to the leader much sooner than if they had had to wait for it to get accepted into a block then come downstream again. This wait is what leads to the more common design of batching.
As the leader knows the transactions because they are accepted, they can make new transactions that depend on the older transactions, assuming they do get accepted. If there was another leader in play, they would be in conflict, and thus they would no longer be able to know whether their transaction would certainly be accepted, as the state machine UTXO might have been replaced by the other leader.
Since each individual transaction is small (because there's no batching), the process can also be cut in the middle, and there will still have been progress. That said, the system isn't foolproof since a leader can still put in trades before and after a trade by a user on a Uniswap-style DEX for example. Figuring out a way to prevent this, through e.g. putting actions into pseudo-blocks with an internally random order, remains as future work.
Market
dApps such as DEXs building on Cardano, developers working on high-throughput applications, users of Cardano and the ecosystem as a whole.
Please describe how your proposed solution will address the Challenge that you have submitted it in.
Intended Fund – Fund9: Developer Ecosystem
Fund Statement – “How can we create a positive developer experience that helps the developer focus on building successful apps?”
What does this proposal entail?
Although the scope of our proposal may seem ambitious, elements of the solution we propose are already under development. If successfully funded, we will:
- Flesh out the design and implement this in practice as a library such that it is easily reusable.
- Formally inspect the properties of the protocol to ensure that our desired properties are upheld (MLabs has several tools at its disposal in this regard including Apropos and our Specification Language previously funded in Fund 8).
- Make sure incentives are aligned.
- Try to reduce MEV as much as possible.
How does increased throughput on Cardano help developers?
Until now, constrained throughput has placed heavy constraints on developers and thereby limited the types of DApps they are capable of delivering. In the case of DEXs, some like SundaeSwap and Minswap have addressed this basic limitation by introducing a trusted batch-based ordering of transactions (e.g., state transitions). Our solution sidesteps this trusted approach, increasing decentralization while maintaining throughput. Since the output of this proposal will be open-sourced, developers building on Cardano will be able to incorporate it into the wide range of smart contract applications they build.
What are the main risks that could prevent you from delivering the project successfully and please explain how you will mitigate each risk?
Since basic portions of our deliverables have already been implemented, this proposal is likely low risk. MLabs employs talented developers, and the Core Team working on this project is entirely familiar with Cardano at a low level. The likeliest stumbling block may occur in the situation that avenues to excessive MEV are difficult to curtail, possibly limiting the real-world impact of this approach.