HW 1: Blockchains

--- tags: Homeworks --- # HW 1: Blockchains :::info **Released:** Monday, January 30, 2023 at 11:59 E.T. **Due:** Sunday, February 5, 2023 at 11:59PM E.T. ::: ## Instructions Submit your answers to the following problems on [Gradescope](https://www.gradescope.com/). Problems are NOT all or nothing. For example, each statement in Problem 1 is worth 2 points. The grading breakdown is visible on Gradescope. The lectures this week may help you complete Problems 2-4. ## Problem 1 (10 points) Here are three properties of cryptographic hash functions. 1. **Collision resistance:** it is hard to find any two $x , y$, where $x \neq y$, such that $H(x) = H(y)$ 2. **Preimage resistance:** your adversary can choose $y$ so that it is hard to find $x$ such that $y = H(x)$. 3. **Second preimage resistance:** your adversary can choose $x$ so that it is hard to find $y$ such that $H(x) = H(y)$ For a nice distinction between preimage resistance and second preimage resistance, check out this [thread](https://stackoverflow.com/questions/28378326/difference-between-preimage-resistance-and-second-preimage-resistance). **Which of the following statements are true (2 points each)?** - [ ] Collision resistance implies preimage resistance. - [ ] Collision resistance implies second preimage resistance. - [ ] Second preimage resistance implies collision resistance. - [ ] Suppose an adversary is trying to steal your unique password to Disney Plus. Your operating system keeps your password secure by hashing and storing them in a file. The primary reason your adversary can't steal your unique password is second preimage resistance. - [ ] If you sign a message by hashing it, the primary property securing your message is collision resistance. ## Problem 2 (4 points) Using what you now know about these key cryptographic hash properties and the concept behind Proof-of-Work ("One CPU, One Vote"), hypothesize how these cryptographic properties may be used in Bitcoin's code to ensure that a miner has performed some amount of computation before voting. In other words, **how can we use these properties or your pre-existing knowledge of hashes to make a kind of computationally intensive "puzzle" for the miner to solve?** If you are already familiar with Bitcoin's Proof-of-Work Consensus Protocol, feel free to ideate alternative approaches. If you are completely lost or just want to confirm your intuition, consider checking out [Bitcoin's White Paper](https://bitcoin.org/bitcoin.pdf) or reviewing the [lecture notes](https://drive.google.com/drive/folders/125TuuYWjKgwn3eTeb-JXUdskGTZU1Mt9?usp=sharing) (Chapter 3 may be particularly helpful). Make your response no longer than 150 words. Submissions will be graded on **effort** and **general conceptual understanding.** ## Problem 3 (8 points) Suppose there are two distinct Bitcoin protocol implementations, called $A$ and $B$. One day an attacker finds a vulnerability in implementation $A$ that causes miners running that implementation to accept transactions that double-spend a UTXO. Implementation $B$ treats such transactions as invalid. **Which of these happens when attackers start submitting double-spending transactions (2 points each)?** - [ ] If 80% of the mining power runs $A$, then miners running $A$ will build long chains not recognized by $B$, and the miners running $B$ will eventually go bankrupt. - [ ] If 80% of the mining power runs $A$, the miners running $B$ will ignore the double spending blocks. They will outcompute the miners in $A$, and the miners running $A$ will eventually go bankrupt. - [ ] If 80% of the mining power runs $B$, then miners running $A$ will build long chains not recognized by $B$, and the miners running $B$ will eventually go bankrupt. - [ ] If 80% of the mining power runs $B$, the miners running $B$ will ignore the double spending blocks. They will outcompute the miners in $A$, and the miners running $A$ will eventually go bankrupt. ## Problem 4 (6 points) Assume everyone has a public/private key pair, and everyone knows everyone else’s public key. For example $PK_{Alice}, SK_{Alice}$ is Alice’s public/private key pair, and everyone knows that $PK_{Alice}$ belongs to Alice. For short, $\{m\}_{Alice}$ denotes a pair $(m, σ)$ where $σ$ is Alice’s signature for $m$ using her private key. The **DeadTreeCoin** cryptocurrency is the latest investment craze. Alice, the banker, is authorized to mint coins. Transactions are published in newspaper classified ads. In a minting transaction, Alice creates a coin, here with serial number 1234, and grants ownership to Bob. :::info $$\textrm{coin$_{1}$} := \{\textrm{mint 1 coin serial 1234 for } PK_{Bob}\}_{Alice} \tag{0.1}$$ ::: In a spending transaction, Bob transfers ownership of a coin to Carol. :::info $$\textrm{coin$_{2}$} := \{\textrm{spend SHA256($\textrm{coin}_{1}$) to } PK_{Carol}\}_{Bob} \tag{0.2}$$ ::: Your job is define valid coins so that (1) no invalid coin appears valid, and (2) no valid coin can be double-spent. Every day, the coin authority buys a classified ad with any new transactions. For this problem, we're evaluating equations Equation 0.1 and Equation 0.2 separately. Thus, when evaluating Equation 0.2, we don't know the provenance of $\textrm{coin}_{1}$. Also note that validity by itself does not imply ownership. **Which of the following pairs of statements accomplishes (1) and (2) (2 points each)?** - [ ] Pair 1 1. In Equation 0.1, $\textrm{coin}_{1}$ is valid if there is no earlier minting transaction with the same serial number. Afterwards, $\textrm{coin}_{1}$ belongs to Bob. 2. In Equation 0.2, $\textrm{coin}_{2}$ is valid if $\textrm{coin}_{1}$ is valid, and there is no earlier spending transaction for that coin signed by Bob. Afterwards, $\textrm{coin}_{2}$ belongs to Carol. - [ ] Pair 2 1. In Equation 0.1, same as above. 2. In Equation 0.2, $\textrm{coin}_{2}$ is valid if $\textrm{coin}_{1}$ is valid and owned by Bob, and there is no earlier spending transaction for that coin signed by Bob. Afterwards, $\textrm{coin}_{2}$ belongs to Carol. - [ ] Pair 3 1. In Equation 0.1, $\textrm{coin}_{1}$ is valid if there is no earlier minting transaction with the same serial number assigning ownership to someone other than Bob (so exact duplicates are OK). Afterwards, $\textrm{coin}_{1}$ belongs to Bob. 2. In Equation 0.2, same as above.