Part 7: Technical introduction - Addressing the challenges  within a blockDAG

Because a DAG is not a chain but a graph, parallel blocks can have conflicts.
Therefore, choosing the new blocks based on the longest chain rule in a DAG is not likely to be secure in fast decentralized networks today's world needs.

If we create one block per 10 minutes, as Bitcoin does right now, there will be almost no forks. So yes, it will be secure under this condition. The absence of forks stems from a massive propagation time (10 minutes), in which the network must announce the new block to all network participants. But when an honest network suffers from any meaningful latency, then choosing the longest chain will not necessarily represent the honest majority of the network reaching the consensus. Instead, the longest chain can represent a centralized attack that does not suffer network latency, whereas the honest network made from a distributed system is encumbered with the latency brought about by its many forks.

That's why DAG has to adopt a different approach to control the ordering and counteract attackers attempting to dominate the majority in the DAG.

Another important thing to realize is the speed aspect of the blockDAG network, or, in other words, the network's block creation rate that leads to increasing the blockDAG width through all the created forks. The width that grows quadratically, not exponentially, is adjusted by the network parameter k.

The wider the blockDAG is, and the more parallel forks it has, or the faster the block creation rate or the block size is, the more latency you will suffer and the smaller the attacker needs to be to create a fraudulent reorganization.

So, we need something that solves the security issue of reorganization attacks while keeping your network as fast as possible.

In a slow network, let's say one block per ten minutes; you will obtain a trivial and narrow DAG whose width parameter equals one, so using the longest chain rule would be secure.
However, if you scale to 100 blocks per second, the latency increases linearly, and the required size of an attacker that might disrupt the network decreases. Thus, to make a DAG network secure against revert attacks, you need to make it fast because a higher block creation rate provides better security against 49% attacks, but remember, it does not protect the network against 51% attacks - the only deterrent against those, regardless of how the blocks are arranged, is high mining hashrate.

A 51% attack pertains to an assault on a blockchain executed by a coalition of miners who possess over 50% of the network's mining hash rate.

The primary deterrent against 51% attacks, whether within a blockchain or a DAG structure, is a high total mining hash rate. To attract miners to the network and ensure its security, the network and its associated fees must be economically appealing.

Mathematical security analysis is consistently based on the premise of an honest majority, meaning it applies under the assumption that more than 50% of the participants in the network are honest and cooperative. In this context, security is a function of the number of confirmations a transaction accumulates. Consequently, a 49% attacker faces the same probability of reversing a transaction with ten confirmations, regardless of whether each confirmation was obtained in 10 minutes or 0.1 seconds.

To make the network secure, besides obtaining that important speed factor, it is imperative to ensure that 51% attacks are economically infeasible. This is achieved by utilizing block rewards and fees, which effectively purchase security against these attacks. Cryptographic defenses alone are insufficient; thus, the economic incentives provided by rewards and fees play a vital role in network security.

Now, let's consider the speed of the network and the volume of data that nodes need to handle.

In the context of network speed, rapid block creation often results in the generation of multiple forks and the accumulation of substantial on-chain data. Robust pruning mechanisms are essential to manage this data effectively, especially in a fast Proof of Work (PoW) environment.
These mechanisms are crucial in ensuring that long-term storage requirements are reasonable and synchronization times remain minimal.

Pruning involves the selective removal of unnecessary block data while preserving the network's integrity. As a result, new nodes can deterministically attain the current network status and swiftly integrate into the system following synchronization, which is exceptionally efficient in a network equipped with a proficient pruning algorithm.

The act of pruning leads to reduced hardware requirements for nodes. With less data to process, nodes can operate on more affordable and sustainable hardware, fostering decentralization and ensuring long-term viability.

A lower barrier of entry and great inclusivity means more decentralization! Great!

It is important to emphasize that higher hardware demands for network nodes can lead to fewer participating nodes, decreasing decentralization and security. Therefore, maintaining low hardware requirements and good pruning mechanisms is critical to securing affordability and sustainability and achieving substantial decentralization across the entire network while ensuring fast synchronization.

