> ## Documentation Index
> Fetch the complete documentation index at: https://docs.starknet.io/llms.txt
> Use this file to discover all available pages before exploring further.

# Merkle tree contract

A Merkle tree, also known as a hash tree, is a data structure used in cryptography and computer science to verify data integrity and consistency. It is a binary tree where each leaf node represents the cryptographic hash of some data (a transaction for example), and each non-leaf node represents the cryptographic hash of its child nodes. This hierarchical structure allows efficient and secure verification of the data integrity.

Here's a quick summary of how it operates and what functionalities it supports:

### How it works:

1. Leaves Creation:
   * Some data is hashed to create a leaf node.
2. Intermediate Nodes Creation:
   * Pairwise hashes of the leaf nodes are combined and hashed again to create parent nodes.
   * This process continues until only one hash remains, known as the Merkle root.
3. Merkle Root:
   * The final hash at the top of the tree, representing the entire dataset.
   * Changing any single data block will change its corresponding leaf node, which will propagate up the tree, altering the Merkle root.

### Key Features:

1. Efficient Verification:
   * Only a small subset of the tree (the Merkle proof) is needed to verify the inclusion of a particular data block, reducing the amount of data that must be processed.

2. Data Integrity:
   * The Merkle root ensures the integrity of all the underlying data blocks.
   * Any alteration in the data will result in a different root hash.

### Examples of use cases:

1. Fundamental use case: Ethereum blockchain integrity
   * Cryptocurrencies like Ethereum use Merkle trees to efficiently verify and maintain transaction integrity within blocks.
   * Each transaction in a block is hashed to form leaf nodes, and these hashes are recursively combined to form a single Merkle root, summarizing all transactions.
   * The Merkle root is stored in the block header, which is hashed to generate the block's unique identifier.
   * <u>Guaranteed Integrity:</u> Any change to a transaction alters the Merkle root, block header, and block hash, making it easy for nodes to detect tampering.
   * <u>Transaction verification:</u> Nodes can verify specific transactions via Merkle proofs without downloading the entire block.

2. Whitelist inclusion
   * Merkle trees allow efficient whitelist verification without storing the full list on-chain, reducing storage costs.
   * The Merkle root of the whitelist is stored on-chain, while the full list remains off-chain.
   * To verify if an address is on the whitelist, a user provides a Merkle proof and the address. The Merkle root is recalculated using the provided data and compared to the stored on-chain root. If they match, the address is included; if not, it's excluded.

3. Decentralized Identity Verification
   * Merkle trees can be used in decentralized identity systems to verify credentials.
   * Off-chain data: a user's credentials.
   * On-chain data: the Merkle root representing the credentials.

### Visual example

The above diagram represents a merkle tree.\
Each leaf node is the hash of some data.\
Each other node is the hash of the combination of both children nodes.

If we were to `verify{:md}` the `hash 6{:md}`, the merkle proof would need to contain the `hash 5{:md}`, `hash 12{:md}`and `hash 13{:md}`:

1. The `hash 5{:md}` would be combined with the `hash 6{:md}` to re-compute the `hash 11{:md}`.
2. The newly computed `hash 11{:md}` in step 1 would be combined with `hash 12{:md}` to re-compute `hash 14{:md}`.
3. The `hash 13{:md}` would be combined with the newly computed `hash 14{:md}` in step 2 to re-compute the merkle root.
4. We can then compare the computed resultant merkle root with the one provided to the `verify{:md}` function.

### Code

The following implementation is the Cairo adaptation of the [Solidity by Example - Merkle Tree contract](https://solidity-by-example.org/app/merkle-tree/).

```rust theme={null}
#[generate_trait]
pub impl ByteArrayHashTraitImpl of ByteArrayHashTrait {
    fn hash(self: @ByteArray) -> felt252 {
        let mut serialized_byte_arr: Array<felt252> = ArrayTrait::new();
        self.serialize(ref serialized_byte_arr);

        core::poseidon::poseidon_hash_span(serialized_byte_arr.span())
    }
}

#[starknet::interface]
pub trait IMerkleTree<TContractState> {
    fn build_tree(ref self: TContractState, data: Array<ByteArray>) -> Array<felt252>;
    fn get_root(self: @TContractState) -> felt252;
    // function to verify if leaf node exists in the merkle tree
    fn verify(
        self: @TContractState, proof: Array<felt252>, root: felt252, leaf: felt252, index: usize,
    ) -> bool;
}

mod errors {
    pub const NOT_POW_2: felt252 = "Data length is not a power of 2";
    pub const NOT_PRESENT: felt252 = "No element in merkle tree";
}

#[starknet::contract]
pub mod MerkleTree {
    use core::poseidon::PoseidonTrait;
    use core::hash::{HashStateTrait, HashStateExTrait};
    use starknet::storage::{
        StoragePointerWriteAccess, StoragePointerReadAccess, Vec, MutableVecTrait, VecTrait,
    };
    use super::ByteArrayHashTrait;

    #[storage]
    struct Storage {
        pub hashes: Vec<felt252>,
    }

    #[derive(Drop, Serde, Copy)]
    struct Vec2 {
        x: u32,
        y: u32,
    }

    #[abi(embed_v0)]
    impl IMerkleTreeImpl of super::IMerkleTree<ContractState> {
        fn build_tree(ref self: ContractState, mut data: Array<ByteArray>) -> Array<felt252> {
            let data_len = data.len();
            assert(data_len > 0 && (data_len & (data_len - 1)) == 0, super::errors::NOT_POW_2);

            let mut _hashes: Array<felt252> = ArrayTrait::new();

            // first, hash every leaf
            for value in data {
                _hashes.append(value.hash());
            };

            // then, hash all levels above leaves
            let mut current_nodes_lvl_len = data_len;
            let mut hashes_offset = 0;

            while current_nodes_lvl_len > 0 {
                let mut i = 0;
                while i < current_nodes_lvl_len - 1 {
                    let left_elem = *_hashes.at(hashes_offset + i);
                    let right_elem = *_hashes.at(hashes_offset + i + 1);

                    let hash = PoseidonTrait::new().update_with((left_elem, right_elem)).finalize();
                    _hashes.append(hash);

                    i += 2;
                };

                hashes_offset += current_nodes_lvl_len;
                current_nodes_lvl_len /= 2;
            };

            // write to the contract state (useful for the get_root function)
            for hash in _hashes.span() {
                self.hashes.append().write(*hash);
            };

            _hashes
        }

        fn get_root(self: @ContractState) -> felt252 {
            let merkle_tree_length = self.hashes.len();
            assert(merkle_tree_length > 0, super::errors::NOT_PRESENT);

            self.hashes.at(merkle_tree_length - 1).read()
        }

        fn verify(
            self: @ContractState,
            mut proof: Array<felt252>,
            root: felt252,
            leaf: felt252,
            mut index: usize,
        ) -> bool {
            let mut current_hash = leaf;

            while let Option::Some(value) = proof.pop_front() {
                current_hash =
                    if index % 2 == 0 {
                        PoseidonTrait::new().update_with((current_hash, value)).finalize()
                    } else {
                        PoseidonTrait::new().update_with((value, current_hash)).finalize()
                    };

                index /= 2;
            };

            current_hash == root
        }
    }
}
```