Merkle trees. Alice can use a binary Merkle tree to commit to a set of elements S = T,..., Tn, so that later she can prove to Bob that some T is in S using a proof containing at most log n hash values. The binding commitment to the entire S is a single hash value. This question explores generalization to k-ary tree, that is, where every nonleaf node has up to k children. 1. Suppose S Ti,T9. Explain how Alice computes a commitment to S using a ternary Merkle tree (i.e. k= 3). Specify exactly how hash function is applied to what arguments. How can Alice later prove to Bob that T4 is in S? = 2. Suppose S contains n elements. Let the length of the hash function output be X. What is the exact length of the proof that proves that some Ti is in S, as a function of n, k, X? 3. What is the storage requirements for the k-ary tree of n leaves each of size s (and where x is the security parameter)? Discuss storage/proof size trade offs in choosing the arity (i.e. number of children per node) for Merkle trees. 4. If you are given n = 1000 Merkle trees of possibly different sizes and arity, how can you quickly (i.e. in work linear in n) combine them into a single Merkle tree and still be able to prove membership?