use super::hash::{Hashable, H256};
#[derive(Debug, Default, Clone)]
struct MerkleTreeNode {
Copyright By PowCoder代写 加微信 powcoder
left: Option
right: Option
hash: H256,
/// A Merkle tree.
#[derive(Debug, Default)]
pub struct MerkleTree {
root: MerkleTreeNode,
level_count: usize, // how many levels the tree has
/// Given the hash of the left and right nodes, compute the hash of the parent node.
fn hash_children(left: &H256, right: &H256) -> H256 {
unimplemented!();
/// Duplicate the last node in `nodes` to make its length even.
fn duplicate_last_node(nodes: &mut Vec
impl MerkleTree {
pub fn new
assert!(!data.is_empty());
// create the leaf nodes:
let mut curr_level: Vec
// create the upper levels of the tree:
while curr_level.len() > 1 {
// Whenever a level of the tree has odd number of nodes, duplicate the last node to make the number even:
if curr_level.len() % 2 == 1 {
duplicate_last_node(&mut curr_level); // TODO: implement this helper function
assert_eq!(curr_level.len() % 2, 0); // make sure we now have even number of nodes.
let mut next_level: Vec
pub fn root(&self) -> H256 {
unimplemented!()
/// Returns the of data at index i
pub fn proof(&self, index: usize) -> Vec
unimplemented!()
/// Verify that the datum hash with a vector of proofs will produce the Merkle root. Also need the
/// index of datum and `leaf_size`, the total number of leaves.
pub fn verify(root: &H256, datum: &H256, proof: &[H256], index: usize, leaf_size: usize) -> bool {
unimplemented!()
#[cfg(test)]
mod tests {
use crate::crypto::hash::H256;
use super::*;
macro_rules! gen_merkle_tree_data {
(hex!(“0a0b0c0d0e0f0e0d0a0b0c0d0e0f0e0d0a0b0c0d0e0f0e0d0a0b0c0d0e0f0e0d”)).into(),
(hex!(“0101010101010101010101010101010101010101010101010101010101010202”)).into(),
fn root() {
let input_data: Vec
let merkle_tree = MerkleTree::new(&input_data);
let root = merkle_tree.root();
assert_eq!(
(hex!(“6b787718210e0b3b608814e04e61fde06d0df794319a12162f287412df3ec920”)).into()
// “b69566be6e1720872f73651d1851a0eae0060a132cf0f64a0ffaea248de6cba0” is the hash of
// “0a0b0c0d0e0f0e0d0a0b0c0d0e0f0e0d0a0b0c0d0e0f0e0d0a0b0c0d0e0f0e0d”
// “965b093a75a75895a351786dd7a188515173f6928a8af8c9baa4dcff268a4f0f” is the hash of
// “0101010101010101010101010101010101010101010101010101010101010202”
// “6b787718210e0b3b608814e04e61fde06d0df794319a12162f287412df3ec920” is the hash of
// the concatenation of these two hashes “b69…” and “965…”
// notice that the order of these two matters
fn proof() {
let input_data: Vec
let merkle_tree = MerkleTree::new(&input_data);
let proof = merkle_tree.proof(0);
assert_eq!(proof,
vec![hex!(“965b093a75a75895a351786dd7a188515173f6928a8af8c9baa4dcff268a4f0f”).into()]
// “965b093a75a75895a351786dd7a188515173f6928a8af8c9baa4dcff268a4f0f” is the hash of
// “0101010101010101010101010101010101010101010101010101010101010202”
fn verifying() {
let input_data: Vec
let merkle_tree = MerkleTree::new(&input_data);
let proof = merkle_tree.proof(0);
assert!(verify(&merkle_tree.root(), &input_data[0].hash(), &proof, 0, input_data.len()));
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com