# CosmWasm Smart Contract Storage Key Permutation (And Its Application) By [yoisha](https://paragraph.com/@yoisha) · 2022-06-07 --- Normally the key of a map might be a simple address or id, but that doesn’t mean it was limited to those simple things. By understanding how smart contracts’ storage operates and using key permutation, we can achieve a more complex composite key that can be used to index our data in a more enhanced way and make our CosmWasm smart contract experience better. Key-Value Storage ----------------- First, we need to understand how the underlying IAVL+ key-value storage operates. ![](https://storage.googleapis.com/papyrus_images/88fd99faa5ac6412a96803b95faeca4f224b48781d6ef2fb7a0963c6a8679e4f.png) [https://docs.cosmwasm.com/tutorials/storage/key-value-store](https://docs.cosmwasm.com/tutorials/storage/key-value-store) The storage of the CosmWasm smart contract is structured with tree modeling. IAVL+ is a kind of self-balancing binary search tree that is used here and has been modified from the original AVL tree to be specially used in smart contract storage. Imagine each circle is a key, corresponding with a value that is tied to that key. The iteration process can be done through key prefixes. For example, the key `JPL` has `J` `JP` `JPL` as its prefixes. So looking back `range(JP)` will contain `JPL` . The underlying process of these prefixes is each key has an underlying fixed-length bytes representation. If we let one key length equal to 2 bytes, then one key can contain the value from `0000` to `FFFF` . For `JPL` , it will be something like `004A,0050,004C` (Comma here is for ease in reading, all bytes are also padded to the left), so we can iterate through `range(JP)` that will go through `0004,A005,0000` to `004A,0050,FFFF` , result in getting `JP` `JPL` `JPLN` `JPV` `JPVS` `JPVSQ` `JPVSQ` `JPVSU` `JPVX` . As you can see, the iteration is pretty simple (and also limiting). Thus there are many cases where these key iteration is not enough for indexing and do not resonate with state design. Key Permutation And Application ------------------------------- Take a look at the struct below. Let's say each treasure has a unique id and one address can be the owner of multiple treasures. Treasure Struct And TreasureTy Enum And if you want to index the treasure by owner and type, you would need 2 distinct maps. One for the owner and one for the type, probably like this. ![](https://storage.googleapis.com/papyrus_images/e961107d006e00da8008e6b38cde0ffd1cd8af4c891832b9ba0e0906061aefa7.png) Mapping ![](https://storage.googleapis.com/papyrus_images/399b3767256573390108510d5265d99f484bc3b1bf31b19afd7e76cea74ebd5e.png) Usage You can’t do much about this if you want to iterate through all treasures with owner or treasure type as prefixes, but there is a catch. Composite Key ------------- Using the key pattern above, you can add treasure type to the owner’s composite key to make it indexable by treasure type too. ![](https://storage.googleapis.com/papyrus_images/72da41b967e6ea5d78f69ec422f99e5cf2d5dd5458e3745855d6a5ae56986d0f.png) So the key bytes representation of this map here is like below. (Not representing the real pattern used, just for illustration)\*\* The namespace can/will be neglected from now on.\*\* Namespace | Address TreasureTy(u8) Id(u64) v | v v v t_o | ################ ################ ################ Namespace --------- The namespace is the internal top key identifier that will separate your multiple composite key map from each other. The namespace specified **can’t** be accessed directly through `prefix` or `range` . (Although low-level implementation is possible) Range Iteration --------------- There are three options to iterate through the range here. Prefix ------ One is using `prefix` , `prefix` will freeze the `n — 1` slot of `n` length composite key and iterate using the last slot as a bound. Total composite key length = 3Address TreasureTy(u8) Id(u64) (<- Prefix ->) (<- Bound ->) v v v ################ ################ ################ `prefix` in this case, will be `(Addr, TreasureTy)` and the bound of that `prefix` is `u64` . Sub Prefix ---------- Another method is using `sub_prefix` , `sub_prefix` will freeze `n — 2` slot of n key. But for normal composite keys that have 2 keys or a single key, this will be a unit type `()` . For example, `Map` and `Map<(Addr, u64), Treasure)>` will both have a unit`()` as the `sub_prefix` . Total composite key length = 3 Address TreasureTy(u8) Id(u64) (<- Prefix ->) (<- Bound ->) v v v ################ ################ ################ `sub_prefix` in this case, will be `Addr` and the bound is `(TreasureTy, u64)` . Namespace --------- The last option is to create another map accessor to access only the namespace. To put it simply, iterate only through the top`namespace` range. Thus return all the values in that namespace. Total composite key length = 0 Total key's bytes representation length = (Addr,u8,u64).joined_key().len() Namespace | X X X v | v v v t_o | 0000000000000000 0000000000000000 0000000000000000 **Custom Prefix And Sub Prefix** -------------------------------- We can also specify how the struct/enum operates as a storage key too. By implementing `PrimaryKey` and `Prefixes` trait, we can fully customize how struct/enum serialize to key bytes representation. And specify how `prefix` and `sub_prefix` access the range too. Usage ----- Using `sub_prefix` method on `treasure_owner` to set the address bytes to a specific address, here we will supply `a_addr` . Address TreasureTy(u8) Id(u64) v v v 0000615F61646472 ################ ################ Then we can use `range` method chain on `Prefix` (Helper struct that is the result of `prefix` and `sub_prefix`) on accessing the iterator. Note that the bound we used here must be joined key bytes of `TreasureTy` and `u64` as said before. If we supply `None` to both bound conditions, it will iterate through all treasures of this address. Equivalent to `(u8::min_value(), u64::min_value())` to `(u8::max_value(), u64::max_value())` . Address TreasureTy(u8) Id(u64) v v v 0000615F61646472 0000000000000000 0000000000000000 Address TreasureTy(u8) Id(u64) v v v 0000615F61646472 00000000000000FF FFFFFFFFFFFFFFFF If we want to use our own bound, it will have to be in the joined key bytes format of `(TreasureTy, u64)` . Suppose that we want to go through this prefix from `TreasureTy::Pearl` at specific id `3840` to the end of `TreasureTy::Coin` . A similar representation will be `(0,3840)` to `(1,u64::max_value())` , and the bytes representation will be as below. Address TreasureTy(u8) Id(u64) v v v 0000615F61646472 0000000000000000 0000000000000F00 Address TreasureTy(u8) Id(u64) v v v 0000615F61646472 0000000000000001 FFFFFFFFFFFFFFFF > **Remarks**: if you use this in query function, as the bound that need to be `(TreasureTy,u64)` your query `start_after` pagination parameter might need to look like `start_after: (TreasureTy, u64)` , or `start_after: Treasure` , or something like that. Using `prefix` method on `treasure_owner` to set the address and treasure type to specific bytes, here we will supply `(a_addr, TreasureTy::BankNote)` . Address TreasureTy(u8) Id(u64) v v v 0000615F61646472 0000000000000002 ################ Then we can use `range` method chain on `Prefix` like normally we do with a composite key with a two key element. (such as initial `treasure_owner` ) Conclusion ---------- By using the more complex composite key, and use `prefix` and `sub_prefix` that follows the key bytes representation, we can bring out a more helpful iterator that can be used to access our data in a specific way in addition to the original way of indexing. --- *Originally published on [yoisha](https://paragraph.com/@yoisha/cosmwasm-smart-contract-storage-key-permutation-and-its-application)*