Kaspad node hardware requirements

Minimum:

• 100 GB disk space

• 7th generation i7 4-core processor or AMD equivalent

• 8GB memory

• 10 Mbit internet connection

Recommended:

• 9th generation i7 8-core processor or AMD equivalent

• 16 GB memory

• 40 Mbit internet connection

Let us explore another challenge: restoring consistency within a DAG.

BlockDAGs and other asynchronous consensus or agreement protocols face difficulties when dealing with a high block creation rate, resulting in conflicts similar to those in systems generating blocks simultaneously. Consequently, it becomes uncertain whether you might inadvertently duplicate information, such as reusing the same unspent transaction multiple times from the previous block. In situations like this, multiple servers from the network might update the database with conflicting transactions, such as a double spend. That is why the blockDAG paradigm needs to give us linear ordering over the DAG and all its events.

In a linear ordering approach, we traverse the sequence by iterating from the earliest to the most recent transaction. We validate transactions that maintain consistency with the previous ones or the current state while we skip or discard inconsistent transactions. An example of this linear ordering method is featured in the GHOSTDAG protocol, coauthored by Yonatan Sompolinsky, Aviv Zohar, and Shai Wyborski.

Within the blockDAG paradigm, blocks are permitted to contain conflicting transactions. However, the network does not update the state using these conflicting transactions.
Instead, the conflicting transactions are subsequently ignored.

Below is a summary of the Kaspa approach to double-spent protection.
Kaspa showcases an exemplary implementation of the blockDAG PoW mechanism, coupled with a robust consensus and ordering protocol.

All the bits that together prohibit the double spent or other reorganization attack

- Kaspa's approach main overview:

- Combines GHOSTDAG protocol and UTXO model.

- Ensures each digital coin is used only once, even during parallel transaction processing.

- GHOSTDAG protocol level:

- Establishes a universally agreed-upon transaction order.

- Resembles a standardized rulebook to prevent confusion in the customer order, akin to bank tellers following a common procedure.

- Transaction sorting:

- Segregates transactions into "blue" (main chain) and "red" (conflicting) sets.

- Streamlines the resolution of teller-like disputes for efficient processing.

- Block classification:

- Divides blocks into "kernels" (approved) and "anticone" (pending approval).

- Systematically manages conflicting transactions within the GHOSTDAG.

- UTXO model:

- Enhances security with "unspent outputs" instead of traditional balances.

- Prevents double-spending by marking spent outputs as unusable.

- Integration for coin security:

- Combines GHOSTDAG protocol with UTXOs to ensure each digital coin can't be reused after a transaction.

- Analogous to a vigilant cashier ensuring that a spent dollar bill cannot be used again.

The challenge of maintaining fast confirmation times while ensuring security.

GHOSTDAG's instant transaction confirmation comes from a rapid and global agreement on DAG ordering, which comes in handy every time a conflicting transaction occurs.

The process flows like this:

GHOSTDAG protocol -> Consensus in block ordering -> All nodes follow the same sequence -> Agreed-upon ordering -> Uniform conflict handling

Confirmation time denotes the duration until you can confidently ascertain, with a high degree of certainty (assuming an honest majority), that the block containing your transaction won't be reordered. It confirms inclusion in the ordering segment that has reached a consensus.
It maintains the same level of security as Bitcoin's Nakamoto consensus; the sole distinction lies in replacing the term "orphaned" with "reordered."

The ordering converges in consensus and does so rapidly; the duration is solely dictated by network latency, regardless of block production rates.

The ordering

That's where GHOSTDAG, a protocol within the PHANTOM family, and its ability to establish a durable event order within a DAG structure really shines. This means that the event sequence remains immune to retroactive changes.

The proper ordering provided by GHOSTDAG encompasses the following key attributes:

1. Topological Order:

- A block cannot appear in the ordering before any of its parents.

2. In Consensus:

- At any given moment, all nodes in the network must unanimously agree on ordering all but a constant number of new blocks.

3. Security:

