The real finality of block DAG

foreword

foreword

first level title

The Importance of Finality

The finality of most blockchain topologies today is based on probability, which means that you can never be 100% sure that a transaction is really complete. For example, in the Bitcoin network, over time (or, in the language of the Bitcoin world, as the number of blocks increases), the probability that an attacker catches up with the rest of the network and reorganizes the blocks varies Exponential decline. This exponential risk reduction gave rise to the "6 block" empiricism. In other words, if 5 more blocks are added to the block containing your transaction, then your transaction is "6 blocks deep", and statistically, the transaction is not very May be subject to rearrangement attacks.

In many cases, probabilistic finalization is fine. However, if you are executing a large number of transactions, each of which depends on the output of the previous transaction, or if you are executing a huge transaction, and you need to be sure that this transaction will never be reversed, then finality is quite important up.

first level title

What does DAG finality mean?

Recall that the rearrangement risk of our early ordering mechanism mainly occurred when the anchor chain changed.

Therefore, as long as we can ensure that the anchor chain is fixed regularly, the ordering of blocks on the anchor chain can be completely determined no matter what happens.

How do we do it? The network will hold regular votes, synchronized with the construction of the block DAG, so as to apply infinite weight to specific blocks near the DAG boundary.

When a block is given infinite weight, it means that all the blocks directly or indirectly pointed to by it through the ghost pointer (ghost pointer) have infinite weight, which means that it is now impossible to overthrow this order by attack.

In the above figure, we have chosen the orange block to give infinite weight, and we can see that this infinity has endowed all blocks on the anchor chain with infinite weight by pointing back to the block DAG (marked in dark gray in the figure). We have now effectively determined the ordering of this anchor chain and all blocks at its own epoch.

first level title

Periodic block selection by a PBFT-like algorithm

To select a block within the DAG for finalization, we employ a process similar to the PBFT (Practical Byzantine Fault Tolerance) algorithm. Considering that PBFT is a well-developed and widely deployed algorithm, the details and potential faults (faults) that will be involved in this article will not be repeated here.

The period block finalization process of PBFT is roughly divided into four steps, as shown in the highly simplified diagram below.

secondary title

1. Propose a new block

• Calculate its eligibility through VRF (SK, previous_PBFT_block_hash, current_vote_type, current_round_number, current_step_number) = (e, π), where e is the eligibility value, and π is the proof of the correct calculation of VRF

• Decide "if e < threshold, then it is eligible to propose a PBFT block in this round"

• Select a DAG block candidate near the boundary but not on the boundary for final confirmation, that is, the block candidate Pt of the current period (Period)

• Create a cycle between Pt and P(t-1) (detailed below), find all blocks contained in this cycle

• Create a concurrent scheduler CS

• Create a PBFT block candidate (Pc) that contains (Pt, CS) and other information such as timestamp, signature, beneficiary

• Calculate the hash of Pc (hash)

• secondary title

2. Vote for the leader

• Calculate its qualification again through VRF (bring in current_round_number plus one and current voting type) to generate another (e, π)

• Decide "if e < threshold then it is eligible for this round"

• Wait for 2 λ, where λ is the network diameter - that is, the shortest distance (in time) between the two furthest nodes in the network

• Calculate the minimum value of e observed when π is also correct, and the creator is the minimum value. When e is the "leader", it is the creator - this node is the one who proposes the next PBFT block candidate

• secondary title

3. Voting for blocks

• Calculate its qualification again through VRF (bring in current_round_number plus one and current voting type) to generate another (e, π)

• Decide "if e < threshold then it is eligible for this round"

• Wait for 2 lambdas

• Calculate whether it has received 2T+1 votes within a given e_min time (here T is 1/3 of the qualified voting nodes in the last round)

• If it does not yet have a PBFT block, it will perform peer-to-peer polling for the Pc corresponding to e_min and the related hash (Pc)

• Verify that the Pc was created correctly

• secondary title

4. Vote to move to the next step

• Calculate its qualification again through VRF (bring in current_round_number plus one and current voting type) to generate another (e, π)

• Decide "if e < threshold then it is eligible for this round"

• Wait for 2 lambdas

• Calculate whether any given Pc has received 2T+1 votes

• Verify that the winning Pc was created correctly

• Calculate the latest verified Pc and commit the result to permanent storage

• first level title

More introduction about our PBFT

What is written above is an extremely simple description

text

This PBFT process is highly secure and scalable

Note that each time a node wants to speak, it calculates a VRF eligibility value to ensure that it is eligible to speak for that round. Eligibility thresholds are set and dynamically adjusted to ensure two things:

The nodes participating in each round are random and potentially different, meaning that once an attacker observes a node as a participant and targets it, it may be disqualified in the next round. This is different from many other algorithms that retain participants (or committee members) for an extended period of time, making them prime targets for attacks.

In any given round, only a fraction of eligible nodes participate, making this PBFT process highly scalable. This means that even if the network capacity expands and the number of qualified participants increases, the actual participants (committee size) of these PBFT rounds relative to the network capacity can easily be set to achieve sub-linear expansion. The smaller the number of participants, the faster the voting process.

first level title

Parallel PBFT chain

Taraxa's PBFT process creates a linear chain of PBFT blocks alongside the existing DAG of blocks.

Every PBFT block has two main goals,

• Complete the finalization of a DAG block in the periodic block

• first level title

Complete finalization of DAG blocks

This PBFT process will confirm a single block within the block DAG. Therefore, unlike most other networks that utilize the PBFT process, it does not serve as the main consensus algorithm to check the entire blockchain process. This is why Taraxa's PBFT process is parallel and largely asynchronous to the block DAG creation process.

Whenever a new DAG block is finalized, we create a finalized anchor chain and a set of related blocks on the anchor chain (implemented along the epoch of each anchor block). The collection of entire blocks is called a period, which can also be seen as a snapshot of a finalized sorted cluster of blocks.

first level title

concurrent scheduling

Concurrent scheduling determines ordering in the following ways:

• The ordering of blocks, this is defined by the ordering mechanism, because there are many blocks in a cycle.

• Filter out redundant transactions between blocks. Because we use a DAG data structure, it is very likely that multiple block proposers will package the same set of transactions into different DAG blocks, resulting in a certain degree of transaction overlap. Taraxa designed a transaction arbitration mechanism (will be introduced in detail in a later article) to help adjust this overlap - we hope to minimize this situation but not zero, otherwise there will be excessive isolation of transactions.

• Divide transactions into concurrent sets and sequential sets.

• This is a key part of our concurrent EVM design (which will be introduced in a later article), in which a set of speculative execution algorithms are used to divide transactions into those that can be safely executed in parallel and those that must be executed sequentially.

  You can also think of concurrent scheduling as the result of combining all the individual DAG blocks into a single block and embedding each PBFT block.

Stay tuned!

Stay tuned!