---
tags: Homeworks
---

# HW 1: Blockchains

:::info
**Released:** Monday, January 29, 2024 at 11:59 E.T.
**Due:** Sunday, February 4, 2024 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/1cnjMyu9_kkDlh_MXsLWPBaggKH9ZyON0?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.