辅导COMP0143编程、辅导Python程序
- 首页 >> Algorithm 算法 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:
Q1 Q2 Q3 Q4 Q5 Total
Marks 20 30 15 15 20 100 marks
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.
1
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: The identifier of a transaction input.
tx id: The identifier of the transaction.
sig id: 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.
output id: 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.
2
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]
3
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.
4
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 Docker container.
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.
5
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 > 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 > Settings > Advanced > 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.
6
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.
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:
Q1 Q2 Q3 Q4 Q5 Total
Marks 20 30 15 15 20 100 marks
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.
1
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: The identifier of a transaction input.
tx id: The identifier of the transaction.
sig id: 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.
output id: 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.
2
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]
3
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.
4
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 Docker container.
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.
5
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 > 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 > Settings > Advanced > 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.
6
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.