MLabs - Cardano Throughput Solution

[IMPACT] 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.

[IMPACT] 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.

[IMPACT] 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.

[FEASIBILITY] Please provide a detailed plan, including timeline and key milestones for delivering your proposal.

1st month

• Research the specifics of the protocol design, particularly the slot leader specification method
• Source feedback on the overall design

2nd month

• Begin implementation of the protocol as a library
• Formal verification of implementation details

3rd month

• Testing and verification
• Reducing MEV, furthering balancing of incentives across the protocol
• Initial use cases

[FEASIBILITY] Please provide a detailed budget breakdown.

Engineering hours: 1015

Total: $81,200

Breakdown:

Feature Total Time

Planning and Design: 100

Slot Leader Specification Method: 150

Planning and Integration with Spec Language: 115

Design and Testing of On-chain Mechanisms: 150

Ergonomic and Efficiency Improvements: 100

Reducing/Testing MEV: 50

General Testing of Protocol Function and Incentives: 150

Subtotal: 815

Change Budget: 200

Total Time: 1015 hours

Total Cost $81,200

[FEASIBILITY] Please provide details of the people who will work on the project.

MLabs

MLabs has quickly become one of the premier development firms in the Cardano Ecosystem. We are an IOG Plutus Partner and work regularly with IOG to develop the Cardano blockchain and ecosystem. Our team is composed of talented developers who have helped build community projects such as:

• Liqwid
• SundaeSwap
• Minswap
• Optim
• Many others

Through our work with early-stage projects, we have one of the largest groups of Haskell/Plutus developers in the community.

Website: https://mlabs.city/

Core Team

Compilers and Formal Methods

Las Safin

Las is a software engineer and formal methods specialist who is experienced with dependently typed languages such as Idris and Agda and who is interested in Cedille. At MLabs, he helps manage Nix environments for use in development and writes application specifications as well as compilers.

Las has also made significant contributions to Cardano tooling. Most notably, he is the creator of Plutarch. Plutarch is a typed eDSL in Haskell for writing efficient Plutus Core validators. Plutarch significantly lowers the resource demands of validators written in the eDSL while providing developers more fine-grained control of the Plutus Core generated. See the GitHub link for more information.

Plutarch: https://github.com/Plutonomicon/plutarch

GitHub: https://github.com/L-as

Performance Optimization and Type systems

Chase Maity

Chase is a polyglot software developer with expertise in Haskell and C. He’s interested in type systems, programming language design, and performance-optimizing compilers. At MLabs, he has worked on both on-chain Plutarch code and off-chain smart contracts; as well as providing technical specialist assistance on Plutus Core and its intricacies. Outside of MLabs, Chase spends time contributing to open source, and learning more about Haskell and type systems.

Chase is also a core contributor to Plutarch, having been a close contributor since before the 1.0 release. He was also the writer of the first Plutarch validator to be used in production, through the Minswap project. Currently, Chase aims to help Plutarch achieve even higher limits both in terms of ergonomics and in terms of on-chain efficiency.

GitHub: https://github.com/TotallyNotChase

[FEASIBILITY] If you are funded, will you return to Catalyst in a later round for further funding? Please explain why / why not.

The deliverables of this proposal will be accomplished with the funds requested. However, we may request additional Catalyst funding in the future to extend the scope/impact of the project.

[FEASIBILITY] Are you or any member of your team working on any other proposals in this Fund9?

[FEASIBILITY] Are you or your team working on any other proposals from previous Funds?

[AUDITABILITY] Please describe what you will measure to track your project's progress, and how will you measure these?

We will measure:

• the number of features implemented
• the number of issues discovered and resolved
• the usability of this approach to dApp projects that have incorporated it
• the number of contributors adding to the GitHub repo
• the number of Cardano projects relying on this approach
• the general perception of the project in the space

We expect growth/positive results in these areas and are committed to meeting the milestones we have established throughout this proposal.

[AUDITABILITY] What does success for this project look like?

Success for this project involves adding to the list of throughput and scalability mechanisms available for developers on Cardano seeking to build performant dApps that can support high volumes of transactions. Our solution should approach a Nash equilibrium, be hard or impossible to game, and offer a more decentralized solution than what is currently available throughout the ecosystem.

[AUDITABILITY] Please provide information on whether this proposal is a continuation of a previously funded project in Catalyst or an entirely new one.

This is a new proposal.