Track Owned Kitties

Now that we can generate unique kitties, we need to consider all the ways we need to store and track those kitties.

Redundant Storage

As a rule, you only want to store data in your blockchain which is necessary for consensus. Blockchains are extremely slow, low powered, and expensive. Blockchains are extremely good at one thing: achieving agreement among a decentralized and untrusted set of individuals.

When building a blockchain, you need to think about the various constraints:

  • Execution Constraints
  • Memory Constraints
  • Storage Constraints
  • Bandwidth Constrains
  • etc...

In the case of adding redundant storage, all of these constraints come into play! So let's talk about that a bit.

Iteration

It is common when writing code that you might want to perform iteration over items stored in your blockchain.

In general iteration should be avoided where possible, but if unavoidable it is critical that iteration be bounded in size.

We literally cannot allow code on our blockchain which would do unbounded iteration, else that would stall our blockchain, which needs to produce a new block on a regular time interval.

Maps

When you store and iterate over a map, you need to make two considerations:

  1. That the map may not have a bounded upper limit.
  2. That each access to the map is very expensive to the blockchain (each is a unique read to the merkle trie).

If you want to do iteration, probably you do NOT want to use a map for exactly these reasons.

Maps are great instead for when you need to access or manipulate a single item at a time.

Vec

When you store and iterate over a vector, the only real consideration you need to have is how large that vector is.

Accessing large files from the database is going to be slower than accessing small files.

Once you access the vector, iterating over it and manipulating it is relatively cheap compared to any kind of storage map (but not zero, complexity about vector access still applies).

If you want to do iteration, you definitely would prefer to use a vector.

Middle Ground

But sometimes you need to iterate over data, and store a lot of data. This is where we can do a middle ground.

While it is not great for your Storage Constraints to store redundant data, it can be much better for all your other constraints.

Let's say we want to answer the question: Give me all the kitties owned by Shawn.

If all the kitties are stored just in the map, then we would need to iterate over all of them to find which ones are owned by Shawn.

However, if we ALSO store a vector of kitties owned by Shawn in another storage, yes we would have redundant information in our database, but we will also be able to answer this question much more efficiently.

A key part of designing your storage is making it efficient for the tasks your code will need to execute. Similarly, you will need to design your code to be efficient for the storage constraints you have.

Honestly, its a lose / lose situation most times, but it is part of what we need to do when designing blockchain systems.

Storage Optimizations

Storing vectors is a pretty normal part of Pallet development, and there are ways we can optimize adding items to a vector.

Let's look at a naive way to add a new item to the vector:

#![allow(unused)]
fn main() {
let mut owned_kitties: Vec<[u8; 32]> = KittiesOwned::<T>::get(owner);
owned_kitties.append(new_kitty);
KittiesOwned::<T>::insert(owner, owned_kitties);
}

The first call we need to make is get which returns to us all the data in the vector, and all that data is stored in a merkle trie in a database that is really expensive to read from.

Then we add the item to the vector, and then write the whole new item back into storage.

But this is way more inefficient than we need! We don't actually need to know what is inside the vector to add a new item to it, we can just say "add this item".

So we can convert the whole logic to:

#![allow(unused)]
fn main() {
KittiesOwned::<T>::append(owner, new_kitty);
}

In this case, we use our own storage abstractions to avoid needing to read the whole vector in our runtime logic to simply add a new item to it.

Fun fact, this optimization actually lead to a 95% performance increase for the polkadot-sdk back before Polkadot launched and we were benchmarking it!

Your Turn

Now that you understand the tradeoffs associated with creating redundant storage, let's make a new StorageMap called KittiesOwned which can help us more easily find what kitties an account is the owner of.

Then let's update the mint function to append the kitty's DNA to the KittiesOwned vector for the owner.

