COMP9088: Cryptocurrencies and decentralized ledgers Semester 1 2022
Homework 1
due: Thursday 2022-03-17 22:00 AEDT
1. Hash functions and signatures: Signature schemes are typically defined to work for a finite domain of possible message (the message spaces). Suppose you have a signature scheme S which is correct and secure (existentially unforgeable) for domain M={0,1}t, that is, S can be used to sign any t-bit message. Suppose you also have a hash function H which outputs t bits and is collision-resistant.
Copyright By PowCoder代写 加微信 powcoder
Consider a modified signature scheme S’ which can sign messages of unlimited length, where: S’.Sign(sk, m) = S.sign(sk, H(m))
Prove that this scheme is existentially unforgeable as long as S is existentially unforgeable and H is collision-resistant.
2. Beyond binary Merkle trees: Alice can use a binary Merkle tree to commit to a set of elements S = {T1, …, Tn} so that later she can prove to Bob that some Ti is in S using a proof containing at most ⌈log2n⌉ hash values. The binding commitment to S is a single hash value. In this question your goal is to explain how to do the same using a k-ary tree, that is, where every non-leaf node has up to k children. The hash value for every non-leaf node is computed as the hash of the concatenation of the values of its children.
a. Suppose S = {T1, …, T9}. Explain how Alice computes a commitment to S using a ternary Merkle tree (i.e. k=3). How can Alice prove that T4 is in S?
b. Suppose S contains n elements. What is the length of the proof that proves that some Ti is in S, as a function of n and k?
c. For large n, what is the proof size overhead of a k-ary tree compared to a binary tree? Can you think of any advantage to using a k>2? (Hint: consider computation cost)
3. Bitcoin script: Alice is on a kayaking trip and is worried that her phone (which contains her private key) might fall overboard. She would like to store her bitcoins in such a way that they can be spent with knowledge of a password. Accordingly, she stores them in the following ScriptPubKey address:
OP_SHA1 <0x13818a5684a7ed4dce8433c3f57e13b589b88852> OP_EQUALVERIFY
a. Write a ScriptSig script that will successfully redeem this transaction. [Hint: it should only be one line long.]
b. Explain why this is not a secure way to protect bitcoins using a password.
c. Would implementing this using pay-to-script-hash (P2SH) fix the security issue(s) you identified? Why or why not?
4. Lightweight clients: Suppose Bob runs an ultra lightweight client which receives the current head of the blockchain from a trusted source. This client has very limited memory and so it only permanently stores the most recent blockchain header (deleting any previous headers).
a. If Alice wants to send a payment to Bob, what information should she include to prove that her payment to Bob has been included in the blockchain?
b. Assume Alice’s payment was included in a block k blocks before the current head and there are n transactions per block. Estimate how many bytes this proof will require in terms of n and k and compute the proof size for k=8, n=256.
c. One proposal is to add an extra field in each block header pointing to the last block which has a smaller hash value than the current block. Explain how this can be used to reduce the proof size from part (b). What is the expected size of a proof (in bytes) now in terms of n and k? To simplify your analysis, you may use asymptotic (Big O) notation. What are the best-case and worst-case sizes?
5. BitcoinLotto: Suppose the nation of Bitcoinia has decided to convert its national lottery to use Bitcoin. A trusted scratch-off ticket printing factory exists and will not keep records of any values printed. Bitcoinia proposes a simple design: a weekly run of tickets is printed with an address holding the jackpot on each ticket. This allows everybody to verify that the jackpot exists. The winning ticket contains the correct private key under the scratch material. There are no additional trusted parties (or judges) in the protocol.
a. If the winner finds the ticket on Monday and immediately claims the jackpot, this will be bad for sales because players will all realize the lottery has been won. Modify your design to prevent this (of course, you can’t prevent the winner from proving ownership of the correct private key outside of Bitcoin).
b. Some tickets inevitably get lost or destroyed. So you’d like to modify the design to roll forward any unclaimed jackpot from Week n to the winner in Week n+1. Can you propose a design that works, without enabling the lottery administrators embezzle funds? Also, you want to make sure that the Week n winner can’t wait until the beginning of Week n+1 in an attempt to double their winnings.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com