COMP0143: Cryptocurrencies Coursework 1
COMP0143: Cryptocurrencies Coursework 1 (Resit)
University College London
Released: August 8, 2022
Due: August 29, 2022 at 16:00 UK time
1. This assignment is part of the mandatory assessment of the COMP0143: Cryptocurrencies module and will count 25% towards your final overall mark.
2. Assignment submission is due via Moodle through the TurnItIn interface on August 29, 2022 at 16:00 UK time. Late submissions will be accepted with deductions according to UCL’s late submission policy.
3. Only PDF submissions that are typeset with LaTeX will be accepted, with the exception of students with disability accommodation.
4. This assignment is open note, open book, and open course resources. You must identify sources as accurately and fully as possible. UCL plagiarism policies will be strictly enforced. For more details, see http://www.ucl.ac.uk/current-students/guidelines/plagiarism.
5. You are not allowed to consult other people (outside of course staff) on this work. Each student has to work on the assignment individually.
6. Your answers will be judged in terms of their quality, the depth of understanding, and also their brevity. Explain your answers clearly, but succinctly. Partial credit may be awarded.
7. The assignment has a maximum of 100 marks allocated as follows:
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 = {t1, . . . , tn}. The hash value for any of these internal nodes is computed as the hash of the concatenation of all of its children.
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]
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]
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? [2 marks]
(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]
2
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. [3 marks]
(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).
[5 marks]
Question 3 [25 marks]
(a) For each of the following cryptocurrency clients describe briefly (i.e., in at most two to three sentences) their properties and how they operate.
(i) Miners [2 marks] (ii) Full nodes [2 marks]
(iii) SPV nodes [2 marks] (iv) Seed nodes [2 marks]
(b) Assume Bob runs a super lightweight client which stores only the header of the most recent block in the Bitcoin blockchain.
(i) If Alice wants to send money to Bob, what information must she include to prove to him that her payment has been included in the blockchain? [4 marks]
(ii) If Alice’s payment was included in a block k blocks before the current header and there are n transactions per block, how many bytes does the proof require in terms of k and n? Compute the concrete proof size for k = 8 and n = 256. [5 marks]
(iii) One proposal is to add an extra field into block headers that points to the last block with a smaller hash value than the current one. Explain how this can be used to reduce the proof size. What is the expected size in bytes and in terms of its big-O complexity of a proof in terms of k and n? What are the best- and worst-case sizes? [8 marks]
Question 4 [25 marks]
Alice is planning a backpacking trip and worries that her mobile phone with her cryptocurrency wallet keys might get stolen. She investigates possible solutions to keep her funds safe.
(a) Alice comes up with the idea to store her bitcoins in such a way that they can be redeemed by proving knowledge of a password. Accordingly, she stores them in the following ScriptPubKey address:
OP SHA256 ff03fc3d437f6e4f4e492e52394f447cc5cdbc499d765d57e7c633457b630068 OP EQUAL
Write a ScriptSig script that will successfully redeem the above transaction given the password and show the contents of the stack after each operation of the script. [4 marks]
(b) Assume Alice chooses an 8-digit pin. Explain why her bitcoins can be stolen soon after the UTXOs are posted to the blockchain. [2 marks]
(c) Suppose Alice chooses a diceware-generated passphrase consisting of 10 words (for more details on diceware passphrases see https://en.wikipedia.org/wiki/Diceware). Is the ScriptPubKey above then a secure way to protect her bitcoins? Why or why not? [5 marks]
(d) Can you design another passphrase-based mechanism allowing Alice to manage her bitcoins se- curely? Explain briefly how your system works and what its potential advantages are in comparison to the above ScriptPubKey procedure. Does your system have any disadvantages? [7 marks]
(e) Alice’s best friend Claire, a cryptocurrency enthusiast, recommends Alice to use a 2-of-3 multisig wallet and offers to help her set things up. Briefly describe the functionality of such a wallet and its advantages and how a secure setup could look like. Provide ScriptPubKey and ScriptSig script entries to access Alice’s funds. [7 marks]
