NFT Wallets Unleashed: A Data Structures and Application Design Journey

Introduction

Whether or not you're caught up in the NFT hype, as a software engineer, staying abreast of recent innovations is crucial. It's always fascinating to delve into the technologies underpinning such trendy features. Typically, I prefer to let the dust settle before jumping in, but now seems like a good time to explore "what NFTs are all about."

Terminology

NFT stands for Non-fungible tokens. Non-fungible tokens are tokens based on a blockchain that represent ownership of a digital asset. Digital asset may be anything, from a hand-crafted image, a song, a music, a blog post or entire digital book, or even a single tweet (which is, basically, a publicly available record from a database of the well-known public company). These assets have public value and can be owned by someone.

Unlike fungible tokens, such as Bitcoins or Etheriums, which are replaceable with identical units (they have the same value and one can be exchanged for another), NFTs are unique (cannot be equally exchanged), ensuring the ownership of unique digital assets and enforcing digital copyright and trademark laws. NFTs are based on blockchain technology, guaranteeing ownership and facilitating ownership transfer.

What We Build

We're creating an NFT Wallet prototype using a C# console app with (not that famous yet) .NET CLI SDK. The System.CommandLine library, although still in beta, is promising and enables the creation of clean and efficient command-line interfaces.

The minimal requirements for NFT Wallets are as follows:

1. Keep the records of tokens' ownership history.
2. Support Mint transactions (creating tokens)
3. Support Burn transactions (destroying tokens)
4. Support Transfer transactions (changing ownership)

We assume transactions are in JSON format, but for educational purposes, we'll read them from a formatted JSON (text or file on disk) since we lack a real blockchain network server.

Keep It Simple

To keep things simple, we'll ignore details like specific blockchain networks, hash-generation algorithms for unique NFTs, and the persistent storage choice (in our prototype, we will use an XML file on disk).

API

Considering the mentioned requirements and limits, we'll support the following commands:

Read Inline (--read-inline <json>)

Reads a single JSON element or an array of JSON elements representing transactions as an argument.

$> program --read-inline '{"Type": "Burn", "TokenId": "0x..."}' 
$> program --read-inline '[{"Type": "Mint", "TokenId": "0x...", "Address": "0x..."}, 
                           {"Type": "Burn", "TokenId": "0x..."}]'

Read File (--read-file <file>)

Reads a single JSON element or an array of JSON elements representing transactions from the specified file location.

$> program --read-file transactions.json

NFT Ownership (--nft <id>)

Returns ownership information for the NFT with the given ID.

$> program --nft 0x...

Wallet Ownership (--wallet <address>)

Lists all NFTs currently owned by the wallet with the given address.

$> program --wallet 0x...

Reset (--reset)

Deletes all data previously processed by the program.

$> program --reset

NFTs Transactions

As it was mentioned above, we have to support the following transactions.

Mint

{ 
  "Type": "Mint", 
  "TokenId": string, 
  "Address": string 
}

A mint transaction creates a new token in the wallet with the provided address.

Burn

{ 
  "Type": "Burn", 
  "TokenId": string 
}

A burn transaction destroys the token with the given id.

Transfer

{ 
  "Type": "Transfer", 
  "TokenId": string, 
  "From": string, 
  "To": string 
}

A transfer transaction changes ownership of a token by removing the “from” wallet address, and adds it to the “to” wallet address.

Transactions Operations

In the following example of a batch of transactions, we create three new tokens, destroy one and transfer ownership for another one:

[
	{
		"Type": "Mint",
		"TokenId": "0xA000000000000000000000000000000000000000",
		"Address": "0x1000000000000000000000000000000000000000"
	},
	{
		"Type": "Mint",
		"TokenId": "0xB000000000000000000000000000000000000000",
		"Address": "0x2000000000000000000000000000000000000000"
	},
	{
		"Type": "Mint",
		"TokenId": "0xC000000000000000000000000000000000000000",
		"Address": "0x3000000000000000000000000000000000000000"
	},
	{
		"Type": "Burn",
		"TokenId": "0xA000000000000000000000000000000000000000"
	},
	{
		"Type": "Transfer",
		"TokenId": "0xB000000000000000000000000000000000000000",
		"From": "0x2000000000000000000000000000000000000000",
		"To": "0x3000000000000000000000000000000000000000"
	}
]

As seen, tokens are identified by imaginary hex-formatted values. Wallet addresses should be supported by our underlying imaginary blockchain network. Verification of these values is skipped, focusing on the efficiency of operations and storage in our NFTs wallet.

Data Structure Design

To support all necessary operations, we have to think about efficient execution of a following three types of tasks:

