Bitcoin and Cryptocurrency Tech. exercise

Alice can use a binary Merkle tree to commit to a set of elements S- (Ti, .., T so that later she can prove to Bob that some T is in S using a proof containing at most [log2n hash values. In this question your goal is to explain how to do the same using a k-ary tree, that is, where every non-leaf node has up to k 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 S- {T1, ..xpin how Alice computes a commitment to S using a ternary Merkle tree (i.e. k-3). Draw and label the nodes in this Merkle tree. How can Alice later prove to Bob that Ta is in S? (i.e. the nodes Alice has to provide as proof) b. Suppose S contains n elements. What is the length of the proof that proves that some Ti is in S, as a function of n and k? For large n, what is the proof size of a 3-ary tree compared to a binary tree (in terms of n)? c. d. Can you think of any advantage to using a k > 2? (Hint: consider computation cost) Alice can use a binary Merkle tree to commit to a set of elements S- (Ti, .., T so that later she can prove to Bob that some T is in S using a proof containing at most [log2n hash values. In this question your goal is to explain how to do the same using a k-ary tree, that is, where every non-leaf node has up to k 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 S- {T1, ..xpin how Alice computes a commitment to S using a ternary Merkle tree (i.e. k-3). Draw and label the nodes in this Merkle tree. How can Alice later prove to Bob that Ta is in S? (i.e. the nodes Alice has to provide as proof) b. Suppose S contains n elements. What is the length of the proof that proves that some Ti is in S, as a function of n and k? For large n, what is the proof size of a 3-ary tree compared to a binary tree (in terms of n)? c. d. Can you think of any advantage to using a k > 2? (Hint: consider computation cost)