olivmath / merkletreers Goto Github PK

View Code? Open in Web Editor NEW

5.0 2.0 1.0 299 KB

🌳 The simple and easy implementation of Merkle Tree

Home Page: https://crates.io/crates/merkletreers

Rust 100.00%

cryptography keccak256 merkle-tree rust ethereum merkle-proof merkle-root merkletreejs merkly

merkletreers's Introduction

🌳 Merkle Tree

The simple and easy implementation of Rust Merkle Tree

Credits
How to install
How it works
How to use
Roadmap
Contributing
License

Credits

How to install

cargo add 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

Before read a code of conduct: CODE_OF_CONDUCT
Follow the guide of development: CONTRIBUTING

License

MIT

merkletreers's People

Contributors

Stargazers

Watchers

Forkers

palinko91

merkletreers's Issues

Bug in leaves

Investigate what happens in a case where there are duplicate sheets in the sheet list

How are the proofs generated?
How is the root generated?

["m","e","r","k","l","e","t","r","e","e","r","s"]

Make Merkle Proof Compatible with

Merkly

Python

from merkly.mtree import MerkleTree
import hashlib


def sha256(x, y):
    data = x + y
    return hashlib.sha256(data).digest()


leaves = ["a", "b", "c", "d", "e", "f", "g", "h"]
tree = MerkleTree(leaves, sha256)
leaf = "a"
proof = tree.proof(leaf)
formatted_proof = [
    {"data": node.data.hex(), "position": node.side.name.lower()} for node in proof
]

assert formatted_proof == [
    {
        "data": "3e23e8160039594a33894f6564e1b1348bbd7a0088d42c4acb73eeaed59c009d",
        "position": "right",
    },
    {
        "data": "bffe0b34dba16bc6fac17c08bac55d676cded5a4ade41fe2c9924a5dde8f3e5b",
        "position": "right",
    },
    {
        "data": "8e2c530a100033894555cde1c7d4e36f7c6e553ee3914022ec7a13e1196baed2",
        "position": "right",
    },
]

MerkleTreeJs

JavaScript

const { MerkleTree } = require('merkletreejs');
const SHA256 = require('crypto-js/sha256');

const leaves = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'].map(x => SHA256(x));
const tree = new MerkleTree(leaves, SHA256);
const leaf = SHA256('a');
const proof = tree.getProof(leaf).map(node => ({ data: node.data.toString('hex'), position: node.position }));

console.log(proof)
[
    {
      data: '3e23e8160039594a33894f6564e1b1348bbd7a0088d42c4acb73eeaed59c009d',
      position: 'right'
    },
    {
      data: 'bffe0b34dba16bc6fac17c08bac55d676cded5a4ade41fe2c9924a5dde8f3e5b',
      position: 'right'
    },
    {
      data: '8e2c530a100033894555cde1c7d4e36f7c6e553ee3914022ec7a13e1196baed2',
      position: 'right'
    }
])

Merkle Proof Verify Compatible

Make Merkle Root Compatible with

Merkly

Python

from merkly.mtree import MerkleTree
import hashlib


def sha256(x, y):
    data = x + y
    return hashlib.sha256(data).digest()


leaves = ["a", "b", "c", "d"]
tree = MerkleTree(leaves, sha256)
root = tree.root.hex()

assert root == "14ede5e8e97ad9372327728f5099b95604a39593cac3bd38a343ad76205213e7"

I tried to help a bit and write a function to verify the leaf with the proof and root, but somewhy it's not working. Even I seen in the proof basically always the first element is the leaf itself so I tried to ignore that in the function, or tried to not, the result is same I'm always getting false, when I should get true. Maybe the proof output is not what should be?

The example code:

use hex;
use merkletreers::merkletree::node::Node;
use merkletreers::merkletree::tree::MerkleTree;
use tiny_keccak::{Hasher, Keccak};

fn hash(a: [u8; 32], b: [u8; 32]) -> [u8; 32] {
    let mut k256 = Keccak::v256();
    let mut res = [0u8; 32];

    k256.update(&a);
    k256.update(&b);
    k256.finalize(&mut res);

    return res;
}

pub fn verify(leaf: &str, proof: &Vec<Node>, root: &str) -> bool {
    let leaf_b: [u8; 32] = hex::decode(leaf).unwrap().try_into().unwrap();
    let root_b: [u8; 32] = hex::decode(root).unwrap().try_into().unwrap();

    let mut proof_b: Vec<[u8; 32]> = Vec::new();
    for i in 0..proof.len() {
        let r = match &proof[i].r {
            None => "None",
            Some(string) => string,
        };

        let l = match &proof[i].l {
            None => "None",
            Some(string) => string,
        };

        if r != "None" && r != leaf {
            let htob: [u8; 32] = hex::decode(r).unwrap().try_into().unwrap();
            proof_b.push(htob);
        }

        if l != "None" && l != leaf {
            let htob: [u8; 32] = hex::decode(l).unwrap().try_into().unwrap();
            proof_b.push(htob);
        }
    }
    println!("Leaf in bytes: {:?}", &leaf_b);
    println!("Root in bytes: {:?}", &root_b);
    println!("Proof in bytes: {:?}", &proof_b);

    let mut computedhash = leaf_b;
    for proofelement in proof_b.into_iter() {
        if computedhash <= proofelement {
            // Hash(current computed hash + current element of the proof)
            computedhash = hash(computedhash, proofelement);
        } else {
            // Hash(current element of the proof + current computed hash)
            computedhash = hash(proofelement, computedhash);
        }
        println!("Computed hash bytes: {:?}", &computedhash);
    }

    computedhash == root_b
}

fn main() {
    let wallet_addresses_to_whitelist = vec![
        "a",
        "b",
        "c",
        "d",
    ];

    let tree = MerkleTree::new(wallet_addresses_to_whitelist.clone());
    let root_hash = &tree.root;
    let leaf = &tree.leafs[0];
    let proof = &tree
        .clone()
        .proof("a");

    println!("The whole tree: \n{:?}\n\n", &tree);
    println!("The root is: \n{:?}\n\n", &root_hash);
    println!("The leaf is: \n{:?}\n\n", &leaf);
    println!("The proof is: \n{:?}\n\n", &proof);

    let verify_result = verify(leaf, proof, root_hash);
    println!("The verify result is: {:?}", verify_result);
}

struct MerkleTree could get #[derive(Debug, Clone, PartialEq, Eq)] similarly like the Node

It would be handy to have these derives, because I tried to do some other actions after getting the .proof() out of the tree but it consumed by the function and I can't clone the tree now so had to generate a new one to write the code further. Thats why I think a clone function could be handy and also Eq and PartialEq because maybe someone else want to compare MerkleTrees in the future.

olivmath / merkletreers Goto Github PK

merkletreers's Introduction

🌳 Merkle Tree

Table of Contents

Credits

How to install

How to works

How to Use

Roadmap

Contributing

License

merkletreers's People

Contributors

Stargazers

Watchers

Forkers

merkletreers's Issues

Make Merkle Proof Compatible with

Make Merkle Root Compatible with

Recommend Projects

Recommend Topics

Recommend Org