- A computationally inferior adversary cannot retroactively alter the ordering of blocks.

4. Liveness:

- There should be a clear criterion for when a block is "finalized," meaning it will never change its place in the ordering. Every block should meet this criterion within a constant amount of time.

5. Efficiency:

- Determining, calculating, and maintaining the order should be feasible for today's computers, even in the face of a continually expanding DAG.

On the other hand, SPECTRE, another important protocol from the Yonatan research line that is outside of the PHANTOM family of protocols, has the same property but weakened in a way that the ordering could not change retroactively in a way that affects the unspent transaction output (UTXO) set.

Little protocol detour before we return to our main topic

The SPECTRE protocol, recognized for its speed and mentioned earlier, was initially considered as a candidate for the first Kaspa consensus before the core team decided to adopt GHOSTDAG instead.

Yontan once said to Shai Wyborski that SPECTRE is his most beautiful creation.
This protocol provides many interesting features, such as throughput limited by hardware (and not security as it is in Bitcoin) and confirmation times that are limited only by the delay of the actual network.

SPECTRE and GHOSTDAG are somewhat parallel because they have properties other protocols from Yonatan's research line do not. GHOSTDAG has linear ordering, while SPECTRE is parameterless.

The aim was to craft a gem that extracts the finest attributes from diverse protocols, leading to an ultimate PoW consensus. This endeavor harmonizes all these distinctive advantages into a unified protocol named DAGKNIGHT, credited to Michael Sutton and Yonatan Sompolinsky.

The DAGKNIGHT project originated in 2020/2021 in the long Covid quarantine. It was discovered as an unexpected byproduct of working on other challenges, achieving both linear ordering and being parameterless, thus acting as a technological diamond in terms of flow.

DAGKNIGHT, the protocol that eliminated the need to have a certain assumption about the network, achieves Nakamoto consensus security independent of block rates (same as GHOSTDAG and SPECTRE), has a rapidly converging linear ordering (same as GHOSTDAG), is suitable for smart contracts (same as GHOSTDAG), is responsive to actual network latency (same as SPECTRE), capable of confirmation times that can approach the network limits without risk as any degradation in network conditions will result in DAGKNIGHT automatically increase its confirmation times to maintain stability - thus scales itself as network latency is improved, is planned to be applied as the next Kaspa consensus, and my wild guess is that it will be somewhere between late 2024 and end of 2025. 

The GHOSTDAG protocol and its advanced successor, DAGKNIGHT, introduce significant enhancements to the Proof of Work (PoW) ecosystem. Through Kaspa's innovative work within the BlockDAG framework, these protocols are instrumental in realizing the vision initially proposed by Satoshi Nakamoto. By addressing key challenges such as scalability, security, and decentralization, GHOSTDAG and DAGKNIGHT contribute to the evolution of blockchain technology, offering a robust foundation for the next generation of decentralized applications.

Before concluding our exploration of advanced consensus protocols, it's pertinent to revisit the SPECTRE protocol, lauded for its innovation yet noted for its limitations in real-world, blockDAG-based Proof of Work (PoW) applications. SPECTRE, once considered a promising candidate for enhancing the blockchain landscape, requires careful consideration due to its unique approach to transaction ordering and conflict resolution, which directly impacts its suitability for certain blockchain functionalities.

SPECTRE was designed to enhance the scalability and speed of cryptocurrency transactions. It addresses limitations inherent in traditional blockchain technologies by introducing a new way of achieving consensus even under high throughput conditions and fast confirmation times. SPECTRE is engineered to remain secure against attackers with up to 50% computational power and can operate efficiently at high block creation rates, ensuring transactions are confirmed in seconds.

However, even though SPECTER is a highly efficient protocol suitable for VISA transaction speed,
it generates a pairwise ordering, which is potentially cyclic and nonlinear. This characteristic means it might not always be possible to linearize the ordering. In instances where a transaction conflict occurs before confirmation, SPECTRE theoretically allows for the possibility of delaying confirmation indefinitely, highlighting a vulnerability known as 'weak resistance to Liveness attacks.' Due to this potential for non-linear ordering, SPECTRE is generally considered unsuitable for smart contract applications, where linear transaction history is crucial.

