Merkle-trees is a "mode of operation" for hash functions. They allow to construct a hash function that takes as input a value a large value using a hash function that accepts much smaller input:s Consider for example a CRHF Hu: {0,1)2n'h {0,1)", using Merkle trees one can design a hash function H,: (0,1)2-(0, 1)" for some fixed positive integer h. The Merkle-tree construction is a binary tree of depth h constructed as follows: for every n-bit input block xi2x2h we define the parent of two nodes to have value H,(a.b) where a and b are the values of the parent's two children. Then, the root node has value y-H, (xi.X2). Also, order of inputs matters when hashing up the tree, i.e. it should always be Hia I| b) where "a" is the left side child and "b" is the right side child. a. Show that if an adversary can find a collision for H then can find a collision for H (i.e. prove that H is collision resistant assuming His collision resistant.) *1 T2 T3 T5 T6 Merkle-trees is a "mode of operation" for hash functions. They allow to construct a hash function that takes as input a value a large value using a hash function that accepts much smaller input:s Consider for example a CRHF Hu: {0,1)2n'h {0,1)", using Merkle trees one can design a hash function H,: (0,1)2-(0, 1)" for some fixed positive integer h. The Merkle-tree construction is a binary tree of depth h constructed as follows: for every n-bit input block xi2x2h we define the parent of two nodes to have value H,(a.b) where a and b are the values of the parent's two children. Then, the root node has value y-H, (xi.X2). Also, order of inputs matters when hashing up the tree, i.e. it should always be Hia I| b) where "a" is the left side child and "b" is the right side child. a. Show that if an adversary can find a collision for H then can find a collision for H (i.e. prove that H is collision resistant assuming His collision resistant.) *1 T2 T3 T5 T6