Introduction

NFTs have thus far been valued mostly for their aesthetics. “We like the art”. Certainly original artworks, generative collections, photography and other forms of purely visual art will remain a core usecase of NFTs far into the future. However, with the growth of the metaverse and blockchain-based gaming ecosystems like DeFi Kingdoms, Crabada, Axie Infinity and others, it is increasingly clear that in-game items are likely to become even more important. I believe that the most popular web3 native games of the future will leverage the creativity of their players by allowing them to combine their in-game items, represented as NFTs, in unique ways to gain advantages over other players. Why? Because the NFT gaming model largely turns pay-to-win monetization models on its head. The creator of the game, and the NFTs associated within it, have an opportunity to sell an NFT once, and only gain a royalty % of future sales. Users are able to choose between buying NFTs directly from the publisher or to buy them from other users. This inherently reduces the overall supply of buyers available to the publisher as well. One solution to this problem would be for the publisher to not only profit from a royalty cut of secondary sales, but also to use smart contracts to control the effects of combining individual NFTs into composite forms and take additional profit. In this article I describe a simple system I implemented in solidity that enables order-specific combinations of NFTs to be created (somewhat) efficiently. By creating an order-dependent, “NFT alchemy” becomes possible, where the output effects (not determined here, but left to be implemented on a usecase-by-usecase basis) are totally unique based upon inputs.

An Example Usecase

In first-person-shooter games, base weapons are often customizable with a variety of attachments. Add-on items, which can be unlocked via gameplay or bought using in-game currency, modify the statistics of the base weapon and give the player an edge in battle. A well-crafted system does not place these attachments on a linear scale from best to worst, but gives each item a balanced impact. This way, the player must utilize their own creativity in order to find the right combination of items that give them the desired result. How could one do this with a blockchain-based game? Certainly, the off-chain aspects of a game could handle the rule system of how items impact the underlying weapon (in this example). So all a user would have to do is own the NFTs and let the game client handle the rest. This, however, isn’t very interesting and lacks flexibility. What if a user wants to sell their loadout as a bundle? What if the publisher wants to collect royalties from these sales, or from the combination action itself? What if the sequence in which a user combines their NFTs needs to matter? To allow for this level of flexibility, as much as possible should be tracked on chain. The system I explain below attempts to bring the entire process of NFT combinatorics on-chain.

Describing the System

To do NFT combinatorics, we need two things: a vault that accepts NFTs as deposits and stores them internally, associating each with their rightful owner, and a data structure that is order-dependent that a user can modify with only the NFTs that they own within the vault. Each user should be able to create more than one of these structures, and all of them should be tracked within the vault contract. The game’s client would determine what the visual and gameplay outcomes of these combinations would be, but the combinations themselves would live on-chain. This allows for them to be both monetized, transferable and enforcable.

Part 1: The Vault

The vault is the simpler of the two parts of this system. A user selects NFTs that they want to deposit, then sends them to the vault. In return, the vault generates receipt tokens (here called ltokens ) that represent the user’s deposits for their own records. The vault associates each NFT with its rightful owner, but importantly, does so in an unordered manner. It also assigns a new, internal token id to each deposit that is unique to the vault and private. I define a struct to track the data of each deposited NFT as:

struct depositedNFT {
  address owner;
  address tokenContract;
  uint tokenId;
  uint internalTokenId;
}

where the internalTokenId is the unique, private value for the smart contract to make use of. Next, in a generic solidity mapping, mapping (address => uint) I track the number of deposits per user, and in another mapping (uint => depositedNFT) I track internal token id’s so they can be indexed. These are relatively unstructured data as we cannot index by address, but rather can only do so by tokenId. The reason for this is that I am attempting to follow the design pattern of a standard ERC-721 contract to the extent that it is possible, and also due to the relative limitations of solidity lists and mappings. For reference, here is how I handle making deposits to this vault:

function createDeposit(address _tokenContract, uint _tokenId) public returns (bool) {
    (bool success, bytes memory data) = _tokenContract.delegatecall(abi.encodeWithSignature("transferFrom(address, address, uint256)", msg.sender,a,_tokenId)); 
    require(success, "transfer failed");
    totalDeposits[msg.sender].add(1);
    uint next = _getNextId();
    currentDeposit = depositedNFT(msg.sender, _tokenContract, _tokenId, next);
    _mint(msg.sender,next); 
    _allDeposits[next] = currentDeposit;
    return true;  
  }

Basically what happens here is that the user, after approving the contract (done elsewhere), allows it delegate a transferfrom call to the NFT in question’s contract, which takes it to the custody of the vault. Then, it mints an lToken to the user and tracks the total number of deposits and the NFT’s metadata in a struct. Because this vault contract inherits from ERC721 we can use the _mint function to create the lTokens.

To enable support for ordering of these items and attributing collections (which are always unique) to their owners, I use the data structure that anyone who has taken some variation of a Computer Science 101 course has implemented: the Linked List.

