Provable NFT Collections on Algorand

Context

NFTs are created using Algorand Standard Assets (ASAs), which are built into the protocol and created using a special type of transaction. This is distinct from some other blockchains where a smart contract is necessary to represent assets.

Source: https://developer.algorand.org/docs/get-started/tokenization/nft/

NFTs are often intended to be collections, but on Algorand there's nothing that intrinsically links one NFT to another.

Explorers and marketplaces have their own ways of assigning an NFT to a collection, usually based on the creator's address and the asset's unit name prefix.

But it would be nice to have a standard and decentralised way to do this.

There are two ARC proposals I'm aware of that move in this direction:

• ARC-40: Mutable Asset Set Schema & Validation

• ARC-53: Metadata Declarations

The concepts discussed in the blog post could potentially extend them with more efficient proofs.

Cardinality

One-to-many relationships are very common in the real world and something we frequently need to model in a database.

A customer has many orders. A library has many books.

And an NFT collection has many NFTs.

If you had to store a collection in a database without repeating values, you might be tempted to put all the information in one table using complex types:

Or to create a second table to store the NFTs, and have the 'NFTs' column in the Collections table just reference the IDs:

There are several problems with this approach, but two of the most pertinent are that it's not scalable, and it's difficult if not impossible to enforce referential integrity.

A better solution is usually to add a foreign key to the NFT table:

That way, it doesn't matter if a collection has one NFT or a million NFTs (assuming the database has enough space).

Each piece of information is defined once, and we can safely add as many rows as we need.

The same principles apply when we're thinking about NFT collection metadata.

If the collection metadata contains the asset IDs of each NFT, there's always going to be a limit on scalability.

So a better approach is probably to store the collection ID in each NFT's metadata.

But how do we prevent fraudulent assets and collections being minted?

Provability

Let's imagine that an NFT collection is recorded using a soulbound token.

If the collection token metadata contains the asset IDs of all of its NFTs, what's to stop someone minting a fraudulent one?

I could mint a collection token that points to the asset IDs of any assets I like, whether they really belong to that collection or not.

Yes, we could try to verify that the person who minted the collection token is also the creator of the assets. But what if the assets are minted from multiple accounts?

It's much simpler if the assets themselves point to the collection token ID.

Only the asset creator or manager would have the ability to change which collection an asset belongs to.

So that's half the problem solved.

But there's nothing to stop me minting a new NFT, and pointing its metadata to a collection it doesn't really belong to.

The collection itself needs a succinct commitment to its assets.

Merkle Trees

Merkle trees have two properties that fit the bill: we can commit to any number of assets using a single hash value, and we can quickly verify that an asset is part of a collection.

Adapting the approach we discussed previously, we could store:

Let's run through proof generation and verification quickly, using merkletreejs:

const { MerkleTree } = require("merkletreejs");
const CryptoJS = require("crypto-js");

const assetIds = [1, 2, 3];
const leaves = assetIds.map((x) => CryptoJS.SHA256(x.toString(16)));
const tree = new MerkleTree(leaves, CryptoJS.SHA256, { sortPairs: true });
const root = tree.getRoot().toString("hex");

We define a collection with 3 assets and get the merkle root:

0932f1d2e98219f7d7452801e2b64ebd9e5c005539db12d9b1ddabe7834d9044

This goes in the collection metadata.

Next, we generate an inclusion proof for each asset.

To prove asset 1 is in the collection, we run:

const leaf = CryptoJS.SHA256("1");
const proof = tree.getProof(leaf);
console.log(tree.getHexProof(leaf));

And put the resulting proof in the asset's metadata:

['0x6b86b273ff34fce19d6b804eff5a3f5747ada4eaa22f1d49c01e52ddb7875b4b', '0x4e07408562bedb8b60ce05c1decfe3ad16b72230967de01f640b7e4729b49fce']

We could also store the leaf (hash of the asset ID), but it can easily be derived again later.

To verify the proof for this asset:

>>> leaf = "d4735e3a265e16eee03f59718b9b5d03019c07d8b6c51f90da3a666eec13ab35"
>>> proof = [
...     "0x6b86b273ff34fce19d6b804eff5a3f5747ada4eaa22f1d49c01e52ddb7875b4b",
...     "0x4e07408562bedb8b60ce05c1decfe3ad16b72230967de01f640b7e4729b49fce"
... ]

>>> xtob = lambda x: bytes.fromhex(x.removeprefix("0x"))
>>> print(reduce(lambda i, j: sha256((j + i, i + j)[i < j]).digest(), map(xtob, proof), xtob(leaf)).hex())
0932f1d2e98219f7d7452801e2b64ebd9e5c005539db12d9b1ddabe7834d9044

If the result is equal to the collection's merkle root, then the proof is valid.

The length of the proof array is log2(n), where n is the number of leaves (assets in the collection).

So it scales pretty well:

>>> import math

>>> n_leaves = (3, 10, 10_000, 100_000, 1_000_000)
>>> for n in n_leaves:
...     print(f"The proof length for a tree with {n} leaves is {math.ceil(math.log2(n))}")
The proof length for a tree with 3 leaves is 2
The proof length for a tree with 10 leaves is 4
The proof length for a tree with 10000 leaves is 14
The proof length for a tree with 100000 leaves is 17
The proof length for a tree with 1000000 leaves is 20

One of the key advantages of using a merkle tree is that this could be verified on chain.

You might have a smart contract that should take some action only if it receives an asset from a particular collection.

If the collection metadata has an array of a million asset IDs, it will be too big to pass to the smart contract in an application call.

Even if that were possible, the contract would run out of op codes long before it could verify that the array contains a given asset ID.

A Simpler Alternative

If you want to reduce the size of the metadata further, and don't care about efficient proofs, you could use a hash chain or a circular linked list.

A circular singly linked list is a data structure where each node contains a pointer to the next node, and the last node points back to the first node.

An NFT collection could be represented as follows:

Collection ID --> Asset 1 ID --> Asset 2 ID... Asset N ID --> Collection ID

The metadata for both the collection and the assets would be very concise.

Each token simply points to the next token in the list.

But verifying that an asset belongs to a collection would be very inefficient, and impossible to do on chain in a single application call.

Summary

Merkle trees may provide an efficient way to verify that an NFT belongs to a collection, without relying on centralised registries.

Proofs could be verified on chain and off chain, enabling new use cases for smart contracts.

The solution should scale to support large collections, and caters for assets that are minted by any number of addresses.