# State merkle tree

# What Is Merkle tree?

In cryptography and computer science, a hash tree or Merkle tree is a tree in which every leaf node is labelled with the cryptographic hash of a data block, and every non-leaf node is labelled with the cryptographic hash of the labels of its child nodes. Hash trees allow efficient and secure verification of the contents of large data structures.

Hash trees like Merkle tree structures used by many blockchains try to solve this problem: How can securely store the data? By using the merkle tree we can make sure all the nodes have the same state and store the same data.

# State hash

In Zarb, merkle is used to verify the state of blockchain in each block. The state hash in each block is the hash of two merkle trees: accounts merkle tree and validators merkle tree

In Zarb merkle is used to verify the state of blockchain in each block. The state hash in each block is the hash of two merkle trees: accounts merkle tree and validators merkle tree.

State hash

# Scalability of merkle tree

Using a merkle tree to calculate the state of the blockchain comes with a difficulty: When the number of the accounts are big, calculating the root hash is not easy. On the other hand, a simple Merkle tree is not scalable for calculating the root hash of many accounts.

In Zarb, we solved this problem by using account numbers to calculate the hash of leaf nodes. Each account in Zarb has a dedicated account number. With using that account number we can make sure that the position of the leaf nodes in the merkle tree is always fixed. So we don’t need to rebuild the merkle tree if an account state is changed. We can simply save the previous merkle tree and recalculate the parent hashes by fetching neighbor hashes when it’s needed.

Account tree