Part 2: Ordering The Data

Why use a linked list, and not a regular solidity list? 1) because they’re more fun. 2) because linked lists make ordering matter. You can’t just index into a list, you have to traverse it. This has an important impact for a game: it implicitly enforces the client to process data in a particular way. That way, you require all players to abide by the same ‘rules of combination’. Another nice benefit is that writing to a linked list is always the same cost in terms of gas; in other words, a linked list can become infinitely long but traversing and writing to it are always the same cost. The downside, on the other hand, is that shuffling the list around can be expensive. But I assume for these use cases that one wouldn’t want to do that anyways.

A linked list is really three things: a pointer to the head of the list, the data store of all the list items and an int tracking the length of the list. To get an item out of the list, we traverse the list until the desired length has been reached and copy the item into local memory. I took inspiration from “Linked Lists in Solidity” published on Coinmonks by Austin Thomas Griffith, but updated the code for current versions of solidity and also to handle multiple lists within the same contract.

struct listItem {
    bytes32 next;
    uint internalTokenId;
  }

  // track a user's lists entries
  mapping (address => mapping (bytes32 => listItem)) public userItems;
  mapping (address => uint) public lengths;
  mapping (address => bytes32) public heads;

The three variables described above become three mappings so that each user may have their own list. To accommodate each user having multiple lists (which is the ultimate aim), a mapping of mappings would be needed for userItems. While NFT’s are stored loose in the vault as structs containing their contract address and token id, this is not information we want to store twice. So, this is where the _internalTokenId comes in. This allows us to connect the loose storage to the ordered storage without copying more data than is necessary, reducing overall cost. Adding to the linked list is relatively straightforward:

function addLinkedListEntry(uint _internalTokenId) public returns (bool) {
    require(isDepositOwner(_internalTokenId), "You don't own this NFT");
    listItem memory itm = listItem(heads[msg.sender],_internalTokenId);
    bytes32 id = keccak256(abi.encodePacked(itm.internalTokenId,block.timestamp,lengths[msg.sender]));
    userItems[msg.sender][id] = itm;
    heads[msg.sender] = id;
    lengths[msg.sender] = lengths[msg.sender].add(1);
  }

All that is needed to be done is to create a new list item, create a new hash that identifies it within the list and update the head to point to the correct location. No matter how many times a new item is written, the cost of writing an individual item does not go up. Additionally, by tracking only the head we are enforcing a particular order of traversal. In order to traverse the list the following functions are needed:

// get the token id associated with this entry
  function getEntry(bytes32 _id) public returns (bytes32, uint) {
    return (userItems[msg.sender][_id].next,userItems[msg.sender][_id].internalTokenId);
  }

  // get the tip of the list
  function getHead(address _sender) private returns (bytes32) {
    return heads[_sender];
  }

  // traverse the list
  function traverseUntil(uint _stop) public returns (uint) {
    require(_stop < lengths[msg.sender], "Stopping point beyond maximum length");
    bytes32 head = getHead(msg.sender);
    uint point = 0;
    //begin traversal
    uint internalId;
    while (point < _stop) {
      (head,internalId) = getEntry(head);
      point = point.add(1);
    }
    return internalId;
  }

getEntry resolves a hash to a pointer to the next item and its internalTokenId, which can be used to retrieve the actual NFT’s information. getHead simply returns the current head, while traverseUntil executes a while loop until the stopping point is reached. Here the assumption is made that list items are not to be popped from the list when they are traversed to, although this feature could also be accounted for. Now, we have a complete system that takes in NFTs as deposits, orders them in a list and then allows each list to be traversed.

Limitations

Deposited NFTs don’t yet have a withdraw function - withdraws would also require a re-ordering of the linked list, which is not something I have implemented yet.
Extensive use of structs could increase gas costs, although I attempted to keep overall cost as low as possible by reducing data redundancy.
The effects of the list ordering would need to be determined in part by a frontend (although frontends could not cheat in terms of the order itself, so would not gain an advantage in my estimation)
Depositing and linking occur in separate transactions, and the user will need to pay for both. A frontend would have to provide options to do both of these things. On the other hand, one could view this as convenient, as you could deposit at one point and link at another

Future Work

Improve the test suite
Build a frontend
Implement withdrawals, list re-ordering and connect each user’s head pointer to its corresponding NFT receipt (lToken). This would enable users to also directly transfer the NFT linked lists between one another as bundles
Allow for users to have multiple linked lists at a time. It appears that using a collection factory contracts would be the best way forward, in order to avoid the state of the original contract bloating too much. In this setup, rather than storing each linked list centrally, the user could use the factory contract to create their own repository of lists in a similar fashion to Uniswap factory contracts that manage liquidity pools. Then within each deployed contract a mapping of mappings would track each of the individual lists.
Publish the code (I will do this when I finish making tests)