Technical deep dive into auction contracts

Plutus Pioneer Program

A fundamental challenge of working with Cardano’s eUTxO model is utxo (unspent transaction output) contention. Put simply, only one transaction can use a given piece of data per block. The issue of utxo contention first really became known to the development community in late 2021, with the first cohort of the Plutus pioneer program. The idea for the Grabbit protocol was conceived as a part of this program, and planning started only months later in early 2022.

English Auction

One of the protocols referred to multiple times in the program is the English Auction protocol. This very basic auction protocol is heavily affected by the problem of contention.

Explanation

The basic idea of an English auction is simple. An auction lot is presented by the seller, with a starting bid that can be raised by any participant in the auction to whatever amount they are willing to pay for the lot.

The protocol presented in the pioneer program emulated this in the most obvious, direct way. To start an auction the seller places the lot in a utxo, which includes a datum showing the current bid. To bid, a bidder consumes the utxo, updating it to represent the bid they’re willing to pay. This repeats, with the amount bid increasing each time:

At the end of the auction, the seller consumes the utxo again, sending the lot to the bidder and taking the bid.

The Problem

The limits of contention become immediately apparent when attempting to bid in this auction. If two or more people attempt to bid on the same auction at the same time, they both try to consume the same utxo at the same time, creating the contention problem. In this case, only one bidder will get to bid. This is nondeterministic, meaning the one who gets chosen will be random, unless manipulated by the minting pool. The other bidder’s transaction will fail because of contention. Their funds and fees will remain in their wallet, and they can try again, but they may have missed a crucial bidding window, or even miss that their bid never went through. From a seller’s perspective, This means the more popular the auction, the harder it is to interact with. Clearly, this is a problem for all parties involved.

However, the value of decentralized auctions on chain cannot be denied. Auctions allow for price discovery for the lot, ensuring that the seller and buyer get a fairer price. Sellers can be less concerned about underestimating the value of their NFTs, and buyers less likely to overestimate. Many token launches include a price discovery event to ensure a fair price for their buyers. Auctions provide the same service, but at any time, for any token.

With this in our vision, we chose to push forward and find a better way to do auctions.

The Grabbit Protocol

Objectives

At the platform level, Grabbit isolated several key objectives early in the process:

• True Decentralization
• User Experience
• Creator Focus
• Easy Onboarding

These objectives are reflected at all levels of the platform, from the UI, to the contracts, to the business planning. As we went through the design process, we found more specific, technical keys to satisfying the platform objectives:

• Prevent Contention: contention creates many problems — user frustration, unpredictability, node interference, etc. We don’t want our users to have to deal with that.
• Ensure Fairness: neither bidder nor seller should be able to act in a way that causes significant or unexpected financial loss within the rules of the protocol.
• Enable Trustless Interaction: behavior should be deterministic and decentralized, so that no privileged third party can alter the outcome or procedure of the auction to benefit themselves or other parties.
• Prevent Permalocking: unstable contracts that lock assets can potentially result in a permanent loss of those assets. Contracts should always allow for unrestricted withdrawal unless doing so would violate the previous objectives.

Core Approach and Specification

State Threading

At its core, the Grabbit protocol’s solution is based on an existing solution to contention: State Threading. State threading works by creating separate utxos for each minimal piece of information (state) that needs to be tracked. These utxos can then be consumed and recreated individually without interfering with the rest of the state.

💡 If you’d like to read more about generic implementation of state threading for your app, check out this document in the Plutonomicon:

plutonomicon/statethread.md at main · Plutonomicon/plutonomicon

For our auctions we use state threading to create separate threads for each individual bidder. Each bidder can create a bid on an auction which includes the amount they’re bidding and some additional identifying information. These threads are tracked via unique non-fungible tokens which are placed within each utxo.

Imagine a bidding war between two bidders, with each increasing their bids multiple times. This is exactly the sort of activity you might expect to see in the last few minutes of an auction. In the English Auction example shown above, this sort of activity could easily result in contention, as each bidder vies to increase the one auction utxo. With state threading, the two bidders each have exclusive access to the utxo (shown in purple) containing their bid. Contention is no longer a possibility.

Finite Set

In order to successfully complete our auction, we need to be able to collect all the threads and verify the highest bid. This requires special care. If we rely on the offchain to collect the threads for us, a malicious actor could choose to exclude all the threads with a bid higher than their own to win the auction at whatever price they want. If we collect the threads offchain, we centralize that power, defeating the whole point of doing the auction on chain. The onchain protocol must have a way to keep track of all the state threads, so it can tell when any transaction is attempting to break the auction in this way.