• Persist information about ownership relationship between imaginary NFT token ids and NFT wallet addresses provided.
• Quickly answer what wallet contains a token, by token id.
• Quickly answer what tokens are owned by certain wallet.
• Efficiently change the ownership of the Token between the wallet addresses.

We begin by creating a class to represent a single transaction.

public class Transaction
{
    // Transaction type: Mint, Burn, Transfer, etc. 
    // As a type, we may use enum here as well.
	[JsonProperty("Type", Required = Required.Always)]
	public string Type { get; set; }

	[JsonProperty("TokenId", Required = Required.Always)]
	public string TokenId { get; set; }

    // Address of the Wallet to own Token Id created (Minted)
	[JsonProperty("Address", Required = Required.Default)]
	public string Address { get; set; }

    // From Address of the Transfer operation.
	[JsonProperty("From", Required = Required.Default)]
	public string From { get; set; }

    // To Address of the Transfer operation.
	[JsonProperty("To", Required = Required.Default)]
	public string To { get; set; }
}

In the world of NFTs, the owner is represented by a wallet address, and we add a timestamp to track when a new token is created or transferred between wallets.

public class OwnershipInfo
{
	[XmlElement("WalletAddress")]
	public string WalletAddress { get; set; }

	[XmlElement("Timestamp")]
	public DateTime Timestamp {  get; set; }
}

Most efficient algorithms should be executed with O(1), right? Hash-based collections allow us to support GET operations with O(1) efficiency, which means we have to use Dictionary< K, V > for the whole storage. But to make all operations efficient, we have to sacrifice memory as it's not enough to have only one efficient collection. Instead, we are going to use multiple collections in memory. Let's look at it piece by piece, first, and then discuss this solution.

> Remember, in the following code, we don't verify tokens ids or wallet addresses.

Which Wallet Owns the Token?

Since a token can be owned by only one wallet, a direct address-to-address map between Token ID (key) and Wallet Address (value) is used. This allows us to easily support the "--nft" operation, answering the question of who the owner is.

public class TokenStorage
{
	// To easily find owning wallet by NFT token.
	public Dictionary<string, string=""> NftTokenWalletMap { get; set; }
}

public async Task<string> FindWalletOwnerAsync(string tokenId)
{
	if (_tokenStorage.NftTokenWalletMap.ContainsKey(tokenId))
	{
		return await Task<string>.FromResult(_tokenStorage.NftTokenWalletMap[tokenId]);
	}

	return null;
}

Which Tokens Wallet Owns?

To efficiently list tokens owned by a wallet, a map of Wallet Addresses (key) to lists of their Token IDs (value) is maintained, so we can easily support "--wallet" operation.

public class TokenStorage
{
	// To easily find list of owned Tokens in the wallet.
	public Dictionary<string, list="">> WalletNftTokensMap { get; set; }
}

public async Task<list<string>> GetTokensAsync(string walletId)
{
	var result = new List<string>();

	if (_tokenStorage.WalletNftTokensMap.ContainsKey(walletId) &&
		_tokenStorage.WalletNftTokensMap[walletId] != null)
	{
		result = _tokenStorage.WalletNftTokensMap[walletId];

		result.Sort();
	}

	return await Task.FromResult(result);
}

Ownership Transfer and History

To efficiently support the history of ownership changes for each token, we need to map Token Id (key) to a list of Owners Wallet Addresses (values). This list must be sorted in a way that we can efficiently take the last one (but still, be able to list all the history, when needed). We also want to efficiently insert new history records (to the end). Linked List is what suits well for this history-record data structure: it allows us to insert new records and take the last one with O(1) efficiency.

public class TokenStorage
{
	// To easily change the ownership.
	public Dictionary<string, nfttoken=""> NftTokenOwnershipMap { get; set; }
}

public class NFTToken
{
	public string TokenId { get; set; }

	/// <summary>
	/// Allows to efficiently insert new owners.
	/// </summary>
	public LinkedList<ownershipinfo> OwnershipInfo { get; set; }
}

With these structures, we can efficiently support minting, burning, and transferring operations on NFTs in TransactionManager. Follow the comments in code.

Mint New Token

