Exercises

1. Prove that a (simple undirected graph) is a DAG if and only if there are no two vertices $A$ and $B$ such that $A$ is reachable from $B$ and $B$ is reachable from $A$

2. Prove that a rooted DAG has only one root

3. Show that a rooted DAG is a tree if and only if for any block $B$ that is not the root, there is a single path from $B$ to the root

4. Is the following a good tie-breaking rule? Given a tie between $A$ and $B$, mine over the block that has an earlier timestamp.

5. Recall that a satoshi is one hundred millionth of a bitcoin. Assuming that Bitcoin stops coin emission when the reward drops below satoshi, how long will it take for all rewards to be emitted since the network started? By how much the total supply was decreased by discarding sub-satoshi block rewards?

6. * Show that if we apply the Eyal-Sirer strategy to a miner with more than half of the hash rate we recover the standard double-spending attack.