COMP6451 T1 2023
Assignment 1
Total Marks: 30
Due: 17:00 March 10, 2023
(All rights reserved - distribution to 3rd parties and/or
placement on non-UNSW websites prohibited.)
Submissions: Submit your solutions as a pdf or text file via the course moodle
page. Your submission must be your individual work - UNSW rules concerning
this will apply (see the Course Outline). Turnitin will be used to perform simi-
larity checks. Use of ChatGPT and other generative AI tools for this assignment
is prohibited. In general, these are short answer questions — aim to keep your
answers brief but precise. Answer all parts, and show your working.
Question 1 (5 marks): (Cryptographic Hash Functions) Consider the
following proposal for a hash function h. Let p be a large prime and let g be
a generator mod p. Represent messages as sequences x= x1, x2, . . . xn where
the xi are numbers mod p. We define the hash of such a message x by h(x) =
gx1+x2+...+xn mod p.
1. (2 marks) Show that this hash function is good for use as a message digest
for error correction purposes, in the sense that it has a high probability of
detecting errors if messages x are transmitted in the form (x, h(x)), and
a message (x, y) that is received is treated as correct if h(x) = y.
In particular, for concreteness, suppose that the messages Alice will be
sending are all of length two (x = x1, x2), and are generated uniformly at
random.
Suppose also that we know that communications channel that we are us-
ing contains occasional bursts of random noise (e.g., from sunspots on
a radio channel) that may potentially damage every bit of the message
(x, h(x), including the hash. When Alice sends a message (x, h(x)), with
probability p, the channel delivers the message to Bob exactly as trans-
mitted. With probability 1 p, the channel delivers to Bob a message
(y, z) selected uniformly at random, where y = y1, y2 and y1, y2, z are all
numbers mod p. (The channel never delivers a message to Bob if Alice
1
did not send a message.) Bob accepts a message (y, z) that he receives as
a correct transmission of a message y from Alice if h(y) = z, and treats it
as corrupted otherwise.
If Bob receives a message and hash (y, z) and accepts it as correct, what
is the probability that y is not the message sent by Alice?
2. (3 marks) Which of the three properties of cryptographic hash functions
(pre-image resistant, second pre-image resistant, and collision-free) are
satisfied by the function h? Explain your answers. In case you say that
the property is satisfied, give reasons to believe that it is. In case you say
that the property is not satisfied, give a proof that that it is not satisfied
(i.e., explain how an attacker could efficiently do what the property says
cannot be done efficiently).
Question 2 (5 marks): (Digital Signatures) Suppose that h is a hash
function taking long messages as input and producing 256 bit outputs and that
M is a long message. Consider the following idea for constructing a signature
scheme:
A private signature key Ks is a pair of randomly generated sequences
x1, ..., x256 and y1, ..., y256, both of length 256, where each value xi and yi
is a 256 bit message.
The corresponding public verification key Kv is the pair of sequences
h(x1), ..., h(x256) and h(y1), ..., h(y256)
To sign message M , where the hash h(M) is the sequence of bits b1...b256,
define sign(M,Ks) = (M, z1...z256) where zi = xi if bi = 0 and zi = yi if
bi = 1.
1. Explain how you could verify this signature is correct: what does the ver-
ification function V (Kv, (M, r1 . . . r256)) do to check that (M, r1 . . . r256)
is message M signed using the signature key corresponding to Kv?
2. Explain why this scheme is secure - why is it hard for an attacker to forge
a signed document that passes the test? Clarify what assumptions on the
hash function are needed for your argument.
3. Is it safe to use the same private key to sign more than one message? If
not, explain what an attacker could do to attack a user who does this.
2
Question 3 (5 marks): (Monetary Supply Laws) One of the ways in
which currencies (both standard and crypto-) differ is in their rules concerning
how money is created. Different rules have different economic consequences
and incentivize users and investors in potentially complex ways. One important
economic metric is the inflation rate, which is the annual rate at which the
cost of goods and services increases. As we have experienced in recent years,
the factors impacting inflation are diverse and unpredictable, and may include
pandemics, wars and catastrophic weather events. However, it is clear that one
of the main reasons for the presently high inflation, and its consequences on
people’s lives, is the amount of new money that was created by central banks
during the pandemic. Central bank doctrine in recent decades has been that
deflation (decreasing cost of goods over time) is bad, because people tend to
hoard money rather than spend, since they know they can buy the same goods
cheaper later, and this causes unemployment as the economy grids to a halt.
On the other hand, nobody likes high inflation when wages are fixed. Many
central banks take the view that 2-3% inflation is socially optimal.
In this question, we focus on the monetary inflation rate r as a proxy1 for
price inflation. For a given period, this rate is defined as r = (M ′ M)/M ,
where M is the amount of money in existence at the start of the period and M ′
is the amount of money in existence at the end of the period.
Cryptocurrencies use a number of rules to determine how much new money
is created per block. In this question , we calculate the consequences for the
monetary inflation rate. Let Ik be the amount of new money issued in the k-
th block, so that I0 is the amount of money issued in the genesis block of the
cryptocurrency. Write Mk for the total amount of money that has been issued
in the first k blocks. That is, Mk = I0 + . . .+ Ik. Thus, the rate of inflation in
the k + 1-th block is rk+1 = (Mk+1 ?Mk)/Mk.
(a) (A Bitcoin-like supply law, with halving) Suppose that I0 = 2
N ,
and
Ik+1 =
{
Ik/2 if Ik > 1
0 otherwise
Write a closed form solution for Mk in terms of N , and use this to derive
an expression for the rate of inflation rk+1 in the k + 1-th block.
(b) (An Ethereum1.0-like supply law) Suppose Ik+1 = c, where c is a
constant. Write a closed form solution for Mk in terms of I0, and use this
to derive an expression for the rate of inflation rk+1 in the k+1-th block.
(c) In case (b), what happens to rk in the limit, as k →∞?
(d) (A supply law that pays interest to savers/stakers) Suppose that
in each period, a fraction S of the total amount of money is saved, and
new money is created by paying interest at a fixed rate R to the savers.
(The interests is a reward for making available the saved money for some
1In practice, population growth means that the cost of goods and services can be increasing
due to increased competition for limited supply, even if the money supply is fixed.
3
socially productive purpose. In “proof of stake” cryptocurrencies, the
savers are the stakers, and the socially productive purpose is the work
done by them to secure the currency.) That is Ik+1 = MkSR. Write
a closed form solution for Mk in terms of I0, and use this to derive an
expression for the rate of inflation rk+1 in the k + 1-th block.
(e) In case (d), what happens to rk in the limit, as k →∞?
(Hint: one of the lecture slides shows an approach to finding a closed form, not
involving a summation, for 1 + x+ x2 + . . .+ xn.)
Question 4 (5 marks): (Wallet Security) The UNSW Forward Thinking
Student Society decides to live up to its name by accepting annual fee payments
from its members in Bitcoin. Since they are not in possession of a hard wallet,
they decide to use a paper wallet, and Sophie, the Society Secretary, uses the
following process:
Sophie points her browser to a https secured webpage, hosted by a rep-
utable Bitcoin exchange, that provides paper wallet production function-
ality. (In order to attract potential customers to their site, the exchange
offers this functionality openly, and does not require users to have an ac-
count with the exchange or to authenticate themselves in order to access
the page.)
Sophie’s browser runs a Javascript function on the webpage that asks the
user to move the mouse as a source of randomness.
The page uses the randomness to generate and display a Bitcoin private
key, public key and address.
Sophie prints this page and puts it into her home safe.
Sophie copies the public key and address, and closes the webpage.
Sophie publishes the address on the Society’s https secured webpage on
CSE servers with the message “pay your annual subscriptions in Bitcoin
to this address, then email us the transaction and output details so we
can use the money”.
In no more than one page, discuss the security risks involved in this process,
by describing at least 5 distinct attacks that an attacker might try to use to
remotely (i.e., without breaking into anyone’s house) steal the Society’s money.
For each, briefly describe (1) the identity and/or the type of attacker, and the
information and capabilities that they have available to them, (2) the cost to
the attacker in terms of money, difficulty, effort and/or computation time, and
(3) what, if anything, Sophie can do to prevent the attack, or mininize the prob-
ability that the attack is successful.
4
Question 5 (5 marks): (Bitcoin Script) A national security agency has
discovered that it can crack the cryptography being used by the enemy if it can
solve the following puzzle for particular 256 bit values N1, N2:
Find two 32 bit numbers x1, x2 such that
x1 < x2 and N1 ≤ h(x2 x1) ≤ N2.
where h is SHA-256. Solving the puzzle requires a very large and costly amount
of computation, and to offload the cost, the agency comes up with a clever
scheme. They pretend to be a philanthropist who is offering a 1 bitcoin donation
to the first person who solves the puzzle. They hope that this will encourage
many people around the world to use their desktop machines to search for a
solution to the puzzle and submit the solution to the blockchain, where the
agency will be able to read it. Describe precisely how they could do this with
a Bitcoin transaction that will pay 1 bitcoin to anyone who solves the puzzle.
Your answer should do the following:
Give the locking script for this transaction.
Give the unlocking script for the transaction.
Show the sequence of stack values for a successful unlocking computation.
Use abstract values such as x1, h(x1) rather than actual numbers.
Mary and Bob both get lucky, and independently solve the puzzle at ex-
actly the same time. Discuss the factors involved in determining who gets
the reward.
Hint: The complete set of Bitcoin Script opcodes is at
https://en.bitcoin.it/wiki/Script
You might find it helpful to use the Bitcoin Script simulator at
https://siminchen.github.io/bitcoinIDE/build/editor.html
to develop your solution. In your answers, use the opcode words rather than
the corresponding numbers. Also follow the convention of omitting the value-
pushing opcodes (that is, write just x instead of OP DATA 1 x).
Question 6 (5 marks): (Bitcoin Protocol & Applications) Alice, Bob,
Carroll and a thousand others live in a remote lithium mining community in
the Australian outback. All the bank branches in the town have recently been
closed, so the community decides to consider adopting Bitcoin as the currency
for all payment transactions within the community. (Since Bitcoin is not widely
adopted in the rest of the country, they will continue to use Australian dollars for
transactions with the rest of the country.) You have been hired as a consultant
to analyse the feasibility of this idea.
Some factors to be taken into consideration are the following:
Lithium is now a hot commodity, so the community is relatively wealthy,
and in particular, everyone has a smart-phone and a fancy computer at
home. However, there is not adequate wealth for the purchase of additional
computing infrastructure in the form of specialised equipment.
5
The community is well served for internal communications by a wireless
network, and everyone has a wireless modem at home. Local mobile calls
are routed using the wireless network.
Communications with the outside world are not good, however. There are
no landlines connecting the community to the outside world (not even tele-
phone lines or electricity cables), and the community network is connected
to the internet only via a satellite communications link. The satellite serv-
ing the community has an orbit that enables the community network to
connect to the rest of the internet only in the first of every four weeks.
That is, the community has 1 week of connectivity, but then is discon-
nected from the internet for three weeks, before it gets its next week of
connectivity, etc.
In no more than one page, taking into the account the factors above, the details
of the Bitcoin protocol as well as economic considerations, write an analysis
of how well (or not) the community’s adoption of Bitcoin can be expected to
function. Consider, in particular, a mode of use in which all community mem-
bers run a Bitcoin full node at home. If any particular difficulties are likely
to arise, explain what these are, and discuss economic, social and/or technical
approaches for dealing with them. On the basis of this analysis, do you recom-
mend that the community adopt Bitcoin?