COMPSCI 461/661 Assignment 2
Merkle Proof and Doublespend Attack
Due: Fri Sep 25, 2020
1 Written Assignment
1.1 Merkle Proof
1. (2 points) What is the size complexity of 1 blockchain merkle proof relative to the size of a blockchain of
length N with fixed size blocks of M transactions? (Hint: you should take into account both N and M).
2. (2 points) Now what is the size complexity of P blockchain merkle proofs relative to the size of a
blockchain of length N with fixed size blocks of M transactions?
3. (2 points) What does the size complexity approach if block size is unlimited? (hint: in this case the size
of the Merkle trees dominates the headers chain)
4. (2 points) If the elements in a Merkle tree are sorted, it is possible to create a proof that a particular
element E is NOT included in that tree, as defined by its root ”A”. How is that possible? Next, draw a
Merkle tree with 8 leaves with left-to-right sorted elements equal to the numbers 0-8 inclusive but missing
element 6, label the non-leaf nodes alphabetically as described in lecture (top to bottom, left to right
starting with A as the root).
1
5. (5 points) Circle the elements that would comprise your non-inclusion proof in your diagram above, and
specify the FULL information needed for such a proof here:
6. (4 points) (661) What is the size complexity of the full proof that a transaction does not exist in a
blockchain (that sorts the transactions in its block) specified by tip? (you can assume that T transactions
are in every block). For full credit, explore the special cases that would allow much shorter proofs.
1.2 Poisson Distribution and Doublespend Attack
1. (3 points) A certain typing agency employs two typists. The average number of errors per article is 3
when typed by the first typist, and 4.2 when typed by the second. If your article is equally likely to be
typed by either typist, approximate the probability that it will have no errors.
2. (3 points) Suppose you control 30% of the total mining power. What is the probability that you mine at
least 3 blocks in the next hour, given that, on average, one block is mined by someone every 10 minutes?
Page 2
3. (3 points) Suppose you control q > 0.5 proportion of the total mining power, and all blocks in the
blockchain have equal difficulty. You’re working on a branch of the blockchain with 3 blocks, and everyone
else is working on a branch of the blockchain with 3 blocks. What is the probability that your blockchain
will eventually be longer than the main branch?
4. (3 points) 1 block is discovered every 15 seconds on average for Ethereum. What is the probability that
there is a fork on the blockchain within 5 seconds, (assuming that a discovered block is not propagated
that quickly to other miners)?
5. (3 points) Why can a blockchain reorganization not steal any arbitrary money in the blockchain?
Page 3

欢迎咨询51作业君