private bool MintNFTToken(string tokenId, string walletAddress)
{
	// Is token really new/unique?
	if (!_tokenStorage.NftTokenWalletMap.ContainsKey(tokenId))
	{
		// Do we know such wallet address?
		if (!_tokenStorage.WalletNftTokensMap.ContainsKey(walletAddress))
		{
			// Remember a new wallet address.
			_tokenStorage.WalletNftTokensMap.Add(walletAddress, new List<string>());
		}
		
		// Add token to the wallet to Wallet-Token records.
		_tokenStorage.WalletNftTokensMap[walletAddress].Add(tokenId);
		
		// Add Token-Wallet record.
		_tokenStorage.NftTokenWalletMap.Add(tokenId, walletAddress);

		// Create an Ownership entry in history
		var nftToken = new NFTToken
		{
			TokenId = tokenId,
			OwnershipInfo = new LinkedList<ownershipinfo>()
		};

		// Insert the record
		nftToken.OwnershipInfo.AddFirst(
			new OwnershipInfo
			{
				WalletAddress = walletAddress,
				Timestamp = DateTime.Now
			});
		_tokenStorage.NftTokenOwnershipMap.Add(tokenId, nftToken);

		return true;
	}

	return false;
}

Burn Token

private void BurnNFTToken(string tokenId)
{
	if (_tokenStorage.NftTokenWalletMap.ContainsKey(tokenId))
	{
		string walletId = _tokenStorage.NftTokenWalletMap[tokenId];

		_tokenStorage.NftTokenWalletMap.Remove(tokenId);

		if (_tokenStorage.WalletNftTokensMap.ContainsKey(walletId))
		{
			_tokenStorage.WalletNftTokensMap.Remove(walletId);
		}
	}

	if (_tokenStorage.NftTokenOwnershipMap.ContainsKey(tokenId))
	{
		_tokenStorage.NftTokenOwnershipMap.Remove(tokenId);
	}
}

Transfer Token

private bool ChangeOwnership(string tokenId, string oldWalletAddress, 
                             string newWalletAddress)
{
	// Validate that token is actually owned by From
	if (_tokenStorage.NftTokenWalletMap.ContainsKey(tokenId) &&
		_tokenStorage.NftTokenWalletMap[tokenId].Equals(oldWalletAddress))
	{
		// Remove existing Wallet-Token record, it's not valid anymore.
		_tokenStorage.WalletNftTokensMap[oldWalletAddress].Remove(tokenId);
		// Add a new one.
		if (!_tokenStorage.WalletNftTokensMap.ContainsKey(newWalletAddress))
		{
			_tokenStorage.WalletNftTokensMap.Add(newWalletAddress, new List<string>());
		}
		_tokenStorage.WalletNftTokensMap[newWalletAddress].Add(tokenId);

		// Update a second map that maps back Token to Wallet.
		_tokenStorage.NftTokenWalletMap[tokenId] = newWalletAddress;

		// Now, create a new ownership history record.
		NFTToken nftToken = _tokenStorage.NftTokenOwnershipMap[tokenId];
		nftToken.OwnershipInfo.AddFirst(
			new OwnershipInfo
			{
				WalletAddress = newWalletAddress,
				Timestamp = DateTime.Now
			});

		return true;
	}

	return false;
}

Finally, our token storage data structures will look like this and will support all the necessary operations with O(1) efficiency with additional memory redundancy.

public class TokenStorage
{
	public TokenStorage()
	{
		NftTokenWalletMap = new Dictionary<string, string="">();
		WalletNftTokensMap = new Dictionary<string, list="">>();
		NftTokenOwnershipMap = new Dictionary<string, nfttoken="">();
	}

	// To easily find owning wallet by NFT token.
	public Dictionary<string, string=""> NftTokenWalletMap { get; set; }

	// To easily find list of owned Tokens in the wallet.
	public Dictionary<string, list="">> WalletNftTokensMap { get; set; }

	// To easily change the ownership.
	public Dictionary<string, nfttoken=""> NftTokenOwnershipMap { get; set; }
}

public class NFTToken
{
	public string TokenId { get; set; }

	/// <summary>
	/// Allows to efficiently insert new owners.
	/// </summary>
	public LinkedList<ownershipinfo> OwnershipInfo { get; set; }
}

Application Design

Following an Object-Oriented Programming (OOP) design, we create a number of entities:

1. All the transactions supported by a TransactionManager.
2. Every CLI command inherited from a base Command with business logic implemented in appropriate CommandHandlers.
3. ConsoleOutputHandlers play the role of a View Interface (similar to MVC concept) to print to the Console, which lets us potentially send outputs of the application to the Display, Network, Web, etc.
4. We do use a NewtonsoftJson library to parse incoming requests as well as a System.Xml to work with our persisting XML-storage file.

All of this allows us to implement a set of unit tests that you also can find in the repository.

Now, thanks to System.CommandLine library, it's easy to wire-up all the commands into a little application as follows:

