Q3. Merkle Tree (13 points) Consider a Merkle tree shown below to store the list of 8 records: Islam, 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. (In producing the parent hash value from its children, hash a concatenated value of the children nodes where the top nodes appears first) Islam Fatima Ahmad Root Hash 10 11 Hessa Khalid 12 w Nayef Huda 15 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 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 of For a general Merkle tree storing N records, validating proof of membership takes od time. Q2. List with Hash Pointers [7 points] The linked list below uses hash pointers. Each item in this list has three fields: ID, previous item ID, previous node hash, and data. To hash a block, the fields are concatenated in the same order. For example, to hash the block with ID=4, the following value is hashed (after replacing ??? with the right Prex Hash value): 43???Hessa a. [4 points) Fill the missing hash values for this list (replace ??? by the appropriate value) Head Pointer: Head Hash: 4 ??? ID 3 Prey Hash ??? Data Hessa 2 Pres: ID Prey Hash Data Ahmad ID Pres: ID Prey Hash Data 1 ??? Fatima Pres: ID Prey Hash Data = null Islam Q3. Merkle Tree (13 points) Consider a Merkle tree shown below to store the list of 8 records: Islam, 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. (In producing the parent hash value from its children, hash a concatenated value of the children nodes where the top nodes appears first) Islam Fatima Ahmad Root Hash 10 11 Hessa Khalid 12 w Nayef Huda 15 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 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 of For a general Merkle tree storing N records, validating proof of membership takes od time. Q2. List with Hash Pointers [7 points] The linked list below uses hash pointers. Each item in this list has three fields: ID, previous item ID, previous node hash, and data. To hash a block, the fields are concatenated in the same order. For example, to hash the block with ID=4, the following value is hashed (after replacing ??? with the right Prex Hash value): 43???Hessa a. [4 points) Fill the missing hash values for this list (replace ??? by the appropriate value) Head Pointer: Head Hash: 4 ??? ID 3 Prey Hash ??? Data Hessa 2 Pres: ID Prey Hash Data Ahmad ID Pres: ID Prey Hash Data 1 ??? Fatima Pres: ID Prey Hash Data = null Islam
