IS3101 Cryptocurrency & Blockchain (2021/22 Semester B)
Department of Information Systems, College of Business, City University of
Tutorial 1: Building blocks of blockchain
Intended Learning Outcomes:
Copyright By PowCoder代写 加微信 powcoder
ILO1: Explain the concepts related to cryptocurrency, blockchain, and distributed ledger technologies. ILO3: Evaluate security issues related to cryptocurrency and blockchain.
Activity 1. Explore Past Hackathon/Competition [5 minutes]
The Gold and the awards went to team members of Infi.io, and , both of them are studying BBA Global Business System Management at CityU.
https://www.cb.cityu.edu.hk/is/events/news/2020/20191130111.html
Undergraduate students shine in HK Blockchain Developer Hackathon 2021.
https://www.cb.cityu.edu.hk/is/events/news/2020/20191130.html
Activity 2. Hash [5 minutes]
Try to find out the original value of the given hashes.
Cracking a Hash value/ digest Original Value Hashes
af0b0363e6faaadefd142a3716a78440
21580adaee64b471e73264ed6de5fd16
Page 1 of 3
IS3101 Cryptocurrency & Blockchain (2021/22 Semester B)
Department of Information Systems, College of Business, City University of
Activity 3. Lecture Questions [40 minutes] Individual Exercise
Q1. Authenticated Data Structures. You are designing SecureBox, an authenticated online file storage system. For simplicity, there is only a single folder. Users must be able to add, edit, delete, and retrieve files and to list the folder contents. When a user retrieves a file, SecureBox must provide a proof, that the file hasn’t been tampered with, since its last update. If a file with the given name doesn’t exist, the server must report that, again with a proof.
We want to minimize the size of these proofs, the time complexity of verifying them, and the digest’s size that the user must store between operations. (Naturally, to verify proofs, users must at all times store some nonzero amount of state derived from the folder contents. Other than this digest, the user has no memory of the contents of the files she added.)
Here’s a naive approach. The user’s digest is a hash of the entire folder contents, and proofs are copies of the entire folder contents¡ªthis results in a small digest but large proofs and long verification times. Besides, before executing add/delete/edit operations, the user must retrieve the entire folder so that she can recompute the digest.
Alternatively, the digest could consist of a separate hash for each file, and each file would be its proof. The downside of this approach is that it requires digest space that is linear [Note: linear here means in proportion] in the number of files in the system.
Can you devise a protocol
and digest size are all sublinear
communication for the user to be able to update her digest when she executes and add, delete, or edit.
[Note: protocol is a set of rules/ procedures]
[Note: grows slower than the size of the problem]
[Note: a secondary or subsidiary protocol]
Q2. Birthday Attack.
A hash function is a mathematical function with the following three properties:
¡ñ Its input can be any string of any size.
¡ñ It produces a fixed size output. We will assume a 256-bit output size.
¡ñ It is efficiently computable. Intuitively this means that for a given input string, you can figure
out what the output of the hash function is in a reasonable amount of time. More technically, computing the hash of an n-bit string should have a running time that is O(n).
We said that it has to be impossible to find a collision. Yet, there are methods that are guaranteed to find a collision. Consider the following simple method for finding a collision for a hash function with a 256-bit output size: pick 2256 + 1 distinct value, compute the hashes of each of them, and check if there are any two outputs are equal. Since we picked more inputs than possible outputs, when you apply the hash function.
where proof size, verification time, ? You might need a sub- that involves some amount of two-way
some pair of them must collide
The method above is guaranteed to find a collision. But if we pick random inputs and compute the hash
values, we¡¯ll find a collision with high probability long before examining 2256 + 1 inputs. In fact, if we
randomly choose just 2130 + 1 inputs, it turns out there¡¯s a 99.8% chance that at least two of them are
Page 2 of 3
IS3101 Cryptocurrency & Blockchain (2021/22 Semester B)
Department of Information Systems, College of Business, City University of
going to collide. The fact that we can find a collision by only examining roughly the square root of the
number of possible outputs results from a phenomenon in probability known as the birthday
Let H be an ideal hash function that produces an n-bit output. By ideal, we mean that as far as we can tell, each hash value is independent and uniformly distributed
. Trivially, we can go through 2n + 1 different values, and we are guaranteed to
find a collision. If we’re constrained for space, we can just store 1 input-output pair and keep trying new inputs until we hit the same output again. This has time complexity
Alternatively, we could compute the hashes of about O(2n/2) different inputs and store all the input- output pairs. There’s a good chance that some two of those outputs would collide (the “birthday paradox”). This shows that we can achieve a time-space trade-off: O(2n/2) time and O(2n/2) space.
Is there an attack for which the product of time and space complexity is o(2n)? [Note: The little oh notation is used to describe an upper bound]
Q3. Randomness. In ScroogeCoin, suppose Mallory tries generating (sk, pk) pairs until her secret key matches someone else’s. What will she be able to do? How long will it take before she succeeds, on average? What if Alice’s random number generator has a bug and her key generation procedure produces only 1,000 distinct pairs?
Activity 4. Submit your work
Please submit your answers to Canvas.
Upload to Canvas under “Tutorial 1 Submission”. (Deadline: 1 week after class, 23:59. Late submission will result in 50%/day deduction)
[Note: In statistics, a type of probability
[Note: {0,1}n denotes the set of sequences
distribution in which all outcomes are equally likely]
of 1’s and 0’s of length n]
doubles with each addition to the input data set. The growth curve of an O(2n) function is exponential –
[Note: time complexity is the amount
of computer time it takes to run an algorithm]
[Note: O(2n) denotes an algorithm whose growth
starting off very shallow, then rising meteorically]
, but has O(1)
[Note: O(1) means that it takes a constant
space, like 14 kb, or three mb, no matter the amount of data in the set.]
space complexity
[Note: space
complexity is the computer memory required by an algorithm to execute a program and produce output].
Page 3 of 3
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com