Cardax blog

Archives


Categories


Meta


Streaming merge: the Cardax concurrency algorithm

Cardax Dev teamCardax Dev team

The issue of concurrency arises for any decentralized application that allows multiple users interact with it, if the results of user actions are not independent from each other. Cardax is an automated market-maker (AMM) decentralized exchange (DEX), which makes it a prime example of such a concurrent decentralized application. At any given time, we expect that multiple liquidity providers may want to deposit/withdraw liquidity and multiple traders may want to swap liquidity. Each of these actions affects the liquidity reserves in the DEX and each swap may affect the prices for subsequent actions.

We have developed a general-purpose algorithm (we call it “streaming merge”) that will allow our users to interact with our protocol concurrently without interruption or interference from anyone. The algorithm provides exclusive threads to users under which they can submit their actions, and then merges those actions into a single thread that respects their timing. This merged thread can then be deterministically processed by a sequential action resolver—batches of consecutive actions at a time—accessing at that time any global state (e.g. DEX token reserves) that it needs.

Crucially, streaming merge guarantees that, once a user’s submitted action shows up on-chain in a block, it will be executed before any later actions, up to the on-chain environment’s ability to distinguish different times (more on that below). In other words, the order of execution for user actions is not under the discretion of Cardax nor anyone else (e.g. order batching bots, third party aggregators).

Streaming merge will provide concurrency to the Cardax AMM DEX, where “actions” include traders’ swap orders and liquidity providers’ deposits/withdrawals of liquidity, but it is a general solution that we intend to re-use for other services that will be hosted on Cardax in the future. In time, we will release it as a general library that will hopefully put to rest most concerns about concurrency on Cardano—our contribution to the community!

In this article, we would like to walk you through the core of streaming merge, where users submit actions to their own exclusive threads, and those actions are merged together into a single thread.

Actions

A user action is a package of (1) terms for execution and (2) a value deposit denominated in one or more tokens. For example, a Cardax swap order action would specify the amount of token X that the user wants to buy, and include some deposit of token Y to pay for the purchase.

The streaming merge algorithm treats user actions as sealed and opaque—it leaves the action’s contents intact, merely moving them around from user’s thread to the merged thread. The algorithm is only concerned with the timing of actions and which users submitted them, not the specifics of the actions nor the global state needed to execute them.

Figure 1

Figure 1 shows an opaque action (on the left) and the contents inside of it (on the right).

This modular approach alleviates the problems related to concurrent access of global state, and it will allow us to expand quite naturally beyond AMM DEX orders to a wider range of fully-configurable DeFi services—the merging algorithm can remain the same, while the action resolvers can be evolved.

Parallel threads of actions over time

Picture in your mind a set of parallel threads. At each discrete point in time, each thread may have an action submitted from its user.

Figure 2

Figure 2 shows three parallel threads of user actions, zoomed-in to a particular period of time. The first thread has actions at times 2, 5, 11, and 12; the second at times 1, 2, 3, 4, 8, 9, 12, and 15; and the third at times 2, 3, 5, 6, and 13.

If you zoom-in the threads to a particular period of time in the past—where user actions are known—can you figure out how to merge the users’ actions into a single thread, respecting action times and without giving any user an unfair advantage over other users?

One way to do it is:

  1. At each time, gather actions from the user threads into groups of simultaneous actions.
  2. Within each group, randomly permute the order of the simultaneous actions, to avoid giving any one user a systematic advantage. For example, if there are three simultaneous actions {X,Y,Z}, then one of the following permutations will be selected with equal probability: XYZ, XZY, YXZ, YZX, ZXY, ZYX.
  3. Flatten the sequence of permuted groups into a single thread of actions.

This is a high-level sketch of the approach that we have chosen, after considering multiple alternatives.

A sparser representation of threads – sequences of timestamped actions

Figure 2 (above) is convenient to visually represent parallel threads, because it aligns the threads’ actions along a timeline, which makes it easier to see the groups of simultaneous actions. However, it is not a very compact representation, because it explicitly shows for each thread all the times at which it did not contain actions.

An equivalent but more efficient representation of a thread would timestamp each action and omit the times at which the thread did not contain actions.

Figure 3

Figure 3 shows a more compact representation of the threads in Figure 2. The arabic number inside each action represents its timestamp, and the roman numeral below the action represents its sequential position within the thread.

