How to use a DAG to find the longest chain
1. Introduction
In the first part #1 we talked about how probabilistic finality works and why it's needed. Also we saw an example of how blocks might be structured and linked to each other:
The data structure above resembles a Directed Acyclic Graph (DAG) and fortunately DAGs allow for an easy way to find the longest chain. This is an important part of achieving probabilistic finality.
A DAG is made up of nodes (also called vertices) and edges. An edge represents a link between 2 vertices (e.g. 3000.1->3001.1). We can and should traverse a DAG to find out more about its structure, like how far away is vertex 3005.1 from vertex 3000.1
Additionally a DAG has some unique properties. Find out more about it here
2. How to find the longest chain
If we look again at the example above, it becomes apparent that 3005.1 is the tip of the longest chain. But how can we find it out programmatically?
We are going to use Depth First Search to traverse the graph and mark every vertex with its distance from the starting vertex.
We start at 3000.1 and give it a distance of 0. Now we traverse through all vertices and give each a distance of parent distance + 1. So 3001.1 has a parent distance of 0 and +1 gives a distance of 1.
3. Conclusion
If we store blocks as a DAG, we can use Depth First Search to find the longest chain.
4. Next Up
We will finally make our hands dirty and implement a DAG in Crystal
UPDATE: #3 Finding the longest chain implementation
Top comments (0)