Scaling Bitcoin with BlockDAG
In the previous post, I explained about Bitcoin forks and 51% attacks. I introduced the throughput-security trade off that Bitcoin has, where increasing the block size can increase the number of forks, and reduce the reorg attack threshold to be less than 50% of the hashing power. In this post I’ll explain how we can circumvent the problem and increase the throughput without harming security.
Introducing BlockDAGs
The problem with forks is that their work could be used to secure the main chain, but instead their work is wasted and ignored. In order to solve this problem we need to harness their work so they can help us face attackers. DAGs come to the rescue! A DAG (Directed-Acyclic-Graph) is a graph where every node you add can point to any number of existing nodes. We can intuitively see how DAGs can help us solve the fork problem: if the main chain could point to the forked blocks their work will not be discarded when facing an attacker.
In the blockDAG paradigm the mining protocol is a little different. Every miner has to build blocks that extend all of the tips that it’s aware of (the DAG tips are the blocks that don’t have any children).
Note: In this post arrows point from new blocks to their parents. The orientation of the diagram can be changed due to screen space and other considerations, but this rule will always remain.
One of the first questions that arise when dealing with blockDAGs is: How should the blocks and transactions be ordered? Because the DAG can have many parallel blocks, that can include conflicting transactions, we need to find a deterministic way to order it. The ordering mechanism should take attackers into account, so if there are any transaction conflicts the attacker blocks will come last.
In order to do that we can try to make a DAG adaptation of the longest chain rule. The most naive solution will be to give precedence to blocks with a bigger past size as long as the order remains topological (parents come before their children). The past size of a block is the number of blocks in its past. That is to say it’s the number of blocks it points to directly or indirectly. Let’s try to sort the DAG in figure 3 by this rule:
First we’ll calculate the past size of each block:
- A’s past size is 0 because it points to nothing.
- For B, C and D it’s 1 because they point only to A.
- E directly points to C and D, and points indirectly to A, so its past size is 3.
And so on.
Now we’ll start ordering the DAG in a recursive way, from its tips to the root:
- H will come before G because H has greater past size, so now we’ll start to order H’s past in the same way.
- F comes before E because of F’s past size.
- B, C and D have identical past size, so we can just order them by their hash. Let’s assume their hash order is B>C>D.
- A comes first.
So our block order is A, B, C, D, F, E, H, G. The transaction order is defined by the order of blocks, which means if two parallel blocks, like E and F, include conflicting transactions, we can just ignore the transaction from block E because F precedes it.
If we’ll try to adapt the attack from figure 7 in the previous post to a blockDAG paradigm, we can see the attacker tip B has smaller past size (7) than the honest DAG tip A (9), so its conflicting transaction won’t be recorded to the ledger.
But what if the attacker will change its behaviour and will point to blocks of the honest DAG? In figure 5 the attacker’s chain is built such that every block in its chain points to a block in the honest DAG. That will increase its past size to the maximum, while still keeping its own block the parent with the biggest past size. When we’ll apply the same recursive ordering we did before, we’ll see that the attacker’s blocks will always precede the honest blocks. The double spend will succeed, although the attacker created less blocks than the honest network.
So in order to prevent attackers from using the work of honest miners, we need a way to differentiate between attacker blocks and honest blocks. The PHANTOM paper describes such mechanism, and I’ll describe it in the rest of the article.
In order to define attacking blocks we’ll try to understand what an honest blockDAG looks like. We’ll define a few terms that will help us to get a better understanding of blockDAGs.
From a single block’s perspective, the DAG can be divided into three subsets: the block’s past, future and anticone. The block’s past consists of every block it points to, or that its parents point to, and so on. Its future consists of blocks that contain the block in their past. Blocks that are neither part of the block past nor its future, that is to say, blocks that do not belong to the two former categories, define the anticone. In an honest blockDAG the anticone of a block consists of blocks that were not known to the miner at the time of the block creation, or that were created after it by miners that were still not aware of the new block.
We can intuitively say that the size of a block’s anticone depends on two things: the block creation rate (which we’ll denote as λ from now on), and the network delay (which we’ll denote as D). If we increase each one of them, more miners will mine blocks before they have a chance to get all of their peer blocks, and we’ll see wider DAGs. If we make empirical measurements to check what is the maximum delay in the network, we can calculate what is the maximum anticone we expect to see in an honest network.
For example, if we define the block creation rate to be 1 block per second, and the maximum observed network delay is 4 seconds, we can expect a maximum anticone size of 8 blocks: When a miner mines a block, we expect its anticone to include maximum of 4 blocks, because this is the amount of blocks that can be created during the 4 seconds delay period (any blocks that were created more than 4 seconds ago should already be known by the miner, and pointed to, directly or indirectly, by its mined block). Another 4 seconds may pass until the block is propagated to the entire network. During that time, miners that are not yet aware of this block could mine another 4 blocks. From that we derive that the maximum anticone size of the block would be 4 + 4 = 8. And as a general rule we can say that the maximum anticone size of a block in an honest network (which will be denoted as k) is 2Dλ (in the PHANTOM paper k is higher than 2Dλ to take into account anomalies in the block creation rate, but we’ll ignore it in this article).
So when we try to decide if a block is part of the honest DAG we need to ask ourselves the question “If we’ll add this block to the honest DAG, will any block have an anticone size greater than k?” If the answer is no, we can add the block to the honest DAG, but if the answer is yes it means this kind of DAG cannot be created as part of an honest network, so it cannot be added to the current honest DAG, and we reject it unless we find another alternative honest DAG that can include it. We can describe the PHANTOM rule shortly as “find the biggest sub-DAG where no block has an anticone greater than k”. Notice that this is a generalization of the Bitcoin longest chain rule — Bitcoin may be described as PHANTOM with k=0.
Let’s have another look at the same DAG from figure 4 but with the PHANTOM rule, with k=3, and we’ll see that including all of the attacker blocks will make every other block in the DAG have an anticone of 6 blocks, which means it can’t be part of an honest DAG. The attacker blocks (except the tip) will be excluded, they won’t be rewarded, and the double spend attempt will fail.
Choosing the Right k
Let’s try to understand what happens when we choose the wrong k. If we choose k that is too low, it means that many blocks from honest miners will unjustly be considered as dishonest, so their work won’t count, and the network will be more vulnerable to attacks. On the other hand, if we choose a too high k it means we can mistakenly consider attacker blocks as honest. But still, an attacker cannot make more than k blocks that will be considered as honest, so in order to avoid such problems we can just wait k blocks before we consider a transaction to be confirmed. For example, in figure 9 with k=3 if Alice is pending for a transaction in block B, she can wait for block E before transferring her purchased goods. She knows that if the attacker submits block F and G with a conflicting transaction, they will have a 4 blocks anticone, and PHANTOM will categorize those blocks as malicious. If she doesn’t wait for block E there’s no guarantee the attack won’t succeed, because PHANTOM cannot work on resolutions lower than k.
In conclusion, it’s better to find a too high k than a too low k, because the former will harm the user experience while requiring a longer confirmation time, while the latter will decrease the reorg attack threshold to be less than 50%.
PHANTOM for practical use
PHANTOM tries to find the biggest sub-DAG with an anticone smaller than k+1. Unfortunately, this is a very costly operation when we’re dealing with large DAGs. This is why the GHOSTDAG algorithm was invented as a greedy and more efficient variant of PHANTOM. This will not be covered in this article, but anyone who’s interested in further reading can read about it in the PHANTOM paper.
Further discussion and reading
If you want to discuss this blog post, or ask more about blockDAG, you are more than welcome to post a reply here or join Kaspa’s Discord Server. The Kaspa project is working on implementing fast and scalable money based on BlockDAGs.