This is the fundamental data structure that we need on the Cardano UTXO ledger to represent threads of user actions submitted over time.

Building user threads on the blockchain

On the Cardano ledger, information and value are contained in unspent transaction outputs (UTXOs) that are produced and consumed by transactions. Each UTXO is produced exactly once in one transaction and may eventually be consumed exactly once in another transaction.

The active UTXO set at a given time consists of the UTXOs that have not yet been consumed, containing all of the on-chain information and value that are potentially available to validation scripts at that time. In other words, if a transaction wants to re-allocate value and/or rely upon on-chain information, then it must consume the UTXOs from the active UTXO set that contain that value and/or information.

How do you implement a sequential data structure (like the one in Figure 3) within the active UTXO set? The trick is to use a sequential family of NFTs, which uses a combination of monetary scripts and validator scripts to guarantee that each successive NFT can only be minted once, in a transaction that involves its direct predecessor.

A user’s thread always starts as a single UTXO that contains only the first sequential position NFT and nothing else – we’ll call this UTXO the “thread tip”. The user can add an action to the thread in an Add transaction that proceeds as follows:

  1. Consume the thread tip UTXO.
  2. Consume some inputs that contain the value that the user will deposit into her action.
  3. Produce a UTXO that contains the user’s action (i.e. terms and value deposit) and the position NFT from the consumed thread tip. Store the timestamp in the UTXO datum.
  4. Mint the next position NFT.
  5. Produce the next thread tip UTXO, which contains only the position NFT minted in this transaction.
Figure 4

Figure 4 shows four transactions build-up the on-chain representation of the first (purple) thread from Figure 3. Each transaction consumes the latest thread tip UTXO (hollow circle input) and some UTXO with value to be deposited (solid circle input), producing a positioned action UTXO (solid circle output) and the next thread tip (hollow circle output).

Once a position NFT gets attached to some action, it can only be separated from the action in a transaction that burns the position NFT. This ensures that the corresponding position can only be filled once in a given thread, and the contents at that position are maintained until it is time to consume the thread.

In this way, each user builds up her own thread independently and without interference from anyone else.

Merge and permute actions from threads

Our process to merge actions from user threads is reminiscent of the merge sort algorithm, except that we merge more than two lists at a time and we randomly permute elements that are tied for time instead of keeping their original order stable, as merge sort does. Thus, the resulting merged thread is sorted by action time, with a fairly randomized tie-breaker.

On the blockchain, we implement the merge process as an iteration of transactions, which terminates when there are no more actions remaining to move from user threads to the merged thread. In other words, if we are merging N user threads, then each of these transactions moves between 1 and N actions from the user threads to the merged thread, until all actions have been moved.

The merged thread always starts as a single UTXO that contains only the first sequential position NFT for the merged thread and nothing else – we’ll call this UTXO the “merged thread tip”. Each Merge transaction proceeds as follows:

  1. Consume the merged thread tip UTXO.
  2. Consume the first not-yet-merged action UTXO from each user thread. If the merged thread tip contains a user thread position NFT, then the “first not-yet merged action UTXO” for that user thread is the UTXO that contains the next consecutive position NFT for that user thread; otherwise, it’s the first position NFT for that user thread.
  3. Determine the earliest time among the actions consumed by this transaction.
  4. Partition the consumed actions into those whose times are equal to the earliest time, and those that whose times are later than the earliest time.
  5. For each of the actions with later times, produce a UTXO that is identical to the consumed UTXO for that action, which includes the action and the user thread position NFT. In other words, these actions are propagated “untouched” by this Merge transaction, to be dealt with later.
  6. Randomly permute the actions with the earliest time, with uniform probability of permutations.
  7. For each of the randomly permuted actions, mint the next consecutive merged thread position NFT and produce a UTXO that contains the action and the just-minted merged thread position NFT.
    (Do not include the corresponding user thread position NFT for the action in this UTXO)
  8. Gather the user thread position NFTs (if any) from the old consumed merged thread tip UTXO, and the user thread position NFTs from the actions with the earliest time. Among these, keep only the largest position NFT per user thread, and burn the others.
  9. Produce the next merged thread tip UTXO. Mint the next consecutive merged thread position NFT and place it in the new merged thread tip UTXO. Include the user thread position NFTs from the previous step in the new merged thread tip UTXO.
