Importance of Finality Most blockchain topologies today have probabilistic finality, in that you are never 100% sure whether or not the transactions are truly set in stone. For example, in BTC, you get an exponential falloff in the probability that an attacker will be able to catch up to the rest of the network and reorganize the blocks as time (or in the world of BTC, # of blocks) goes forward. This exponential risk falloff gave rise to the “6 block” rule of a thumb whereby once you’ve observed 5 blocks built on top of the block containing your transaction, making your transaction “6 blocks deep”, then it is statistically highly unlikely that your transaction would be part of some reordering attack. In many cases, having a probabilistic finality is fine. But in cases where you’re executing a large number of transactions that are dependent on previous outcomes, or if you’re executing one extremely valuable transaction where you need to be absolutely sure that the transaction won’t be reversed, then finality becomes critically important. In its native state, the in Taraxa’s Block DAG is also one that provides probabilistic finality. To achieve true finality, we’ll need something extra. ordering mechanism What does Finality Mean in Taraxa? Recall that reordering risk from our earlier is primarily incurred when the anchor chain changes. ordering mechanism So as long as we can make sure that, periodically, an anchor chain can be nailed down, then the order for the blocks along that anchor chain will have finalized ordering no matter what happens. How do we do that? The network will periodically take a vote, in parallel with the Block DAG’s construction, to place on a specific block near the frontier of the DAG. infinite weight When a block has been given infinite weight, that means all the blocks it points to directly and indirectly via the ghost pointer now all have infinite weight, meaning it’s now impossible to override the ordering with an attack. In the figure above, we selected the orange block to have infinite weight, and we can see that infinity has carried through backwards into the Block DAG to give infinite weights to all the blocks (marked in dark gray) along the anchor chain. Now we have effectively finalized the ordering of this anchor chain and all the blocks in its associated epochs. So how do we select which block to give infinite weight to in the first place? Period Block Selection via PBFT-like Algorithm To select a block inside the DAG to finalize, we leverage a process that’s similar to the Practical Byzantine Fault Tolerance (PBFT) algorithm. Because PBFT is a well-studied and widely-deployed algorithm, we won’t spent too much time describing every detail and potential faults that could occur in this article, just the broad strokes. There are roughly four (4) steps in our PBFT period block finalization process, as described in the diagram. highly simplified Let’s go through this one by one. In each phase, a node … 1. Proposes New Block his eligibility via , where is the eligibility value, and is the proof of correct VRF calculation Computes VRF (SK, previous_PBFT_block_hash, current_vote_type, current_round_number, current_step_number) = (e, π) e π if then he is eligible to propose a PBFT block this round Decides e < threshold a DAG block candidate to finalize, somewhere near the frontier but not at the frontier, this is the current Period block candidate Picks Pt a Period (more on this later in this article) between the and , find all the blocks included within the Period Constructs Pt P(t-1) a Concurrent Schedule, Constructs CS a PBFT block candidate ( ) that includes ( ), among other information (e.g., timestamp, signature, beneficiary) Constructs Pc Pt, CS the hash of Computes Pc , , along with his eligibility proof to his peers Broadcasts hash(Pc) Pc (e, π) 2. Votes on Leader his eligibility via VRF again, with incremented by 1 and the current vote type, producing another Computes current_round_number (e, π) if , then he is eligible to participate in this round Decides e < threshold for 2λ, where λ is the network diameter — the shortest distance (in time) between the two most distant nodes in the network Waits the lowest observed for which is also correct, the creator if the lowest is the “leader” — this node is the candidate to propose the next PBFT block Computes e π e his vote for the that corresponds to the lowest to be the leader along with his eligibility proof to his peers Broadcasts hash(Pc) e , (e, π) 3. Votes on Block his eligibility via VRF again, with incremented by 1 and the current vote type, producing another Computes current_round_number (e, π) if , then he is eligible to participate in this round Decides e < threshold for 2λ Waits if he has received votes for any given , where is 1/3 of the eligible voting nodes for the last round Computes 2T+1 e_min T peers for the that corresponds to the and the associated if he does not yet have the PBFT block Polls Pc e_min hash(Pc) to be correctly constructed Validates Pc his vote for , along with his eligibility proof to his peers Broadcasts Pc (e, π) 4. Votes to Move Forward his eligibility via VRF again, with incremented by 1 and the current vote type, producing another Computes current_round_number (e, π) if , then he is eligible to participate in this round Decides e < threshold for 2λ Waits if he has received votes for any given Computes 2T+1 Pc the winning to be correctly constructed Validates Pc the newly validated and commits results to permanent storage Computes Pc his vote to move forward to proposing the next PBFT block, along with his eligibility proof to his peers Broadcasts (e, π) A Few More Words on the PBFT That was an extremely simplified description That was an extremely simplified description of what happens in our PBFT process. It is simplified because we haven’t described all the ways things could go wrong, e.g., no node computed an that was below the threshold, votes do not reach quorum, large numbers of nodes crashing during the middle of a round, etc. e 2T+1 This PBFT process is highly secure and scalable Note that every time a node tries to speak, it computes a VRF eligibility value to make sure it is allowed to speak during that round. The eligibility threshold is set and dynamically adjusted to ensure that 2 things, The , meaning that once an attacker observes a specific node is a participant and marks him for attack, it’s likely that during the next round he is no longer eligible. This is in contrast to many other algorithms that keep the participant (or committee member) around for an extended period of time, making them prime targets for targeted attack. Only , making this PBFT process highly scalable. This means that even as the network size scales up and the number of eligible participants increase, the number of actual participants (committee size) of these PBFT rounds can easily be set up to scale sub-linearly vs. the network size. Smaller number of participants means faster voting processes. nodes that participate in each round is random and likely different a subset of eligible nodes participates in any given round Combine randomly selected participants and sub-linearly increasing committee size, we get a highly secure and scalable PBFT process. The Parallel PBFT Chain Taraxa’s PBFT process creates a linear chain of PBFT blocks alongside the existing Block DAG. Each PBFT block has two primary purposes, into a Period blockHost a that prescribes how transactions are to be computed 1. Finalize a DAG block concurrent schedule 2. Finalize a DAG block. This PBFT process confirms a single block inside the Block DAG. Hence, it is not used, like in most other networks that leverage the PBFT process, as the primary consensus algorithm which gates the progress of the entire blockchain. This is why in Taraxa the PBFT process happens in and largely vs. the Block DAG construction process. parallel asynchronously Each time a new DAG block is finalized, we create a finalized anchor chain and an associated set of blocks along that anchor chain (via epochs along each anchor block). This entire set of blocks is called a , which can be thought of a snapshot of a cluster of blocks that have achieved finalized ordering. Period Each Period contains many DAG blocks, which leads us to the other task of the PBFT block, to define the order in which transactions are to be computed, via the concurrent schedule. The Concurrent Schedule The concurrent schedule defines order in several ways: The , as defined by the , since there are many blocks within a Period. order of the blocks ordering mechanism between blocks. Because we are working in a DAG data structure, it could very well happen that multiple block proposers would have included the same set of transactions into separate DAG blocks, leading to a certain amount of transaction overlap. Taraxa has a transaction jurisdiction mechanism (in a later article) to help tune this overlap — we want to minimize it but it cannot be kept at zero, as that could lead to excessive transaction orphaning. Splitting the transactions into . This is a critical part of our concurrent EVM design (a topic for a later article), whereby a set of speculative execution algorithms split a set of transactions into those that could be safely parallel-executed vs. those that must be sequentially executed. Filtering out redundant transactions concurrent vs. sequential sets Ultimately, you can think of the concurrent schedule as the combined result of all the individual DAG blocks into a single block, embedded into each PBFT block. We'll be sharing more of our ongoing work in the realm of blockchain networks design beyond consensus only, and would love to hear your thoughts and critique.

How to Approach True Finality For Block DAG?

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

Could Block Proposals Be Fair and Efficient Without Proof of Work (PoW)?

(1/100) Crypto Countdown: Golem

A Research Report on the Trader $JOE DeFi Platform

07/03/2018: Biggest Stories in the Cryptosphere

05/02/2018: Biggest Stories in the Cryptosphere

Could Block Proposals Be Fair and Efficient Without Proof of Work (PoW)?

(1/100) Crypto Countdown: Golem

A Research Report on the Trader $JOE DeFi Platform

07/03/2018: Biggest Stories in the Cryptosphere

05/02/2018: Biggest Stories in the Cryptosphere

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps