HW 2: Bitcoin

Released: February 13th, 11:59pm EST
Due: February 19th, 11:59pm EST

Instructions

Submit your answers to the following problems on Gradescope. Information to help you answer these questions may be found in the lecture slides, recordings, and notes.

Problem 1 (10 points)

Suppose that Bitcoin's current minting reward is

$R$, and that a miner

$M$ mines a block with total transaction fees of

$F$.

Transaction Outputs are defined as:

$\{\text{amount, public key}\}$

Let

$F,F^{\prime },N\in \mathrm{I}{\mathrm{R}}^{+},\text{ and }N<F^{\prime }<F$.

Suppose that the block's coinbase transaction is as follows:

$\text{Inputs}:\{\}$

$\text{Outputs}:\{\{R,P{K}_0\},\{F^{\prime }-N,P{K}_1\},\{N,P{K}_2\}\}$

If this block is included in the chain, which of the following statements are necessarily true?

• $M$ is a participant in a mining pool
• $M$ is infiltrating a mining pool, and has diluted the rewards for miners within that pool
• Collectively, the transaction senders in this block receive a refund of
  $F-F^{\prime }$, proportional to the transaction fees that they included in their transactions
• The maximum long-run total supply of Bitcoin remains the same
• The transaction is malformed, as it does not contain any valid inputs

Problem 2 (10 points)

Alice has a set of elements

$S=\{e_0,...,e_{n-1}\}$. Recall that in a Merkle tree representation of

$S$, each leaf

$i$ is labeled with

$H(e_i)$, and each internal node is the hash of the concatenation of its two children. The tree’s root is called the root hash.

Alice wants to prove to Bob that

$e_i\in S$. Which of the following statements are true (2 points each)?

• The primary hash function property underlying the security of the merkle tree is preimage resistance.
• It is enough for Alice to send Bob
  $[{\log }_{2}n]+c$ hash values to prove
  $e_i\in S$ , where
  $c$ is a constant independent of
  $n$.
• Bob has access to all of the transactions contained in a block
  $B$. Carol has block
  $B$ on her blockchain. To check whether Carol has tried to tamper with the set of transactions included in
  $B$, Bob only needs to request the root hash from her.
• Instead of taking the hash of the concatenation of a node’s two child hashes, it would be equally secure to take the hash of their product.
• Suppose Alice uses a
  $k-\mathrm{ary}$ tree,
  $k\ge 2$, where every non-leaf node has up to
  $k$ children, and is labeled with the hash of the concatenation of the child hashes. It is enough for Alice to send Bob
  $[{\log }_{k}n]+c$ hash values to prove
  $e_i\in S$, where
  $c$ is a constant independent of
  $n$.

Problem 3 (4 points)

Suppose that Alice owns 10 BTC. The conversion rate from BTC to USD is

$1:10$. She owns no other cryptocurrencies.

Recently, debates about Bitcoin's block size have been raging, and a faction of the Bitcoin developers have decided they will fork from Bitcoin and create a new cryptocurrency called Bitcoin Cash (ticker: BCH).

Bitcoin Cash operates exactly the same as Bitcoin, except that the block size is double that of Bitcoin. Thus, Bitcoin UTXO are also valid UTXO on Bitcoin Cash.

Coinbase, a cryptocurrency exchange, decides to include Bitcoin Cash in its list of assets. Coinbase's conversion rates are as follows:

BTC to USD:

$1:7$
BCH to BTC:

$11:2$
ETH to BTC:

$3:20$

What happens to the total value of Alice's cryptocurrency holdings?

• Increases
• Decreases
• Stays the same
• Cannot be known

Alice decides to purchase a pizza slice using BCH. What happens to her total number of BTC?

• Increases
• Decreases
• Stays the same
• Cannot be known

Problem 4 (10 points)

Which of the following are potential inefficiencies in Bitcoin?

• The POW consensus algorithm, due to its inability to provide consistency guarantees.
• The block size, which severely limits Bitcoin's transaction throughput.
• Forks are difficult to recover from: anytime there is a fork, it can take days for nodes to come to consensus
• Validation times are long: a merchant may have to wait several hours before a transaction is "confirmed"
• Bitcoin mining requires a lot of unused storage space power (one GB = one vote). The unused storage space would be better used elsewhere.

