Merkle trees

A Merkle tree is a tree consisting of leaves and nodes. Each non-leaf node is defined with a value or a label and contains a hash of its children. This builds a hash tree, where the root of the tree is a value distributed by a trusted-third party, used to provide a verification of large-scale data structures. Competing teams need to understand the concept of Merkle trees, calculate certain hash values, and finally compute a signature in a hash-based tree construction.

An online server for saving users' files, uses Merkle tree structures to store values related to specific documents. We know that this server uses the hash function SHA-256 for hashing the nodes. The files, which are represented by the nodes, are marked with a unique number, in order to make the hashing procedure easier (so we don’t have to hash the whole file, but the corresponding number to the file). Given the figure below(see artifacts -> merkle.png), the public root node:

R= 8b80cda3f604e6406501a427e4ee699a2b33bd30a0ee0c05e3c406cee667c570 

Task 1: Check whether the values 24 and 593 belong in the files' numbers.

Task 2: Compute the value H5678.

Task 3: Signature Generation:

Assume a simplified signature generation scheme using Merkle trees and One Time Signatures, where a signature on a message m has the following format:

    Sig(m) = (H(m)|| pub_key || auth_path)

with pub_key = H_i, i={1,...,8} the leave node and auth_path is the authentication path of sibling nodes starting from the chosen public key. Generate the signature of the message {ECSC2019 challenges are fun} using H1 as public key.