To keep track of the threads, we created an implementation of a singly-linked list with each node in the list represented by a separate utxo. Each node includes an key identifying itself and reference to the next node.

To resolve an auction, a series of transactions are first submitted which collapse this list by comparing the bids corresponding to neighboring nodes. Eventually, this process results in a list with one node remaining — that of the highest bidder. To finalize the auction, this last node is consumed — sending the bid to the seller, and the lot to the bidder.

In order for this process to be secure, we rely on the finite set to adhere to several properties. Given the importance of the set to the functioning of the protocol, we had the finite set formally verified (mathematically proven) to be a linear ordered reducible set:

• Linear — the next field never references more than one node.
• Ordered — the next field always references the next smallest key, or Nothing.
• Reducible — a set of only one node can always be reached using the remove operation.
• Set — the key field can never be identical for two nodes.

As part of our plans to give back to the community we hope to open source the code for this in the future. If you’d like early access, reach out in our Discord to discuss.

An astute reader might realize that this list introduces new contention. Just like any singly linked list, new nodes can be entered into the list by only updating the preceding node to point to your new node, and making your node point to the following node. This means that we must consume one of the nodes in the list each time we add a node. As the list gets longer, the chance of contention gets lower, with more nodes to choose from for consumption when inserting. We take advantage of this to make contention vanishingly unlikely for insertion, which I’ll discuss further in the section on Separators. For regular bidding, however, we are able to fully prevent contention with finite set operations — layering.

Layering

If we were to build our state threads directly into the finite set, we would introduce additional contention with list insertions/removals, who would not only conflict with other nodes attempting to insert into/remove from the same spot in the list, but would also conflict with any bids the owner of the previous node might place. To prevent this problem we include a layer of separation between the finite set and the bid threads. Each thread not only includes the bid information, but a reference to its corresponding node.

These bid threads can still be updated as was shown above, so long as the reference persists. In order to remove a node from the set, one must consume both the set node and the bid referencing it. This ensures no orphans are left behind in either layer.

Using layering we significantly reduce the (already low) potential for contention in the course of an ordinary auction, but we will show how we reduced contention even further in future sections.

The Auction Lifecycle

The auction protocol is run by 4 scripts working in tandem, 2 minting policies and 2 validators. These correspond directly with the two layers outlined above: each layer has it’s own minting policy and validator.

For the finite set, the FinSetMP takes care of minting & burning the identifying tokens for each node, while the SetNodeValidator gives permissions over the modification & removal of existing nodes.

For the state layer, the StateTokenMP handles creation of the bid threads identifying tokens, as well as a couple less frequently used tokens. The AuctionValidator handles the logic of updating bids, canceling auctions, resolving auctions, and more.

Each minting policy is parameterized to be specific to the auction, allowing all relevant outputs to each layer of a particular auction to be found with a quick search over policy ID.

Creating an Auction

When creating an auction there are two key outputs that must be created:

1. The Auction Escrow — this includes the lot, a unique identifying token, and a datum with auction configuration such as starting price, buy now price, start & end times and more.
2. The Origin Node — the first node in a finite set, its key and next fields are both Nothing, representing an empty set.

The parallel layers should be clear here. Seller’s create the start of the auction both in the finset layer and the state layer, with unique identifying tokens created by the corresponding minting policies, sent in outputs to the corresponding validators.

Because we don’t need the validators to release any utxos when creating a new auction, both validators can be left out of the transaction. Only their script addresses are needed.

💡 Each of these outputs (and most outputs we specify in the protocol) also include some multiple of minAda. These are deposits, a small amount of Ada dedicated to ensure the auctions run smoothly. These deposits do several things to help make the protocol smoother, safer & faster to use.

1. Anti-locking protection in case a user runs out of funds to submit transactions. Actions such as withdrawing a bid or an auction will never cost Ada.
2. De-incentivizing bad actors. Without a minimum Ada requirement the finite set may be vulnerable to contention-based denial of service attacks. With minAda, such attacks become prohibitively expensive very fast.
3. Incentivizing good actors. A portion of the deposits placed in the auction are free to be taken by whoever constructs the resolve transactions. This encourages decentralization of background processes by more technical members of the space, while still offering the smooth user experience of NFTs won in an auction being delivered automatically.
4. The surplus funds can act as a buffer to prevent any imbalance in funds that might appear as a result of transaction fees, which could cause problems for validation.