Problem 5 (6 points)

Suppose that Carol operates a Blockbuster in Dallas, Tx and it's currently 2010 (Bitcoin hasn't taken off yet). She's friends with Satoshi Nakamoto, who's trying to convince her to accept Bitcoin as payment for movie rentals. Carol decides to support Satoshi, and starts accepting Bitcoin as payment. However, Carol isn't familiar with the intricacies of Bitcoin and doesn't require any confirmations on Bitcoin transactions.

Alice wants to rent How To Train Your Dragon 2 and pay 1 BTC for that rental.

Transaction Outputs are defined as:

$\{\text{amount, public key}\}$

Alice creates two transactions and pre-mines block

$B_B$, which includes Transaction B.

${\text{Input}}_1$ is valid.

Transaction A:

$\text{Inputs}:\{{\text{Input}}_1\}$

$\text{Outputs}:\{\{1,P{K}_{Carol}\},\{2,P{K}_{Alice}\}\}$

Transaction B:

$\text{Inputs}:\{{\text{Input}}_1\}$

$\text{Outputs}:\{\{3,P{K}_{Alice}\}\}$

Carol accepts Transaction A as payment, immediately broadcasting it to local nodes in the network. At the same time, Alice broadcasts

$B_B$ to the network. Which of the following statements are true?

• Nodes treat block
  $B_B$ as malformed, since it includes a transaction with an already spent UTXO (Transaction B)
• Transaction A has the same fee as Transaction B
• This is an example of a 51% attack

Problem 6 (6 points)

Each Bitcoin node keeps track of a UTXO Set, which contains all of the spendable outputs on the Bitcoin network. This set reflects the UTXO on the node's current chain.

When a fork occurs, a node has to update its UTXO Set to reflect the changes caused by the new blocks in that fork.

When a node hears about a longer chain with more POW, it orphans its existing chain and adopts the new one. In adopting the new one, the node must update its UTXO Set by reversing the changes caused by the blocks from the old, now orphaned chain.

Suppose that node

$N$'s current chain is:

$Chai{n}_0:B_0⟶B_1⟶B_2⟶B_3⟶B_4⟶B_5$

Now, suppose that

$N$ hears about

$Chai{n}_1$, a longer chain with more POW:

$Chai{n}_1:B_0⟶B_1⟶B_2⟶B_3⟶B_6⟶B_7⟶B_8$

$N$ wants to mine on the longest chain, so it must update its UTXO Set to reflect

$Chai{n}_1$'s UTXO. This updating process involves "reverting" blocks: for each block it reverts,

$N$ must (1) erase that block's newly created UTXO and (2) reestablish the inputs used in that block as valid UTXO.

Which of the following statements are necessarily true?

• $N$ must "revert" blocks in LIFO order (
  $B_5$ before
  $B_4$), in case
  $B_5$ contains outputs from
  $B_4$.
• $Chai{n}_1$'s UTXO Set contains a larger number of UTXO than
  $Chai{n}_0$'s.
• $Chai{n}_0$'s UTXO Set is worth more than
  $Chai{n}_1$'s (assume no burning has occured)

Problem 7 (10 points)

Bitcoin's energy debate has existed for almost as long as Bitcoin itself. The conversation typically revolves around the acknowedgement that Bitcoin takes a large amount of energy to resolve any one transaction (with a total energy expenditure per year greater than some small countries), it is overall slow in terms of transaction throughput, and that it seems to be dwarfed in both efficiency and speed by something like Visa.

For more detailed information about this debate, feel free to refer to articles you find by yourself, or these compiled resources that feature differing perspectives (1, 2, 3, 4, and 5).

For this problem, you will be tasked with writing two responses, each less than 100 words. Your responses will be graded on effort as well as demonstrated understanding.

A) In your first response, summarize the energy debate around Bitcoin and highlight what you think are some key insights, as well as what you believe to be some misconceptions or inaccuracies.

B) In your second response, briefly explain the comparison between Bitcoin and Visa and point to some reasons why they may be considered to be similar as well as some alternate reasons for why they differ (whether that be in function, implementation, philosophy, or some other category entirely).