COMP0143: Cryptocurrencies

Coursework 2

Instructions

●  This assignment is part of the mandatory assessment of the COMP0143:  Cryptocurrencies module and will count 75% towards your final overall mark.

●  Assignment submission is due via Moodle through the TurnItIn interface on January 12, 2022 at 16:00 UK time.  Late submissions will be accepted with deductions according to UCL’s late submission policy.

●  This assignment is open note, open book, and open course resources. Students 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.

●  Students are not allowed to consult other people (outside of course staff) on this work.  Each student has to work on the assignment individually.

●  All questions have to be answers.  Answers will be judged in terms of their quality, the depth of un- derstanding, and also their clarity.   Explain your answers clearly,  but succinctly.   Partial credit may be awarded.   Marks available for each question are  indicated  in square  brackets.   The assignment  has a maximum of 100 marks allocated as follows:

●  For the submission create a single zip archive that contains:

1.  A single  LaTeX  PDF file with your answers created from the provided  LaTeX template.   Only PDF submissions that are typeset with  LaTeX,  e.g., via https://www.overleaf.com/edu/ucl, will be accepted.  Submissions must not include screenshots, e.g., of handwritten solutions or of code, unless explicitly permitted.  Students with disability accommodations are excluded from this requirement.

2.  A single Python3 code file called bitcoin.py that contains your code for Q1 and Q2.  Do not submit files in Jupyter/IPython format!

3.  A single Solidity code file called TicTacToe.sol that contains your code for Q3.

Data  description  for  questions  Q1  and  Q2:  You  are given  a truncated version of the  Bitcoin blockchain, starting from the genesis block and ending at block height 100017.  This is real Bitcoin data,  but the transaction data is simplified and some transactions have been removed or modified. Thus, it does not work to use an external version of the Bitcoin blockchain (e.g., one parsed from an online block explorer), and the code you write for the project would need to be adapted to work on the real Bitcoin blockchain. The data is split across four CSV files, transactions.csv, inputs.csv, outputs.csv, tags.csv, containing different types of identifiers.  The on-chain identifiers would all

be 256-bit hashes in the real Bitcoin data, but for the sake of this assignment identifiers are numeric.

The transactions.csv file contains two columns:

id:    A unique transaction identifier.

block id:    The block in which the transaction appeared.

The inputs.csv file contains four columns:

id: tx id: sig id:

output id:

The identifier of a transaction input.

The identifier of the transaction.

The identifier of the public key associated with this input (i.e., the public key used in the scriptSig). This value is 0 if tx id is a coin generation transaction and − 1 if the transaction is using some non-standard script that does not involve a public key.       The identifier of the UTXO that this input is spending.  This value is − 1 if tx id is a coin generation transaction.

The outputs.csv file contains four columns:

id:    The identifier of a transaction output.

tx id:    The identifier of the transaction.

pk id:    The identifier of the public key associated with this output (i.e., the public key used in the scriptPubKey). This value is − 10 if the transaction is using some non-standard script that does not involve a public key.

value:    The amount being sent to this output (in satoshis).

The tags.csv file contains three columns:

type:    The type of the service (one of Exchange, DarkMarket, Vendor, or Wallet). name:    The name of the (fictional) service.

pk id:    The identifier of the public key that belongs to this service.

Note: To answer questions Q1 and Q2 you are allowed to use the Python 3 Standard Library and the data analysis module pandas.

Question 1:  Bitcoin Blockchain - Basic Analysis [20 marks]

Answer the following questions with respect to the given dataset:

(a)  How many transactions are there in total?  [1 mark]

(b)  How many transactions have one input and one output?  [1 mark]

(c)  How many transactions have one input and two outputs?  [1 mark]

(d)  How many UTXOs are there in total?  [1 mark]                  (e) Which UTXO has the highest associated value?  [1 mark]

(f)  How many distinct public keys were used across all blocks?  [1 mark]

(g) Which public key received the highest number of bitcoins and how many bitcoins did it receive?

[2 marks]

(h) Which public key acted as an output the most number of times and how many times did it act

as output? [2 marks]

(i)  Several of the transactions in the dataset are invalid.  List five of these transactions, identified by their transaction id tx id, along with the reason why they are invalid.  [10 marks]

