SEEM5770/ECLT5840-无代写-Assignment 3
时间:2022-11-29
The Chinese University of Hong Kong
Department of Systems Engineering and Engineering
Management
SEEM5770/ECLT5840 Open Systems/Electronic
Commerce
2022-23 Assignment 3: Transaction and Bitcoin
This assignment is for understanding transaction and bitcoin, which is worth
of 14% of the unit’s assessment. The due for the assignment 3 is 11:59pm
on December 2, 2022. You need to put down your student id and your name
when you submit your assignment. A soft-copy submission is required to be
submitted to the online eLearning system. Note that we do not have much time
before the final exam, and we plan to give you correct answer before the final
exam.
Late submission is not allowed.
The questions in this assignment ask for explanations. Answer all the questions.
The explanations should be concise descriptions of your understanding. You
should clearly show all the formulas you use, and all the steps followed to get
your answers.1
Question 1: We discussed transaction, in particular, schedule and concur-
rency control by locking. By a lock-based protocol, there is a concurrency-
control manager; a transaction will send a lock request (shared or exclusive) to
the concurrency-control manager to request the permission, and can only con-
tinue to execute when the lock request is granted by the concurrency-control
manager; and a transaction needs to inform the concurrency-control manager
by sending a unlock request when the transaction does not need the lock.
Answer the following questions regarding the three examples, the left, the mid-
dle, and the right, in the slide 14.40 in database-c.pptx.
1. Following the example given in the slide 14.35 in database-c.pptx, show
1Departmental Guideline for Plagiarism (Department of Systems Engineering and Engi-
neering Management): If a student is found plagiarizing, his/her case will be reported to the
Department Examination Panel. If the case is proven after deliberation, the student will auto-
matically fail the course in which he/she committed plagiarism. The definition of plagiarism
includes copying of the whole or parts of written assignments, programming exercises, reports,
quiz papers, mid-term examinations and final examinations. The penalty will apply to both
the one who copies the work and the one whose work is being copied, unless the latter can
prove his/her work has been copied unwittingly. Furthermore, inclusion of others’ works or
results without citation in assignments and reports is also regarded as plagiarism with similar
penalty to the offender. A student caught plagiarizing during tests or examinations will be
reported to the Faculty office and appropriate disciplinary authorities for further action, in
addition to failing the course.
1
2022-23 2
how the concurrency-control manager grants the locks requested by the
two transactions, T and T ′, for each of the three examples.
2. Following the conflicting instructions (the slide 14.19 in database-c.pptx),
show a) the left is not conflict serializable, b) the middle is serializable,
and c) the right is conflict serializable.
3. Reconsider the right example. the two transactions, T and T ′, lock the
items, A and B, in the same order, that is to lock A followed by locking
B. Do you see some possible problem if they lock in different orders, for
example, in the right example, T remains unchanged as follows
Lock-X(A);
Lock-X(B);
read(A);
A := A + 50;
write(A);
unlock(A);
read(B);
B := B + 100;
write(B);
unlock(B);
whereas T ′ is changed to the following.
Lock-X(B);
Lock-X(A);
read(A);
A := 2A + 50;
write(A);
unlock(A);
read(B);
B := B*100;
write(B);
unlock(B);
Show the problem using the lock-based protocol.
Question 2: On the slide 3-11 of database-b.pptx, we show an ASCII
code. There is an extended ASCII code including ASCII code as well as other
additional characters. An ASCII code can be seen as a decimal number. As
shown in the slide 1-11 of database-b.pptx, digital numbers from 0 to 9 are
encoded from 48 to 57, small alphabet letters from “a” to “z” are encoded
from 97 to 122, and capital alphabet letters from “A” to “Z” are encoded from
65 to 90. Any of the decimal numbers in the extended ASCII is encoded as
a 8-bit character. For example, for “a”, it is 97 (decimal), which is equal to
64 + 32 + 1 = 26 + 25 + 20, and therefore is 01100001 in binary representation
(bit representation). Here, a character string can be represented as a sequence
2022-23 3
of bits which is a multiple of 8. In other words, we can divide a given string
into 8-bit blocks. Consider a function f as follows.
f(b0b1b2b3b4b5b6b7) = b3b1b0b5b2b4b6b7
where bi is a bit. Let M be a k character string where M = m1m2 · · ·mk. Here
mi can be considered as a character or a 8-bit block. We can design a hash
function h as h(m) = ck where ck is calculated as follows.
c1 = f(m1)
c2 = f(c1 ⊕m2)
c3 = f(c2 ⊕m3)
· · ·
ck = f(ck−1 ⊕mk)
Note that ⊕ is the exclusive-or (XOR) operator (referring to the slide 1-8 in
blockchain-1.pptx or https://en.wikipedia.org/wiki/Exclusive or.)
1. What is the hash value for a message “Puzzles”?
2. Let k = 3. In general, there are 224 possible inputs, and there are 28
possible outputs. What is the weakness of this hash function? Find two
k = 3 character strings, M ′′ and M ′, that are hashed to the same hash
value such as h(M ′′) = h(M ′).
Question 3: Consider the following search puzzle (slides 1-25 and 1-26 of
blockchain-1.pptx) which consists of
• a hash function H that gets a 10-bit input and returns a 4-bit output:
specifically, let x = x0x1x2x3x4 be of 5 bits, r = r0r1r2r3 be of 4 bits,
and y = y0y1y2y3 = H(x‖r), where ‖ is to concatenate x and r into one
bit sequence.
H(r0r1r2r3b0b1b2b3b4b5)
= b2b4r2b5 ⊕ 1r1b2b3 ⊕ r01b1b4 ⊕ b0b30r3 ⊕ b1b2b31
• a puzzle-ID id = 1010, and
• a target set Y = {0101}.
Find all solutions x to this puzzle; that is, find all 6-bit inputs x such that
H(id ‖ x) ∈ Y