class Program
{
    static async Task<int> Main(string[] args)
    {
        var root = new RootCommand();
        root.Description = "Wallet CLI app to work with NFT tokens.";

        root.AddCommand(new ReadFileCommand());
        root.AddCommand(new ReadInlineCommand());
        root.AddCommand(new WalletCommand());
        root.AddCommand(new ResetCommand());
        root.AddCommand(new NftCommand());

        root.Handler = CommandHandler.Create(() => root.Invoke(args));

        return await new CommandLineBuilder(root)
           .UseHost(_ => Host.CreateDefaultBuilder(args), builder => builder
                .ConfigureServices(RegisterServices)
                .UseCommandHandler<readfilecommand, readfilecommandhandler="">()
                .UseCommandHandler<readinlinecommand, readinlinecommandhandler="">()
                .UseCommandHandler<walletcommand, walletcommandhandler="">()
                .UseCommandHandler<resetcommand, resetcommandhandler="">()
                .UseCommandHandler<nftcommand, nftcommandhandler="">())
           .UseDefaults()
           .Build()
           .InvokeAsync(args);
    }

    private static void RegisterServices(IServiceCollection services)
    {
        services.AddHttpClient();
        services.AddSingleton<ifilesystem, xmlfilesystem="">();
        services.AddSingleton<itransactionsmanager, transactionsmanager="">();
        services.AddSingleton<iconsoleoutputhandlers, consoleoutputhandlers="">();
    }
}

Run Your Wallet

Now, we can run our little CLI. It contains a nice little help listing the commands (thanks to System.CommandLine library):

>nft.app.exe -h
Description:
  Wallet CLI app to work with NFT tokens.

Usage:
  Nft.App [command] [options]

Options:
  --version       Show version information
  -?, -h, --help  Show help and usage information

Commands:
  --read-file <filePath>  Reads transactions from the ?le in the speci?ed location.
  --read-inline <json>    Reads either a single json element, or an array of 
                          json elements representing transactions as an argument.
  --wallet <Address>      Lists all NFTs currently owned by the wallet of 
                          the given address.
  --reset                 Deletes all data previously processed by the program.
  --nft <tokenId>         Returns ownership information for the nft with the given id.

If we read all the transactions from JSON file, then we can find XML wallet storage "WalletDb.xml" after execution is finished.

>Nft.App --read-file transactions.json

Now, let's execute the following transactions one by one:

>Nft.App --read-file transactions.json 
Read 5 transaction(s) 

>Nft.App --nft 0xA000000000000000000000000000000000000000
Token 0xA000000000000000000000000000000000000000 is not owned by any wallet 

>Nft.App --nft 0xB000000000000000000000000000000000000000
Token 0xA000000000000000000000000000000000000000 is owned by 0x3000000000000000000000000000000000000000 

>Nft.App --nft 0xC000000000000000000000000000000000000000
Token 0xC000000000000000000000000000000000000000 is owned by 0x3000000000000000000000000000000000000000 

>Nft.App --nft 0xD000000000000000000000000000000000000000
Token 0xA000000000000000000000000000000000000000 is not owned by any wallet 

>Nft.App --read-inline  "{ \"Type\": \"Mint\", \"TokenId\": \"0xD000000000000000000000000000000000000000\", \"Address\": \"0x1000000000000000000000000000000000000000\" }"
Read 1 transaction(s) 

>Nft.App --nft 0xD000000000000000000000000000000000000000
Token 0xA000000000000000000000000000000000000000 is owned by 0x1000000000000000000000000000000000000000 

>Nft.App --wallet 0x3000000000000000000000000000000000000000
Wallet 0x3000000000000000000000000000000000000000 holds 2 Tokens: 
0xB000000000000000000000000000000000000000 
0xC000000000000000000000000000000000000000 

>Nft.App -—reset 
Program was reset 

>Nft.App --wallet 0x3000000000000000000000000000000000000000
Wallet 0x3000000000000000000000000000000000000000 holds no Tokens 

Outcomes

As we can see, we were able to implement all operations with O(1) efficiency. Unfortunately, it involves trade-offs in memory usage. In production scenarios, considerations for large datasets that may not fit into a single machine's RAM might lead to compromises. Depending on requirements, sacrificing efficiency for optimized memory usage or vice versa may be necessary.

While this example demonstrates a compromise for a standalone system, in a production environment, third-party software supporting scalable mappings with redundancy might be preferred. This introduces additional complexity but is crucial for operational efficiency in distributed systems.

This exploration provides insights into the world of NFTs and the data structures supporting their operations. I hope it was interesting and useful for you.

Stay tuned for more!

History

• 29^th January, 2024: Initial version