Conflux Research Group | GHAST Mechanism: Adaptive Weight “GHAST” Explained
In order to solve the “liveness attack” problem, Conflux has designed a GHAST mechanism solution.
The core parts of the GHAST mechanism can be summarized as follows:
- The heaviest chain rule is applied, but the block has three different weights: 0, 1, X. Where X is a relatively large number, for example X = 1000 (ignoring the situation involving adjustment of mining difficulty).
- There are two types of blocks in the network: normal blocks and special blocks. The weight of the normal block is always 1; the weight of the special block is determined according to the difficulty of the block (Difficulty) — there are 1/X special block weights of X, while the rest are 0. Mining a normal block has the same difficulty as a special block.
- The block type is determined by the historical Tree-Graph structure of the block. As the generator of a block cannot arbitrarily specify the block type.
- In the absence of an attack, all newly generated honest blocks should become normal blocks; after the attacker conducts any kind of “liveliness attack” and continues for a long enough time, all newly generated honest blocks become special blocks.
Let’s introduce these rules in detail:
Heaviest Chain Rule
In the process of selecting the main chain via the heaviest chain rule, the initial step is to add the genesis block to the main chain. In each subsequent operation, all children blocks of the current last main chain block are selected and the child tree of each child block is calculated by its weight. And then the child with the highest weight is selected from the subtree.
When the block weights are changed from one to three, we can still use the same rules, but when calculating the weight of the subtree, we no longer simply count the number of blocks, but use the added total of the weights.
There is also an additional restriction: a block with a weight of zero cannot become part of the pivot chain, but it can become the parent block of another block. This condition guarantees that the weight for each subtree with a weight of zero will be zero.
Normal Blocks and Special Blocks
Three different weights come from two types of blocks, normal blocks and special blocks. Blocks with a weight of 1 all come from normal blocks, while blocks with a weight of 0 and X all come from special blocks.
Normal blocks are well understood, and they are no different from the blocks in the consensus mechanism for Bitcoin, Ethereum, and Conflux (before the introduction of “GHAST”).
However, special blocks are more complicated. Its generation difficulty is the same as normal blocks, but the block weight is determined by the difficulty value. This may be more abstract, so let’s look at an example:
Suppose that in the current network parameters, the block header hash of a block has 32 bytes, that is, 256 bits. The block with the first 60 bits of 0 is regarded as a valid block, and the value of X is 1024. Then when a miner is mining a normal block, the first 60 bits of the block header hash are found to be 0, this will give the valid normal block a weight of 1. When a miner is mining a special block, and finds the the first 60 bits of a block header hash to be 0, then this is a valid special block. If bits 61 to 70 of this block header hash are all 0, then the weight of the special block is 1024. Otherwise, although the special block is valid, the weight is 0. That is, each time a miner generates a special block it has a probability block weight of 1024/1024, where a probability block weight of 1023/1024 is 0. However, the expected value of the final weight is still 1.
Letting miners generate special blocks is similar to increasing the block difficulty by X times through the consensus mechanism, and slowing down the block production speed by X times. After the block generation speed is slowed down, it is helpful for solving the problem of a “liveness attack.” We will analyze the details of this part later.
The “Historical Tree-Graph Structure” Determines Normal Blocks or Special Blocks
In our design, miners cannot decide on their own whether to mine a normal block or a special block. Whether a block is normal or special is determined by the “historical tree graph structure” of the block.
The historical tree graph structure of a block (denoted as block b) refers to: starting from this block, backtracking along the parent and reference edges, until the genesis block, these blocks (excluding block b itself). The tree graph structure formed from this backtracking is the historical tree graph structure of block b.
For an honest node, the historical tree graph structure of the generated block b is the tree graph structure that the node sees when it generates this block b (as the tree graph structure requires the miner to refer to all the seen, unreferenced areas).
Whether a block is a normal block or a special block is completely determined by the history of the tree graph structure.
The advantage of determining the special block from the historical tree graph structure is that everyone can independently determine whether a block should be a normal block or a special block, as there will be no differences when an agreement is reached — the block’s own parent side and reference edges are unmodifiable.
As long as everyone agrees on whether each block is a normal block or a special block, it naturally agrees on the weight of the corresponding block, so as to avoid divergence when choosing the main chain.
Rules for Determining Normal Blocks or Special Blocks
How to decide whether a block should be a normal block or a special block based on the “historical tree graph structure” of a given block? The design of this rule requires careful consideration.
When no attack behavior is observed, all newly generated honest blocks should be normal blocks; after the attacker is found to carry out any kind of “liveness attack” which continues for a sufficient period of time, all newly generated honest blocks should be considered as special blocks.
Regarding the intermediate state of the two, that is, when an attack with a short duration is observed, in accordance with the idea of letting honest nodes seek common ground while reserving differences, we allow some honest nodes to generate normal blocks, and other honest nodes to generate special blocks.
In fact, active attack behavior can be reflected in the historical tree structure of a block.
If there are two sub-trees of similar size and large weight in the historical tree structure of a block, it can be speculated that an attacker is performing a balance attack. When discovered, honest nodes should generate special blocks.
On the other hand, if each block in the historical tree graph structure can be quickly confirmed according to the confirmation rules, it means that there are no problems (at least temporarily there are no problems that can be observed by honest nodes). At this time, honest nodes should generate normal blocks.
Conflux is a State-of-the-Art public blockchain system that can achieve high TPS without sacrificing decentralization or security. By delicately combining its unique and advanced algorithm with a novel structure — — Tree Graph (TG), Conflux makes consensus no longer a performance bottleneck, thereupon solves a series of problems in the industrialization of public chains. Currently, in its first stage, Conflux adopts a PoW (Proof of Work) mechanism as the basis of its consensus.
