(This post is part of the Understanding GHOSTDAG series)

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?Draw all ways to complete this rooted tree to a rooted DAG:

Draw all spanning trees of this DAG:

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.

* 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.

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\}$

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?The graph visualizing the iterative algorithm for topological sorting has no $B_2.MergeSet$, why is that?

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

*Find a chain selection rule that induces an ordering rule that is

*not*topological*Find a tie-breaking rule that causes HCR to be non-transitive

*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?

*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.

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

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

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

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.**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).)

Enjoyed reading this article?

More articles like this# Comments

No comments yet!