Beyond binary Merkle trees: Alice can use a binary Merkle tree to commit to a set of elements = {1, , } so that later she can prove to Bob that some is in using a proof containing at most log hash values. In this question your goal is to explain how to do the same using a 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 its children. a. Suppose = {1, , 9}. Explain how Alice computes a commitment to S using a ternary Merkle tree (i.e. = 3). How can Alice later prove to Bob that 4 is in . b. Suppose contains elements. What is the length of the proof that proves that some is in , as a function of and ? c. For large , what is the proof size overhead of a tree compared to a binary tree? Can you think of any advantage to using a > 2? (Hint: consider computation cost)