# BlockDAG and Nakamoto protocol
## Consistency

In Inclusive protocol, a block has pointers to all its predecessors, and when a block is committed, we commit all its ancestors as well. This is similar to nakamoto consensus, but in addition to the main chain in nakamoto, we commit more blocks on sideways. These additional blocks are included by an *inclusive* algorithm, where for a committed block in the main chain, it traverses all its ancestors in a predefined deterministic order and include all blocks that is consistent with the current set of accepted blocks. In the following reasoning, we try to reduce the Inclusive protocol to nakamoto and show that it is as secure as nakamoto.

- **All honest nodes will agree on the prefix of their longest path**

The committed blocks in Inclusive DAG is a super-graph of the nakamoto chain, and the longest chain in DAG is exactly the same as the nakamoto chain. The inclusive protocol still always extends the longest chain (along with other tips) as in nakamoto, thus all honest nodes will agree on the prefix (k-deep) of the longest chain same as in nakamoto protocol. And the success probability of adversaries to create a longer private chain is as low as in nakamoto, given the same puzzle difficulty.

- **The same set of blocks will be confirmed if their longest prefix agree**

So the problem introduced by Inclusive is that can we make sure that those additional blocks which are not part of the nakamoto chain are committed consistently in all replicas. As discussed above, we reach the same main chain as in nakamoto consensus, and here in Inclusive, each block in this main chain also contains the hash of all its predecessors. Thus the predecessor information has also reached consensus in all honest replicas, i.e. the DAGs on all honest replicas are the same.

Alternatively, assume one block $B_i$ that is not in the nakamoto chain gets committed by one honest replica, it implies that it is an ancestor of some other block $B_j$ that is in the main chain, which indicates that $B_i$ is at least k-deep from the longest tip. Thus it should have reached all honest replicas and is committed by all honest replicas because of $B_j$ in the main chain. And the chance $B_i$ gets reverted is as low as that for $B_j$.

Note that even though at some tree level, different replicas may see different tips and solve on different puzzles, eventually the version with most included blocks (i.e. longest in the sense of number of blocks) will reach other replicas and replace their local version, similar as in nakamoto.

- **Total order of confirmed blocks will be the same**

Since all replicas have the same set of committed blocks, their order can be determined deterministically, e.g. first order by its level, then for blocks in the same level, order by their hash value.

## Liveness

### **Let's prove that liveness in Inclusive / blockDAG is the same as the Nakamoto protocol**

First of all, we can recap on which assumptions Nakamoto protocol's liveness relies.
Liveness ensures that the chain will grow by a certain amount of block under a certain amount of time. To add a block, nakamoto protocol requires:

- A proof of work for the new bloc to add
- The broadcast of this new block to all honest nodes

In Inclusive / blockDAG, we only make 2 changes:

- The inheritance of a new block to add: in Nakamoto protocol, a block extends the longest path, is it to say the last block on the longest path whereas in Inclusive / blockDAG a new block extends all tips.
- The confirmation rule, we still keep the longest path but across all ancestors, by confirming all ancestors deep enough.

Since here, the confirmation rule doesn't impact the process of adding some new blocks. It is used to validate them for consistency. So, we have to prove that the new inheritance process doesn't change the liveness in the protocol.

To add a new block in Inclusive / blockDAG, we have to:

- Solve the proof of work including hash of all tips
- Broadcast the new bloc

Only the proof of work differs from the Nakamoto protocol. However, we can show that Inclusive / blockDAG can be reduced to Nakamoto protocol.

Let's consider all last blocks. All the blocks will provide a nonce N for the proof of work. Because those nonce are in a finite ensemble, we can imagine a block which is the concatenation of all of them (here the size doesn't matter) and whose the nonce will be the same as N. We don't need to focus on blocks previous the last ones because they don't play any role in the block creation process if not participate to the nonce. With this new large block, we have kept all information and our new block extends only one such as in the Nakamoto protocol.

We can also consider the proof of work as a function. Let’s call B the Blocks space and H the space of hashes. We have

$\forall \space b \in B \space and \space h \in H, \space PoW(h, \cdot) : b \mapsto s$

Where s is the solution of the proof of work for the block to add b with h the hash of all new blocks. This is exactly the same function as in the Nakamoto protocol, only the space of hashes can change.

So, we can reduce the block adding operation of the Inclusive / blockDAG to the one of the Nakamoto protocol.

We have shown that all requirements for liveness in Nakamoto protocol are exactly the same for Inclusive / blockDAG.

Inclusive / blockDAG liveness is the same as the Nakamoto's one.

## **Possibility of double spend attack on DAG**

In the DAG application blockchain network, each block has adjacent blocks to refer to, and finding one block will lead to other blocks connected to it, reflecting a high degree of usability, but at the same time, after the blocks are connected, the mining behavior will be more frequent and may lead to more hard forks, and consistency will be challenged. More seriously, as blocks no longer follow a sequence, there will be a significant increase in the number of conflicting transactions within blocks, such as double-spending, so this is the same problem as the Satoshi Nakamoto consensus. However, the dilemma of combining DAG with blockchain network applications proves that it is only an application model and is itself a data structure framework rather than an off-the-shelf solution, so there are both good and bad cases of specific DAG applications to blockchain networks, and in the following we will analyse one DAG-based protocol in particular: SPECTRE.


Under the SPECTRE protocol, voting is possible using the DAG structure, where each block Z can be voted on in total to determine the order in which blocks X or Y are generated. The block with the majority vote is adopted. So for an attack, as shown in the diagram below, we can think of the blocks as competing with each other, and the chain in red is independent of the main chain (the double flower attack chain), and the existence of this independent chain is not known even after all the information is shared between the blocks, so there is a small chance that this hidden chain may become a longer one during the block generation process, thus taking control of the whole blockchain control of the entire network.

### ****DAG voting mechanism to identify attacks****

To prevent this, a mechanism of voting by all users is used in SPECTRE's DAG blockchain network protocol to form the architecture of the entire network. So users can decide the order in which blocks X and Y are generated, and the votes on each block are pooled into a majority opinion of the users, and simply following such an order for packaging prevents them from dominating the generation of the entire blockchain network for profit.


The newly produced block in the diagram, which originates from the result of a joint vote between block group X and block group Y, is generated immediately after the X block chain, according to the majority principle. The subsequent black block group only carries information about block X without reference to the Y block chain, which means that, for the black block, the Y block chain is hidden and there is no way to know of its existence. Similarly, there is no way to know about the existence of the red block group attached to the Y block chain, as there is no reference to the X block chain.


Therefore, when this New block in the above diagram is generated, it can be known that it is a block belonging to X by referring to the adjacent blocks. By analogy, the final derivation of the attribution of all blocks based on the voting mechanism determines the architecture of the entire blockchain network. As can be seen, blockchain Y does not refer to any trusted block node to implement a double-spend attack defence against this blockchain network. So we can conclude that compared to other DAG application blockchain networks mentioned at the beginning, SPECTRE's network architecture design security is greatly improved, the reason is that under such a mechanism, after normal users generate blocks, it is impossible for attackers' blocks to account for the majority of blocks to launch an attack, trusted blocks are always superior to questionable suspicious blocks, while achieving the whole network extremely high availability of the entire network. This design ensures that there is no lack of sequencing instructions that could scatter connections to each other.