Question 1 [25 marks]
(a) Consider an m-ary Merkle tree, i.e., a hash tree where every internal node has up to m ≥ 2
children, over a set of elements S = ft1; : : : ; tng. The hash value for any of these internal nodes
is computed as the hash of the concatenation of all of its children.
(i) Suppose n = 9 and m = 3. How can Alice compute a commitment C to S using such a
ternary Merkle tree? Assuming Bob knows C, how can Alice later prove to Bob that t4 is
in S? Justify your answers. [5 marks]
(ii) What is the length of the proof l that some value ti is in S as a function of parameters n
and m? [4 marks]
(iii) For large n, is it better to use a binary or ternary tree if our goal is to minimize the proof
size? Justify your answer. [5 marks]
(b) Why do Bitcoin blocks include the root hash of a Merkle tree over all transactions in addition to
the full list of transactions? What would be the consequence if this root hash was not included?
(c) What is the purpose of gas in Ethereum? What could go wrong if gas was free? [4 marks]
(d) When the genesis block of Zcash, a privacy-oriented cryptocurrency, was created, the block
header included several details from events taking place on that day. Among those details were
the blockheights and hashes of a Bitcoin block and an Ethereum block that were mined on the
same day. What were those blockheights and hashes? What were the Zcash creators trying to
prove by including these values in the genesis block? [5 marks]
Question 2 [25 marks]
(a) Assume Alice and Bob are competing Bitcoin miners. If they discover blocks nearly simultaneously,
neither of them will have time to hear about the other’s block before broadcasting their own.
What determines whose block will end up in the blockchain permanently? Describe the process.
(b) Explain why ASICs are less helpful to miners in Ethereum than in Bitcoin. [3 marks]
(c) How can a miner establish an identity in a way that is hard to fake and connect it to a real
world entity (e.g., the company operating the miner) so that anyone can tell which blocks were
discovered by that particular miner? [3 marks]
(d) If a miner misbehaves, can other miners boycott the offender on an ongoing basis? If so, how?
If not, why? [3 marks]
(e) In Bitcoin, the difficulty adjustment algorithm uses timestamps that miners place into blocks to
measure the amount of real-world time used to add a batch of 2016 blocks to the longest chain,
and then adjust accordingly the proof-of-work difficulty for the next 2016 blocks.
(i) Suppose miners were free to put whatever timestamps they wanted into blocks. How could
miners use this power to manipulate Bitcoin’s difficulty adjustment algorithm and boost
their rewards? Give a concrete example of an attack. [5 marks]
(ii) Explain the rules that govern block timestamps in the Bitcoin protocol. Cite the source(s)
you used to answer this question; just URLs are fine. [3 marks]
(iii) Discuss to what extent the rules in (ii) mitigate the attack(s) that you described in (i).
EasyDue™ 支持PayPal, AliPay, WechatPay, Taobao等各种付款方式!
E-mail: firstname.lastname@example.org 微信:easydue