Lazy ownership tree based on pallet-unique's owner

[h4x3rotab]

An important feature of RMRK spec is to allow any NFT to own other NFTs. This is called nested NFTs. It makes NFTs composable. Typical use cases are:

• A set of NFTs can be combined as a single object that can be send and sell in an auction as a whole
• By following some special rules (defined in BASE), some NFTs can be combined in a meaningful way that produce some special effects. E.g. glasses can be equipped to a Kanaria bird and can be rendered as a complete portrait

Current approach

Now the basic NFT is implemented by pallet-unique. On top of it, RMRKCore offers the advanced feature including the nested NFT. The basic logic can be described as below:

• RMRKCore stores an additional layer of the NFT ownership
  • Let's call it rmrk-owner, in contrast to unique-owner
• Every RMRK NFT has a rmrk-owner
• Rmrk-owner can be either AccountId or CollectionIdAndNftTuple (Nft for short)
• When minted, both rmrk-owner and unique-owner is set to the creator
• When burned, it recursively burn all the children NFTs
• When transferred, the destination can be either an AccountId or Nft
  • When transfer to an AccountId, both rmrk-owner and unique-owner are set to the new owner. Then it recursively set unique-owenr of all its children to the new owner.
  • When transfer to a Nft, the rmrk-owner is set to the dest NFT, the unique-owner is set to the unique-owner of the dest NFT. Then it recursively set the unique-owenr of all its children to the the same account.

This approach is suboptimal in three aspects:

• rmrk-owner and unique-owner is theoretically redundant -- the former is a superset of the later. It increases the difficulty to maintain both relationship in sync.
• The burn and transfer operation has to be recursive because we need to proactively update the ownership of the NFTs in unique (unique-owner). It's an overhead.
• If we allow users the direct access to the underlying pallet-unique (or through xcm), it's likely they can break the sync between unique and RMRK

So here, we'd prefer an approach that can minimize the redundancy of the data and reduce the complexity and the overhead to maintain the data structure.

Proposal

The proposal is simple: use the ownership in pallet-unique to trace the hierarchy of the NFTs.

The ownership in pallet-unique is represented by AccountId. At the first glance, it doesn't fit our requirement which is to allow a NFT to own other NFTs. However the AccountId isn't necessary to be a real wallet. It's just an address that can be backed by anything. In our case, we can create "virtual account" for each NFT instance by mapping their (CollectionId, NftId) tuple to an AccountId via hashing.

Once each NFT has a virtual AccountId associated, we can safely establish the hierarchy with pallet-unique's builtin ownership:

• When minted: just mint a unique NFT
• When transferred: simply transfer the NFT to the new owner
  • When transfer to an AccountId, just call unique's transfer
  • When transfer to a NFT, generate its corresponding virtual AccountId, and then we do the same transfer as above]
• When burned: check the NFT has no child, then just burn it

In this way, each operation is O(1) except the ownership check (discussed below). Even if you do a transfer of a NFT with heavy children, or put it to a sale, only the ownership of the top one needs to be changed.

The virtual account trick

This is a common trick widely used in Substrate. The virtual accounts are allocated to on-chain multisig wallets, anonymous proxies, and even some pallets. The benefit is that the AccountId unifies the identity representation for all kinds of entities, It can fit to any place that accepts an account to manage ownership.

