PLEASE NOTE: THIS VERSION IS OUTDATED

This version of Understanding GHOSTDAG is deprecated and unmaintained. Please visit the book’s new home.

Understanding GHOSTDAG is an open book I started writing in July 2024. The book is divided into five parts:

The fundamentals of decentralized consensus, proof of work, block chains and blockDAGs
Securely reducing storage requirements via pruning, MLS mining, and harmonic storage mass
Fee markets in blockDAGs
Self scaling (a.k.a. parameterlessness) and the DAGKnight protocol.
Miscellanea

Some of the sections are starred (marked with an *) to indicate that they require a bit more mathematical/technical maturity (though I am sure most of them could be enjoyed by sufficiently stubborn laymen). Non-starred sections never rely on starred sections. Sections that are particularly tricky or require bachelor level math are doubly-starred.

In the mathematical appendix I collect semi-formal introductions of mathematical topics that rise from the discussion. I made an effort to draw many of the motivations and examples from the world of cryptocurrencies, so hopefully the appendix would be beneficial to readers who already know these topics.

Below is a tentative table of the contents of the Understanding GHOSTDAG, with links added to parts as they are written. I will do my best to post one to two weekly posts, at least for the first three episodes, after which I dive into less charted territories.

PLEASE NOTE: THIS VERSION IS OUTDATED

This version of Understanding GHOSTDAG is deprecated and unmaintained. Please visit the book’s new home.

Preface and Introduction

Part I: blockChains and blockDAGs

Before we can talk about GHOSTDAG we need to understand blockDAGs, and for that, we better (though we don’t strictly need to) have a solid understanding of blockChains. While blockChains are the simplest form of blockDAG, they still afford a rich, nuanced, often confusing theory. A solid understanding of blockchains doesn't just prepare us to tackle the more involved blockDAGs, but also provides a great point of comparison. An anchor of understanding. It is much easier to judge blockDAG protocols when we can compare them to blockChains, asking what they lose, what they improve, and what stays largely the same. Introducing blockChain concepts as a stepping stone to understand their equivalents in the blockDAG setting will be a reoccurring theme throughout this entire series, so it is important to build a solid basis.

Chapter 1A: BFT Vs. PoW. To set the stage and get warmed up, we will start where most explanations of consensus start: with the Byzantine generals problem. This problem is considered by many as the birthplace of consensus theory. We will follow up by introducing proof-of-work and finish with a comparison.

Post 1: Byzantine Fault Tolerance
Post 2: Proof-of-Work
Post 3: BFT vs. PoW
Exercises

Chapter 1B: the BlockChain Paradigm. The BlockChain paradigm gives us a concrete way to frame the vague problem of “reaching consensus”. We can abstract away most of the details and remain with the problem of selecting a chain.

Post 1: Some Background
Post 2: Chain Selection Rule
Post 3: the Heaviest Chain Rule and GHOST
Exercises

Chapter 1C: Security of a BlockChain. Now that we know what a chain selection rule is, we need to understand what makes a chain selection rule good. Following a short discussion of how cryptographers think of security notions, we will introduce the main security notions for a blockChain.

Post 1: What is Security?
Post 2: Safety
Post 3: Liveness
Post 4: Confirmation Times
Post 5: Sketch of Bitcoin Security Proof*
Post 6: Selfish Mining*
Exercises

Chapter 1D: the BlockDAG Paradigm. The BlockDAG paradigm is a generalization of the BlockChain paradigm. The tree is replaced with a structure called a DAG, which allows each block to point at several other blocks. The chain selection rule is replaced with an ordering rule that resolves conflicts while keeping all the blocks. We introduce the paradigm and see some important instances.

Post 1: DAGs and Topological Sorting
Post 2: the BlockDAG Paradigm
Post 3: Honesty Vs. Rationality
Post 4: Security of BlockDAGs
Post 5: Some BlockDAGs
Exercises

Chapter 1E: GHOSTDAG. We are finally positioned to introduce the man of the hour. We will introduce the GHOSTDAG protoccol and use all the insights and fundamentals we developed in previous episodes to understand it better.

Post 1: The PHANTOM Protocol
Post 2: The GHOSTDAG Protocol
Post 3: Security, Rationality, and Selfish Mining
Post 4: Sketch of GHOSTDAG Security Proof*
Post 5: GHOSTDAG confirmation times
Post 6: Coinbase Processing and SPV Proofs
Post 7: Reachability Queries*
Post 8: Deferred Processing and Disqualified Blocks*
Exercises