Question 2:  Bitcoin Blockchain - Cluster and Tagging Analysis [30 marks]

The multi-input heuristic says that public keys used as input to the same transaction are controlled by the same entity.  Assuming there is no mixing or other obfuscation in place, write code to cluster the public keys in the given dataset according to this heuristic.  Use commenting to mark this code clearly in your file.

(a)  How big is the cluster that contains public key (pk id) 41442?  Identify the cluster according to

its keys with the lowest and highest numeric values.  [4 marks]

(b) Which cluster has the largest number of keys, and how many keys does it contain?  Identify it

according to its keys with the lowest and highest numeric values.  [4 marks]

(c) Which cluster controls the most unspent bitcoins, and how many bitcoins does it control? Identify it according to its keys with the lowest and highest numeric values.  [4 marks]

(d) Which transaction is responsible for sending the largest number of bitcoins to the cluster with the most unspent bitcoins, i.e., to one or more of the keys in this cluster?  [4 marks]

(e)  Is this clustering heuristic accurate?  Identify at least one potential source of false positives (keys

that are clustered together but are not actually owned by the same entity) and one source of false negatives (keys that were not clustered together but are owned by the same entity). What strategy could you use to make your clustering heuristic more accurate?  [3 marks]

While clustering  is already a  useful way to gain some  insights  into the  Bitcoin ecosystem, tagging provides a way to learn additionally the real identity of entities and track money as it is transferred between them. Use the tags available in tags.csv to associate both individual keys and larger clusters with (fictional) real entities.  Use commenting to mark this code clearly in your file.

(f) Which tagged entity controls the most unspent bitcoins, and how many bitcoins does it control?

Be careful to consider entities that may control multiple tagged clusters.  [4 marks]

(g)  How many transactions sent bitcoins directly from a (fictional) exchange to a (fictional) dark

market?  How many bitcoins in total were sent across these transactions?  [4 marks]

(h) What are the risks associated with accepting as conclusive the results of this analysis, when a

transaction seems to demonstrate a clear connection between two entities, such as a user and an exchange? What about in the two-hop case (or, more generally, a multi-hop case) where the user sends to one key and then that key sends to an exchange? What strategy could you use to gain further confidence in the results of this analysis?  [3 marks]

Hints:  You do not have to filter out invalid transactions for your analysis.  It is useful to implement the following helper functions: 1) a method cluster(inputs,  key) which returns the cluster of keys corresponding to the given public key key and input data inputs (from inputs.csv) and 2) a method unspent(utxos,  cluster) which returns the amount of unspent BTC of the given cluster cluster and UTXO set utxos.

Question 3:  Solidity - Tic Tac Toe [15 marks]

You are given a decentralized application for a tic-tac-toe game with a backend written in Solidity. The game is not yet functional and your task is to complete it.  Please read the following instructions carefully.

Docker.   To keep setup overheads to a minimum, the entire app is packaged inside a Dockercontainer. To get ready, please install the Docker desktop app on your machine.  It may be helpful to go through the Docker tutorial to get familiar with the tool even though it is not strictly necessary to finish this coursework as all instructions provided here are self-contained. After installing the Docker desktop app, you can start the tutorial container via

docker  run  -d  -p  80:80  docker/getting-started

To view the tutorial browse then to http://localhost:80. The time required to finish it is about 2h.

MetaMask.   The other tool that you need to interact with your decentralized application is the wallet browser extension MetaMask.   Since tic-tac-toe is a two  player game you need two installations of MetaMask, e.g., in two different browsers.  We recommend to use Chrome and Brave.  You can also run it in one browser by creating two different users in Chrome/Brave and by installing MetaMask for each. Afterwards you will need to configure MetaMask to connect to your local test chain.  Ensure you have enabled the option for MetaMask to connect to test chains. This is not graded but is needed as part of the setup.

Running  the  Game.   The smart contract you should complete for this  assignment  is  located  at contracts/TicTacToe.sol.  The missing code snippets are marked with /*Please  complete  the code  here.*/.  In total there are 7 functions that you need to complete:

●   threeInALine() [2 marks]

●   getStatus() [3 marks]

