(This post is part of the Understanding GHOSTDAG series)

1. A strong connectivity component in a directed graph is a set of vertices such that each vertex in the set is reachable from any other vertex in the set. What is the largest strong connectivity component possible in a DAG? What is the smallest strong connectivity component possible in a directed graph that is not acyclic?

2. Draw all ways to complete this rooted tree to a rooted DAG:

   

3. Draw all spanning trees of this DAG:

   

4. A DAG is said to have the no-incest property if the following does not happen: there are vertices $A,B,C$ such that $A$ points at $B$ and $C$ and $B$ is reachable from $C$. Draw the simplest DAG that doesn’t have the no-incest property.

5. * Propose an algorithm that is given a DAG and transforms it into a DAG with the no-incest property by removing arrows, such that if $A$ was reachable from $B$ in the original DAG it will also be reachable in the output.

6. Let $G$ be a rooted DAG and $B$ a vertex in $G$, prove the following:

   • $ClosedCone(B) \cup Anticone(B) = G$

   • $Cone(B) \cap ClosedAnticone(B) = \{B\}$

7. List all topological sortings of the “getting dressed” DAG. If you could remove one vertex from the graph before doing that exercise, which one should you choose to work as least as possible? Why?

8. The graph visualizing the iterative algorithm for topological sorting has no $B_2.MergeSet$, why is that?

9. Prove the correctness of the iterative algorithm, namely that the sorting it outputs is indeed topological

10. *Find a chain selection rule that induces an ordering rule that is not topological

11. *Find a tie-breaking rule that causes HCR to be non-transitive

12. *Find a necessary and sufficient condition for a tie-breaking rule to make HCR transitive. Are the tie breaking rules we’ve discussed satisfying this condition?

13. *Say that there are $n$ chains going through $B$ and $n’$ chains going through $B’$. We can find the best chain among all these chains (w.r.t. some transitive chain-selection rule) by comparing any two chains in this set. This requires comparing $\Theta((n\cdot n’)^2)$ pairs of chains. Find an algorithm for finding the best chains that only requires comparing $O(n+n’)$ pairs of chains.

14. *Prove that GHOSTDAG (with the lexicographic hash tie-breaking rule) is transitive.

15. *Prove that HCR and GHOSTDAG are monotone chain-selection rules

16. **Prove that a transitive monotone chain-selection rule induces a topological sorting

17. The attack we’ve seen on the DAGified GHOTS protocol assumes that $|B.Future| - |B’.Future|$ starts from $1$ and remains constant as long as only honest blocks are created. In practice, it does not necessarily start from $1$ and there is some chance that honest blocks will only be in the future of exactly one of the blocks $B$ and $B’$. Explain why the attack still works.

18. **Explain why the incomplete version of SPECTER we proposed is succeptible to premining attacks. (Reminder: a premining attack is where the adversary wants to revert some arbitrarily old transaction, but doesn’t care which transaction. So they can decide that they are starting to work now so that a year from now they could revert an $n$ day old transaction. If the attempt fails, they try again. A premining attack is successful if the probability of success is inversely polynomial in $n$ (unlike in Bitcoin, where we have seen it is inversely exponential).)