Part II: Reducing Storage Costs

(Most of the posts in this series are based on a keynote lecture I gave in the DAG-DLT workshop on the first day of June 2024, which was unfortunately not recorded. However, the current part is based on my workshop about controlling storage in high throughput permissionless systems in NBX Warsaw 2024, which was fortunately bootlegged.)

A high-throughput system like Kaspa cannot appeal to architectures that low-throughput systems like Bitcoin can (barely) get away with. In particular, unlike Bitcoin, Kaspa does not have the privilege to store the entire ledger. On the surface, it may seem that forgoing the ledger trades-off security. Perhaps surprisingly, this is not the case. An elegant protocol by Aggelos Kiayias, Nikos Leonardos, and Dionysis Zindros allows us to enjoy the same security while only saving a fraction of the ledger. However, adapting this protocol to DAGs is deceptively difficult.

Another reason for concern is the state bloat. In particular, organic and adversarial increase of the UTXO set. Kaspa deals with the problem in a novel way, which we call harmonic block mass. In Kaspa Improvement Proposal 9 we provided a specification tailored for Kaspa. However, unlike most of the book, this idea is extremely general, and can be adapted to any DLT, from UTXO PoW DAGs to L2s over PoS chains. However, it is still fitting this book for several reasons: such a solution is required for high throughput systems, it was invented through working on Kaspa, and it is just really really cool.

The posts in this part will be roughly as follows:

Chapter 2A: Background. We explore the problems we need to solve, how they are traditionally solved, what goes wrong in high throughput, and what we should expect from our solutions.

Post 1: the Immutable Ledger
Post 2: State Bloat
Post 3: Social Vs. Cryptographic Consensus

Chapter 2B: Pruning block data. We first consider the problem of removing block data while keeping the headers. We explain why this problem is trivial for chains yet extremely difficult for DAGs. We then explore a solution proposed by Yonatan Sompolinsky, Michael Sutton, and myself.

Post 1: Data Pruning in Chains
Post 2: A Security Definition, Naive Attempts, and Climbing Attacks
Post 3: The Pruning Rules for GHOSTDAGs
Post 4: Sketch of Security Proof*
Post 5: Cryptographic Receipts

Chapter 2C: Pruning block headers. We present the protocol by Kiayias et. al and an adaption thereof to DAGs by Ori Newman and Yonatan Sompolinsky.

Post 1: Non-Interactive Proofs of PoW (NiPoPoWs)
Post 2: The Mining in Logarithmic Space (MLS) Protocol
Post 3: Adaptation to DAGs
Post 4: Sketch of Security Proof*

Chapter 2D: Mitigating state bloat. We discuss the state bloat problem and existing solutions, and proceed to consider the harmonic storage mass approach devised by Yonatan Somolinsky, Shai Wyborski and Michael Sutton.

Post 1: The State Bloat Problem
Post 2: Existing Solutions: State Sharding, Demurrage and Stateless Clients
Post 3: the Harmonic Mass Formula and It’s Consequences
Post 4: Sketch of Security Proof*
Post 5: Micro Transactions and Compounding UTXOs

Part III: the Fee Market

A common concern about DAGs is that they do not really increase throughputs because parallel blocks can contain a lot of redundancies. What is the benefit of having ten blocks in parallel if they all contain the same transaction? Apparently, not only is this not a problem, but the dynamics of a fee market on a blockDAG have some miraculous properties that remove many of the undesirable phenomena we see in blockChains.

Chapter 3A: Security Budget and Fee Markets. We discuss the role of fees in PoW. We then inspect the fee markets of blockChains and the undesirable dynamics they beget.

Post 1: the Security Budget Problem.
Post 2: Rationality of Players and Equilibria of Markets
Post 3: Race-to-the-bottom Vs. Bidding Wars, Bitcoin’s Hellish Dichotomy

Chapter 3B: Transaction Selection Games. As Yoad Lewenberg, Yonatan Sompolinsky and Aviv Zohar in their 2015 paper Inclusive Block Chain Protocols, the equilibrium fee market strategy in blockDAGs is probabilistic in nature. We explore what this means and what are the consequences.