●   checkStatus() [2 marks]

● myTurn() [2 marks]

●  myTurn() [2 marks]

● validMove() [2 marks]

●   validMove() [2 marks]

To set up and play your tic-tac-toe game, you need to:

1.  Install and start the Ganache test chain:

docker  run  -p  8545:8545  -d  trufflesuite/ganache-cli:latest  -g  0 2.  Build the tic-tac-toe game:

docker  build  -t  tic-tac-toe  .

Ensure you run this command from the directory containing the Dockerfile for the project.  Note: This command will fail the first time you execute it because the smart contract is not yet complete and still has some syntax errors.  Hence, your first task is to fix these syntax errors after which you can start the app.  For testing purposes you can temporarily comment out the line RUN  npx hardhat  compile in the Dockerfile which omits compiling the smart contract.  Make sure to re-include it later on otherwise your app will not work!

3.  Start the web server:

docker  run  -p  8080:8080  -d  tic-tac-toe

4.  Browse to http://localhost:8080/ in two separate web browsers, each with its own MetaMask installation and connected to the local test chain.  Follow the instructions on the site to start the game.

Testing and Debugging.

● We provide several test cases to test the basic functions of your contract, which, however, is not complete as you are supposed to test your application through the UI and with MetaMask.

● To check the (incomplete) test results, you can run

docker  run  tic-tac-toe  npm  test

If you like, you are encouraged to extend the tests yourself.

● Our grading script will follow a similar methodology as the test script,  i.e., to test your smart contract and grade based on the test results.

● You can view the output and error messages of MetaMask using the browser developer tools (e.g., Inspect s Console in Brave/Chrome).

● After rebuilding your app and reloading the web UI, MetaMask sometimes complains about invalid nonces.  To resolve this issue you can delete the transaction history by resetting MetaMask via Account s Settings s Advanced s Reset Account.

●  If you are located in China, make sure to connect to the UCL network via a VPN before going through the setup otherwise some steps may fail (like installing packages via npm inside Docker containers).

Submission.   As your solution, please only submit the completed TicTacToe.sol file.

Question 4: Transaction Privacy [15 marks]

The Wasabi wallet is often touted as one of the most widely used privacy-enhancing technologies that builds on top of Bitcoin. It is an open-source and non-custodial Bitcoin wallet that implements trustless Coinjoins to break the link between inputs and outputs of a Bitcoin transaction.

(a)  Imagine a user who runs a single Wasabi wallet. Answer the following questions:  [5 marks]

(i)  How many inputs can they provide to a single Wasabi Coinjoin and how many outputs do they receive?

(ii)  Explain what is a change output, what is a denominator output and why there are several

instances of denominator values.

(iii)  How can a blockchain observer link (at least probabilistically) the inputs of a user to their

change outputs?

(iv)  Identify the denominators and provide three pairs of input combinations and change outputs

for the following Wasabi Coinjoin:                                                                                         https://btc.com/b959570eb6ded08eed1589176319cf836379f0f2d72d94f120e319189af43296

(b)  This question is about anonymity sets.  [5 marks]

(i)  Describe  in your own words what  is the  anonymity set of a transaction’s output  in the context of a Wasabi Coinjoin.

(ii) What is the anonymity set of each denominator for the Wasabi Coinjoin given below, given

that the input combinations to which they correspond have an anonymity set equal to 1 (i.e., they are deposits to the Wasabi wallet)?

(iii) Why are users told to never co-spend change outputs with mixed coins?                (iv)  Identify a user who made a co-spending mistake in the following Wasabi Coinjoin:

https://btc.com/3fe8e0f93914e7567c8c204075ca0d8666be8b2cbc780c1d38ca3b7d6c13a4c5

(c)  Bitcoin’s public, auditable nature allows regulators to trace any arbitrary Bitcoin they would like.

[5 marks]

(i)  Many claim that by tracing Bitcoin, that this makes Bitcoin not fungible.  Do you agree? Explain.

(ii)  Some cryptocurrency exchanges look at only the last n transactions that a coin has been

involved in and won’t accept the coin if one of those transactions involved an address tied to a known drug market (or other illegal activity).  Explain why or why not you think this is a good idea.