#![allow(unused)]
fn main() {
use super::*;
use frame::prelude::*;
use frame::primitives::BlakeTwo256;
use frame::traits::Hash;

impl<T: Config> Pallet<T> {
	// Generates and returns DNA
	pub fn gen_dna() -> [u8; 32] {
		// Create randomness payload. Multiple kitties can be generated in the same block,
		// retaining uniqueness.
		let unique_payload = (
			frame_system::Pallet::<T>::parent_hash(),
			frame_system::Pallet::<T>::block_number(),
			frame_system::Pallet::<T>::extrinsic_index(),
			CountForKitties::<T>::get(),
		);

		BlakeTwo256::hash_of(&unique_payload).into()
	}

	pub fn mint(owner: T::AccountId, dna: [u8; 32]) -> DispatchResult {
		let kitty = Kitty { dna, owner: owner.clone() };
		// Check if the kitty does not already exist in our storage map
		ensure!(!Kitties::<T>::contains_key(dna), Error::<T>::DuplicateKitty);

		let current_count: u32 = CountForKitties::<T>::get();
		let new_count = current_count.checked_add(1).ok_or(Error::<T>::TooManyKitties)?;

		/* 🚧 TODO 🚧: `append` the `dna` to the `KittiesOwned` storage for the `owner`. */

		Kitties::<T>::insert(dna, kitty);
		CountForKitties::<T>::set(new_count);
		Self::deposit_event(Event::<T>::Created { owner });
		Ok(())
	}
}
}
#![allow(unused)]
#![cfg_attr(not(feature = "std"), no_std)]

fn main() {
mod impls;
mod tests;

use frame::prelude::*;
pub use pallet::*;

#[frame::pallet(dev_mode)]
pub mod pallet {
	use super::*;

	#[pallet::pallet]
	pub struct Pallet<T>(core::marker::PhantomData<T>);

	#[pallet::config]
	pub trait Config: frame_system::Config {
		type RuntimeEvent: From<Event<Self>> + IsType<<Self as frame_system::Config>::RuntimeEvent>;
	}

	#[derive(Encode, Decode, TypeInfo, MaxEncodedLen)]
	#[scale_info(skip_type_params(T))]
	pub struct Kitty<T: Config> {
		// Using 32 bytes to represent a kitty DNA
		pub dna: [u8; 32],
		pub owner: T::AccountId,
	}

	#[pallet::storage]
	pub(super) type CountForKitties<T: Config> = StorageValue<Value = u32, QueryKind = ValueQuery>;

	#[pallet::storage]
	pub(super) type Kitties<T: Config> = StorageMap<Key = [u8; 32], Value = Kitty<T>>;

	/* 🚧 TODO 🚧: Create a new `StorageMap` called `KittiesOwned`.
		- The `Key` of this map is `T::AccountId`.
		- The `Value` of this map is `Vec<[u8; 32]>`.
		- The `QueryKind` should be set to `ValueQuery`.
	*/

	#[pallet::event]
	#[pallet::generate_deposit(pub(super) fn deposit_event)]
	pub enum Event<T: Config> {
		Created { owner: T::AccountId },
	}

	#[pallet::error]
	pub enum Error<T> {
		TooManyKitties,
		DuplicateKitty,
	}

	#[pallet::call]
	impl<T: Config> Pallet<T> {
		pub fn create_kitty(origin: OriginFor<T>) -> DispatchResult {
			let who = ensure_signed(origin)?;
			let dna = Self::gen_dna();
			Self::mint(who, dna)?;
			Ok(())
		}
	}
}
}
#![allow(unused)]
fn main() {
use super::*;
use frame::prelude::*;
use frame::primitives::BlakeTwo256;
use frame::traits::Hash;

impl<T: Config> Pallet<T> {
	// Generates and returns DNA
	pub fn gen_dna() -> [u8; 32] {
		// Create randomness payload. Multiple kitties can be generated in the same block,
		// retaining uniqueness.
		let unique_payload = (
			frame_system::Pallet::<T>::parent_hash(),
			frame_system::Pallet::<T>::block_number(),
			frame_system::Pallet::<T>::extrinsic_index(),
			CountForKitties::<T>::get(),
		);

		BlakeTwo256::hash_of(&unique_payload).into()
	}

	pub fn mint(owner: T::AccountId, dna: [u8; 32]) -> DispatchResult {
		let kitty = Kitty { dna, owner: owner.clone() };
		// Check if the kitty does not already exist in our storage map
		ensure!(!Kitties::<T>::contains_key(dna), Error::<T>::DuplicateKitty);

		let current_count: u32 = CountForKitties::<T>::get();
		let new_count = current_count.checked_add(1).ok_or(Error::<T>::TooManyKitties)?;

		KittiesOwned::<T>::append(&owner, dna);
		Kitties::<T>::insert(dna, kitty);
		CountForKitties::<T>::set(new_count);

		Self::deposit_event(Event::<T>::Created { owner });
		Ok(())
	}
}
}
#![allow(unused)]
#![cfg_attr(not(feature = "std"), no_std)]