Post 1: Warmup: the Constant Fee Case
Post 2: General Transaction Selection Games
Post 3: Properties of Randomized Fee Markets
Post 4: Incentive non-Attacks*
Post 5: Fee Estimation
Post 6: Alternative Approaches: Bucketing and Monopolistic Fee Markets

Part IV: Self Scaling

When any permissionless distributed system is claimed to have “instant confirmations” or to “operate as fast as the internet,” there is a little implicit asterisk: that the “speed of the internet” is “known.” In practice, when such a system is deployed, it is parameterized with respect to a bound on network latency. This bound must be chosen with a large margin of error; otherwise, the network's security will be compromised. This forces decentralized systems to operate sub-optimally. Consequently, confirmation times do not improve with network conditions and are not increased in case of deterioration. The DAGKnight is the first protocol that circumvents this limitation.

Unfortunately, at this point, I do not understand DAGKnight myself well enough to know how this episode should be structured. Sure, I understand what it achieves and the general idea, but when it comes to how it actually works the best I can provide is an intuitive explanation. As we go, we will understand how these posts should be divided and what the should contain.

Part V: More Topics

This part is mostly about “tying loose ends”. It contains posts about “smaller” topics deserving some attention, but not ones I would like to write an entire chapter about. Some of these topics are crucial, others are just things I like and want to talk about.

Chapter 5A: Decentralized ASIC Mining. In this chapter, we argue the benefits of ASIC mining, and in particular that, combined with rapid emissions and high BPS, it is actually more decentralized and secure than mining on generic hardware.

Post 1: the Pros and Cons of ASIC Mining
Post 2: Designated Hardware Always Wins
Post 3: Rapid Emissions and Coin Spread
Post 4: High BPS/TPS and Hardware Entry Barriers

Chapter 5B: Difficulty Adjustment. The difficulty adjustment algorithm (DAA) is the component in charge of maintaining a fixed block rate despite ever-changing hash rates. We explore some approaches to difficulty adjustment in blockChains and describe the approach we chose for Kaspa. (This approach uses the blue score of blocks and is thus GHOSTDAG specific and does not translate directly to other blockDAG protocols.)

Post 1: Warmup: Difficulty Adjustment in Bitcoin with Authentic Timestamps
Post 2: Difficulty Epochs Vs. Sliding Windows
Post 3: Difficulty Fluctuations and Weighing Functions
Post 4: Handling Timestamp Manipulations
Post 5: Adaptation To DAGs, Whet Even Are The “Most Recent” Blocks?
Post 6: Security of Bitcoin with Varying Difficulty*

Chapter 5C: Reachability Queries. Given two blocks in a BlockDAG, how can we tell whether they are parallel or if one is in the past of the other? Computing GHOSTDAG requires answering this question several times per block. An efficient implementation is crucial if we ever hope to have a practical implementation of GHOSTDAG. However, this is a very hard problem. (So hard that several teams that tried to implement GHOSTDAG declared it “inefficient“.) In this section, we explain what makes this problem so difficult, and present an algorithm by Michael Sutton that solves it.

Chapter 5D: MEV Resistance. The high parallelism of high BPS blockDAGs makes it impossible to predict in real-time how the set of blocks containing a particular transaction will look like. Yonatan Sompolinsky observed that this property could be leveraged to combat MEV. The rough idea is that miners use their blocks to bid for the privilege of including the transaction, with the bid money going back to whoever created the transaction. The high parallelism makes it impossible to manipulate auctions, making the equilibria of this process reflect a fair division of the extracted value between the transaction creator and the miner who included it. In this post, we will survey MEV in general, and some existing approaches to mitigating it. We will proceed to discuss auctions and a bit of their theory. Finally, we will provide a toy version of how MEV resistance could work on Kaspa, along with some quantitative analysis.

Chapter 5E: Quantum Mining*. Not really specific to Kaspa, but this is a topic I am asked about a lot. Quantum mining might be a long shot, but understanding its dynamics is a great challenge to put your understanding of PoW to the test. These topics do not require any understanding of quantum computation besides some very specific facts that I will present in a self-contained way.

Post 1: Quantum Computation Primer: Measurements and Grover’s Algorithm
Post 2: Classical Vs. Quantum Mining
Post 3: Aggressive Mining
Post 4: the Optimal Waiting Time for Small Quantum Miners
Post 5: A Quantum Difficulty Attack

Understanding GHOSTDAG: Table of Contents

Shai (Deshe) Wyborski

Researcher and Writer