9 releases (2 stable)

1.2.0 Feb 6, 2024
1.0.0 Feb 6, 2024
0.4.1 Oct 16, 2022
0.3.1 Oct 13, 2022
0.1.0 Oct 3, 2022

#4 in #keccak256

MIT license

250KB
213 lines

🌳 Merkle Tree

The simple and easy implementation of Rust Merkle Tree


Build Test Crates.io

GitHub last commit GitHub commit activity

Crates.io

Table of Contents

Credits

GitHub Contributors Image

How to install

# Cargo.toml

[dependencies]
merkletreers = "*"

How to works

  • We use keccak-256 under-the-hood

This library provides a clean and easy to use implementation of the Merkle Tree with the following features:

  • Create Leaf
  • Create Root
  • Create Proof
  • Verify Proof

How to Use

Create a Merkle Tree

use merkletreers::tree::MerkleTree;
use merkletreers::utils::hash_it;

// Hash each element of leaves to convert into a [u8;32]
let leaves = ["a", "b", "c", "d", "e"]
    .iter()
    .map(|data| {
        let mut buffer = [0u8; 32];
        hash_it(data.as_bytes(), &mut buffer);
        buffer
    })
    .collect::<Vec<[u8; 32]>>();

// Create our Merkle tree
let tree = MerkleTree::new(leaves);

Create a Root

use merkletreers::tree::MerkleTree;
use merkletreers::utils::hash_it;

// Hash each element of leaves to convert into a [u8;32]
let leaves = ["a", "b", "c", "d", "e"]
    .iter()
    .map(|data| {
        let mut buffer = [0u8; 32];
        hash_it(data.as_bytes(), &mut buffer);
        buffer
    })
    .collect::<Vec<[u8; 32]>>();

// Create our Merkle tree
let tree = MerkleTree::new(leaves);

// Create our Merkle Root
let root = tree.root;
assert_eq!(
    root,
    [
        29, 208, 210, 166, 174, 70, 109, 102, 92, 178, 110, 26, 49, 240, 124, 87, 174, 93, 247,
        210, 188, 85, 156, 213, 130, 109, 65, 123, 233, 20, 26, 93
    ]
);

Create Proof of a leaf

use merkletreers::node::{Node, Side};
use merkletreers::tree::MerkleTree;
use merkletreers::utils::hash_it;

// Hash each element of leaves to convert into a [u8;32]
let leaves = ["a", "b", "c", "d", "e"]
    .iter()
    .map(|data| {
        let mut buffer = [0u8; 32];
        hash_it(data.as_bytes(), &mut buffer);
        buffer
    })
    .collect::<Vec<[u8; 32]>>();

// Create our Merkle tree
let tree = MerkleTree::new(leaves);

// Create our Merkle Root
let root = tree.root;
assert_eq!(
    root,
    [
        29, 208, 210, 166, 174, 70, 109, 102, 92, 178, 110, 26, 49, 240, 124, 87, 174, 93, 247,
        210, 188, 85, 156, 213, 130, 109, 65, 123, 233, 20, 26, 93
    ]
);

// Create your Merkle Proof for 'c' element
// First we need hash element to convert into a [u8; 32]
let mut leaf = [0u8; 32];
hash_it("c".as_bytes(), &mut leaf);
let proof = tree.make_proof(leaf);
assert_eq!(
    vec![
        Node {
            data: [
                241, 145, 142, 133, 98, 35, 110, 177, 122, 220, 133, 2, 51, 47, 76, 156, 130,
                188, 20, 225, 155, 252, 10, 161, 10, 182, 116, 255, 117, 179, 210, 243
            ],
            side: Side::RIGHT
        },
        Node {
            data: [
                128, 91, 33, 216, 70, 177, 137, 239, 174, 176, 55, 125, 107, 176, 210, 1, 179,
                135, 42, 54, 62, 96, 124, 37, 8, 143, 2, 91, 12, 106, 225, 248
            ],
            side: Side::LEFT
        },
        Node {
            data: [
                168, 152, 44, 137, 216, 9, 135, 251, 154, 81, 14, 37, 152, 30, 233, 23, 2, 6,
                190, 33, 175, 60, 142, 14, 179, 18, 239, 29, 51, 130, 231, 97
            ],
            side: Side::RIGHT
        }
    ],
    proof
);

Verify Proof of a leaf

use merkletreers::node::{Node, Side};
use merkletreers::tree::MerkleTree;
use merkletreers::utils::hash_it;


// Hash each element of leaves to convert into a [u8;32]
let leaves = ["a", "b", "c", "d", "e"]
    .iter()
    .map(|data| {
        let mut buffer = [0u8; 32];
        hash_it(data.as_bytes(), &mut buffer);
        buffer
    })
    .collect::<Vec<[u8; 32]>>();

// Create our Merkle tree
let tree = MerkleTree::new(leaves);

// Create our Merkle Root
let root = tree.root;
assert_eq!(
    root,
    [
        29, 208, 210, 166, 174, 70, 109, 102, 92, 178, 110, 26, 49, 240, 124, 87, 174, 93, 247,
        210, 188, 85, 156, 213, 130, 109, 65, 123, 233, 20, 26, 93
    ]
);

// Create your Merkle Proof for 'c' element
// First we need hash element to convert into a [u8; 32]
let mut leaf = [0u8; 32];
hash_it("c".as_bytes(), &mut leaf);
let proof = tree.make_proof(leaf);
assert_eq!(
    vec![
        Node {
            data: [
                241, 145, 142, 133, 98, 35, 110, 177, 122, 220, 133, 2, 51, 47, 76, 156, 130,
                188, 20, 225, 155, 252, 10, 161, 10, 182, 116, 255, 117, 179, 210, 243
            ],
            side: Side::RIGHT
        },
        Node {
            data: [
                128, 91, 33, 216, 70, 177, 137, 239, 174, 176, 55, 125, 107, 176, 210, 1, 179,
                135, 42, 54, 62, 96, 124, 37, 8, 143, 2, 91, 12, 106, 225, 248
            ],
            side: Side::LEFT
        },
        Node {
            data: [
                168, 152, 44, 137, 216, 9, 135, 251, 154, 81, 14, 37, 152, 30, 233, 23, 2, 6,
                190, 33, 175, 60, 142, 14, 179, 18, 239, 29, 51, 130, 231, 97
            ],
            side: Side::RIGHT
        }
    ],
    proof
);

// Verify our Merkle Proof for 'c' element
let result = tree.check_proof(proof, leaf);
assert_eq!(result, root);

Roadmap

Feature Status Priority
Create Root 🔥
Create Proof 🔥
Verify Proof 🔥
Compatible with MerkleTreeJs 🔥
Compatible with Merkly 🔥
Leafs of any size 🧐
Use any Hash function 🧐

Contributing

License

MIT

Dependencies