Exercise 1: Given a set of data D, construct a Merkle Tree.
Assume that D is a power of 2 (the binary tree is perfect).
Example input: D = [A1, A2, A3, A4]
Example output:
Root
┌──────────┐
│ H7 │
│ H(H5|H6) │
┌────────┴──────────┴──────────┐
│ │
│ │
┌────┴─────┐ ┌─────┴────┐
│ H5 │ │ H6 │
│ H(H1|H2) │ │ H(H3|H4) │
└─┬─────┬──┘ └─┬──────┬─┘
│ │ │ │
┌─────────┴┐ ┌┴─────────┐ ┌────────┴─┐ ┌─┴────────┐
│ H1 │ │ H2 │ │ H3 │ │ H4 │
│ H(A1) │ │ H(A2) │ │ H(A3) │ │ H(A4) │
└───┬──────┘ └────┬─────┘ └────┬─────┘ └────┬─────┘
│ │ │ │
A1 A2 A3 A4
Exercise 1b: Write a function that will verify a given set of data with a given root hash.
Exercise 2: Write a function that will use a proof like the one in Exercise 3 to verify that the proof is indeed correct.
Exercise 3 (Hard): Write a function that returns a proof that a given data is in the tree.
Hints:
- The proof should be a set of ordered data hashes and their positions (left 0 or right 1).
- Let's say we are asked to prove that H3 (A3) is in this tree. We have the entire tree so we can traverse it and find H3.
Then we only need to return the hashes that can be used to calculate with the hash of the given data to calculate the root hash.
i.e Given a data H3, a proof [(1, H4), (0, H5)] and a root:
H3|H4 => H6 => H5|H6 => H7 = root
*/ #![allow(dead_code)] #![allow(unused_variables)] use sha2::Digest;
pub type Data = Vec; pub type Hash = Vec;
pub struct MerkleTree { // ??? }
/// Which side to put Hash on when concatinating proof hashes #[derive(Debug, Clone, Copy, PartialEq)] pub enum HashDirection { Left, Right, }
#[derive(Debug, Default)] pub struct Proof<'a> { /// The hashes to use when verifying the proof /// The first element of the tuple is which side the hash should be on when concatinating hashes: Vec<(HashDirection, &'a Hash)>, }
impl MerkleTree { /// Gets root hash for this tree pub fn root(&self) -> Hash { todo!("For tests to work") }
/// Constructs a Merkle tree from given input data
pub fn construct(input: &[Data]) -> MerkleTree {
todo!("Exercise 1")
}
/// Verifies that the given input data produces the given root hash
pub fn verify(input: &[Data], root_hash: &Hash) -> bool {
todo!("Exercise 1b")
}
/// Verifies that the given data and proof_path correctly produce the given root_hash
pub fn verify_proof(data: &Data, proof: &Proof, root_hash: &Hash) -> bool {
todo!("Exercise 2")
}
/// Returns a list of hashes that can be used to prove that the given data is in this tree
pub fn prove(&self, data: &Data) -> Option<Proof> {
todo!("Exercise 3")
}
}
fn hash_data(data: &Data) -> Hash { sha2::Sha256::digest(data).to_vec() }
fn hash_concat(h1: &Hash, h2: &Hash) -> Hash { let h3 = h1.iter().chain(h2).copied().collect(); hash_data(&h3) }
#[cfg(tests)] mod tests { use super::*;
fn example_data(n: usize) -> Vec<Data> {
let mut data = vec![];
for i in 0..n {
data.push(vec![i as u8]);
}
data
}
#[test]
fn test_constructions() {
let data = example_data(4);
let tree = MerkleTree::construct(&data);
let expected_root = "9675e04b4ba9dc81b06e81731e2d21caa2c95557a85dcfa3fff70c9ff0f30b2e";
assert_eq!(hex::encode(tree.root()), expected_root);
let data = example_data(3);
let tree = MerkleTree::construct(&data);
let expected_root = "773a93ac37ea78b3f14ac31872c83886b0a0f1fec562c4e848e023c889c2ce9f";
assert_eq!(hex::encode(tree.root()), expected_root);
let data = example_data(8);
let tree = MerkleTree::construct(&data);
let expected_root = "0727b310f87099c1ba2ec0ba408def82c308237c8577f0bdfd2643e9cc6b7578";
assert_eq!(hex::encode(tree.root()), expected_root);
}
}
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent