Technology Sharing: Safe and Fair Block Dag Sorting
foreword
foreword
In the previous article, we saw that the problem that can arise in the DAG topology is to define the order of blocks and transfers. In this post, we describe Taraxa's mechanism that not only ensures ordering in Block DAGs, but also ensures that the ordering process is safe and fair.
Why is sorting challenging?
What's so hard about sorting in a Block DAG?
If we just look at any DAG data structure, we can only establish partial ordering, which means we can only determine the ordering relationship between some blocks, but not all blocks. Here is an example.
In the image above, we can say with 100% certainty that the blue block definitely comes before the green and orange blocks in the sort. Why? Since the green and orange blocks point to the blue block, it means that when the orange and green blocks are created, the blue block already exists, otherwise the orange and green blocks don't know they will point to it.
But, how can we know the ordering relationship between the green and orange blocks? There is no definitive answer to this question, the answer depends on the type of sorting algorithm used, and the order may be completely different for different algorithms.
In the ranking process, we not only have to retain one degree of freedom, but many choices need to be made to ensure that the ranking algorithm is both fair and safe, because there is a need to ensure that dishonest participants do not bias the majority of honest network participants or attack.
Now let's take a look at the sorting algorithm of Block DAG designed by Taraxa to see how we can solve these problems.
popularity contest
In Taraxa's Block DAG topology, each block includes backward pointers that point not only to a single parent block (as in a single-chain topology), but also to what the block proposer has seen and believed All blocks on the DAG boundary (edge). There are a lot of concepts here, let's unpack them one by one.
What are boundaries? In a Block DAG (or any DAG data structure), a frontier refers to the latest set of blocks that no other blocks point to.
In the image above, the blue block is the "boundary" block, while the rest of the blocks are not. Frontier blockchains are interesting because these blocks are the base of all blocks, and other blocks created by block proposers (analogous to block creators) are ordered after them. From a certain point of view, the next new block will definitely refer to these blocks. However, not every node will see the same boundaries (or the same Block DAG) as each node experiences a different network propagation delay and sees a completely different situation when encountering any given block. Therefore, block proposers may base their blocks on different boundaries at any given moment.
What is a pointer or parent block? Pointers, represented by arrows in the diagram, are data embedded within a block that "points" or references another block. In Taraxa's DAG block structure, the pointer will point to the parent block set. The parent block is the block pointed to by the pointer, so it can be understood as the parent of their previous block.
In the image above, we see that the blue block has two pointers to the two parent blocks represented by the green blocks. This means that when a proposer creates a blue block, the proposer knows two (2) blocks on the Block DAG boundary, and considers these two blocks valid, so points the created blue block to both of them.
The process by which these pointers connect blocks is effectively a popularity contest - simply which block will be pointed to by the most blocks and be considered valid. Additionally, if the blocks pointing to a particular block are themselves "popular" (meaning many other blocks point to them), then the "popularity" will also carry over to that specific block (the parent block).
Now, let's measure the popularity of each block.
weight - popularity score
To measure the popularity of each neighborhood, we adopt the GHOST protocol proposed by Zohar and Sompolinsky. GHOST helps to calculate the weight of each block ("popularity" of each block) based on pointers embedded in the Block DAG.
What is "weight"? If the Block DAG is rotated sideways, it can be considered that each child block and its descendants are isolated from the parent block, so the weight of any block under GHOST is the sum of the weights of the block and all its descendants.
The weights represent the collective effort of all attempts to gradually build other blocks on top of that block, even if this effort is uncoordinated and spread across multiple descendants.
>The GHOST protocol is very simple,
>Each block itself naturally has a weight of 1
>Each block has a weight equal to its own weight (1) plus the weight of all blocks pointing to it
Start at the boundary of the DAG block and measure backwards
Here is an example.
Starting with border blocks, we can assign weights to each block. The blue block is at the border of the DAG, no blocks point to it, so it has a weight of 1. The green block has only one block pointing to it (the blue one), so we add the green block's own block weight (1) plus the block pointing to it's weight (1), and we get 2, which is New weights for green blocks. Going further, the orange block points to 3 blocks, so its weight is the sum of the weight of the three blocks plus its own weight of 1: 5+20+12+1=38.
Looks good, why can't we sort by weight now? Well, not quite. There are some very subtle issues with this simple strategy, let's investigate them further.
Ways to confuse the order
Let's look at a simple example to understand why just using weight values as the logical basis of the sorting mechanism is not enough.
In the image above, we start with scenario (a).
(a) We see that there are two orange blocks, both of which have a weight value of 1, so their order is ambiguous.
(b) Another block is added that points to the previous two blocks, but now they both have a weight value of 2 and still have an ambiguous order.
(c) After adding a few more blocks, the problem with the orange blocks does not go away, they still have the same weight. Not only that but now it's even worse, the new problem is that the yellow blocks also have ambiguous ordering.
In the example above, we're assuming everyone is honest - but we can still run into problems. What if you introduce a malicious player? That player can actively obfuscate the ordering on the block DAG structure. Let's see an example below.
In this example, we start with (b).
(b) We have 2 orange blocks with ambiguous ordering.
(d) Another block comes along and solves the problem, we now have a definite ordering. Long live!
(e) But not for long... a malicious player is actively looking to keep the ambiguous ordering and creates a block (red) which increases the border block and weights back to where we were before The problem, the two orange blocks are again not well ordered.
Another implication of this attack is that malicious players can not only maintain the fuzzy ordering, but also switch the ordering before and after adding blocks, leaving the network in a state of continuous chaos.
While these are very simple examples, such problems can occur on a larger scale, where entire clusters of blocks are in an indeterminate ordering state.
So how do we solve this problem? We will introduce the concepts of anchor chains and ghost pointers next.
Anchor Chain - the most popular route
The next step after calculating the weights is to determine the anchor chains in the Block DAG. If the weight is the popularity score of each block, then the anchor chain is the most popular path through the Block DAG. Blocks observed while traversing (walking) paths are also widely observed (very common) by the network.
How to build an anchor chain? Simple! Just pick a starting point — or in Taraxa’s case, the previous block with real-time finality (our article on real-time finality is coming soon) — and walk forward to it Among the sub-blocks of , each step selects the block with the highest weight. Here is an example,
In the figure above, starting from block G and moving forward, there are 3 weighted blocks to choose from (381, 765, 381), the heaviest of which is 765. Continue to go in this direction according to this logic, the path from the G block to the end point is the constructed anchor chain (green).
This is how anchor chains are generated, which "anchor" the Block DAG into a path from which we can now build a sorting algorithm.
While this method of calculating the anchor chain solves the problem of having the same weight for each pointed block, it introduces another problem, since an attacker can still keep changing the anchor chain (doesn't converge very quickly). So we introduce ghost pointers to help the network converge to a fixed anchor chain faster, thus achieving deterministic ordering.
Not all pointers are created equal
To further prevent the network from falling into disorder, we introduce a special pointer called a ghost pointer. The basic idea is that when each block is created, it points to all the blocks on the boundary that it has seen and verified as legitimate, but such blocks are special.
The special block is the termination block of the anchor chain. In addition to acknowledging the existence of other legal blocks on the boundary of the Block DAG, each newly added block will also point to the ghost pointer of the termination block. An important change here is that only the block pointed to by the ghost pointer is considered in the calculation of the block weight, and the blocks pointed to by other pointers are not considered.
The parent block becomes the block that only has the special ghost pointer pointing to it. In the Taraxa Block DAG structure, each block will only point to one parent block. Other blocks simply observe other blocks of the block tree (the original text is the leaves can be understood as blocks), or "ancestors" - in Ethereum, they are called "uncles" or "ommers". This can be mentioned earlier, or it can be very explicit about how many parents a block can have.
This solves a fundamental problem of how to ensure that all blocks on the boundary are not presented in an ambiguous form during the implicit voting process represented by the DAG graph.
>Let's take a quick look at an example,
>Thick arrows are ghost pointers (calculated weights)
The thin arrow is the confirmation pointer (no weight)
(a) Two blocks (1.1 and 1.2) point to the first genesis block (0), the thick line is the ghost pointer because only one parent block exists and both blocks point to it. The order is ambiguous now, but we can use the lowest hash for comparison, assuming (1.1) wins and is considered a candidate for the ghost pointer of future blocks.
(b) 3 blocks are added, but due to network delays, not all of these blocks see every new block at the same time, which means that some nodes can see some blocks faster piece. For example, fewer network hops due to closer physical distance will speed up the speed at which nodes see blocks. Both block (2.1) and block (2.2) have seen the previous two blocks (1.1 and 1.2), so they both point ghost pointers to these two blocks and honestly identify (1.1) as being on the anchor chain of the termination block. However, (2.3) doesn't see (1.1), so it can only use the ghost pointer to point to (1.2) and can't do anything else. Note that according to our rules, the weight of the block has been updated, but only the part of the subblock pointing to it using the ghost pointer is counted.
(c) The block of the next layer appeared, the (3.1) block saw the (2.1) and (2.2) blocks at the same time, and the (3.2) block saw the (2.1) and (2.3) blocks at the same time, Block (3.3) saw blocks (2.1, 2.2, and 2.3) at the same time. At launch each block selects the terminating block on the anchor chain they see, points its ghost pointer to it, and proceeds.
Together with anchor chains, ghost pointers help force the network to converge to anchor chains, stabilizing the overall ordering. Next, we describe how blocks are ultimately ordered based on anchor chains.
Sort by Anchor
Using ghost pointers, let's recalculate the weights in the previous Block DAG example. Note again that only the block pointed to by the ghost pointer will have its weight calculated into the parent block.
Once the anchor chain is drawn, we construct epochs around each block (anchor block) on the anchor chain. The epoch is the number of blocks that the anchor block can observe, or the block that the anchor block directly or indirectly points to. Think of them as friends of the super popular anchor blocks.
In the figure above, we plot each anchor block epoch using a red dotted line. Unfortunately, the first anchor block with a weight of 25 is only epoch himself. The next anchor block of weight 21 has epoc, including itself and the two other blocks of weight 1 that it can observe. The third anchor block has a weight of 18 and only one anchor block can be observed. The next block has a weight of 17, and its epoch is 3, which includes a block with a weight of 1 that it can directly observe, and another block with a weight of 2 that it can observe indirectly. In this way we continue to differentiate until the epoch of each anchor block has been drawn.
Now we are ready to sort the blocks! Blocks are first ordered by epoch from oldest to newest (left to right). In each epoch, the weight value is used to determine which block comes first by looking at which block points to which block. Or if this method fails, use the block hash as the judgment method of the block with the same distance as the anchor block.
Looking at the epoch graph, G is the first (1). There will only be one block in the next epoch, so this block with weight 25 is the second block (2). Moving to the next epoch, two blocks with a weight value of 1 are before the anchor block with a weight of 21 (because they point to the block with a weight of 21), the way to compare these two blocks is to compare whose hash value is lower Determine (3) and (4), and then, the fifth block (5) is a block with a weight value of 21. We keep going until all blocks in all epochs are sorted.
As shown below, the numbers in each block indicate order, not weight.
We are finally done!
But are we really done? What about the blocks that didn’t get sorted?epochThere are always some blocks near the boundary of the Block DAG structure that do not belong to the anchor chain
a part of. But don't worry, as more blocks are added to the boundaries, they will eventually be included.
Don't the anchor chains (and thus the resulting order) change over time?Yes! There is a risk of reordering within the Block DAG structure. This risk decreases exponentially over time, but is never really eliminated, which is why Taraxa needs to implement a real-time finality process (article forthcoming).
True real-time finality is introduced in the Block DAG structure without the risk of reordering, which is the basis for building DApps in the network.
