Question 1

Suppose a hash function H(x,y) whose range is {0,1,…,2n-1}, can be used for a proof of work scheme. Once an x and a target threshold t are published, the miners need to find a y such that H(x,y)< t. Suppose that x, and y are both m-bit binary strings and consider the hash function

Here ⊕ denotes a bit-wise xor. Show that this H is insecure as a proof of work hash. In particular, suppose t is fixed ahead of time. Show that a clever attacker can find a solution y with minimal effort once x is published. Hint: the attacker can do precomputation before x is published.

Question 2

One can use a binary Merkle tree to commit to a list of elements so that later he can prove that using a Merkle proof containing at most hash values. The binding commitment to is a single hash value. Evaluate and explain how to do the same using a -ary tree, that is, where every non-leaf node has up to children. The hash value for every non-leaf node is computed as the hash of the concatenation of the values of all its children.