COMP9088: Cryptocurrencies and decentralized ledgers Semester 1 2022
Tutorial Sheet, Week 2 Week of March 7, 2022
1. Merkle trees. Consider the following , in which leaf nodes (containing data) are shaded blue and internal nodes are shaded in red. The labels on the internal nodes are for convenience describing the tree, each node¡¯s value is the hash of its two children:
a. Which nodes are needed for a proof that 7 is included in the set? Which nodes are re-computed?
Copyright By PowCoder代写 加微信 powcoder
b. If the verifier knows that the leaves of the tree are in sorted order, how can they be given proof that the element 3 is not in the set committed to by this tree?
c. Suppose that as an optimization for a tree with n nodes, instead of just storing the root of the tree the verifier stores k internal nodes (at level lg k) in the tree. How large would a data inclusion proof be in this case? How much work would it take to verify?
2. Signature schemes. Assume we want a security parameter of ¦Ë. That is, we assume an attacker which can perform poly(¦Ë) operations (a polynomial function of ¦Ë). We want the attacker¡¯s probability of winning the existential forgery game to be 2-¦Ë.
a. What is the minimum size that public keys output by the signature scheme¡¯s key generation function KeyGen() must be?
b. What is the minimum size that signatures output by the signature scheme¡¯s Sign() function must be?
3. Birthday paradox revisited
a. What is the probability of two random people sharing a birthday? For simplicity, you can
ignore leap years and assume the birthdays are uniformly distributed on the calendar.
b. Given a room full of N people, there are N choose 2 = N(N-1)/2 pairs of people. What is the expected number of collisions (pairs of people sharing a birthday) in a room with N people?
c. When is the expected number of collisions 1?
d. Why is the answer for part (c) different from the traditionally cited formulation of the “Birthday paradox¡¯¡¯ that the odds are greater than 50% that a room full of 23 people will share a birthday?
e. Given a room full of N people, what is the expected number of sets of three people who all share a birthday and for what integer value of N is this higher than 1? You can use the same approximation as in part (b)
4. Bitcoin addresses: Bitcoin addresses are typically exchanged via a 160-bit hash formatted in base56, like so:
3HHZfn1wo93snzEf5kDmkSx1vPmyCxYAxm
a. How many characters are in a Bitcoin address if it is a 160-bit hash formatted using an alphabet of 56 symbols?
The alphabet in use is the following:
23456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnpqrstuvwxyz
b. ¡°What¡¯s missing¡¯? Why do you think these letters are not used in Bitcoin addresses?
c. Why is it secure to distribute the hash of your public key as your address, rather than the key itself?
d. Suppose Bob¡¯s address is X=H(PKBob) and an attacker Mallory wants to find another public key PKMallory such that X=H(PKMallory). What would be the effect if Mallory found such a key?
e. Recall that for a hash with t bits of output, a birthday attack takes only O(2t/2) bits of work to find a collision. Do birthday attacks apply here? Why or why not? If not, how much work on expectation must Mallory expend to find such a key?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com