(This post is part of the Understanding GHOSTDAG series)

We are finally set to define the security of a blockDAG protocol.

It turns out that most of the work we did to define the safety, liveness and confirmation times for blockChains can carry over as is. This will allow to very quickly adapt our definitions to the blockDAG setting, and move on to introducing some examples and discussing their security.

Adapting the Definition

Recall that in the blockChain setting, we first defined the notion of confidence. We said that a merchant has $\varepsilon$-confidence in a transaction txn against an $\alpha$-attacker if we can assure him that the probability that an $\alpha$-attacker manages to revert txn is at most $\varepsilon$. We broke this process into two steps: the second step is that the block containing the transaction remained for sufficiently long on the selected chain, we denoted the time it takes $S(\alpha,\varepsilon)$. The first step is how long until the block appeared in the selected chain for the last time, we denoted this time $L(\alpha,\varepsilon)$. A subtlety about $L$ is that it also includes any fluctuations of the block into and out of the selected chain. Recall the following diagram:

The only component of the definition that depends on the underlying protocol is $S(\alpha,\varepsilon)$. The form of definition we are looking for is given in terms of how long time some property $P$ holds before the merchant has $\epsilon$-confidence against an $\alpha$-attacker. Once we find a DAG-appropriate analogue for $P$, everything else will fall into place.

In the blockChain paradigm, the propery $P$ is “the block is on the selected chain”. This does not translate well to blockDAGs because there is no selected chain. Instead, the DAG paradigm outputs an ordering which always contains all blocks.

To find the correct choice for $P$, we ask ourselves why the selected chain is important to us, what makes it a natural choice, and what takes its place in the DAG paradigm. Even though there could be many chains that go through $B$, they all look the same (at least) up to $B$: if two chains share a block, they also share all the blocks in its past:

That is, instead of saying “$B$ is on the selected chain” we could equivalently say “the set of blocks on the selected chain from the point of view of $B$ does not change”. This restatement is only a bit clumsy, so lets make it clumsier yet: “the set of blocks on the selected chain from the point of view of $B$, and their ordering, does not change”. This new addition seems trivial: of course the ordering does not change, there is only one way to topologically order a chain! But this unnatural restatement does have an important property: it makes sense for blockDAGs as well! It captures the idea we sought after in a way that does not appeal to the blockChain exclusive notion of selected chain.

This leads us to the following property $P$: the (objective) ordering up to $B$ does not change. As we discussed in a previous post, this property implies (but is actually stronger) that the set of transactions processed from $Past(B)$ does not change.

Significance of Liveness

Some may argue that the liveness condition is two stringent. A common reasoning is that it does not really matter whether blocks change order because the only scenario where this has any effect on the ledger is if there is a double spend, and then the only transactions that are affected are those created by dishonest parties, so it is not a concern that the conflict is never resolved since only malicious actors are punished.

This is not quite the case for several reasons, the main once being that double-spend might be the result of an honest mistake or a bug.

A subtler consideration is that of smart contracts. There are many forms of smart contracts, but one feature they all share is that the way a certain transaction behaves can depend on future blocks.

Say, for example, me and my landlord have a simple contract that handles our rent. I deposited 12,000 kaspa into the contract, and the following holds: every month, 1,000 kas are paid to my landlord, unless we post a mutually signed notice that the lease ended early, and then the remaining balance goes back to my account. Say that for some reason I did decide to end the lease early and, with my landlord’s blessing, we both posted the end of lease notice. How much money should I get back? If the lease was posted around the middle of the month then the answer is pretty well defined. If it was posted on the last block of the month, an attacker might be able to cheaply change the ordering in a way that pushes the lease termination one block into the future, and now suddenly 1,000 of my kas are now my landlord’s. They might even be able to change the ordering back and forth indefinitely changing our balances, not allowing them to ever converge. In the next post we will see such an attack.

In the next post we will also discuss a protocol called SPECTRE. SPECTRE is a beautiful protocol, but it has a caveat: it only provides a property called weak liveness. Weak liveness does not agree that the ordering doesn’t change (or equivalently, that all nodes see the same ordering), but “only” that both orderings result in the same state. That is, blocks could change places, but only in a way that does not change what transactions were approved. Consequentially, SPECTRE converges very fast (even in light of conflicts), but is only adequate for transactional layers and is inadequate for expressiveness that requires more complicated dependence between blocks.

BlockDAGs from BlockChains

Finally, we will see a technique for transforming chain selection rules to ordering rules.

Under certain condition, a block selection rule induces a topological ordering. In the next chapter, we will use the ordering induced by the HCR and GHOST chain selection rules as highly instructional anti-examples. Both protocols fail spectacularly, but each fails in a different (might even say polar) way: DAGified HCR fails safety, whereas DAGified GHOST failed liveness. Understanding these protocosl and their shortcomings will provide valuable insight of the sweet spot one must find when devising a secure BlockDAG protocol.

The idea of the induced topological ordering is as follows: given two blocks $B$ and $B’$, choose the block that has the “best chain” going through it. It is not obvious that this results in a well defined ordering at all. Even if it is, it is not guaranteed that the sorting is topological. In fact, neither are necessarily true. With a bit of effort, one can troll us with a chain rule for which the ordering above fails.

For example, consider the following blockDAG:

One can define a chain selection rule that prefers chain 2 over chain 1 over chain 3. So when considering the chains that go through either $B$ or $B’$ there is no “best” chain, so the ordering is not well defined.

Such pathologies do not happen for HCR and GHOST, and the ordering is will defined and topological.

Transitive and Monotone Chain Rules*

It is not true that all chain selection rules induce a well-defined and topological sorting. However, if we require that the chain rule satisfies two natural properties (that are clearly satisfied by HCR and GHOST), then it does induce a well-defined and topological sorting.

The first property is Transitivity. This property implies that the induced ordering is well-defined (though not necessarily topological). Transitivity simply means that if the chain selection rule will select tip 1 over tip 2 and tip 2 over tip 3, it will also select tip 1 over tip 3.

HCR is “obviously” transitive, if it prefers tip 1 over tip 2, this means that the chain from tip 1 to genesis is heavier than the chain from tip 2 to genesis, and the same for tip 2 and tip 3. Hence, tip 1 is heavier than tip 3 and so it will be selected by HCR. The caveat here is actually the tie-breaking rule. A poorly chosen tie-breaking rule could render HCR non-transitive.

In Bitcoin the tie-breaking rule is as follows: if two chains have the same weight, take the tip which has the lowest hash. Since distinct tips cannot have the same hash, this provides a transitive tie breaking rule. Hence, implementing HCR with this tie-breaking rule results in a transitive chain rule.

The transitivity of the chain rule implies that any set of chains contains a “best” chain, in particular the set of chains that go through either $B$ or $B’$, making the ordering well defined.

Proving that GHOST (with an appropriate tie-breaking rule) is also transitive will remain an exercise for the reader.

The second property is monotonicity. Monotonicity means that extending a chain will always make it more preferable. That is, if the chain selection rule prefers tip 1 over tip 2, and now a new block is added that points to tip 2, then the chain selection rule will prefer the new tip over tip 1.

Proving that HCR and GHOSTDAG are monotonic is very easy, proving that a monotonic and transitive tie-breaking rule always induces a topological sorting is a bit harder, both remain as exercises for the reader.