Interacting with your Bid

The first step of bidding on an auction is getting your node into the finite set and creating your bid thread. This is also by far the most complex step. The contracts need to confirm that you’re inserting a correct node into the correct place in the set, minting the correct identification tokens, and have started a bid thread correctly.

Thanks to layering, once your finset node is in place, bidding is beautifully simple:

Finally, if you’ve been outbid and want to reclaim the money you’ve committed, you can refund your bid. This effectively works as the reverse of the enroll transaction. You remove your node from the finite set by consuming the utxo, burning the identifying token, and changing the previous node to point to the next one. Finally you consume your bid utxo, keeping the funds you left in there for yourself.

To prevent abuse by last minute bid withdrawals, the refund transaction requires a reference input from a bid higher than the bid being withdrawn. The highest bidder is not allowed to withdraw.

Resolving an Auction

Resolving an auction happens in two parts. The first part is collapsing the list by removing bids that are not the winning bid. Once an auction has passed the deadline, we allow anyone to resolve the auction. This is to incentivize a decentralized approach to auction resolution that is neither user dependent, or Grabbit dependent.

To remove a bid, two references are needed:

1. The auction escrow must be referenced to prove that the auction has ended (unless the transaction is submitted by the bidder).
2. A bid higher than the one being refunded must be referenced to prove that this bid is not winning the auction.

This can be done simultaneously within a block for up to N/2 nodes at a time, resulting in a list collapse of O(logN) complexity.

This approach also allows for a smoother user experience. Once you have created your auction or submitted your bids, you do not need to be involved further at all. Whether you win or lose, sell or auction ends with no bids, the auction resolvers will automatically send the appropriate tokens to your wallet when the auction ends.

Since there’s no way to refund the winning bid, once the bids have been collapsed to the point where there’s a single node left, we know this bid has won. Now we get to finalize the auction by triggering the resolve endpoint.

The resolve endpoint consumes the finite set head & winning node, the auction escrow, and the winning bid. It redistributes the auction lot to the winner, the royalties to the beneficiaries, the fees to the market, and finally the winnings to the seller. All state and finest tokens are burned, officially signifying the end of the auction.

Extra Features

These features are not core to the protocol, but provide ways to improve the user experience. Given the length of this article, these are discussed in brief only. Future articles may go more in depth into these features. At the moment, only Buy Now has been implemented on Grabbit.Market, but we expect to support all three in the near future.

Buy Now

Sellers have the option to set a price at which any buyer may immediately end the auction and receive the lot. The auction escrow remains without the lot, instead with a token which indicates that the auction was bought. Any bidders who had entered the auction before the buy now endpoint was triggered can be refunded with a reference to this token.

When auction resolution rolls around, rather than being distributed to the winner, the token is burned.

Separators

Separators help ameliorate the contention found when inserting nodes into the finite set. At any time the seller has the option of inserting bid-less nodes into the set at arbitrary points. These points are postfixed to prevent conflict with existing bidders’ nodes, but can still be used as nodes for insertion & removal from the list.

While this solution doesn’t entirely remove the problem, when enough are used for the amount of traffic an auction sees, it effectively eliminates contention in an auction altogether.

As an added bonus, these separators can be added & removed in bulk, greatly reducing the cost in gas fees that would ordinarily be needed for this solution.

Extensions

The seller also has the option to allow for auction extensions, whereby a bidder who has lost the auction at the last minute can submit a transaction to continue the auction for awhile longer. While the Cardano L1 is reasonably quick, it’s not yet quite on par with the speed sometimes wanted for last minute bidding, and occasionally bids placed last minute will miss the deadline. We have plans for solving this altogether, such as with the Hydra-Auction implementation, but for now extensions allow us to ensure bidders get a fair experience, while sellers also benefit by allowing the auction price to rise higher than it otherwise would have.

Extensions may be submitted by referencing a bid higher than the bidder’s that was placed within a critical bidding period at the end of the auction. The period refreshes for each extension, and multiple extensions in succession are allowed; however, if at any time the seller feels like the auction has extended for too long, he may submit a transaction to deny further extension, ending the auction at the current deadline regardless of whether recent bids have been made.

The Future of Grabbit

