HW 1: Blockchains

Instructions

Submit your answers to the following problems on Gradescope. 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.

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 or reviewing the lecture notes (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.

In a spending transaction, Bob transfers ownership of a coin to Carol.

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.