Q3. Merkle Tree [13 points) Consider a Merkle tree shown below to store the list of 8 records: 35Name$S, Fatima, Ahmad, Hessa, Khalid, Nayef, Huda, and Noor. a. 17 points) What is the root hash value and hash value stored in each of the shown nodes 1-7. (In producing the parent hash value from its children, hash a concatenated value of the children nodes where the top nodes annears first) Fatima Root Hash IIIII Ahmad Hessa Khalid Nayef Huda Noor Hash value Node ID Root Hash b. [2 points) Which of the 16 hash values (including the root hash) of this tree need(s) to be changed by someone who is trying to tamper with the record Fatima without being detected? c. [2 pointsIf you maintain the Root Hash of the tree on your computer and store the tree data on an untrusted server. The types of queries that you send the server are of the form: "Does record X exist in the database?" Whenever the series answers "Yes" (ie the record exists), you want the server to also send a proof that the record excists (.e. the server is not cheating by saying yes if the record does not exist). What would be the proof that the server needs to send (set of node hash values) when he answer the proof data sent by the server? d. [2 points) Complete the following sentence by filling the blank: For a general Merkle tree storing For a general Merkle tree storing records, the size of a proof would be records, validating proof of membership takes OC time. Q3. Merkle Tree [13 points) Consider a Merkle tree shown below to store the list of 8 records: 35Name$S, Fatima, Ahmad, Hessa, Khalid, Nayef, Huda, and Noor. a. 17 points) What is the root hash value and hash value stored in each of the shown nodes 1-7. (In producing the parent hash value from its children, hash a concatenated value of the children nodes where the top nodes annears first) Fatima Root Hash IIIII Ahmad Hessa Khalid Nayef Huda Noor Hash value Node ID Root Hash b. [2 points) Which of the 16 hash values (including the root hash) of this tree need(s) to be changed by someone who is trying to tamper with the record Fatima without being detected? c. [2 pointsIf you maintain the Root Hash of the tree on your computer and store the tree data on an untrusted server. The types of queries that you send the server are of the form: "Does record X exist in the database?" Whenever the series answers "Yes" (ie the record exists), you want the server to also send a proof that the record excists (.e. the server is not cheating by saying yes if the record does not exist). What would be the proof that the server needs to send (set of node hash values) when he answer the proof data sent by the server? d. [2 points) Complete the following sentence by filling the blank: For a general Merkle tree storing For a general Merkle tree storing records, the size of a proof would be records, validating proof of membership takes OC time
