Q3. Merkdo Tree [13 points) Consider a Merkle tree shown below to store the list of 8 records SSNemess, Fatima, Ahmad, Hesia Khalid, Nayef, Hada, and Noo 17 points) What is the root hash value and hash value stored in each of the shown nodes 1-7. SSNamess Fatima Root Hash Ahmad Hessa Khalid Nayel 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? 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 points) If 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 servers answers "Yes" (i.e. the record exists), you want the server to also send a proof that the record exists (i.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 question "Does the record Fatima exist in the database?" How would we validate the answer using the proof data sent by the server? d. (2 points] Complete the following sentence by filling the blank: For a general Merkle tree storing N records, the size of a proof would be ( For a general Merkle tree storing N records, validating proof of membership takes of time. Q3. Merkdo Tree [13 points) Consider a Merkle tree shown below to store the list of 8 records SSNemess, Fatima, Ahmad, Hesia Khalid, Nayef, Hada, and Noo 17 points) What is the root hash value and hash value stored in each of the shown nodes 1-7. SSNamess Fatima Root Hash Ahmad Hessa Khalid Nayel 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? 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 points) If 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 servers answers "Yes" (i.e. the record exists), you want the server to also send a proof that the record exists (i.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 question "Does the record Fatima exist in the database?" How would we validate the answer using the proof data sent by the server? d. (2 points] Complete the following sentence by filling the blank: For a general Merkle tree storing N records, the size of a proof would be ( For a general Merkle tree storing N records, validating proof of membership takes of time