Smart contracts depend on the absolute certainty of transaction sequences to ensure their conditions are met and executed correctly. And since the SPECTRE ordering method might not provide the rigid determinism that smart contracts require, Kaspa core contributors opted for GHOSTDAG.

A complete summary of these protocols can be found in the dedicated chapter of Dr. Sompolinksy's blog section.

I let myself be carried away by technological passion, but I am who I am.

Now, let's summarize what we know so far and move to the finish of this chapter.

Three steps to the blockDAG paradigm

Step 1: Mining the PoW protocol, which we are all familiar with from Bitcoin.

Step 2: DAG ordering.

Step 3: Iteration over the linearly ordered DAG, where you accept every transaction according to a certain order outputted by the ordering protocol and then accept every transaction that is consistent with the past.

Step 2 hinted at the last challenge of this chapter and also the part where it could get interesting for anybody who would like to create a successful PoW in a blockDAG paradigm:

Can you get a good ordering algorithm?

To understand this, let's say we have a good and bad ordering algorithm.

An example of a bad ordering algorithm for a DAG is using the longest chain rule.
Here, an attacker can come later than your transaction, inject its own transaction in, and then precede you in the ordering.

The next bad thing to do is simply use the nodes and use them in their descending order, where the network would use the hash of the block to choose the next block to pop.

The issue with this straightforward approach is as follows:
You initiate a transaction, which is broadcasted to the blockDAG network, functioning as described earlier. However, one year later, an attacker could generate a conflicting transaction with your original transaction, executing a double-spend. The attacker would then mine this conflicting transaction concurrently (in parallel) with the block containing the original transaction, continuing until the nonce aligns to precede the original transaction.
In such a flawed ordering protocol, even a year later, an attacker can potentially reverse users' transactions.

In a good ordering algorithm, these attacks from the "past" are recognized as very disconnected, thus suspicious, and not taken into account. Also, In a good ordering algorithm, an attacker can not win by using the work of honest participants to do the job for them and gain credibility that would allow them to succeed.

Hence, we require a system capable of identifying and eliminating manipulations, whether it be mining a block, withholding it off-chain and publishing it after a year, or mining a block and falsely claiming it was mined a year ago. Our goal is to retain only transactions that were correctly mined and successfully entered the order, wherein the miner references all recent blocks and promptly publishes the block. A crucial property of a robust ordering system involves reasoning about lateness over time, aligning with the topology of the blockDAG. Effective reasoning should render a block mined a year ago as an outlier in the DAG, indicating its complete disconnection from most blocks and raising suspicion, as a properly mined block would be well-connected to its surroundings.

Additionally, in a good and effective ordering algorithm, once a transaction is published and a certain amount of time has elapsed, the probability of your transaction being preceded in the ordering by a new unpublished transaction should be close to zero.
This is another desirable property that users need in the network: a stable order that remains unchanged over time. Period.

When you, as a user, publish a transaction, it may take a few seconds (or, in the case of a less efficient protocol, a few minutes) to converge on the ordering of this transaction relative to others. However, after this brief period, in a properly decentralized network, you are assured a very high probability that no new transactions will precede yours, you will not be front-run by trading bots, and your position in the ordering is secure.

This feature would be highly appreciated by Uniswap traders on Ethereum in 2021-2022.

"Observing the 3 BPS blockDAG in a network visualizer is a very soothing experience.
I like to use this as a screensaver :)."
- Yonatan Sompolinsky, IBM weekly call-meeting for blockchain enthusiasts, 2022

Congratulations on reaching the end of this extensive exploration! 

Stay tuned, and see you soon in our upcoming piece, where the superlatives of Kaspa will be unveiled, promising yet another thrilling exploration into the future of decentralized technology. Your continued support and enthusiasm make these discussions not just possible but truly rewarding.

Until then, may your curiosity continue to lead you to new discoveries!