Figure 5

Figure 5 shows the first three transactions in the merge process for the three threads shown in Figure 3. As in previous figures, the arabic numbers indicate action times and the roman numerals indicate position NFTs. Since we are merging actions from multiple user threads, we have prefixed the action times and user thread position NFTs with a corresponding thread identifier for each thread in Figure 3: “A” for the purple thread, “B” for the green thread, “C” for the gold thread. Unprefixed roman numerals correspond to merged thread position NFTs.

In Figure 5, the merged thread tip UTXOs going into and out of each Merge transaction have a white background and black border. The merged thread UTXO outputs have a black border and are colored according to the user thread from which their respective actions originated. The colored UTXO outputs without a black border correspond to the action UTXOs that have been propagated through the Merge transaction untouched. The colored UTXO inputs correspond to the actions consumed from user threads by the Merge transaction.

Note the three actions (C–2, A–2, B–2) that were added to the merged thread by the second Merge transaction in Figure 5. This is just one of the six permutations that the second Merge transaction could have chosen for these three simultaneous actions, as shown in Figure 6.

Figure 6

As a result of the merge process in Figure 5, the first six actions in the merged thread are shown in Figure 7.

Figure 7

Divide time into cycles

Astute readers may have noticed that the user always needs exclusive access to her latest thread tip UTXO, so that she can continue to add actions to her thread without interference from others. On the other hand, the merge process always needs access to the earliest not-yet-merged action for each thread.

What happens when the merge process catches up to a user thread’s tip, having already merged all the actions for that user thread? The merge process needs to access the user’s thread tip to continue merging the other threads, but the user needs to access the tip to continue adding actions.

Our solution is to divide time into cycles—periods of time of equal duration. Each thread (including the merged thread) has a separate tip in each cycle, and uses that tip to add actions within that cycle. Users always add actions to their threads in the currently active cycle, whereas the merge process can only access those actions when the cycle elapses.

Simultaneity on the blockchain

What does it mean for two user actions to be “simultaneous”? Ideally, given that the blockchain is a “chain of blocks of transactions,” we could consider two actions to have the same time if they were added to the chain in the same block. We can’t do better than this, because the state of the blockchain only evolves when a new block is added to it.

Unfortunately, this ideal resolution of time is not currently achievable with Cardano’s on-chain validation and minting scripts, because scripts cannot currently see the slot numbers / timestamps that their inputs were created in. This information should be available—after all, the blockchain is fundamentally an immutable ledger of information attested to by parties at particular points in time. We will collaborate with the Cardano core developers to bring this feature to Plutus.

In the meantime, we and all other dApp developers on Cardano must rely on a coarser resolution of time in our on-chain scripts. When a transaction is submitted to be included in the blockchain, the submitter may indicate a validity time-interval during which the transaction may be added to the blockchain; it may not be added to the blockchain outside that interval.

On-chain minting and validation scripts can access this validity time-interval as part of the transaction context during script execution, which allows us to note the validity time-interval in a minted NFT or UTXO datum. This can be used as a coarse proxy for the slot number / timestamp at which the transaction’s outputs were created. The precision of this proxy can be controlled via validation scripts that impose conditions on the duration of the transaction’s validity time-interval, but a shorter interval duration reduces the chance that the transaction will be picked up from the mempool to be added to a block. We are calibrating the best duration for this proxy, and it will be configurable by the community after launch.

The streaming merge algorithm guarantees that user actions in the merged thread will be sorted by action time, to the extent that the on-chain scripts used by the algorithm can distinguish time.

Conclusion

At Cardax, we care deeply about creating a fair, predictable, and efficient DeFi ecosystem on Cardano. In furtherance of this goal, we have developed a general algorithm to tackle concurrency on Cardano in a modular way. This “streaming merge” algorithm provides exclusive threads to users under which they can submit their actions, and then merges the actions, sorting by time and breaking ties fairly.

In this article, we provide a fairly in-depth walkthrough of the core of the algorithm. We have simplified the exposition a bit by omitting some finer implementation details and edge cases. Future articles in this series will walk you through two major parts of the design that we have not yet described here:

We appreciate the support and collaboration of our community on our journey to build the Cardax DEX. Stay tuned! :slight_smile:

Comments 0
There are currently no comments.