The virtual accounts are usually just hard-coded string or hashes without any private key associated. For example, the AccountId of a multisig wallet can be generated by hash('multisig' ++ encode([owners]). Similarly, we can generate the virtual account id for each NFT like below:

fn nft_to_account_id<AccountId: Codec>(col: CollectionId, nft: NftId) -> AccountId {
    let preimage = (col, nft).encode();
    let hash = blake2_256(&preimage);
    (b"RmrkNft/", hash)
        .using_encoded(|b| AccountId::decode(&mut TrailingZeroInput::new(b)))
        .expect("Decoding with trailing zero never fails; qed.")
}

In the above example, "RmrkNft/" takes 8 bytes, and if AccountId is 32 bytes, we got 24 bytes entropy left for the hash of the nft ids.

Or if we are sure we can get an address space large enough to directly include the ids (e.g. AccountId32 can include CollectionId + Nft Id, which is just 8 bytes), we can just encode the ids to the account id directly. This enables reverse lookup much easier:

fn nft_to_account_id<AccountId: Codec>(col: CollectionId, nft: NftId) -> AccountId {
    (b"RmrkNft/", col, nft)
        .using_encoded(|b| AccountId::decode(&mut TrailingZeroInput::new(b)))
        .expect("Decoding with trailing zero never fails; qed.")
}

fn decode_nft_account_id<AccountId: Codec>(account_id: AccountId) -> Option<(CollectionId, NftId)> {
    let (prefix, tuple, suffix) = account_id
        .using_encoded(|mut b| {
            let slice = &mut b;
            let r = <([u8; 8], (CollectionId, NftId))>::decode(slice);
            r.map(|(prefix, tuple)| (prefix, tuple, slice.to_vec()))
        })
        .ok()?;
    // Check prefix and suffix to avoid collision attack
    if &prefix == b"RmrkNft/" && suffix.iter().all(|&x| x == 0) {
        Some(tuple)
    } else {
        None
    }
}

Ownership check

A drawback of this approach is that given a NFT in a tree, you cannot easily find if the user is owner if the tree. This can be solved by a reverse lookup:

• Save a reverse map: the map from the virtual accounts to the NFTs
  • (Actually can be saved if decode_nft_account_id is available)
• When finding the tree owner, we start from a NFT, check if its owner is in the reverse map
  • If no, this NFT is the root, and its owner is the result
  • If yes, we recursively lookup the parent NFT until we reach to the root

In this way, a lookup is O(h) where h is the depth of the NFT in the tree. It can be described in pseudocode:

type AccountPreimage = StorageMap<_, T::AccountId, TwoX64Concate, (CollectionId, NftId)>;

fn lookup_root(col: CollectionId, nft: NftId) -> (T::AccountId, (CollectionId,NftId)) {
    let parent = pallet_uniques::Pallet::<T>::owner(col, nft);
    match AccountPreimage::<T>::get(parent) {
        None => (parent, (col, nft)),
        Some((col, nft)) => lookup_root_owner(col, nft),
    }
}

Children

When burning a NFT itself, we need to ensure the is has no child. This can be done by either

• require no child under it,
• or automatically transfer its children to the caller before burning,
• or automatically burn all the children before burning.

It's easy to recursively burn all the children. To track the children of a NFT, a straightforward solution is to keep a record of all its children, and update the list dynamically when adding or removing a child:

type Children = StorageMap<(CollectionId, NftId), TwoX64Concat, Vec<(CollectionId, Nft)>, ValueQuery>;

fn add_child(parent: (CollectionId, NftId), child: (CollectionId, NftId)) {
    Children::<T>::mutate(parent, |v| {
        v.push_back(child)
    });
}
fn remove_child(parent: (CollectionId, NftId), child: (CollectionId, NftId)) {
    Children::<T>::mutate(parent, |v| {
        *v = v.iter().filter(|nft| nft != child).collect();
    });
}
fn has_child(parent: (CollectionId, NftId)) -> bool {
    !Children::<T>::contains_key(parent).empty()
}

Caveat: Note that this essentially builds an index for the ownership of the nfts. It can only get updated if the change of the ownership was initiated by the RMRK pallet. A bad case is that if a user transfer a NFT to another nft via pallet-uniques directly, the RMRK pallet will know nothing about this ownership change. The children index will be out-of-sync, and therefore when burning the parent nft, some children may be missed.

A solution is to somehow disallow pallet-uniques to transfer an NFT to another NFT. Or we can add a notification handler to pallet-uniques to call back whenever a transfer was done.

Pseudocode

fn mint(origin: OriginFor<T>, owner: T::AccountId, col: CollectionId, nft: NftId) {
    ensure_signed(origin)?;
    pallet_uniques::Pallet::<T>::mint(origin, owner, col, nft)?;
    Ok(())
}

fn burn(origin: OriginFor<T>, owner: T::AccountId, col: CollectionId, nft: NftId) {
    let who = ensure_signed(origin)?;
    // Check ownership
    let (root_owner, _) = lookup_root_owner(col, nft);
    ensure!(who == root_owner, Error::BadOrigin);
    // Check no children
    ensure!(!has_child((col, nft)), Error::CannotBurnNftWithChild);
    // Burn
    let parent = pallet_uniques::Pallet::<T>::owner(col, nft);
    pallet_uniques::Pallet::<T>::burn(Origin::signed(parent), col, nft);
    // Maintain the children
    if parent != root_owner {
        remove_child(parent, (col, nft));
    }
    Ok(())
}

fn transfer(origin: OriginFor<T>, col: CollectionId, nft: NftId, dest: AccountIdOrNftTuple) {
    let who = ensure_signed(origin)?;
    // Check ownership
    let (root_owner, root_nft) = lookup_root_owner(col, nft);
    ensure!(who == root_owner, Error::BadOrigin);
    // Prepare transfer
    let dest_account = match dest {
        AccountId(id) => id,
        NftTuple(c, n) => {
            // Circle detection
            let (_, dest_root_nft) = lookup_root_owner(c, n);            
            ensure!(root_nft != dest_root_nft, Error::CircleDetected);
            // Convert to virtual account
            nft_to_account_id(c, n)
        },
    };
    let owner = pallet_uniques::<T>::owner(col, nft);
    pallet_uniques::<T>::transfer(
        Origin::signed(owner),
        col, nft,
        dest_account,
    )?;
    Ok(())
}

Update notes

• 2021-12-31
  • Update the pseudocode in the "virtual account" section, also add an alternative encode scheme
  • Update burning and children indexing section according to Bruno's feedback
  • Correct the symbol names of pallet-uniques
  • Fix typos

[h4x3rotab]

A very important fact we should always keep in mind: In Substrate runtime, the IO access is so expensive that the size of the storage item and the computation usually doesn't matter.

More small value access is much worse than fewer large value access (pretty similar to HDD access in dbms). Therefore by removing the recursive traversal in transfer, we can significantly reduce the performance overhead.

[Swader]

Excellent, thank you, well thought out. Regarding nested children, we should burn recursively - children should burn with their parent. Given that in most cases there will only be a single layer of children, no more than 1 level deep, this should be very cheap to execute. It is an expected operation, and you could in theory prevent someone from using an item (i.e. burn-to-use) by spamming it with children if we were to block burns by reference counters for example.

The reason for not moving all children to owner / EOA automatically is that there is no easy way to then handle pending children (those sent into an NFT by non-owner enter an initial pending state before being ACCEPTed by the parent NFT owner) or non-transferables, e.g. an avatar which has a non-transferable experience card with certain levels and skills. This card has no business existing outside of this avatar, and should burn alongside him.

[bmacer]

Thanks for the analysis. Thinking about burning recursively, would it be possible just to burn the parent itself and create "bastard" children, and implement this by adding an Option to the lookup root function with a check for existence prior to each recursion (returning None)?

[HashWarlock]

The reason for not moving all children to owner / EOA automatically is that there is no easy way to then handle pending children (those sent into an NFT by non-owner enter an initial pending state before being ACCEPTed by the parent NFT owner) or non-transferables, e.g. an avatar which has a non-transferable experience card with certain levels and skills. This card has no business existing outside of this avatar, and should burn alongside him.

Would there be a case where an avatar can have a mix of transferable/non-transferable child NFTs & in the event that an avatar is burned, we would only want to burn non-transferable NFTs, but release the other transferable child NFTs? Would we want to have a property to prevent certain child NFTs from being burnt with the parent or would that introduce complexity to the design?

[yornaath]

Hello! Just chiming in. I have an intuition that the rmrk core could benefit from having something of a reference system? A child of a NFT could either be a direct member or a borrowed reference. Burning a NFT would burn direct children but not borrowed references?

This could also be a nice primitive to have in the runtime to support lending out NFTs?

#[pallet::storage]
#[pallet::getter(fn children)]
/// Stores nft info
pub type Children<T: Config> = StorageDoubleMap<
	_,
	Twox64Concat,
	CollectionId,
	Twox64Concat,
	NftId,
	Vec<(CollectionId, NFTReference)>,
>;

#[derive(Clone, Encode, Decode, Eq, PartialEq, RuntimeDebug, TypeInfo)]
enum NFTReference {
	Lit(NftId),
	Ref(NftId),
}

Dipping my toes in rust and substrate land, so be nice plz 😅

[h4x3rotab]

@Swader Thanks. I've updated the proposal to consider recursive burning by default.

@bmacer Brilliant idea! I love it a lot. By burning the target nft, all its children becomes "rootless" -- if we trace back its root owner, we will walk to a null node, and then we can stop immediately. This indicating some nodes are dirty and ready to clean. Anyone can make a transaction to burn some NFT. If we can add some incentives, like refunding of a small deposit, we can expect people to eagerly help us clean up the dirty nodes. In this way, we even don't need to track the children index.

The only concern is that it will make tracking the current number of the nft harder. We can still track, but the dirty nodes will also be counted in. Not sure if this is a big problem though.

[h4x3rotab]

The reason for not moving all children to owner / EOA automatically is that there is no easy way to then handle pending children (those sent into an NFT by non-owner enter an initial pending state before being ACCEPTed by the parent NFT owner) or non-transferables, e.g. an avatar which has a non-transferable experience card with certain levels and skills. This card has no business existing outside of this avatar, and should burn alongside him.

Would there be a case where an avatar can have a mix of transferable/non-transferable child NFTs & in the event that an avatar is burned, we would only want to burn non-transferable NFTs, but release the other transferable child NFTs? Would we want to have a property to prevent certain child NFTs from being burnt with the parent or would that introduce complexity to the design?

It doesn't introduce a lot of complexity, if the lock is just like a safeguard for accidental burning. However on blockchain we usually don't consider the human mistakes. It's better to handle that by the frontend / sdk. So we don't need to pay even a bit of the engineering overhead.

Non-transferable NFTs will be more troublesome. If we cannot deal with it properly at the pallet-uniques side, an immediate problem I can come up is that a user may transfer the token directly at pallet-uniques to bypass all the RMRK restrictions

[h4x3rotab]

Closing via #31