Q3. Merkle Tree (13 points] Consider a Merkle tree shown below to store the list of 8 records: $$Name$$, Fatima, Ahmad, Hessa, Khalid. Nayef, Huda, and Noor. a. [7 points] What is the root hash value and hash value stored in each of the shown nodes 1-7. $$Names Fatima Root Hash Ahmad Hessa Khalid Nayef Huda Noor Hash value Node ID Root Hash 4 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" (1.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 OG For a general Merkle tree storing N records, validating proof of membership takes time. Q3. Merkle Tree (13 points] Consider a Merkle tree shown below to store the list of 8 records: $$Name$$, Fatima, Ahmad, Hessa, Khalid. Nayef, Huda, and Noor. a. [7 points] What is the root hash value and hash value stored in each of the shown nodes 1-7. $$Names Fatima Root Hash Ahmad Hessa Khalid Nayef Huda Noor Hash value Node ID Root Hash 4 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" (1.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 OG For a general Merkle tree storing N records, validating proof of membership takes time
