Merkle roots to associate Loot item names to metadata

Developer Tools & Infrastructure
#1

Challenge:

Need a way to efficiently verify membership of a Loot Bag in some set X. For example, is Loot Bag 105 a member of the Library guild? In this case, it’s getWeapon function returns Book. We can verify that by calling the Solidity function and passing item ID 105, but we have to somehow understand that the Book string implies membership in the Library guild.

The fact that Books mean membership in the Library guild is an additional piece of metadata that can be used in games, governance and other on-chain mechanism designs. Another example is group raids, where a developer might want to understand what is actually inside the bags in order to improve the game experience.

I’m assuming that comparing a lot of strings in Solidity is a pain for developers. If a developer were to check this on-chain, they would have to compare against all known permutations of Book, such as Book of the Twins and a hundred other variations. Furthermore, they would have to do this for each item name => guild association. Another example is mythical Loot items, which vary in name diversity to an extreme degree, where each name might be different in each Bag. Is there a solution which can scale to handle these degrees of diversity, while still being efficient for on-chain verification, and not being a huge pain for developers?

Solution: Merkle Root verification

I propose using a Merkle tree structure where the leaf nodes consist of the items in the set. The root of the tree, the Merkle root, can then be used to cryptographically verify membership in the set. This verification can happen on-chain, efficiently and securely.

For example, we can take the names of all 4364 mythical items, and produce the Merkle root once, off-chain. Anyone could reproduce this Merkle root for themselves to verify its correctness. The Merkle root is then submitted to a smart contract GuildMetadata.sol, which allows any developer in the Loot ecosystem to call a function such as isItemMemberOfGuild(itemName, guildName).

The item name and the guild name can be passed as arguments to the function, and the function would check for the membership of hash(itemName) within the merkle root for guildName.

Generalizability

Using this technique, there can be a single contract that is used as a Guild metadata contract. Multiple items can be verified, within multiple guilds, so it’s scalable up to a large design space of item => guild combinations. For example:

  • Any Divine items = Divine Lodge guild
  • All Divine Robes = Divine Roles guild
  • All Katanas = Katana guild
  • All Mythical items = Mythical guild
  • Any dragon item = Dragon guild
  • …

It also doesn’t matter how many Bags there are, 8000 or 2 million. They all could use the same technique to create the associations from a group of names to some metadata.

Expanding the names

Using this technique, if a derivative or future project wanted to add names to the set, the Merkle root could just be recomputed and submitted without modifying the contracts that rely on these associations.

Other Association Types

In this example, I used an item-to-guild association, but the technique works with associations to other kinds of data. The general problem of having to check many diverse names for membership in sets can be solved using this technique.

Questions

  • For the divine items to Divine Lodge example, the attribute to check could be the head, foot, chest or hand. Should isItemMemberOfGuild also require an argument for the attribute name to check, or any to check all of them?
  • Are there any other ways to somehow improve this technique?
  • Is it worth it, in terms of gas and compute, to perform the check this way?

Could this work?

I am a Solidity noob so I could be wrong in my thinking of this. I’m relying on second-hand knowledge of how other smart contract systems use Merkle roots, not first-hand experience. I’d love for someone with the Solidity expertise to take this idea, verify it could work and run with it for the benefit of the Loot community. If not, I could try to build myself, but it would take longer.

#2

So I just discovered the LootComponents.sol contract and looks like that has the metadata for the Loot Bag items. That can be used to accomplish the original challenge of knowing which Bag’s are books, etc.

1 Like
#3

LootComponents.sol looks like a piece to the puzzle but theres also this http://LootLoose.com that might be interesting to you :slight_smile:

#4

I have the same issue to access item stats on chain.

Merkle tree is good, but be aware that there are still 221 Loots not minted, if there are new loots minted, you need to update the Merkle root.

My solution is to create an on chain rarity, so there is no need for Merkle tree, the rarity will automatically update even when new Loots minted.

Feel free to check my github: https://github.com/colorloot/colorloot

The main issue of color loot is that we need community to mint color loot, so that it will generate all the rarity data. When all color loot minted, you can use the method to check if a Loot id has a Library Guild.

For example, if you want to get item rarities of Loot Id 1:

ItemRarities rarities = colorLootContract.getItemRarities(1);
struct ItemRarities {
    ItemRarity weapon;
    ItemRarity chest;
    ItemRarity head;
    ItemRarity waist;
    ItemRarity foot;
    ItemRarity hand;
    ItemRarity neck;
    ItemRarity ring;
}

struct ItemRarity {
    uint256 occurrence; // occurrence of the item name
    uint256 threshold; // threshold of occurrences in current level
    string color; // predefined color, i.e. #ff44b7
    string level; // Common, Uncommon, Rare, Epic, Legendary, Mythic
}
#5

Correct. The merkle root needs to be updated for new item names.

The benefit of storing the merkle root publicly is so that users can verify themselves that the root was calculated correctly.

Also, one thing I’ve realized is that the merkle proof should be determined off-chain. Ideally, a client-side Javascript library such as loot-guilds.js could act as a layer to interact with the on-chain contract. This library would produce the proof that allows the on-chain verification of merkle tree membership to succeed. In that spirit, the merkle root itself can be passed as an argument to isItemMemberOfGuild each time. If item names are added or removed, the library can be updated alongside the publicly registered merkle root.