fn main() {
mod impls;
mod tests;

use frame::prelude::*;
pub use pallet::*;

#[frame::pallet(dev_mode)]
pub mod pallet {
	use super::*;

	#[pallet::pallet]
	pub struct Pallet<T>(core::marker::PhantomData<T>);

	#[pallet::config]
	pub trait Config: frame_system::Config {
		type RuntimeEvent: From<Event<Self>> + IsType<<Self as frame_system::Config>::RuntimeEvent>;
	}

	#[derive(Encode, Decode, TypeInfo, MaxEncodedLen)]
	#[scale_info(skip_type_params(T))]
	pub struct Kitty<T: Config> {
		// Using 32 bytes to represent a kitty DNA
		pub dna: [u8; 32],
		pub owner: T::AccountId,
	}

	#[pallet::storage]
	pub(super) type CountForKitties<T: Config> = StorageValue<Value = u32, QueryKind = ValueQuery>;

	#[pallet::storage]
	pub(super) type Kitties<T: Config> = StorageMap<Key = [u8; 32], Value = Kitty<T>>;

	/// Track the kitties owned by each account.
	#[pallet::storage]
	pub(super) type KittiesOwned<T: Config> =
		StorageMap<Key = T::AccountId, Value = Vec<[u8; 32]>, QueryKind = ValueQuery>;

	#[pallet::event]
	#[pallet::generate_deposit(pub(super) fn deposit_event)]
	pub enum Event<T: Config> {
		Created { owner: T::AccountId },
	}

	#[pallet::error]
	pub enum Error<T> {
		TooManyKitties,
		DuplicateKitty,
	}

	#[pallet::call]
	impl<T: Config> Pallet<T> {
		pub fn create_kitty(origin: OriginFor<T>) -> DispatchResult {
			let who = ensure_signed(origin)?;
			let dna = Self::gen_dna();
			Self::mint(who, dna)?;
			Ok(())
		}
	}
}
}
#![allow(unused)]
fn main() {
// Tests for the Kitties Pallet.
//
// Normally this file would be split into two parts: `mock.rs` and `tests.rs`.
// The `mock.rs` file would contain all the setup code for our `TestRuntime`.
// Then `tests.rs` would only have the tests for our pallet.
// However, to minimize the project, these have been combined into this single file.
//
// Learn more about creating tests for Pallets:
// https://paritytech.github.io/polkadot-sdk/master/polkadot_sdk_docs/guides/your_first_pallet/index.html

// This flag tells rust to only run this file when running `cargo test`.
#![cfg(test)]

use crate as pallet_kitties;
use crate::*;
use frame::deps::sp_io;
use frame::runtime::prelude::*;
use frame::testing_prelude::*;
use frame::traits::fungible::*;

type Balance = u64;
type Block = frame_system::mocking::MockBlock<TestRuntime>;

// In our "test runtime", we represent a user `AccountId` with a `u64`.
// This is just a simplification so that we don't need to generate a bunch of proper cryptographic
// public keys when writing tests. It is just easier to say "user 1 transfers to user 2".
// We create the constants `ALICE` and `BOB` to make it clear when we are representing users below.
const ALICE: u64 = 1;
const BOB: u64 = 2;
const DEFAULT_KITTY: Kitty<TestRuntime> = Kitty { dna: [0u8; 32], owner: 0 };

// Our blockchain tests only need 3 Pallets:
// 1. System: Which is included with every FRAME runtime.
// 2. PalletBalances: Which is manages your blockchain's native currency. (i.e. DOT on Polkadot)
// 3. PalletKitties: The pallet you are building in this tutorial!
construct_runtime! {
	pub struct TestRuntime {
		System: frame_system,
		PalletBalances: pallet_balances,
		PalletKitties: pallet_kitties,
	}
}

// Normally `System` would have many more configurations, but you can see that we use some macro
// magic to automatically configure most of the pallet for a "default test configuration".
#[derive_impl(frame_system::config_preludes::TestDefaultConfig)]
impl frame_system::Config for TestRuntime {
	type Block = Block;
	type AccountData = pallet_balances::AccountData<Balance>;
}

// Normally `pallet_balances` would have many more configurations, but you can see that we use some
// macro magic to automatically configure most of the pallet for a "default test configuration".
#[derive_impl(pallet_balances::config_preludes::TestDefaultConfig)]
impl pallet_balances::Config for TestRuntime {
	type AccountStore = System;
	type Balance = Balance;
}

// This is the configuration of our Pallet! If you make changes to the pallet's `trait Config`, you
// will also need to update this configuration to represent that.
impl pallet_kitties::Config for TestRuntime {
	type RuntimeEvent = RuntimeEvent;
}

// We need to run most of our tests using this function: `new_test_ext().execute_with(|| { ... });`
// It simulates the blockchain database backend for our tests.
// If you forget to include this and try to access your Pallet storage, you will get an error like:
// "`get_version_1` called outside of an Externalities-provided environment."
pub fn new_test_ext() -> sp_io::TestExternalities {
	frame_system::GenesisConfig::<TestRuntime>::default()
		.build_storage()
		.unwrap()
		.into()
}

#[test]
fn starting_template_is_sane() {
	new_test_ext().execute_with(|| {
		let event = Event::<TestRuntime>::Created { owner: ALICE };
		let _runtime_event: RuntimeEvent = event.into();
		let _call = Call::<TestRuntime>::create_kitty {};
		let result = PalletKitties::create_kitty(RuntimeOrigin::signed(BOB));
		assert_ok!(result);
	});
}

#[test]
fn system_and_balances_work() {
	// This test will just sanity check that we can access `System` and `PalletBalances`.
	new_test_ext().execute_with(|| {
		// We often need to set `System` to block 1 so that we can see events.
		System::set_block_number(1);
		// We often need to add some balance to a user to test features which needs tokens.
		assert_ok!(PalletBalances::mint_into(&ALICE, 100));
		assert_ok!(PalletBalances::mint_into(&BOB, 100));
	});
}

#[test]
fn create_kitty_checks_signed() {
	new_test_ext().execute_with(|| {
		// The `create_kitty` extrinsic should work when being called by a user.
		assert_ok!(PalletKitties::create_kitty(RuntimeOrigin::signed(ALICE)));
		// The `create_kitty` extrinsic should fail when being called by an unsigned message.
		assert_noop!(PalletKitties::create_kitty(RuntimeOrigin::none()), DispatchError::BadOrigin);
	})
}

#[test]
fn create_kitty_emits_event() {
	new_test_ext().execute_with(|| {
		// We need to set block number to 1 to view events.
		System::set_block_number(1);
		// Execute our call, and ensure it is successful.
		assert_ok!(PalletKitties::create_kitty(RuntimeOrigin::signed(ALICE)));
		// Assert the last event by our blockchain is the `Created` event with the correct owner.
		System::assert_last_event(Event::<TestRuntime>::Created { owner: 1 }.into());
	})
}

#[test]
fn count_for_kitties_created_correctly() {
	new_test_ext().execute_with(|| {
		// Querying storage before anything is set will return `0`.
		assert_eq!(CountForKitties::<TestRuntime>::get(), 0);
		// You can `set` the value using an `u32`.
		CountForKitties::<TestRuntime>::set(1337u32);
		// You can `put` the value directly with a `u32`.
		CountForKitties::<TestRuntime>::put(1337u32);
	})
}

#[test]
fn mint_increments_count_for_kitty() {
	new_test_ext().execute_with(|| {
		// Querying storage before anything is set will return `0`.
		assert_eq!(CountForKitties::<TestRuntime>::get(), 0);
		// Call `create_kitty` which will call `mint`.
		assert_ok!(PalletKitties::create_kitty(RuntimeOrigin::signed(ALICE)));
		// Now the storage should be `1`
		assert_eq!(CountForKitties::<TestRuntime>::get(), 1);
	})
}

#[test]
fn mint_errors_when_overflow() {
	new_test_ext().execute_with(|| {
		// Set the count to the largest value possible.
		CountForKitties::<TestRuntime>::set(u32::MAX);
		// `create_kitty` should not succeed because of safe math.
		assert_noop!(
			PalletKitties::create_kitty(RuntimeOrigin::signed(1)),
			Error::<TestRuntime>::TooManyKitties
		);
	})
}

#[test]
fn kitties_map_created_correctly() {
	new_test_ext().execute_with(|| {
		let zero_key = [0u8; 32];
		assert!(!Kitties::<TestRuntime>::contains_key(zero_key));
		Kitties::<TestRuntime>::insert(zero_key, DEFAULT_KITTY);
		assert!(Kitties::<TestRuntime>::contains_key(zero_key));
	})
}

#[test]
fn create_kitty_adds_to_map() {
	new_test_ext().execute_with(|| {
		assert_ok!(PalletKitties::create_kitty(RuntimeOrigin::signed(ALICE)));
		assert_eq!(Kitties::<TestRuntime>::iter().count(), 1);
	})
}

#[test]
fn cannot_mint_duplicate_kitty() {
	new_test_ext().execute_with(|| {
		assert_ok!(PalletKitties::mint(ALICE, [0u8; 32]));
		assert_noop!(PalletKitties::mint(BOB, [0u8; 32]), Error::<TestRuntime>::DuplicateKitty);
	})
}

#[test]
fn kitty_struct_has_expected_traits() {
	new_test_ext().execute_with(|| {
		let kitty = DEFAULT_KITTY;
		let bytes = kitty.encode();
		let _decoded_kitty = Kitty::<TestRuntime>::decode(&mut &bytes[..]).unwrap();
		assert!(Kitty::<TestRuntime>::max_encoded_len() > 0);
		let _info = Kitty::<TestRuntime>::type_info();
	})
}

#[test]
fn mint_stores_owner_in_kitty() {
	new_test_ext().execute_with(|| {
		assert_ok!(PalletKitties::mint(1337, [42u8; 32]));
		let kitty = Kitties::<TestRuntime>::get([42u8; 32]).unwrap();
		assert_eq!(kitty.owner, 1337);
		assert_eq!(kitty.dna, [42u8; 32]);
	})
}

#[test]
fn create_kitty_makes_unique_kitties() {
	new_test_ext().execute_with(|| {
		// Two calls to `create_kitty` should work.
		assert_ok!(PalletKitties::create_kitty(RuntimeOrigin::signed(ALICE)));
		assert_ok!(PalletKitties::create_kitty(RuntimeOrigin::signed(BOB)));
		// And should result in two kitties in our system.
		assert_eq!(CountForKitties::<TestRuntime>::get(), 2);
		assert_eq!(Kitties::<TestRuntime>::iter().count(), 2);
	})
}

#[test]
fn kitties_owned_created_correctly() {
	new_test_ext().execute_with(|| {
		// Initially users have no kitties owned.
		assert_eq!(KittiesOwned::<TestRuntime>::get(1).len(), 0);
		// Let's create two kitties.
		assert_ok!(PalletKitties::create_kitty(RuntimeOrigin::signed(ALICE)));
		assert_ok!(PalletKitties::create_kitty(RuntimeOrigin::signed(ALICE)));
		// Now they should have two kitties owned.
		assert_eq!(KittiesOwned::<TestRuntime>::get(1).len(), 2);
	});
}
}
diff --git a/src/impls.rs b/src/impls.rs
index ff69cae..05c43d7 100644
--- a/src/impls.rs
+++ b/src/impls.rs
@@ -25,6 +25,9 @@ impl<T: Config> Pallet<T> {
 
 		let current_count: u32 = CountForKitties::<T>::get();
 		let new_count = current_count.checked_add(1).ok_or(Error::<T>::TooManyKitties)?;
+
+		/* 🚧 TODO 🚧: `append` the `dna` to the `KittiesOwned` storage for the `owner`. */
+
 		Kitties::<T>::insert(dna, kitty);
 		CountForKitties::<T>::set(new_count);
 		Self::deposit_event(Event::<T>::Created { owner });
diff --git a/src/lib.rs b/src/lib.rs
index 8795b0e..a92f8e5 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -32,6 +32,12 @@ pub mod pallet {
 	#[pallet::storage]
 	pub(super) type Kitties<T: Config> = StorageMap<Key = [u8; 32], Value = Kitty<T>>;
 
+	/* 🚧 TODO 🚧: Create a new `StorageMap` called `KittiesOwned`.
+		- The `Key` of this map is `T::AccountId`.
+		- The `Value` of this map is `Vec<[u8; 32]>`.
+		- The `QueryKind` should be set to `ValueQuery`.
+	*/
+
 	#[pallet::event]
 	#[pallet::generate_deposit(pub(super) fn deposit_event)]
 	pub enum Event<T: Config> {
diff --git a/src/impls.rs b/src/impls.rs
index 05c43d7..e464223 100644
--- a/src/impls.rs
+++ b/src/impls.rs
@@ -26,10 +26,10 @@ impl<T: Config> Pallet<T> {
 		let current_count: u32 = CountForKitties::<T>::get();
 		let new_count = current_count.checked_add(1).ok_or(Error::<T>::TooManyKitties)?;
 
-		/* 🚧 TODO 🚧: `append` the `dna` to the `KittiesOwned` storage for the `owner`. */
-
+		KittiesOwned::<T>::append(&owner, dna);
 		Kitties::<T>::insert(dna, kitty);
 		CountForKitties::<T>::set(new_count);
+
 		Self::deposit_event(Event::<T>::Created { owner });
 		Ok(())
 	}
diff --git a/src/lib.rs b/src/lib.rs
index a92f8e5..9c10069 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -32,11 +32,10 @@ pub mod pallet {
 	#[pallet::storage]
 	pub(super) type Kitties<T: Config> = StorageMap<Key = [u8; 32], Value = Kitty<T>>;
 
-	/* 🚧 TODO 🚧: Create a new `StorageMap` called `KittiesOwned`.
-		- The `Key` of this map is `T::AccountId`.
-		- The `Value` of this map is `Vec<[u8; 32]>`.
-		- The `QueryKind` should be set to `ValueQuery`.
-	*/
+	/// Track the kitties owned by each account.
+	#[pallet::storage]
+	pub(super) type KittiesOwned<T: Config> =
+		StorageMap<Key = T::AccountId, Value = Vec<[u8; 32]>, QueryKind = ValueQuery>;
 
 	#[pallet::event]
 	#[pallet::generate_deposit(pub(super) fn deposit_event)]
diff --git a/src/tests.rs b/src/tests.rs
index e2b802b..1565cfa 100644
--- a/src/tests.rs
+++ b/src/tests.rs
@@ -214,3 +214,16 @@ fn create_kitty_makes_unique_kitties() {
 		assert_eq!(Kitties::<TestRuntime>::iter().count(), 2);
 	})
 }
+
+#[test]
+fn kitties_owned_created_correctly() {
+	new_test_ext().execute_with(|| {
+		// Initially users have no kitties owned.
+		assert_eq!(KittiesOwned::<TestRuntime>::get(1).len(), 0);
+		// Let's create two kitties.
+		assert_ok!(PalletKitties::create_kitty(RuntimeOrigin::signed(ALICE)));
+		assert_ok!(PalletKitties::create_kitty(RuntimeOrigin::signed(ALICE)));
+		// Now they should have two kitties owned.
+		assert_eq!(KittiesOwned::<TestRuntime>::get(1).len(), 2);
+	});
+}