Private Auctions

We have already created, tested and audited a version of the protocol which allows sellers to whitelist bidders into their auctions. This has many use cases, such as allowing collections to do new auctions for collection holders only, auctions with entry fees, or luxury auction houses running auctions for known buyers or members. Any arbitrary criteria may be used to guard entry.

This works by letting prospective bidders register interest in the auction by submitting a transaction to create a registration escrow, which the seller can then consume at his discretion to enroll the bidder in the auction. From this point the bidder can interact with the auction in the exact same was as he would with the public auction.

This approach actually eliminates the problem of contention on enrollment. Registration escrows are not dependent on any other utxo, and since only the seller can enroll bidders into the auction, there’s no risk of contention from another party when inserting a node into the finite set.

Gated Auctions

Similar to private auctions, gated auctions would allow the seller to only allow certain prospective bidders to enter the auction. However, instead of manually selecting which bidders may enter, they instead define the criteria for entering the auction when creating it. This criteria would usually be something like must hold tokens of policyId deadbeef.

Anyone whose wallet fits this criteria is able to enroll in the auction without further input from the seller, and bid normally, but anyone whose wallet does not fit the criteria will be prevented from entering.

Hydra-Auction

We are thrilled to be collaborating with MLabs on Hydra-Auction. This is a protocol that was originally designed by MLabs for IO as a demonstration of a use case of Hydra. Thanks to Catalyst Fund 10, we have been funded to work together with MLabs on building this protocol into an open source SDK.

For our part, we hope to be able to use this protocol & SDK on Grabbit in the future. With Hydra’s lightning-fast finality, contention will be all but eliminated. We can’t wait to take you all with us as we build Grabbit into the product Hydra has promised for so long.

Open source

To be truly decentralized, a protocol must be able to stand on its own, even if its creators disappear. A key part of that is open sourcing the protocol to allow other developers to interact with it. Our product is not the protocol, but the ways we enable its use. There a several key releases we have in mind, however, we hope the community understands the short delay of open source for both stability testing and our many hours and investment of building the protocol.

• Specification & Documentation — while this article already gives a very in-depth overview, we intend to publish more technical articles like this one, as well as some internal documentation of the code.
• Generalized Finite Set — the finite set is an onchain structure which many protocols will find useful. By open sourcing the generalized version of this we hope to help Cardano developers build more secure protocols with our audited and formally verified code. The code is written in Plutarch v1.2, providing extremely low level control to developers.
• Onchain Contracts — the Grabbit protocol is one of the largest and most complex protocols on Cardano. By open sourcing the contracts we hope to not only give additional confidence to users in the security of the contracts, but also assist developers in learning how to build large-scale dapps on Cardano. These contracts amount to roughly 4200 lines of professional grade Plutarch (v1.2) code.
• Offchain Library — anyone can interact with the onchain contracts if they’re able to understand and construct the transactions needed. However, that sort of action is available only to elite developers in the ecosystem. By publishing our offchain library we hope to make interacting with and building for the protocol accessible to any developers, regardless of experience. This code is written in Typescript with Lucid, a well known & easy to use library.
• Resolution Service Toolkit — in order to decentralize the protocol further and ensure reliability, we intend to release a toolkit to assist community members in creating their own service to construct & submit refund & resolution transactions once an auction ends. Since these transactions are incentivized, such a service will bring in funds (assuming it’s fast enough to be competitive). We expect this service to be attractive to community members with experience running services for income, such as SPOs.

Getting Involved

Want to take part in Grabbit? Here’s some ways you can get involved.

• Try it out! We’re live on Mainnet at grabbit.market. If you’d rather try things on Testnet, we still have our site live on the Preprod Testnet at beta.grabbit.market.
• Follow us on Social Media!
• Twitter
• Discord
• Partner with us! We’re always looking for different members of the ecosystem who would like to work with us. If you have an idea for how we might work together, or just want to do a brainstorming session we’d be happy to chat! Here’s some examples of partnerships we’ve done/are working on:
• Collections
• Influencers
• Charities
• Lending Protocols
• Resolution Services
• We will need people to help keep the resolution of auctions decentralized & fast. If you’d like to think about running a resolution service keep an eye out for the toolkit!
• Decentralization of Ownership
• We are looking into decentralizing the ownership of Grabbit. This should be bigger than just Ikigai. If you’re interested in becoming a part-owner of Grabbit, please let us know.