代写COMP6451、代写Python/Java编程

日期：2023-02-25 08:05

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?